Your program will consist 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 to influence the succeeding play or to change the balance of advantage and disadvantage to the players.

In addition to being able to play the game, your program should make a comment in each move, as if participating in a dialog. Ideally, your program would 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.)

In the starter code, there is a file named agent_template.py You use this to get started writing your agent program. You'll rename this file according to the instructions. 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. Your program must include the following functions. You can have helper functions if you like.

1. prepare(initial_state, k, what_side_I_play, opponent_nickname). Your agent's prepare function will be called by the game master before a new game starts. This function takes four arguments and it should "remember" these values for the game that is about to be played. (However, if your agent is in a match with itself, this prepare method will be called twice. In this case, be careful not to let the agent assume it is playing 'O' on both turns.)

   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.

   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". However, the prepare function 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 a key function, and it will be called by the game-master program to communicate with your agent whenever it is your agent's turn to play.

   The makeMove function should return a list of the form [[move, newState], newRemark]. The move is a data item describing the chosen move. 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 might 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.

   Extra credit is available for newRemark implementations that take various itmes into consideration. See the Extra Credit guidelines towards the end of this page.

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.

6. minimax(state, depthRemaining, pruning=False, alpha=None, beta=None, zHashing=None). This function will be called by makeMove, but it could also be called by code that you write to test the optional extra-credit features. If you are not doing those, just leave the parameters pruning, alpha, beta, and zHashing as they are in the function header, and forget about them.

   The minimax function should be recursive. The parameter depthRemaining will be an integer that gets reduced by one in recursive calls. At the beginning of the body of , your code should check if depthRemaining is zero, and if so, it should call staticEval and not call itself recursively. minimax should return a list whose first element is the numeric value of state as computed by your method. The remaining elements of the list are optional and up to you. For example, you could return information relevant to determining the newRemark string. Your minimax can also perform side effects such as updating counts of calls to your staticEval function, or anything else you need to make your agent work effectively. You could also pass back information about the best move found from state

Follow the directions below to run your K-in-a-Row demonstration game.

Using the TimedGameMaster.py program to run a K-in-a-Row match, create a transcript of a game between your agent and the agent of another student in the class. Set up the match so that your agent plays 'X' and your opponent plays 'O'. Use the following game instance for your match. Your player should play X and the opponent should play O. For this run, you should set a time limit of 1.00 seconds per move (e.g., by editing the appropriate line of code near the top of the TimedGameMaster.py program).

Here is the starter code for this assignment.

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"]

The TimedGameMaster program will automatically generate an HTML file containing a formatted game transcript of your game. Turn in that HTML file. (For an example of such a file, click here.

There are 3 ways to get extra credit in Part I and 3 ways to get extra credit in Part II for a max of 30 points of extra credit.

in Part I:

• A. Implement alpha-beta cutoffs. If you choose this, include a means in your code to turn on or turn off the use of alpha-beta pruning. Then use this capability to run a MakeMove example with it off, and then with it on, in each case counting the number of calls made to your static evaluation function. Be sure to use a fixed-depth search in the comparisons, say 4 ply.
• B. Implement Zobrist hashing. We are not planning to cover this in class, so this would require reading about the technique online or discussing it with the staff.
• C. Provide enhancements to your agent's utterance (newRemark) generation. The extra credit will be based on how well your agent's remarks meet these criteria. To get the extra credit, implement (1) and one, the other, or both, of (2) and (3) 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 is worth 3. A more thorough implementation that shows considertion for multiple features related to one of these two latter criteria is worth additional points. The maximum extra credit here is 5 points.

After your program is working, you may choose to take steps to qualify for the competition if you wish. To enter the competition, first your agent must qualify, and then you submit your evidence of qualification. For your agent to qualify, you must submit game transcripts for two games that meet the following criteria.

1. Each game must be between your agent and a different opponent. (So your agent competes against two other agents.) The submitted games may have your agent playing either X or O (your choice).
2. Your agent must be the winner of at least one of these games.
3. The two games must involve a version of K-in-a-Row in which (a) K is at least 5 and the board is at least 7 by 7, but it can be bigger if you wish.

Turn in both your code file(s) and your game-transcript file(s). Each game-transcript file should be the HTML file that is automatically created when you match up your player with an opponent. For your player file use your UWNetID to make the name have this form: [YourUWNetID]KInARow.py
If you are doing any of the extra credit items (A, B, C, or D), then also turn in your file ExtraCredit.txt that explains those special features of your agent and/or what opponent agents your submitted games involve.
If you wish to enter the competition, explain that in the ExtraCredit.txt file, and submit the additional qualifying game transcript.