In this assignment we expand upon the game of Tic-Tac-Toe to a more interesting generalization of it: "K-in-Row with Forbidden Squares." At the same time, we put our agents into more serious competition, adding lookahead (with the Minimax technique) and pruning (with the alpha-beta method) to the search. In addition, we add an element of fun and creativity that could serve as an opportunity to beat the Turing Test; this takes place via a more elaborate version of the "utterance feature" introduced in Assignment 3. The assignment has two parts: creating your agent and engaging your agent in a first round of competition play.

You should turn in either 2 or 3 files (depending upon whether or not you are doing the extra-credit items in Part I): (1) a file [YourUWNetID]KInARow.py with your game playing agent described in Part I, and (2) an HTML file that provides a transcript of your agent playing against that of another classmate, described in Part II. If you are doing the extra credit items in Part I, then also turn in your file ExtraCredit.txt that explains those special features of your agent.
 

In this part, you will 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 Game Master (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 Game Master; a square on the board that is available is represented by a blank, whereas a forbidden square is represented by a dash "-" ; (e) there can be "handicaps" in the initial state, meaning that some X and/or O tokens can be set up on the board by the Game Master in order either shape the succeeding play or change the balance of advantage and disadvantage to the players.

In addition to being able to play the game, 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 makeMove 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 just one Python file that follows the naming convention mentioned earlier. 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(initial_state, k, what_side_I_play, opponent_nickname, mode='Normal') . This function takes at least four arguments and will accept five arguments, and it will remember these values for the game that is about to be played.

   The first parameter, initial_state, allows your agent to figure out any needed properties of the game board before the playing begins. It is a legal game state that can be used by your player, for example, to determine the dimensions of the board, the locations of forbidden squares, and even the locations of any handicap items. The second parameter, k, is the number of pieces in a row (or column or diagonal) needed to win the game.

   The parameter what_side_I_play is 'X' if your agent will play as X; it is 'O' if your agent will play O.

   The parameter opponent_nickname allows your utterance-generation mechanism to refer to the opponent by name, from time to time, if desired.

   The final parameter, mode, tells your program whether to use its normal utterances or to return diagnostic information instead. This is explained under makeMove. 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.

   Note that your program does not really have to do much at all when its prepare method is called. The main thing it should do is return "OK". You might wonder what the purpose of it is. It has three purposes: one is to set the mode, which is relevant to the reporting of alpha and beta cutoffs as descrbed below. Another aspect the prepare function is that it offers your agent an opportunity to do any initialization of tables or other structures without the "clock running." This is good for setting up for, say, Zobrist hashing, if you are using that. Another kind of preprocessing would be to make, for each of the four directions in which a win can occur, a list of all the squares on the board where such a winning line could actually start. Having these lists can save time in your static evaluation function.

2. introduce(). This function will return a multiline string that introduces your player, giving its full name (you get to make that up), the name and UWNetID of its creator (you), and some words to describe its character.

3. nickname(). This function should return a short version of the playing agent's name (16 characters or fewer). This name will be used to identify the player's moves in game transcripts.

4. makeMove(currentState, currentRemark, timeLimit=10000). This is probably your most important function. It should return a list of the form [[move, newState], newRemark]. The move is a data item describing the chosen move, and its format is the same as that used in Assignment 3. The newState is the result of making the move from the given currentState. It must be a complete state and not just a board. The currentRemark argument is a string representing a remark from the opponent on its last move. The timeLimit represents the number of milliseconds available for computing and returning the move.

   The newRemark to be returned must be a string. During a game, the strings from your agent and its opponent comprise a dialog. Your agent should contribute to this dialog in three ways:

   1. by convincingly representing the character that you have chosen or designed for your agent,
   2. by showing awareness of the game state and game dynamics (changes in the game state), and
   3. by responding in a convincing way to the opponent's remarks.

   A portion of your grade (15 points) will be based on how well your agent's remarks meet the first criterion. Criteria 2 and 3 are for extra credit. To get the extra credit, implement one, the other, or both, and then describe, in a separate file called ExtraCredit.txt what the features are and how they work. Something working that adds in a noticeable way to the dialog and that fits one of the two criteria is worth 5. A more thorough implementation that shows considertion for multiple features related to one of these two criteria is worth 10. The maximum extra credit here is therefore 20 points.

   Your program should be able to report statistics. This will be controlled by the mode parameter in prepare as follows.

   1. mode = "Normal": return an utterance that reflects the personality of your agent, and/or the state or progress of the game.
   2. mode = "Static": return a string that gives the static value (however you compute it) of the current state that is input to makeMove. This allows the graders to test your static evaluation function.
   3. mode = "Dynamic": return a string that tells what depth was reached, how many states were statically evaluated, how many were dynamically evaluated, the number of alpha cutoffs and the number of beta cutoffs, and the dynamic value of the state that results from the chosen move. The string should be of the form: "searched to depth 3; 1217 static evals; 94 dynamic evals; 13 alpha cutoffs; 27 beta cutoffs; dynamic value of new state is -537."
5. staticEval(state). This function will perform a static evaluation of the given state. The value returned should be high if the state is good for X and low if the state is good for O.

   A portion (approximately 20 points) of your grade for Part I will depend on how well your staticEval function works.

Here is the starter code for this assignment. In addition, here is the GameMaster.py file that should be used, instead of RunKInARow.

The following is the representation of the initial board in a KinARow game called "5 in a Row on 7-by-7 board with Corners Forbidden".

              [[['-',' ',' ',' ',' ',' ','-'],
                [' ',' ',' ',' ',' ',' ',' '],
                [' ',' ',' ',' ',' ',' ',' '],
                [' ',' ',' ',' ',' ',' ',' '],
                [' ',' ',' ',' ',' ',' ',' '],
                [' ',' ',' ',' ',' ',' ',' '],
                ['-',' ',' ',' ',' ',' ','-']], "X"]