2010 January 12 / j d a v i s @ c a r l e t o n . e d u

Assignment 4: Tic Tac Toe

The purpose of the assignment is to practice logic and writing Python functions. Specifically, you will write an artificial intelligence to play the game Tic Tac Toe. After you have completed the assignment, your artificial intelligence will be hooked up to a variety of user interfaces:

• computer-vs-computer text interface,
• human-vs-computer text interface,
• human-vs-computer graphical interface,
• and human-vs-computer web interface.
That is, your artificial intelligence will serve as a module for use by other programs. For this reason, it is especially important on this assignment that you write your code to specification. It must do exactly what is expected of it, or else the programs that use it will not work. You may complete the assignment with one partner, or alone if you prefer. Your work is due Saturday at 11:59 AM (midday).

In order to talk about the work to be done, let's lay out some terms. A board is an object representing the Tic Tac Toe board at some stage in the game. The board is a 3 x 3 grid of squares. Each square contains a player — either `'x'`, `'o'`, or `' '`. Of course, `'x'` and `'o'` represent the actual players of the game; the `' '` is used to mark squares where no player has moved yet. If the board is stored in a variable `b`, then here's how you access the individual squares in the board:

 `b[0][2]` `b[1][2]` `b[2][2]` `b[0][1]` `b[1][1]` `b[2][1]` `b[0][0]` `b[1][0]` `b[2][0]`

For example, to test whether player `'x'` is in the bottom right corner of the board `b`, you type

```if b[2][0] == 'x':
...
```

To put player `'o'` into the middle space of the board `b`, you type

```b[1][1] = 'o'
```

(The board is actually a list of lists. The players are actually strings. We'll talk about lists and strings in Python soon; for this assignment you need to know very little about them.)

Before continuing, download `tictactoe.py` to your computer (by right-clicking or control-clicking on that link and saving the file). It already contains some code that I have written. There are two incomplete functions, `hasWon()` and `nextBoard()`. Your job is to write these functions.

The function `hasWon()` takes in two inputs — a board `b` and a player `p` — and returns a Boolean indicating whether that player has won the game with that board. In the version I gave you, the function simply returns `True` all of the time; you need to fix this.

The function `nextBoard()` takes in two inputs — a board `b` and a player `p` — alters the board to reflect the next move by the player, and returns the board. For example, if the board looks like

 `' '` `' '` `' '` `' '` `'o'` `'x'` `'x'` `'o'` `' '`

and the player is `'x'`, then `nextBoard()` should alter the board to look like

 `' '` `'x'` `' '` `' '` `'o'` `'x'` `'x'` `'o'` `' '`

and return that board. You may assume that the player `p` is either `'x'` or `'o'`; `nextBoard()` will never be asked to make a move on behalf of the "extra" player `' '`. In the version I gave you, the function simply returns the board unaltered; you need to fix this.

This function is the essence of the artificial intelligence for Tic Tac Toe. It must recognize when the player in question is about to lose (as in the example above), and prevent the loss. It must recognize when the player in question is about to win, and seal the win. If the player in question is not going to win or lose immediately, then there is more flexibility in choosing what to do. I see two obvious algorithms for choosing a move in this case:

• Choose an empty square randomly.
• Choose the best empty square, based on the algorithm for winning Tic Tac Toe (which you can find on Wikipedia).
Either of these algorithms is acceptable to me, and will earn full credit.

Once you have written these functions, you can test them by running `tictactoe.py` as a program (i.e. typing `python tictactoe.py` in `bash`). This runs the demonstration code at the bottom of the `tictactoe.py` file. The demonstration has the artificial intelligence play for both players and prints out the board after each move.

Submit your work electronically, as usual. It will be graded according to these criteria:

• The function `hasWon()` works (3 points).
• The function `nextBoard()` works (3 points).
• The code is clean and well-commented (3 points).