Assignment 2: State-Space Search with Checkers
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Winter 2009
Create a program that plays the game of Checkers. Your program must implement an interface described below. This is due Friday, January 30, at noon. Turn in two files: source code and textual answers.
 
Playing Checkers (100 points)
All of the following functions should be defined in a single file whose name is your UWNetID followed by the extension .py so that each student's program serves as a Python module that can be imported by a tournament control program that holds matches.
Implement a function makeMove(state, maxPly, maxTime) that computes three things and returns them in a list of the form [newState, stringComment, stringStats]. The parameters to makeMove have the following significance:
  • state has the form [board, whoseMove], where board represents a checkers board. The board is given as a list of the form: 
    [[' ','b',' ','b',' ','b',' ','b'],
 ['b',' ','b',' ','b',' ','b',' '],
 [' ','b',' ','b',' ','b',' ','b'],
 [' ',' ',' ',' ',' ',' ',' ',' '],
 [' ',' ',' ',' ',' ',' ',' ',' '],
 ['r',' ','r',' ','r',' ','r',' '],
 [' ','r',' ','r',' ','r',' ','r'],
 ['r',' ','r',' ','r',' ','r',' ']]
    Here b means black man, r means red man, B means black king, and R means red king. (This particular board position is actually the starting configuration for each game.) We will use as our rules of checkers those posted at this web site. We will assume that the board is made up dark green squares and beige squares, with a dark green square in each player's lower left corner. The pieces will be assumed to be black (for the player who moves first) and red. We will not concern ourselves with timing rules right now, except as in the maxTime parameter discussed below. Your makeMove function must implement a minimax search, and it should also implement alpha-beta pruning. (Solutions that do not implement alpha-beta pruning will be assessed a 15-point penalty.)
  • whoseMove is either 'black' or 'red'. It tells whose turn it is to move.
  • maxPly is an integer in the range -1 to 20. The search for a move should not go deeper than this value. A value of -1 means that the calling program doesn't care what the ply value is; in this case only the maxTime value will limit the resources used by the function.
  • timeLimit is a parameter that specifies the maximum number of milliseconds the program may use to determine its move. In order for this to work, you will need to use a technique such as iterative-deepening depth-first search and monitor the time being consumed by the search as it goes. You will also need to determine how much time to allow for computing the string comment and reporting the statistics; however, these are unlikely to require much time unless you are computing them in some unusual way.
The stringComment that is returned should be a string that expresses something about the way the game is going. You can imagine a human player expressing glee, frustration, surprise, amazement, etc. Try to give your agent this human touch.

The stringStats string should be a brief report on technical aspects of the search for a good move. It should contain the number of board positions evaluated, the number of alpha cutoffs found, the number of beta cutoffs found, and the number of milliseconds (wall time) that were consumed during the search.

Implement a function introduce() that returns a string that explains what the full name of the checkers-playing agent is, and some information about who wrote it (name and UWNetID).
Implement a function nickname() that returns a string representing the short version of the agent's name.
Implement a function staticValue(board) that takes a board and returns a number representing the static value of that board. If this position is favorable for black, the number should be positive, and if it is favorable for red, the number should be negative. This function should be the same one used to evaluate leaf nodes during the search made by your makeMove function.
GUI (Optional, for 10 additional points)
Implement a web-based variation of your program that displays a web page with the starting board on it and contains a means for a user to specify a move and to submit the move. The program should respond to each submission by making its move and displaying the new board position, the string comment, and the statistics. The user should be able to carry on an entire game with your program. You may use HTML forms, any GIF images you like, and, if you know Javascript, you may use that to help build the interface. You should deploy your program on the web using the UW student server. Turn in a URL to the page with the rest of your turned in materials.
Questions and answers.:

Question: What board orientation should we assume for the board representation given?
Answer: Red starts from the bottom and the men move up, until they become kings. Black starts from the top and the men move down until they become kings.

Question: How do I indicate that a game is finished?
Answer: This is purely optional. However, when the game is over, ideally makeMove would return a list whose stringComment starts with one of the following special string prefixes: 'BLACK HAS WON!', 'RED HAS WON!', 'RESIGN!', or 'DRAW!'. 'RESIGN!' means that your program is giving up, as opposed to losing by force. You do not have to handle a DRAW option. 'DRAW!' would be returned if a situation has occurred that is legally a tie situation -- for example moving into the same state for the third time in a game. This would require keeping track of past board positions reached, and is not required for this assignment. The RESIGN option should not normally be used and is not required. However, if none of the possible successors seem hopeful (all have pretty bad values), then you can have your makeMove return 'RESIGN!'. Also, if your makeMove function returns None or an illegal newBoard component, then your program is essentially resigning or forfeiting the game at that point.

Question: What does the maxPly parameter mean my program has to do?
In a competition, the tournament software would use a large number for maxPly, so that it is up to your software to set the real depth (at something lower than the given value). This parameter simply provides the graders with a means to compare the performance of programs on the basis of factors other than how deep you choose to make your search. For example, the number of cutoffs your program finds will usually depend on the depth of the search.

Textual Answers: In a separate file, called A2comments, provide answers to the following questions: 1. What techniques for automatic game playing do you use in your makeMove function? Everyone should include minimax search and alpha-beta pruning, but also mention any optional techniques you may be using such as Zobrist hashing, iterative deepening, and best-first ordering.
2. What methods do you use to create the string comments that accompany each move?
3. Have you tested your program against anyone else's in the class? If so, whose? What was the outcome?
4. What have you learned in this assignment related to (a) state-space search, (b) game-playing intelligence, (c) programming of AI techniques, (d) other?
A Test Harness: You may find it useful to put your game into competition as soon as it is able to make moves. To do this, create a folder "test", put your program into it, download runGame.py, holdGame.pyc, and tanimotoCheckers.pyc, and put them in the same test folder. Edit runGame.py so that it imports your own checkers program and either plays itself or plays a classmate's program (you'll need to put a copy of their program for their pyc file in the folder, too, in that case). To test your program, run the runGame.py program. It imports holdGame.pyc which in turn imports tanimotoCheckers.pyc. Note that the file tanimotoCheckers.pyc doesn't play checkers but simply referees the game, helping enforce the rules. If you get errors when trying to test your program, most likely you are not implementing the makeMove, introduce or nickname functions correctly.
Last updated 21 Jan. with information about the test harness.