You are encouraged to work in teams of two on this assignment. If you work as a team, turn in only one copy of your code, but be sure that both of your names appear in a comment at the top of your file.
For this assignment you will implement a program to play the ancient game of Konane, also known as Hawaiian Checkers, using the Minimax search algorithm. The game is typically played on an N × N board of light and dark pieces. The board shown below is 8 × 8, and uses x for dark and o for light:
0 1 2 3 4 5 6 7
0 x o x o x o x o
1 o x o x o x o x
2 x o x o x o x o
3 o x o x o x o x
4 x o x o x o x o
5 o x o x o x o x
6 x o x o x o x o
7 o x o x o x o x
First, the dark player removes a dark piece at position (0, 0), (7, 7), (3, 3), or (4, 4). (If N is odd, then only the center position or the two corners can be chosen.) Next, the light player removes a light piece adjacent to the space created by the first move. Then the players alternate moves, each jumping one of his/her own pieces over one horizontally or vertically adjacent opponent's piece, landing in a space on the other side, and removing the jumped piece. If desired, this may be continued in a multiple move, as long as the same piece is moved in a straight line. The game ends when one player can no longer move, and that player is considered the loser. For example, after the following moves:
Dark (x) Light (o)
---------------- -----------------
removes (4, 4) removes (4, 3)
(2, 4) to (4, 4) (4, 1) to (4, 3)
(2, 6) to (2, 4) (4, 5) to (2, 5)
(6, 2) to (4, 2) (5, 4) to (5, 2)
(6, 0) to (6, 2) (1, 4) to (3, 4) to (5, 4)
the board looks like:
0 1 2 3 4 5 6 7
0 x o x o x o x o
1 o x o x . x o x
2 x o x o . o . o
3 o x o x . . o x
4 x . x o . . x o
5 o x o . o x o x
6 . . x o x o x o
7 o x o x o x o x
On Tuesday, October 4, we will hold a tournament in class to determine whose program is the ultimate Konane player. The winner of the tournament will receive an exciting Mystery Prize! If your program is not operational for some reason, you must compete against the other programs.
Your program should use the Minimax algorithm with alpha-beta pruning to decide its moves. To use Minimax, you'll need to develop a static evaluation function. During the tournament, your Konane player will conduct a Minimax search to depth 4 on boards of size 8. Your evaluator will largely determine the success of your program, so it is worth spending some time testing various methods.
In order to keep the tournament manageable, we will enforce a time limit on the total amount of time spent by your program deciding on its moves over the course of a game. If your player exceeds this limit, its search depth will be automatically reduced. However, this limit shouldn't be an issue if you use a reasonable evaluation function.
To get you started, I have provided a KonaneBoard class definition that we will use to represent Konane boards. Save this file to your own directory and read through the code. The board state is represented as a two-dimensional list of characters (x, o, or blank). The method possibleOpeningMoves takes 'x' or 'o' as input and returns a list of all of the board positions that can be used for that side's opening move, where each position is represented as a (row, column) pair. For example, if b is the initial board shown above, then b.possibleOpeningMoves('x') would return four positions to choose from:
[(0, 0), (3, 3), (4, 4), (7, 7)]
The method possibleNextMoves takes 'x' or 'o' as input and returns a list of all of the non-opening moves that can be made by that side, where each move is represented as a list of two or more positions corresponding to jumps. For example, after removing the initial pieces at (4, 4) and (4, 3), b.possibleNextMoves('x') would return three moves to choose from:
[((2, 4), (4, 4)), ((4, 6), (4, 4)), ((6, 4), (4, 4))]
As a first step, you may want to start out with a program that plays by simply picking a random move from the list of possible moves, and then add the functionality for Minimax later.
To generate the successors of a state in the game tree, each of the legal moves can be applied to the state in turn. However, in order to avoid excessive copying of states, I strongly recommend that your program update the state itself and then undo the effect of the move after the recursion on the subtree has finished. This way only one copy of the board needs to be maintained as the search descends through the game tree. This will speed up your program significantly.
For each game, your program should gather the following data:
Your Konane program must adhere to the following requirements in order to be able to run in the tournament.
You should not change the KonaneBoard code.
Your program should be implemented as a class called MinimaxPlayer, whose constructor takes two values: a string to serve as a name for your player, and an integer depth limit on the Minimax search performed. For example:
player = MinimaxPlayer("Deep Beige", 4)
creates a player named "Deep Beige" that searches the game tree to a maximum depth of 4.
player.limit stores the depth limit value.
player.initialize(side) initializes your program to play a new game. The side parameter is either 'x' or 'o', indicating which side your program will play.
player.stats() prints the total number of static evaluations made, the number of cut-offs, and the average branching factor since the program was last initialized, and any other relevant information you want your program to keep track of.
player.firstMove(board) takes a KonaneBoard object and returns a (row, column) pair indicating the position of the piece to remove at the start of the game. If the program is playing x, the board will contain no blanks; if it is playing o, the board will contain a single blank. This method must leave the state of the board unchanged.
player.nextMove(board) takes a KonaneBoard object and returns a list of the form
((row1, column1), (row2, column2), ..., (rowN columnN))representing the program's next move, possibly involving multiple jumps, beginning at position (row1, column1) and terminating at position (rowN, columnN). If no move is possible, the special value None is returned. This method must leave the state of the board unchanged.
player.evaluate(board, turn) takes a KonaneBoard object and either 'x' or 'o' indicating whose turn it is, and returns a numerical evaluation of the board in the range -100 to +100, where -100 represents a loss for the player and +100 represents a win.
Choose a unique name for your team and consolidate all of your code into a single Python file named after your team. The KonaneBoard class definition (which should not be changed) should go in a separate file called KonaneBoard.py, which is imported by your main file.
Submit your main file by running the following script from any Pomona Linux machine. Note: be sure to run this script from the directory that contains your Konane code.
/common/cs/submit/cs151-submit
This script will prompt you for the assignment name (in this case, hw05) and then the name of your file to submit. In general, cs151-submit will allow you to submit any number of files, one at a time, but for this assignment you should submit only your main file (not KonaneBoard.py). More information on using cs151-submit is available here.
For convenience, you might want to add an alias to your .bashrc file as follows:
alias cs151-submit='/common/cs/submit/cs151-submit'
Finally, each team should submit only one copy of their code.