Assignment 4: Alpha-Beta Search
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Winter 2005
Create a program that plays the game of Checkers. Your program must implement an interface described below.
Due Friday, February 11, one hour before the beginning of lab. Turn in your source code by 11:30 using the turnin server.
 
Playing Checkers (100 points)
Implement a function makeMove(board, whoseMove, maxPly) that computes three things and returns them in a list of the form [newBoard, stringComment, stringStats]. The parameters to makeMove have the following significance:
  • board represents a checkers board. It is 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 optional timeLimit parameter discussed below. However, we may set ply limits or require time limits later if it proves necessary for practical competitions. 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 0 to 20. The search for a move should not go deeper than this value.
The comment 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.
Implement a function capabilities() that returns an integer that explains the capabilities of your Checkers-playing agent, according to the following scheme. 
0     makeMove function does not work or works only to a very
      limited extent.
1     can make ordinary man moves but cannot jump or use kings.
2     plays Checkers games that do not involve kings
3     plays Checkers (including King moves) but does not implement
      the timeLimit parameter.
4     plays Checkers and implements the timeLimit parameter
      (i.e., is ready for the bonus competition).
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.
timeLimit parameter (Optional, for 5 additional points)
Modify your makeMove function so that it can take an optional fourth parameter, timeLimit. Then, if this parameter is used in a call to makeMove, it 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.
Competition Bonuses: Although all working programs will be represented in a matrix of face-offs, programs that implement the timeLimit parameter will be allowed to compete for bonus points. If your program comes out in the top 50 percent among contenders in the bonus competition, you'll win an additional 5 points, and the overall winner will receive 5 more bonus points.
Coding Requirements: Except for possible extra files involved in the GUI option, all your functions should be implemented in one file. The name of the file must be the same as your UWNetID, and the extension must be the .py Python extension.
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.