Game playing is a popular subfield 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.
Tic-tac-toe is a simple example of such a game. The ancient African game Kalah, alias Mancala, is a more substantial example. There are many variations of Kalah; the Egyptian rule set (as described in lectures) defines one variation.
In many such games, the player who moves first has an advantage. Such is the case with Kalah. So the true test of the relative superiority of two players can be decided only via a two-game match. One player moves first during the first game of the match; the other player moves first during the second game of the match. One of the players is declared the winner of the match based upon the "margins of victory" of the two games.
Accordingly, the objective of the first game of a match is not simply to win. Instead, the objective of the first game is to win by as wide a margin as possible. The objective of the second game of the match is not to win, per se. Instead, the objective of the second game is to achieve an adequately large margin of victory (or an adequately small margin of loss) to win the match.
The heart of many game player programs is the minimax search algorithm. For efficiency, the minimax search algorithm can be enhanced with alpha-beta cutoffs, thus forming the alpha-beta search algorithm. Both the minimax and alpha-beta search algorithms were described in lectures.
Your task in this assignment is to work within a team to create programs that use alpha-beta search to play (1) tic-tac-toe, and (2) Kalah using the Egyptian rule set.
Your tic-tac-toe player should accept one or two command-line arguments. The first argument should be either "FIRST" or "SECOND", indicating whether the program should assume the role of the player who moves first or the player who moves second. The second argument, which may or may not be present, should be a "margin of victory." Your tic-tac-toe player probably will ignore that second argument.
If your tic-tac-toe player is the FIRST player, it should:
If your tic-tac-toe player is the SECOND player, it should:
Each move should consist of a row number (0 to 2), a space, a column number (0 to 2), and an end-of-line mark.
Your tic-tac-toe player need not validate the moves that it reads from its opponent. That is, your player may assume that the opponent provides valid moves.
For debugging, we recommend that you add code to your tic-tac-toe 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 tic-tac-toe player that you submit should write only moves to stdout, and should read only moves from stdin.
Your Kalah player should accept one or two command-line arguments. The first argument will be either "FIRST" or "SECOND", indicating whether the program should assume the role of the player who moves first or the player who moves second.
The second argument, which may or may not be present, should be a "margin of victory," that is, an integer indicating the score by which the player must win this game in order to win the two-game match with its opponent. For the first game of a two-game match, the player will be invoked without its second argument, thus indicating that your player should try to win the game by as many points as possible. For the second game of a two-game match, the desired margin of victory depends upon the outcome of the first game. For example:
Your player may use the "margin of victory" argument to know when it can abbreviate its search. Or, your player simply may ignore the "margin of victory" argument.
If your Kalah player is the FIRST player, it should:
If your Kalah player is the SECOND player, it should:
Each move should consist of an integer followed by an end-of-line mark. If your Kalah player is the FIRST 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 SECOND 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. That is, your player may assume that the opponent provides valid moves.
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.
You and the other students in your precept comprise a software development team. Your job is to produce software modules that, when combined with modules created by the other members of your team, implement your game playing programs.
It is up to the team, with guidance from the preceptor, to decide how to divide the programs 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 also should 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/cos217/Assignment4/sampletttplayer contains the executable code for a tic-tac-toe player, and the file /u/cos217/Assignment4/samplekalahplayer contains the executable code for a Kalah player. You may use those files to answer questions about the desired functionality of your player programs.
The file /u/cos217/Assignment4/tttreferee contains the executable code for a tic-tac-toe referee. The tttreferee program can conduct a game between any two tic-tac-toe players. It should be executed with four command-line arguments: (1) the name of executable file for the FIRST player, (2) the FIRST player's desired margin of victory, (3) the name of the executable file for the SECOND player, and (4) the SECOND player's desired margin of victory. You might use tttreferee to conduct games between your tic-tac-toe player and sampletttplayer, thus testing your tic-tac-toe player.
The file /u/cos217/Assignment4/kalahreferee contains the executable code for a Kalah referee. The kalahreferee program can conduct a game between any two Kalah players. Like tttreferee, it should be executed with four command-line arguments: (1) the name of executable file for the FIRST player, (2) the name of the executable file for the SECOND player, (3) optionally, the FIRST player's desired margin of victory, and (4) optionally, the SECOND player's desired margin of victory. You might use kalahreferee to conduct games between your Kalah player and samplekalahplayer, 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 tic-tac-toe player in a file named tttplayer, and your Kalah player in a file named kalahplayer. That is, the first dependency rule in your makefile should be "all: tttplayer kalahplayer". Your makefile should compile using 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 hats 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 players. You should also submit a readme file that contains:
You should submit your personal work electronically via the command:
/u/cos217/bin/i686/submit 4 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 players. We will execute your players using tttreferee, sampletttplayer, kalahreferee, and samplekalahplayer as indicated above. We will not penalize your grade if your players lose to the given ones. However, we will penalize your grade if your players violate the rules of the game, consume more than the allowed CPU time, or crash.