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.
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:
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:
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:
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:
For more details see his comment at the end of this post.
Now that we have the two basic functions we’re ready to actually write the algorithm.
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:
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.
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:
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…
Labels: IronPython