2012 April 7,
Carleton College, Spring 2012
Prof. Joshua R. Davis, , Goodsell 106B, x4473
In this assignment, you will write an artificial intelligence (AI) for the game Tic Tac Toe. That is, you will write a piece of Python code that can look at a Tic Tac Toe board and select a move to make. Your goal is to get your AI as good as you can, within reason. A perfectly skilled Tic Tac Toe player will never lose; she will always win (if her opponent makes a serious error) or draw (if her opponent makes no errors). This level of sophistication may be too ambitious, but you should try to approach it.
This problem is much bigger than the other problems we've encountered in this course, so we will talk through some of the solution together. In addition to practicing Python (conditionals, loops, lists, functions, etc.), you will practice some common problem-solving strategies. The two main strategies we'll employ are
You may work alone or with one partner. If you work with a partner, then your team should hand in one copy of the work, with both of your names on it. This assignment will be due Sunday at 5:00 PM. It will be submitted electronically.
Let's agree on a basic framework for the problem. A board will be represented in Python as a list of three lists, where each of the lists has length 3 and contains only the markers "O", "X", and " ". For example, here is a board:
board = [[" ", "X", "X"], ["O", "O", " "], [" ", "X", "O"]]
The first list represents the top row of the board, the second list the middle row, and the third list the bottom row. So, for example, board[1][2] is the marker at the end of the middle row, which in this example is " ".
The entire AI boils down to a single function, which we will call move. This function takes two inputs — a board and a player — examines the board from the point of view of that player, selects a move for that player to make, and returns that move as its output. More precisely:
Even more concretely, here is an example of how to write the move function:
def move(b, p):
if b[1][1] == " ":
return [1, 1]
elif b[0][2] == " ":
return [0, 2]
else:
return None
As required, this function takes in two inputs — a board b and a player p. And what does it do? If the middle cell is available, then the AI chooses it. If the middle cell is not available, then the AI chooses the top right cell. If that's not available, then the AI just gives up. This is obviously a terrible AI; it's just supposed to exemplify how move receives input and generates output. Writing a better move is your ultimate goal in this assignment.
Once you've written the move function, we can use it in numerous ways. Our default way is to have the AI play against itself, with us watching. But we can also write a text-based program, where a human plays against the AI. We can write a graphical version too. We can write a web version too. All of these interfaces interact with the same underlying Tic Tac Toe AI, as captured in the move function.
The move function is our way of making the problem "write a Tic Tac Toe AI" concrete. All we need to do is write this function! But writing this function is still a big problem. We need to break it down into smaller problems. Each of these subproblems will be represented by a different Python function, probably. That is, move will make use of several helper functions. Identifying the subproblems and writing their corresponding helper functions is a big part of this assignment.
I am supplying you with a Python file, tictactoe.py, that already contains a bunch of code. (Right-click or control-click that link, to save it to your computer.) You will add your own code to this file, and submit this file for grading electronically. So let's go over the code that's already in there.
The file begins with three lines of comments. In any programming language, a comment is a statement intended for a human reader, marked in a way so that the interpreter ignores it. A comment has no effect on the execution of the program at all, but it can make the program much easier to understand. In Python, any line that begins with a hash mark # is a comment.
Those first few lines of comments describe how the first function, printBoard, is supposed to work. They explain the purpose of printBoard, and explicitly lay out its input and output types, so that you can understand how to use the function. After printBoard comes the otherPlayer function, which we use to switch between the two players. You'll see it used later. These two functions work perfectly; you will not need to edit them.
Next come the hasWon and move functions. These two do not work correctly at all: hasWon never reports that anyone has won, and move considers only two moves before giving up. But don't start fixing these functions yet.
The last function in the file is computerVsComputer. This function runs the computer AI against itself by repeatedly calling the move function. On each move, it prints out the board, so that you can track how the game progresses. This function works perfectly; you will not need to edit it. But you do need to read it carefully, to understand how it works. Because this function is longer than our other functions, I have placed comments within the function, to describe its major steps. Each comment precedes the code that it describes, and is indented exactly as far as that code it describes.
After the computerVsComputer function comes a tiny bit of code at the end of the file. The comments explain its effect. If you run this file, then computerVsComputer is called upon, to give a demonstration of the AI. If you instead import this file into another program, then this code does not run. We'll see how that's useful later.
For now, run the program by entering python2 tictactoe.py in bash. The game plays for a bit, but then stops, because the AI makes an invalid move. Read through the computerVsComputer function again, and try to understand exactly what happened.
Your first task is to write hasWon. Fortunately, you already wrote a version of this code in Part C of the Introduction to Python tutorial. Enter that code into this file, and then make two changes:
Run the program again, to test whether hasWon seems to be working correctly.
As we discussed in class, there are a couple of obvious tactics, that a Tic Tac Toe player employs without even thinking.
If the player can win immediately by playing her marker in a particular space, then she plays it in that space. For example, when the O player sees the board board above, she immediately plays in the upper left corner and wins. She could also win by playing at the end of the middle row; it doesn't matter.
If the player cannot win immediately, she next wonders whether she is in danger of losing immediately. So she looks for places where her opponent can win immediately. For example, when the X player sees the board board above, she immediately plays in the upper left, to block O's impending win there. (Of course, O can still win in the second row. There's not much that poor X can do here.)
If the player cannot win or lose immediately, then she has to do some harder thinking. She needs to plan ahead a couple of moves, if she can. Ideally, she wants to set up a situation like board, where there are two ways to win. But it's difficult to think more than one move ahead, because what the player does depends on what her opponent does, and there are a lot of combinations to worry about.
How about this: If the player can win immediately, then she should. If she can block her opponent's win (or at least one of them), then she should. If neither of these apply, then she may move randomly. A Tic Tac Toe AI that behaves in this way is not perfect, but I'd say that it's basically competent.
Your second task is to write a move function that is basically competent in this way. Here's what I recommend.
Once you think you have a basically competent AI, test it thoroughly. You can run the AI against itself by simply executing tictactoe.py. You can play against the AI by downloading texttictactoe.py, putting it in the same folder as your tictactoe.py file, and running texttictactoe.py.
Your major task in this assignment is to improve upon your basically competent AI, so that it does not simply move randomly, but tries to make some better choices. This part of the assignment is wide open. Think about how you would play a Tic Tac Toe game, and try to figure out how to tell Python to play in that way. Don't try to play perfectly; just try to get some basics working. For example, it's a good idea to claim the center of the board, if you can. So implement that feature, and then test thoroughly. Then make another improvement, and test thoroughly.
When your program is complete — that is, you don't plan to add any new features, and you've tested the program thoroughly, and you've fixed every error you can find — there is still some polishing to do.
When your assignment is completely finished, tested, and polished, you will submit it electronically, following the directions at our Technical Issues page. Submit your work by 5:00 PM on Sunday. It will be graded according to these criteria: