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. Othello (http://www.pressmangames.com/instructions/instruct_othello.html) is a more substantial example.
In many such games, the player who moves first has an advantage. Such is the case with Othello. 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 are described in lectures.
Your task in this assignment is to work within a team to create programs that use alpha-beta search to play tic-tac-toe and Othello.
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 a newline character.
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 be disabled in the work that you submit. The tic-tac-toe player that you submit should write only moves to stdout, and should read only moves from stdin.
Your Othello 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," 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 should 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 Othello player is the FIRST player, it should:
If your Othello player is the SECOND player, it should:
Each move should consist of a column letter (A to H, either uppercase or lowercase) and a row number (0 to 7) with no space in between, and should be terminated by a newline character.
Your Othello 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 Othello 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 Othello player so it uses the standard C clock() function to collect timing statistics, and writes those timing statistics to a file. See the testsymtable.c file from Assignment 3 for an example of code that calls the clock() function.
For debugging, we recommend that you add code to your Othello player that prints a representation of the game state each time it changes. However that code should be disabled in the work that you submit. The Othello player that you submit should write only moves to stdout, and should read only moves from stdin.
We will assign you to a software development team comprised of a subset of students from your precept. 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.
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 outside of precept time.
Your team also should communicate by e-mail. We will create an e-mail list for your team containing the e-mail addresses of you, your teammates, and your preceptor. You should use that e-mail list for communication. (Your preceptor needs to be part of your e-mail conversations.)
Your team should choose three individuals to serve leadership roles:
The choice of Manager, Architect, and Builder are subject to the preceptor's approval. The work assignments also are subject to the preceptor's approval.
You are allowed to:
You are not allowed to:
The /u/cos217/Assignment4 directory contains some executable binary files that you will find helpful:
Your team should have three code repositories, that is, three UNIX directories that will allow you to share code among your teammates:
Each object file in the debug and release repositories should have a name that consists of the initials of the team member who contributed it, followed by the module name, followed by .o. (Examples: AAplayer.o, RDsearch.o.)
The assignment covers a two-week (that is, a four-precept) period. These are the deliverables throughout that period:
The Manager should send a "startup" e-mail to the team's e-mail list. It should indicate the names of the Manager, Architect, and Builder. The e-mail also should indicate the absolute directory names of the team's three code repositories. We recommend that the code repositories be children of the Builder's home directory.
The interface repository should contain the team's interfaces. That is, the interface repository should contain a complete set of interface (.h) files. You can change the .h files subsequently, with notification and justification sent to the team's e-mail list.
The Manager should send a "work assignments" e-mail to the team's e-mail list. The e-mail should indicate work assignments, that is, which team member will develop each module implementation (or partial implementation). The work assignments should be balanced: the Architect, Manager, and Builder should have one or more work assignments, and other team members should have two or more work assignments. The work assignments also should be redundant: you should assign at least two team members to the development of each module implementation (or partial implementation).
The Manager should send a "status report" e-mail to the team's e-mail list. The e-mail should contain a description of work completed so far by each team member. The Manager may compose the descriptions, or may collect them from the team members. One or two sentences per team member is sufficient.
The debug and release repositories should contain object (.o) files to build complete tic-tac-toe and Othello players. The repositories should contain at least one working implementation of each module. You may change those .o files later. You may add more .o files later.
Your debug repository also should contain executable game player programs in files named playerttt and playerothello. The debug repository should contain a bash shell script named buildttt that builds playerttt, and a bash shell script named buildothello that builds playerothello, from chosen subsets of your team's .o files. Similarly, your release repository should contain files named playerttt, playerothello, buildttt, and buildothello.
The playerothello file in your release repository should contain your team's tournament-ready Othello player. The buildothello file in your release repository should contain a bash shell script that builds playerothello from a chosen subset of your team's .o files.
You, as an individual, should submit:
The first dependency rule in your makefile should be "all: playerttt playerothello". The remaining dependency rules should build (1) the two executable files from your .o files and complementary team .o files, and (2) your .o files from your .c files. Your makefile should encode file dependencies to allow for partial builds. Your makefile should build release (not debug) versions of your players.
Your readme file should contain:
You should submit your individual work electronically using these commands:
/u/cos217/bin/i686/submit 4 yourFiles.c /u/cos217/bin/i686/submit 4 teamFiles.h /u/cos217/bin/i686/submit 4 selectedTeamFiles.o /u/cos217/bin/i686/submit 4 playerttt playerothello /u/cos217/bin/i686/submit 4 makefile /u/cos217/bin/i686/submit 4 readme
The interface repository should contain only .h files. The debug and release repositories should contain only .o files (and, eventually, shell scripts and executable binary files). Those are the files that are shared among teammates. No repository should contain .c files. Those files are private to individual teammates.
Develop a protocol for adding/deleting/replacing the .h and .o files that reside in the team's repositories.
A strict protocol might allow only the Builder to change the contents of a repository; all new files must be e-mailed to the Builder. A more relaxed protocol might require each team member to ask the Builder's permission before changing a the contents of a repository. A still more relaxed protocol might require a team member to send an e-mail to the team's e-mail list immediately after changing the contents of a repository.
Periodically make backup copies of the three repositories. Backup repositories will be very helpful if someone accidentally corrupts a repository.
To build the object files that reside in the debug repository, use the -g and -pg arguments to gcc. As you know, the -g argument commands gcc to include information into the resulting object file that gdb will use. The -pg argument commands gcc to include information into the resulting object file that gprof will use. You also might build with gccmeminfo instead of with gcc. But beware that the meminfo*.out files created by programs built with gccmeminfo can consume much disk space.
To build the object files that reside in your release repository, use the -O3 (that's uppercase "oh", followed by the number "3") and -DNDEBUG arguments to gcc. The -O3 argument commands gcc to optimize the machine language code that it produces. When given the -O3 argument, gcc spends more time compiling your code so, subsequently, the computer spends less time executing your code. The -DNDEBUG argument commands gcc to define the NDEBUG macro -- just as if the preprocessor directive "#define NDEBUG" appeared in the .c file(s) that gcc is processing. Defining the NDEBUG macro disables the assert() macro, and thereby can make your code run faster. Building for speed will allow your player programs to search grow deeper search trees than otherwise in the same amount of time, and thus will create a "smarter" program.
Read moves using the fscanf() function. In particular, read the column letter of an Othello move using a statement of this form:
iReturnValue = fscanf(psFile, " %c", &cColChar);
Do not use a statement of this form:
iReturnValue = fscanf(psFile, "%c", &cColChar);
or of this form:
iColChar = fgetc(psFile);
The latter forms fail to skip over leading whitespace characters. Specifically, they fail to skip over the newline character that terminates the previous move.
The C standard writing functions buffer the output that they write to their streams. The output is not sent to its physical destination until (1) the buffer becomes full, (2) the process exits, or (3) you explicitly "flush" the buffer by calling fflush(). In your game player programs, call fflush() after writing each move.
To create a competitive Othello player, analyze your player using gprof, and optimize the sections of code that are particularly time consuming.
Suppose a program contains a module named m, consisting of interface file m.h and implementation file m.c. Furthermore, let's say that m.c is large -- so large that it would be unreasonable for one programmer to develop all of it. To facilitate multi-programmer development, the team could split the implementation into two files: m1.c and m2.c. Then some team members could work on m1.c, and others independently could work on m2.c.
Further suppose, however, that both m1.c and m2.c need to use the same data types. It would be stylistically horrible to place the definitions of those types in m.h; doing so would reveal the data types to clients, thus violating encapsulation. It also would be stylistically horrible to define the data types redundantly within both m1.c and m2.c; redundancy introduces the possibility of inconsistency, especially over time. So where should the shared data types be defined?
One answer is to create another file named mprivate.h. mprivate.h is a "private" header file for the m module which defines the data types used by m1.c and m2.c. Both m1.c and m2.c #include mprivate.h, and thus have access to the definitions of the data types that they need. But mprivate.h is not advertised to clients, and so encapsulation is not violated.
For this assignment, we recommend that your team create "private" header files as required.
Suppose that a program contains modules named m1 and m2, m1 calls functions that are defined in m2, and m1 and m2 are being written by different programmers.
The programmer of m1 may find it convenient to create a stub. A stub is a module that provides a subset of the functionality of m2, often by reading data from a file or the keyboard. A stub thereby allows the programmer to test m1. The programmer of m2 may find it convenient to create a scaffold. A scaffold is a module that provides a subset of the functionality of m1, often by reading data from a file or the keyboard. A scaffold thereby allows the programmer to test m2.
For this assignment, we recommend that your team create scaffolds and stubs as required. You may submit scaffolds and stubs for credit.
We will test your work by building players using your .c files, your team's .h files, and the team .o files that you have selected. We will execute your players using refereettt and refereeothello. We will not penalize your grade if your players lose games or matches. However, we will penalize your grade if your players violate the rules of the game, consume more than the allowed CPU time, or crash.