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 an "utterance" feature. The assignment has two parts: creating your agent and engaging your agent in a first round of competition play.

• (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 software 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, '-'.
• (d). In some variations, there may also be occurrences of 'X' and or 'O' on the initial state as "handicaps."

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 makeMoveAndTalk function below.)

Your program must include the following functions, all defined in your main file. You can have helper functions if you like. Please keep all the functions required by your player either in just one Python file or a small number of files that use the following specific naming rules: Name your main (and what might be your only) 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. Any other files may have any valid Python file name, provided that the name starts with your UWNetID. This will prevent naming conflicts between identifiers belonging to opposing players during matches.

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 makeMoveAndTalk. 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.". 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 debugging mode, which is relevant to the reporting of alpha and beta cutoffs as described below. Another is to disqualify any program whose author believes that the program is NOT ready to play a particular version of the game. For example, if your program can play K in a row for K=3 but not K>3, for some reason, then your program might return "I can't handle K>3." instead of "OK". The third purpose is to offer your agent an opportunity to do any initialization of tables or other structures without the clock running. If the match is a timed match, then it might be nice to have free time for setting up for, say, Zobrist hashing, if you are using that.
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. (Turning this one in is optional. We will give partial credit for this one in case makeMoveAndTalk does not work.)

   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 Assignment 2. Some testing code is available for this function. 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. makeMoveAndTalk. Implement a function "makeMoveAndTalk(state, lastUtterance)" that returns a list of length 2 of the form [newState, newUtterance]. This function must return a legal new state. The state should be one of the elements on the list created by successors(state), though you don't have to use the successors function in this. Your new state just has to be a legal successor to the given state. The newUtterance for makeMoveAndTalk should be a string that (a) answers any question in lastUtterance, and that (b) reflects your player's personality. It might or might not reflect the state of the game (but it should, at least much of the time).
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.

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 the utterance does not need to mention anything about alpha or beta cutoffs. The makeMoveAndTalk function should return its answer within maxMillisecPerMove. You can assume this will never be less than 50 and will usually be around 1000 or more for tournament play. The utterance you return from makeMoveAndTalk must reflect both the personality of your player and, usually, 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." Here's an example of a display after an agent of this sort made its move in a game of Five in a Row on a 7 by 7 Board with Corners Forbidden.

Testing: We are providing two ways for you to test some of your code. One involves testing only your successors function. There are two files for this: 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 GroundTruth26.pyc computes the correct set of successors for this comparison. It is compiled for Python 2.6. Here is GroundTruth27.pyc compiled for Python 2.7.

The other way of testing your code is to upload your program to the tournament website and try competing. Here is the website:

K-in-a-row Tournament site.

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 makeMoveAndTalk), staticValue (same). In the event that your program does not compete, we may run this "stepping stone" function to give partial credit. staticValue, however, will be graded separately. The staff plans to grade your staticValue functions by importing your main file, calling your prepare() function, and then calling your staticValue() function on one more more legal states. This means that (a) both your prepare() and staticValue() functions should be defined in your main file, (b) neither of these functions should require importing other files, and (c) importing and running these functions should not cause anything to be printed out -- all results from the functions must be part of their legal return values.

Although your makeMoveAndTalk function must produce a new state and an utterance, we will not be grading the utterances until after the Nov. 5 versions are due. That will allow you more time to work on coming up with appropriate utterances. The utterances for the Oct. 29 version of your program can be as simple as a constant "Now it's your move."

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 respond to questions or comments and how they 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).