Tic Tac Toe (C Plus Plus)
From LiteratePrograms
- Other implementations: C++ | Python
This program is under development.
Please help to debug it. When debugging
is complete, remove the {{develop}} tag.
In this article we're going to implement a simple minimax algorithm with alpha-beta pruning, used in a game of tic-tac-toe.
Contents |
Position class
First, I will define the most important piece of our code, and that is the Position class. That is a class that represents a Tic-Tac-Toe position. Note that it contains all of the game-specific code, so replacing it is all you need to do to reuse this code for another game.
Basic methods
Before defining the class, we need a header to prototype it as we go along. This header will be included in all the files of our program.
<<tic.h>>= #ifndef TIC_H #define TIC_H constant definitions Position class prototype utility functions #endif
The preprocessor lines are a safeguard so this header won't get included twice. I've also indicated what are the general things our header should contain. Let's start:
<<constant definitions>>= enum piece {O = -1, EMPTY, X};
To enhance readability. Whenever a space is occupied by an "x" it's represented by value X, etc.
Now let's get to writing the Position class.
<<Position class prototype>>= class Position { private: piece board[9]; bool possible_moves[9];
This is the internal representation of a position. The board is stored as an array of 9 pieces. The board actually looks like this:
| |
board[0] | board[1] | board[2]
| |
----------------------------------
| |
board[3] | board[4] | board[5]
| |
----------------------------------
| |
board[6] | board[7] | board[8]
| |
The constructors for the class:
<<Position class prototype>>= public: Position(); // this creates an empty board Position(const Position &p); // copy constructor <<position.cpp>>= #include "tic.h" #include <iostream> Position::Position() { unsigned int i; for (i=0; i<9; i++) { board[i] = EMPTY; } } Position::Position(const Position& pos) { unsigned int i; for (i=0; i<9; i++){ board[i] = pos.board[i]; } }
Both constructors are pretty simple, actually. They only initialize the board array; the first sets all entries to empty and the second copies the board from the other position.
Next, we're going to write a getter and a setter for the board array, to preserve encapsulation:
<<Position class prototype>>= piece getSquare(const int square) const; // const as it doesn't modify this void setSquare(const int square, piece p); <<position.cpp>>= piece Position::getSquare(const int square) const { return board[square]; } void Position::setSquare(const int square, piece p) { board[square] = p; }
Iterating through possible moves
The tools I used to implement the iterating mechanism weren't the best possible and it may sound confusing, but it does work.
We use the possible_moves structure to store the moves we haven't looked at yet, and we iterate by picking the earliest move in that structure in each pass.
We need a function to reset the possible_moves structure. It should basically set to true all of the possible moves, i.e., the empty squares:
<<Position class prototype>>= void refreshPossibleMoves(); // updates possible_moves <<position.cpp>>= void Position::refreshPossibleMoves() { unsigned int i; for (i=0; i<9; i++){ if (board[i] == EMPTY){ possible_moves[i] = true; } else { possible_moves[i] = false; } } }
Next, we need a function that returns the next move and clears that move from the possible_moves structure, because we have already looked at it. Note that the return value of 0 indicates that we have already looked at all moves.
<<Position class prototype>>= int getNextMove(); // get square of next possible move <<position.cpp>>= int Position::getNextMove() { unsigned int i; for (i=0; i<9; i++){ if (possible_moves[i]) { possible_moves[i] = false; return (i+1); } } return 0; }
If the move iterating technique is not clear right now, when I use it it will probably be.
Outputting the board to the screen
Of course, we need a way to tell the user what the current state of the board is. For that I'm going to create a small utility function called piece_to_char. It returns the char that best corresponds to the actual piece (an int) on the board. This one isn't added to the header as we don't need it anywhere else.
<<position.cpp>>= char piece_to_char(int p) { if (p == EMPTY) return ' '; else if (p == X) return 'X'; else return 'O'; }
Now, for the actual print function. In this function we will create a new board, called print_board, that contains the same information as board, but with characters instead of ints. Then it's just a matter of printing the 3 rows of this new board.
<<Position class prototype>>= void print() const; // prints board to stdout <<position.cpp>>= void Position::print() const { char print_board[9]; unsigned int i; for (i=0; i<9; i++){ print_board[i] = piece_to_char(board[i]); } std::cout << print_board[0] << '|' << print_board[1] << '|' << print_board[2] << std::endl; std::cout << print_board[3] << '|' << print_board[4] << '|' << print_board[5] << std::endl; std::cout << print_board[6] << '|' << print_board[7] << '|' << print_board[8] << std::endl; }
Finding out about the state of the board
We need to have a way to know what is the state of the board -- either someone has won, it's a tie, or it's still undefined. It's logical to have the Position class give us that info. These methods probably need no explanation of what they do:
<<Position class prototype>>= bool isOver() const; // is game over? // isWin will return X or O depending on who won int isWin() const; // is the game won? int isTie() const; // is the game a tie?
Now we have to think about how to implement those methods. For the isWin() method we can just check: for each row of the possible winning rows, if the squares are occupied by the same piece (not the EMPTY value, of course!). But how are we going to know which are the winning rows? Simple: let's add them to the constant definitions. Then the isWin implementation follows.
<<constant definitions>>= int const winning_rows[][3] = {{0, 3, 6}, {1, 4, 7}, {2, 5, 8}, {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {0, 4, 8}, {2, 4, 6}}; <<position.cpp>>= int Position::isWin() const { unsigned int i, index1, index2, index3; for (i=0; i<8; i++){ index1 = winning_rows[i][0]; index2 = winning_rows[i][1]; index3 = winning_rows[i][2]; if (board[index1] == board[index2] && board[index2] == board[index3] && board[index1] != EMPTY) { return board[index1]; } } return 0; }
To check if there's a tie, it's enough to check if all squares are filled:
<<position.cpp>>= int Position::isTie() const { unsigned int i; for (i=0; i<9; i++){ if (board[i] == EMPTY) return 0; } return 2; }
The isOver() method is also very straightforward. Simply put, if it's a tie or if someone has won, then the game has ended.
<<position.cpp>>= bool Position::isOver() const { return (isWin() || isTie()); }
Making moves
Now, we need to make moves. To make moves, we need to decide who is to play, and we can do that based on the oddness/parity of the number of remaining squares. The following functions do just that:
<<Position class prototype>>= unsigned int countEmptySquares() const; // count how many empty squares there are piece toPlay() const; // who plays at this position? <<position.cpp>>= unsigned int Position::countEmptySquares() const { unsigned int i, depth; for (i=0; i<9; i++){ if (board[i] == EMPTY) depth++; } return depth; } piece Position::toPlay() const { unsigned count = countEmptySquares(); if (count & 1) return X; else return O; }
To finish up, let's use the toPlay() method to make the actual move methods: one to play at a square and one to clear a square:
<<Position class prototype>>= void play(int square); // play in square "square" void undo(int square); // clear square "square" <<position.cpp>>= void Position::play(int square) { board[square-1] = toPlay(); } void Position::undo(int square) { board[square-1] = EMPTY; }
Note the -1 in square-1. This is done to avoid the non-inituitiveness that results in using 0-based indexing, both for our players and for ourselves. It makes much more sense to label the board as
1|2|3 4|5|6 7|8|9
than
0|1|2 3|4|5 6|7|8
<<utility functions>>=
|
| Download code |