2016 October 7,

CS 111: Assignment: Tic Tac Toe

In this assignment, you will write an artificial intelligence (AI) for the game Tic Tac Toe. You will submit a single Python file, ticTacToeAI.py, to the COURSES file server, just as you have in previous assignments. Your work is due at 11:59 on Tuesday night.

Here are some files that you will need. Download them all to a single directory on your computer.

• ticTacToeText.py provides a text interface to Tic Tac Toe. Run this file to try out a game. You will not be editing this file at all, but read it to understand how it works. Notice that it uses ticTacToeAI.py for its AI.
• ticTacToeSelf.py is just like ticTacToeText.py, except that it plays the AI against itself. In fact, it differs from ticTacToeText.py in only one line.
• ticTacToeTurtle.py provides a rudimentary graphical interface to Tic Tac Toe. Run this file to try out a game. You will not be editing this file at all, but skim it to get an idea of how it works. Notice that it uses the same ticTacToeAI.py for its AI.
• ticTacToeAI.py contains the AI. Read it carefully to understand how it works. Right now it is very primitive. You will edit this file to improve the function aiMove. This file must also contain the hasWon function. The rest of the file's content is up to you.

In class, we have discussed this rudimentary outline for the Tic Tac Toe AI:

1. If the AI can win on this move, then it does. Otherwise...
2. If the opponent can win on its next move, then the AI blocks that move. Otherwise...
3. The AI uses some other strategy to select its next move.

How can we implement the first step of the outline? Intuitively, we list the available cells of the board. Then, for each cell, we try it out. That is, we temporarily place our piece in that cell, and test whether we have won the game. If so, then that's a good move. If not, then try the next available cell. If there are no more cells available, then we can't win on this move.

How can we implement the second step of the outline? We mimic the first step. However, instead of testing whether our piece (X or O) is about to win, we test whether the opponent's piece (O or X) is about to win. If so, then we take that move away from the opponent.

The third step of the strategy is room for you to be creative. Your solution should be better than just moving randomly. Your code should contain comments that explain your ideas in English.

Test your code by running both the text-based and the turtle-based user interfaces with your AI. Also test your AI against itself.