Assignment 3: Alpha-Beta Pruning
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Autumn 2009
The reading for this assignment is the game-playing part of Chapter 5 of The Elements of Artificial Intelligence Using Python.
Due Monday, October 26. Catalyst CollectIt at 11:00 AM.

You should turn in one Python file containing your function definitions and global variables.
 
The assignment is to create a program -- consisting mainly of a collection of specific functions, for playing games of "K in a Row". We define a K in a Row game as a kind of generalized Tic-Tac-Toe with the following features: (a) Just as in Tic-Tac-Toe, there are two players: one plays X and the other plays O; (b) the board is rectangular, but is not necessarily 3 by 3; it is mRows by nColumns, where these numbers are chosen by the referee at the beginning of the game; (c) a player wins by getting K in a row, where K is not necessarily 3; K can be any integer greater than 1 and less than or equal to the maximum of mRows and nColumns; (d) there can be "forbidden squares" on the board; these are chosen at the beginning of the game by the referee; a square on the board that is available is represented by a blank, ' ', whereas a forbidden square is represented by a dash, '-'.
 
Your program should have a well-defined "personality". Some examples of possible personalities are these: friendly; harmless joker; blunt joker; paranoid; wisecracker; sage; geek; wimp; competitive freak; fortune-teller (based on the state of the game). The personality will be revealed during games via the "utterances" made by the program. (For more details, see the description of the makeGoodMove function below.)
 
Your program must include the following functions. You can have helper functions if you like. Please keep all the functions required by your player in one Python file. Name your file in this style: yourUWNetIDKINAROW.py. For example, my player would be in a file tanimotoKINAROW.py. This will facilitate your player's being part of the class tournament.

1. prepare. Define a function "prepare(k, mRows, nColumns, maxMillisecPerMove, isPlayingX, debugging)" that will accept four integers and two booleans and remember these values for the game that is about to be played. The first parameter, k, is the number of pieces in a row (or column or diagonal) needed to win the game. The two parameters mRows and nColumns give the height and width of the board, respectively. The parameter maxMillsecPerMove represents a time limit that your move-making function will be required to respect. The boolean parameter isPlayingX will be True if your player is to play the X pieces and False if your player is to play the O pieces. The final parameter tells your program whether to print diagnostic information when it makes its moves. This is explained under makeGoodMove. Your prepare function should return a string. The string should either be "OK" or a string that gives some reason why your program will not be able to play the specified game, such as "I require at least 17 milliseconds to make my moves.", "Let's quit right now because nobody can get 7 in a row on a 3 by 5 board.".
2. introduce. Define a function "introduce()" that will return a multiline string that introduces your player, giving its name, the name of its creator (you), and a clue about its personality.
3. nickname. Define a function "nickname()" that will return a string of length no more than 15 giving a nickname for your player that will be used in reporting the moves of the game and the comments made.
4. successors. Implement a move generator "successors(state)" for the game K in a row that returns a list of the legal new states from the given state, assuming it is playing for the side it was "prepared" for. Assume that a state is represented in the same general manner as was used in Lab 2 and Assignment 2. As mentioned below, some testing code is available.

Here's a representation for a possible starting state in a game after a call prepare(4, 5, 6, 1000, True, True) has been made. 

['X', [['-', '-', ' ', ' ', '-', '-'],
       ['-', ' ', ' ', ' ', ' ', '-'],
       [' ', ' ', ' ', ' ', ' ', ' '],
       ['-', ' ', ' ', ' ', ' ', '-'],
       ['-', '-', ' ', ' ', '-', '-']]]
Note the forbidden squares, in which neither X nor O is allowed to go. These can be anywhere on the board, but they will not change during a game.
5. makeMove. Implement a function "makeMove(state)" that returns a list of length 2 of the form [newState, utterance]. This function must return a legal new state (one of the elements on the list created by successors(state), though you don't have to use the successors function in this. The utterance for makeMove just has to be a string that reflects your player's personality and does not have to reflect the state of the game.
6. staticValue. Design a static evaluation function "staticValue(state)" that will work without errors no matter what values of k, mRows and nColumns have been set by your prepare() function. Explain in comments in the code how this function works and in particular, the rationale for any special features you have put in related to patterns on the board.

If you use outside references or websites in your design of this function, make sure that you include a comment in the code about each reference used, including the URLs of any web resources used. It's easy to include a multiline comment using the triple quoting feature of Python. You can put such a string as the first part of the body of a function or at the top level, preceding the function definition.

7. makeGoodMove. Create an improved version of your makeMove function and name it "makeGoodMove". It should correctly use Minimax search and Alpha-Beta pruning. If the parameter "debugging" was set by prepare() to True, then your program should print out a message every time a cutoff is found. The message should be of the form: "In Move 6 of the game, it is X's turn, and an alpha cutoff occurs at Ply 3 out of 6 because provisional value is 35 but opponent could achieve 27." The Move is 0 at the beginning of the game, and it is X's turn. Then the Move is 1 and it is O's turn, etc. An alpha cutoff will occur at an odd-numbered ply when at the root it is X's turn. A beta cutoff will occur at an even ply when at the root it is X's turn. "out of 6" here is saying that the overall search was to a depth of 6. The provisional value is the one in the MiniMax algorithm at the level where the cutoff is found. If the parameter "debugging" is False, then nothing should be printed out by your makeMove function. makeGoodMove should return its answer within maxMillisecPerMove. You can assume this will never be less than 50 and will usually be around 500 for the main tournament. The utterance you return from makeGoodMove must reflect both the personality of your player and the state of the game in some way. For example, if your personality is geeky, an utterance might be something like "Oh gosh, I've searched to a depth of 4 but the static value of the board I'm giving you is -117. My chances of recovery seem very slight." A paranoid might utter, "What do you mean by going there? You now have 7 in a row and I think you are trying to do me in."
Test harness Here is some code you can use for testing your successors function. There are two files: The file moveTester.py will call your successors function (once you edit in the correct name of your Python file). It will compare it with the correct list of successors for the given state, and then it will tell you if your successors are the same as the correct ones. The compiled Python file GroundTruth.pyc computes the correct set of successors for this comparison. Here is a version of GroundTruth that works wih Python 2.6.
Grading Notes Most of the functions above are essential for tournament play. These are all except: successors (which you might need anyway for your implementation of makeGoodMove), staticValue (same), and makeMove. In the event that your program does not compete, we may run these "stepping stone" functions to give partial credit. staticValue, however, will be graded separately. While the details of grading this assignment will be worked out later, here are some aspects to keep in mind. It will be important for your program to be able to play in the tournament. We'll be looking for both imagination and "functionality" in the personality and its reflection in the utterances. How the utterances reflect both personality and game state will be important. We plan to award some extra credit to the top few (five?) programs in the tournament and the "best" use of utterances (possibly via voting by the class).
Updates and Corrections If necessary, updates and corrections will be posted here and mentioned in class or on the mailing list. (Last updated Oct. 17 with links to moveTester.py and GroundTruth.pyc.)