Intelligent Tic Tac Toe

CPSC 120 Project #3— tic-tac-toe artificial intelligence
Introduction
In this project you will write a C++ program that implements an artificial intelligence player for the game of tic-tac-toe.
Background
Tic-tac-toe, also known as noughts & crosses, is a two player game played on a 3x3 square grid.
One player is called X and the other player is O. Players alternate placing their mark (X or O) in squares of the grid. The X player goes first. If a player makes a line of three horizontal, vertical, or diagonal marks, they win the game.
Your objective is to create a computer player that makes the best move it can.
Example 1: winning moves
One rule of thumb is that if you can win the game with one move, you should do that
immediately. For example, in the following board,
1
X X
O
O
X can win by taking the center cell in the top row:
X X X
O
O
Example 2: blocking moves
If there are no winning moves, but it’s possible to block the other player
from winning on their next turn, you need to block them to stay in the
game. Suppose the board looks like the following, and it is X’s turn:
O X
X O
X has no winning moves, and O could win by playing in the bottom row
and center column. X must play that position to prevent O from winning:
O X
X O
X
Representing the board in a computer
In order to write a program for tic-tac-toe, you need a way of representing
the game board using C++ variables. I recommend using one variable
2
for each of the 9 game cells. We can make things more convenient for
ourselves by representing cells as integers using the following convention:
Cell Contents Integer Code
empty 0
X 1
O 2
In the remainder of the handout, I will use the following notation to refer
to individual cells of the board:
A B C
D E F
G H I
Using this convention, X moved to cell B in Example 1. X moved to cell H
in Example 2.
You may use these letter codes to inspire your variable names, but this is
not required.
Limitation
Your computer player only needs to consider moves in the top row of the game
board. In other words, your program should consider moving into cells A, B, and C, but does not need to worry about other cells.
This limitation helps to keep the scope of the project within reason. Considering
moves to all 9 cells, using what we’ve covered so far, would require a very long and repetitive program.
After we cover arrays later in the semester, you might want to think about
how you handle the full 3 × 3 board concisely using arrays.
3
What to do
Your program should:
1. Prompt the user to type in the state of the board, represented by 9
integers between 0 and 2.
2. Print a picture of the board to standard output.
3. Decide on a move for the X player. Only cells A, B, and C need to be
considered.
4. Print out a description of X’s move, including the following pieces of
information:
• the cell X moves to, as a letter A-I
• if this move lets X win, say that
• otherwise, if this move blocks O from winning, say that
5. Print out a picture of the board, including X’s move.
For full credit, your player must use the following strategy:
1. If X has any winning move available, it must take it.
2. Otherwise, if X can block O from winning, X must do so.
3. Otherwise, X can pick any empty cell among A, B, or C.
In other words, your computer player must first try to win if possible. If it cannot win, it must then try to block if possible. If winning and blocking are both impossible, it may pick any cell in the first row (A–C) that does not already have an X or O.
If you have time and interest, you could extend the game in any of the following ways:
1. Make your player take clever moves when there are no obvious wins
or blocks. 4
2. Allow your player to move into cells D — I.
3. Play a full game, from start to finish, instead of a single move. All of these are optional.5 Sample input/output
In the following example, X takes a winning move:
En te r board s t a t e as 9 i n t e g e r s , 0−2:
1 1 0 2 0 0 0 2 0
Curren t board :
+−+−+−+
| 1 | 1 | 0 |
+−+−+−+
| 2 | 0 | 0 |
+−+−+−+
| 0 | 2 | 0 |
+−+−+−+
X moves to C to win !
New board :
+−+−+−+
| 1 | 1 | 1 |
+−+−+−+
| 2 | 0 | 0 |
+−+−+−+
| 0 | 2 | 0 |
+−+−+−+
6
Next, X has no winning moves, and takes a blocking move:
En te r board s t a t e as 9 i n t e g e r s , 0−2:
1 0 0 0 2 0 0 2 1
Curren t board :
+−+−+−+
| 1 | 0 | 0 |
+−+−+−+
| 0 | 2 | 0 |
+−+−+−+
| 0 | 2 | 1 |
+−+−+−+
X moves to B to block .
New board :
+−+−+−+
| 1 | 1 | 0 |
+−+−+−+
| 0 | 2 | 0 |
+−+−+−+
| 0 | 2 | 1 |
+−+−+−+
7
Finally, X has neither a winning nor blocking move, and may move to
either A or B; C is not empty. This computer player chooses B, although A
would’ve been a better choice.
En te r board s t a t e as 9 i n t e g e r s , 0−2:
0 0 2 0 0 0 1 0 0
Curren t board :
+−+−+−+
| 0 | 0 | 2 |
+−+−+−+
| 0 | 0 | 0 |
+−+−+−+
| 1 | 0 | 0 |
+−+−+−+
X moves to B
New board :
+−+−+−+
| 0 | 1 | 2 |
+−+−+−+
| 0 | 0 | 0 |
+−+−+−+
| 1 | 0 | 0 |
+−+−+−+
What to turn in
Your submission will be a written report, submitted electronically as a PDF
file through Moodle. Your report should include
1. Your C++ source code.
2. Your structure chart.
3. A the input and output for each of the three examples above:
(a) 1 1 0 2 0 0 0 2 0 (your program should choose C to win)
(b) 1 0 0 0 2 0 0 2 1 (your program should choose B to block)
(c) 0 0 2 0 0 0 1 0 0 (your program can choose A or B)
4. The input and output for different examples where...
(a) ...X must choose a winning move
(b) ...X must choose a blocking move
(c) ...X has neither a winning nor blocking move
8
(d) ...only one cell is empty, and X chooses it
There should be a total of 7 input/output dialogues.
The first page must include your name and a title. If you work as a pair,
list both partner’s names, and turn in only one submission.
Hints
Logic
To work properly, your program must first look for winning moves. If
none are found, your program must then look for blocking moves. If neither
of those kinds of moves are available, your program can look for open
space. It is important that these alternatives be considered in that order;
this kind of situation implies that your program will need to consider possibilities
in an if/else manner.
I think the most straightforward way of approaching this is to write a very
long chain of if/else if/else if/else if/.../else statements.
Each if or else if considers one potential move that X could make.
There may, however, be other ways of approaching this.
Printing out the board Conveniently, all three possible board states 0, 1, and 2, can be printed using exactly 1 character. So you can print a tidy grid using a single column
for each cell. You can create the horizontal lines using the minus character ’-’, the vertical lines using the pipe character ’|’, and the intersections using the plus
character ’+’.
The sample outputs are based on both these tips.
9
Printing out aspects of the move I have two suggestions about how to print out the description of X’s move. First, if you have an if statement that decides on a move, you could print out a message about that move between the curly braces (f and g) that define the statement’s body.
A second approach is to have an char variable for the cell X chooses, and bool variables for whether the move is a win, and whether it’s a block.
Then, after your program has decided where to move, you can have one set of print statements that use those variables.
Getting started
There are a lot of details to this project; too many to simply start programming without any forethought. Developing a structure chart before you start programming will be particularly important for this project.