CS 151: Programming Assignment 2

Search and Games [90 points]
due Wednesday, February 20 11:55pm


The purpose of this assignment is to program some of the search algorithms and game playing strategies that we have learned in class.  In particular, you will implement two aspects of an artificial intelligence game that plays Mancala (and other two-player games): search with alpha-beta pruning, and a game board evaluator.   Your goals are to implement alpha-beta pruning correctly, and to create the best AI player you can.  We will hold a tournament between the submitted players, and the winner of the tournament will receive a free Mancala game.  (However, your placement in the tournament will have no effect on your grade).

Part 1: Introduction to Mancala

Mancala Board

Mancala is a two-player game from Africa in which players moves stones around a board (shown above), trying to capture as many as possible.  In the board above, player 1 owns the bottom row of stones and player 2 owns the top row.  There are also two special pits on the board, called Mancalas, in which each player accumulates his or her captured stones (player 1's Mancala is on the right and player 2's Mancala is on the left).  

On a player's turn, he or she chooses one of the pits on his or her side of the board (not the Mancala) and removes all of the stones from that pit.  The player then places one stone in each pit, moving counterclockwise around the board, starting with the pit immediately next to the chosen pit, including his or her Mancala but NOT his or her opponents Mancala, until he or she has run out of stones.  If the player's last stone ends in his or her own Mancala, the player gets another turn.  If the player's last stone ends in an empty pit on his or her own side, the player captures all of the stones in the pit directly across the board from where the last stone was placed (the opponents stones are removed from the pit and placed in the player's Mancala).  The game ends when one player cannot move on his or her turn, at which time the other player captures all of the stones remaining on his or her side of the board.

For slightly more detailed instructions on how to play, see this page.

Part 2: Provided Code

Download the code for this assignment here: pa2code.zip

I have provided code to support the basic game play, as well as a simple AI player (it's REALLY simple).  It contains the following files:
You should download these files and make sure you can run them.   To run a GUI game between two humans, load the file MancalaGUI.py (from IDLE, just press F5, or from the command line just type "from MancalaGUI import *").  Then create two players with type HUMAN (the ply is ignored for human players, and can be left as its default value):
>>> player1 = Player(1, Player.HUMAN)
>>> player2 = Player(2, Player.HUMAN)
>>> startGame(player1, player2)
You should see a window appear (it may appear in the background).  You can now play Mancala with a friend.

But what if you don't have a friend, you ask?  Well, never fear!  The computer will play against you (and I guarantee you will win).  To play against the computer you simply need to create a computer player to play against, e.g:
>>> startGame(Player(1, Player.HUMAN), Player(2, Player.RANDOM))  # Ply is also ignored for random players
or
>>> startGame(Player(1, Player.HUMAN), Player(2, Player.MINIMAX, 5))

You can also play Tic Tac Toe using the same player object (but no GUI provided with Tic Tac Toe... you can use your own from last assignment).  Load the Tic Tac Toe game, and then use the "hostGame" function to play the game.

Once you understand how to run the code, make sure you read though the provided code and understand what it does.  Notice that the minimax algorithm we discussed in class has already been implemented.

Part 3: A Better Board Score Function [40 points]

The board score function in the basic player is too simple to be useful in Mancala--the agent will never be able to look ahead to see the end of the game until it's way too late to do anything about it.  Your first task is to write an improved board score in the MancalaPlayer class, a subclass of Player.    You may wish to consider the number of pieces your player currently has in its Mancala, the number of blank spaces on its side of the board, the total number of pieces on its side of the board, specific board configurations that often lead to large gains, or anything else you can think of.

You should experiment with a number of different heuristics, and you should systematically test these heuristics to determine which work best.  Note that you can test these heuristics with the MINIMAX player, or you can wait until you've completed part 4 below (alpha-beta pruning).  In addition to your code, you will submit a short (1-2 paragraphs) writeup about how you chose your final score function.  What did you try along the way?  What worked well and how did you determine what works well?  

Part 4: Alpha-Beta Pruning search [40 points]

The next part of the assignment is to implement the alpha-beta prune search algorithm described in your textbook and in class.  Look in the code to see where to implement this function.  You may refer to the pseudocode in the book, but make sure you understand what you are writing.  

In your alpha-beta pruning algorithm, you do NOT have to take into account that players get extra turns when they land in their own Mancalas with their last stones.  You can assume that a player simply gets one move per turn and ignore the fact that this is not always true.  Notice that my provided version of minimax also makes this simplifying assumption.  This makes the scoring function slightly inaccurate.  You have the option of fixing this inaccuracy in one of the extra credit options below.

You probably wish to test your alpha-beta pruning algorithm on something simpler than Mancala, which is why I have provided the Tic Tac Toe class.  Using alpha-beta pruning, it's possible for an agent to play a perfect game of Tic Tac Toe (by setting ply=9) in a reasonable amount of time.  The first move will take the agent awhile (20 seconds or so), but after that the agent will choose its moves quickly.  Contrast this to minimax, where a ply greater than 5 takes an unreasonable amount of time.  

Test your algorithm carefully by working through the utility values for various board configurations and making sure your algorithm is not only choosing the correct move, but pruning the tree appropriately. You will need to submit at least one example that illustrates that your algorithm correctly prunes the search tree.  For example, consider the board:
X X _
_ O _
_ _ _

Your search will first try an O in the top right corner and should find that that move leads ultimately to a tie.  Now consider this point in the search tree:
X X _
O O _
_ _ _

where O has tried a move in the left, center spot.  On the next level (when X plays in the top right), the algorithm immediately sees that X will win, resulting in a score of 0 for O.  Since X is the min player, X will choose this move unless there is a move with an even LOWER value (which there is not).  Thus, the best O can do is a score of 0 if it moves in the middle left.  It does not need to try the other positions for X because it knows that it is not going to choose to play here (because blocking X in the top row leads to a score of 50, which is better).  Thus the algorithm will prune the rest of the search tree at this point after it has tried the top right corner for X.  

To write this up, I would first illustrate that my program behaves correctly in this case by adding print statements to my code, which might then produce the following output:

alpha is 50.0, score is 0.0. Aborted on move 2 in minValue on 
XX2
OO5
678

Then I would explain what is going on as above.  You should choose a different example when testing your code.  Come see me if you have questions about this part.  Your explanation of what is going on is worth a significant part of your grade, so be sure that you understand the above explanation and that you can produce one of your own.

Part 5: Creating your best custom player [10 points]

Create a custom player using any technique you wish that plays the best game of Mancala possible.  This will be the player that you enter into the class tournament.  Your only restriction is that your player must make its moves in about 10 seconds (you don't need to get fancy with timers or anything, but if it runs significantly longer than that, it will be disqualified from the tournament).

Next, choose a name for your player.  You should rename both the MancalaPlayer subclass and the Player.py file to match your player's name.  (This is so they can be easily identified in the tournament).  

I will hold a tournament of these players (the finals to be held in class, time permitting), and the winner will receive their very own Mancala board game.

Optional Extra Credit #1 [up to 5 points]:

Improve on the Mancala GUI that I provided.  You can start with my code and add to it, or simply start over from scratch.  Submit your GUI files, clearly named and commented, with the rest of your assignment.

Optional Extra Credit #2 [up to 5 points]:

As described above, my minimax implementation does not take into account the fact that a player gets another move if his or her last stone ends in the player's own Mancala.  Write a new minimax function, called "minimaxBonus" and a new alpha-beta pruning function, called "abPruneBonus", that takes into account that a player gets another move on their turn if they land in their own Mancala with their last stone.  You should also be sure to provide test cases in a file called "bonus.txt" that shows that your new algorithms do indeed work as expected (this is somwhat tricky, but important).

What to submit

Be sure to include both your name and your partner's name on all files.  You may submit these files through either person's Sakai account.