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 defines one variation.
The heart of many game player programs is the minimax algorithm. For efficiency, the minimax algorithm often is enhanced with alpha-beta cutoffs, thus forming the alpha-beta search algorithm. Both the minimax and alpha-beta algorithms will be described in lectures.
Your task in this assignment is to work within a team to create a Kalah player program that adheres to 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.
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 (i.e. integers) 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/samplekalahplayer 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/samplekalahreferee contains the executable code for a Kalah referee. The samplekalahreferee 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 samplekalahreferee to conduct games between your Kalah player and samplekalahplayer, thus testing your Kalah player.
By 8:00 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 kalahplayer. As usual, it should use the "-Wall", "-ansi", and "-pedantic" compiler options. It may also, at your discretion, use the "-DNDEBUG" compiler option to disable calls to assert, thus improving efficiency (perhaps at the expense of robustness). Your team should also have a readme file indicating which team member developed which implementation (.c) files and the makefile. 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 11:59 PM on the due date, each person should submit the implementation (.c) files that he or she 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 kalahplayer. 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 kalahplayer. We will execute your kalahplayer using samplekalahreferee and samplekalahplayer, as indicated above. We will not penalize your grade if your kalahplayer loses to samplekalahplayer. However, we will penalize your grade if your kalahplayer generates an invalid move, consumes more than the allowed CPU time, or crashes.