Game playing is a popular sub-field of the artificial intelligence (AI) branch of computer science. AI researchers have paid particular attention to "deterministic two-player games of perfect information" such as chess and checkers.
The ancient African game of Kalah, alias Mancala, is such a game. There are many variations of the game; the Kalah Egyptian rule set (as described in lectures) defines one variation.
The heart of many game player programs is the minimax search algorithm. For efficiency, the minimax search algorithm often is enhanced with alpha-beta cutoffs, thus forming the alpha-beta search algorithm. Both the minimax and alpha-beta search algorithms will be described in lectures.
Your task in this assignment is to work within a team to create a Kalah player program that uses the Egyptian rule set, and that is implemented using alpha-beta search.
Your Kalah player should accept one command-line argument. That argument should be either "MIN" or "MAX", indicating whether the program should assume the role of the MIN player or the MAX player. By convention, the MIN player always makes the first move of the game.
If your Kalah player is the MIN player, it should:
If your Kalah player is the MAX player, it should:
Each move should consist of an integer. If your Kalah player is the MIN player, then it should express each of its moves as an integer in the range 0-5, thus indicating which of its 6 bowls should be emptied. If your Kalah player is the MAX player, then it should express each of its moves as an integer in the range 7-12.
Your Kalah player need not validate the moves that it reads from its opponent. It is the Kalah referee's responsibility to do that. (You will create a referee in the next assignment.)
As described in lectures, your Kalah player should use an incremental game state evaluation process. It should express each move as a sequence of atomic "deltas," and should update the value of the game state each time it applies a delta.
Your Kalah player is allowed to consume no more than 2 minutes of CPU time for all its moves put together. Through experimentation you should set the depth limit of the alpha-beta search accordingly. Hint: You might design your Kalah player so it uses the standard clock function to collect timing statistics, and so it writes those timing statistics to a file.
For debugging, we recommend that you add code to your Kalah player that prints a representation of the game state each time it changes. However that code should not be present in the work that you submit, or it should be disabled. The Kalah player that you submit should write only moves to stdout, and should read only moves from stdin.
In your precept, you will be assigned to a team. Your job is to produce software modules that, when combined with modules created by the other members of your team, implement your Kalah player.
It is up to the team, with guidance from the preceptor, to decide how to divide the program into modules. Furthermore, it is up to the team, with approval of the preceptor, to assign team members to modules.
Your team will need to communicate to decide upon module interfaces and work assignments. At least two precepts will be devoted to team meetings. We anticipate that your team will need to schedule additional meetings.
Your team should also communicate by e-mail. You should create and use an e-mail alias that lists the members of your team. You should include your preceptor in that e-mail alias.
The file /u/cs217/Assignment3/sampleplayer contains the executable code for a Kalah player. You may use it to answer questions about the desired functionality of your Kalah player.
The file /u/cs217/Assignment3/samplereferee contains the executable code for a Kalah referee. The samplereferee program can conduct a game between any two Kalah players. It should be executed with two command-line arguments: the name of executable file for the MIN Kalah player, and the name of the executable file for the MAX Kalah player. You might use samplereferee to conduct games between your Kalah player and sampleplayer, thus testing your Kalah player.
By 4:59 PM on the due date, your team should have a complete set of object (.o) files, a complete set of interface (.h) files, and a makefile. The first rule of the makefile should build your Kalah player in a file named player. As usual, it should use the "-Wall", "-ansi", and "-pedantic" options. To improve the performance of your player, your makefile also may use the "-DNDEBUG" option to disable the assert macro (perhaps at the expense of robustness) and the -O3 option to command the compiler to produce optimized code. You should place those team files in a directory on arizona that is accessible to all members of your team and to your preceptor. You should send e-mail to your preceptor indicating the name of that directory.
By 8:59 PM on the due date, you should submit the implementation (.c) files that you personally developed. Those files must be such that they can be used, along with your team's interface files, object files, and makefile, to build your player. You should also submit a readme file that contains:
You should submit your personal work electronically via the command:
/u/cs217/bin/submit 3 filesthatyoudeveloped readme
We will test your work by using your team's makefile, your team's object code files, your team's interface files, and your (individual) implementation files to build your player. We will execute your player using samplereferee and sampleplayer, as indicated above. We will not penalize your grade if your player loses to sampleplayer. However, we will penalize your grade if your player violates the rules of the game, consumes more than the allowed CPU time, or crashes.