Getting started with IronPython – Part 4: MiniMax algorithm

After learning the basics of IronPython programming in the previous posts you’re ready for the fourth post – where I’m going to add simple AI logic to the Mancala game.

Previous Posts:

As part of my quest to learn how to program in Python I’ve decided to implement a simple Minimax algorithm.

The algorithm is simple and relies on a elementary principle – each turn you will choose the best move and your opponent will choose the worst move for you. By building a search tree with a limited depth we can then choose each time either the maximum result possible or the minimum result according to the player’s turn.

You can read more about Minimax algorithm in Wikipedia – or continue reading and learn it from my implementation.

Getting board value and available moves

The first thing needed for our algorithm is a method that will evaluate the “board value”, in our case we can calculate the board as the number of seeds in my store minus the number of seeds on the opponent store or in IronPython:

image 

The second ingredient is a method that will return all of the possible moves from a specific board. Finding all of the possible moves is simple just iterate all of the pots on one player side and choose all of the pots that have seeds in them:

image 

Update:

Michael Foord suggested that I use a single list comprehension (see comments below) instead of the code above, I’ve tried doing so and liked the result. here is calculateValue version 2:

image

An index field was added to the pot class and now I can get all of the available moves in a single line. It seems like a better more “Pythonish” solution of creating the list by certain criteria instead of writing a less easy to understand iteration.

Update 2:

As Danilo Cabello pointed out that I slightly missed the point, as a C++/C# developer I tend to overuse for and index and Python can do exactly what I need without keeping index field as part of the class:

image

For more details see his comment at the end of this post.

The Minimax Algorithm

Now that we have the two basic functions we’re ready to actually write the algorithm.

 

image

The Minimax algorithm is recursive by nature, and as such it requires a stop condition, in our case either the game has ended (no more moves) or the desired depth has been reached (lines 3-8).

Lines 10-16 checks whether its the player’s turn (Max) or the opponent (Min). I’ve used Lambda and function pointer to decide if to use a Max or Min functions. If you’re familiar with Lambdas from other programming language you should be able to understand it. basically I’ve declared a method that takes two arguments and returns a Boolean value. Declaring a new function pointer (or delegate) is simple like any other declaration in Python just write a variable and you’re pretty much done.

Lines 18-27 are the heart of the algorithm:

  • First choose a move and call the method again with the resulting board
  • Then if the result is better (depending on the lambda used) keep the best score and the path that caused it.

finally the method returns two values – the best score and the path. I really like the fact that Python methods can return several values, no more ref and out parameters for me.

The Story so far

Now that we have a (simple) AI player our game is almost finished, in case you’ve forgotten what this is all about you can take a look the Mancala class diagram:

image

As always this post’s code is available for download so you can check it and give me some pointers.

Stay tuned – we have at least one more post to go…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s