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:

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:


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:

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: