This assignment is to be done individually. As noted elsewhere, the assignment is to be programmed in C or C++. No external libraries or source code is permitted, except as noted by your instructor or TAs. Your program should compile using gcc / make on the ECE Linux lab machines in Trottier 5110. Additional notes on assignment submission are given below.
The game of "Black & White" is played on a 5x5 grid in a way that resembles Checkers and Othello. Starting from an empty board, players alternate placing a disc of their color on the board. White plays first. Each player has 5 discs, and when all discs are on the board, players alternate by moving one of their pieces at each turn. A piece may be moved one square horizontally or vertically, or "jumped" horizontally or vertically over a single adjacent opponent's piece, into an empty square. Jumping over an opponent's piece causes that piece to change color (i.e. to become a piece belonging to the player who jumped). Unlike in checkers, multiple jumping is not allowed. Jumping over ones own pieces is not allowed. Diagonal moves are not allowed. The winner is the first player to line up five of her pieces, either horizontally, vertically, or diagonally, or else to make it impossible for the opponent to make a valid move.
Implement a game-playing agent to play the game of Black & White. Your agent will alternate moves with a human opponent. The computer is expected to be alotted no more than 7 seconds of computation time per move.
Your interface should be a simple text-only system, which displays the current board state as a matrix of comma-separated characters, with 1 denoting a white piece, 0 denoting a black piece, and suitably formatted whitespace denoting an empty square. For example, the board configuration above would be represented as follows:
,1, , , 1,1, , , 1, ,1,0, 1,1, , , ,0,0, ,The game should permit the user to play against the computer by inputting moves from the command line. Each square in the grid can be labeled by its <x,y> position, with 1,1 corresponding to the top-left square. Moves are entered by specifying the position of the piece to move in the form <xy>, and one of the compass directions, N, S, E, W. For example, to move the black piece at the bottom middle of the board one square to the right, the command would be 34E. To jump the white piece in the center of the board over the black piece to the right of it, the command would be 33E .
For this part of the assignment you may evaluate game states as being either an inevitable win for white (+1), a loss for white (-1), or a neutral state (0).
In Part I of this assignment, our evaluation function was extremely simplistic. This left our agent with the ability to make intelligent moves only when its lookahead horizon could detect a sequence leading to a guaranteed win. However, as described in the text, when we are forced to cut off the search at non-leaf nodes, we can exploit a heuristic evaluation function to to provide a meaningful estimate of the utility, or "goodness", of the corresponding state.
Your task is to design a useful evaluation function for non-terminal nodes and demonstrate that it leads to improved performance.
In actual game play, it is possible for both players to take the same sequence of moves repeatedly, leading to a cycle in the game tree. Such cycles are costly in both time and space, reducing the efficiency of the game-playing agent. In order to avoid generating cycles of moves in the search tree, a naive solution would be to maintain an array of all board configurations (and their associated values) inspected previously. Of course, this is insufficient and impractical, but you can do better.
In order to obtain the bonus marks, you must not only implement a solution to the cycles problem, but explain, in your report, the method you used and demonstrate its performance improvement.
You must submit, at the start of class on the due date, a hardcopy consisting of the following:
In addition to the hardcopy submission, you must provide an electronic version of your assignment in a gzipped tar file using the UNIX tar(8) format. The electronic submission must include:
You will submit the assignment through the assignment submission section of WebCT Vista.
Your submission must be supplied by the assignment deadline. Assignments will not be considered complete if they have not been submitted both in hardcopy and electronically or if the two versions of the source code differ. Incomplete submissions will not be marked. The hardcopy and electronic versions may be submitted at different times within the assigned deadline.
The gzipped tar file must create, when opened, a directory named with your student ID, containing all the source files (there may be subdirectories, if needed) and the Makefile as described above. An optional file named README may be included, containing a summary of the supplied files, in particular, the naming of the log files.
An example sequence of UNIX shell commands that creates a gzipped tar file as specified follows [comments in square brackets]:
[Create the source directory for student with id 952334.] % mkdir ./952334 [Copy all the necessary files to it.] % cp foo.c bar.c part?.log README ./952334 [Create the gzipped tar file with the directory content.] % tar zcvf 526-A1-952334.tgz ./952334
Last updated on 17 January 2006
by Yon Visell