Determining the winning condition for Tic-Tac-Toe

Question

I'm writing a tic-tac-toe game in C++ and now I found a function to check if a player has a winning board for a connect four game.

The function looks like this:

bool haswon(int64_t board)
{
    int64_t y = board & (board >> 7);
    if (y & (y >> 2 * 7)) // check \ diagonal
        return true;
    y = board & (board >> 8);
    if (y & (y >> 2 * 8)) // check horizontal -
        return true;
    y = board & (board >> 9);
    if (y & (y >> 2 * 9)) // check / diagonal
        return true;
    y = board & (board >> 1);
    if (y & (y >> 2))     // check vertical |
        return true;
    return false;
}

I would be looking for an explanation of the above function.

Then I could perhaps try to implement the same thing for my tic-tac-toe. I'm fairly OK with the bitwise operators

#include <iostream> 
#include <bitset> 

namespace tictactoe { 

    constexpr std::size_t N = 3;

    using board = std::bitset<N*N>;

    constexpr char NOUGHT = 'O'; 
    constexpr char CROSS = 'X';

    bool curr_move_noughts = true;

    board combined() { 
        return noughts | crosses;    // combined bit board for both players
    } 

}

Answer 1

The pure fact you don't understand this function should be a big warning sign not to implement your Tic-Tac-Toe winning test in a similar manner. If you do, you will probably not understand your own code in a few weeks any more.

Instead, use a two-dimensional array or vector, and some loops to check the winning conditions. And don't think too much about speed or memory space as long as you don't experience any significant, measurable bottlenecks.

Answer 2

Using bits to represent a Tic-Tac-Toe board is perfectly fine and is as easy and maintainable as using two dimensional array. Since there are only 8 possibilities for winning condition, you can just check the board against every cases.

1 0 0       0 1 0      0 0 1     1 1 1    0 0 0
1 0 0       0 1 0      0 0 1     0 0 0    1 1 1
1 0 0       0 1 0      0 0 1     0 0 0    0 0 0

0 0 0       1 0 0      0 0 1
0 0 0       0 1 0      0 1 0
1 1 1       0 0 1      1 0 0

To keep the clean-ness of the code, try to abstract the implementation of the board away from the your game logic. It is easier to change the board implementation later if you dislike the bitboard representation.

class Board
{
    private:
        uint32_t board;

    public:
        Board() { board = 0; }

        /* Check if there is any of our piece
           placed in this (x, y) location */
        bool Check(int x, int y) {
            return (board & (1 << y * 3 + x)) > 0;
        }

        /* Make a move in this (x, y) location */
        void Move(int x, int y) {
            board = board | (1 << y * 3 + x);
        }

        /* Check if we have won */
        bool IsWin()
        {
            return (board & 292) == 292 || (board & 146) == 146 ||
                   (board & 73) == 73 || (board & 448) == 448 ||
                   (board & 56) == 56 || (board & 7) == 7 ||
                   (board & 273) == 273 || (board & 84) == 84;
        }
};

Keep two boards for player 1 and player2.

Board player1;
Board player2;

Check if (x, y) location is unoccupied

if (!player1.Check(x, y) && !player2.Check(x, y)) {
    // unoccupied slot
}

Check if player 1 has won

if (player1.isWin()) {
    // player 1 has won.
}

Answer 3

Think of it as a binary number where all the ones are your pieces. To simplify my explanation, I'll just consider one row of 8. The rest all work similarly.

Consider a winning case of four in a row: 11110000. board && (board >> 1) gives you 1110000, which is all the ones with a one immediately adjacent to the left. Doing this again with y & (y >> 2) does the same check, but for two to the left. The combination of the two yields a non-zero value when you get four in a row.

The other offsets do the same thing, but wrapping to the next row instead of checking immediately adjacent squares. 8 wraps immediately below, 7 wraps below but one to the left, and 9 wraps below but one to the right.

This happens to be possible because of the powers of two involved. In a 3x3 grid you can't do something similar. You can use it to check for two in a row or four in a row, but not three.

That being said, even if the bit-shifting did work for tic-tac-toe, you shouldn't use it. Connect four has 4,531,985,219,092 possible games, so it makes sense to optimize this function as much as possible, to be able to compute a deeper tree in a reasonable time, even if that means sacrificing some readability. Tic-tac-toe has only 255,168 possible games, which means you can recalculate every combination on every move in a naïve way, and still have time to spare. In such cases, readability should be paramount.

There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.

—Turing award winner Tony Hoare

The reason you don't optimize when you don't have to is the bugs are no longer obvious. For example, the following board is incorrectly reported as a win:

10000001
00000010
00000100
00000000
00000000
00000000
00000000
00000000

Answer 4

Forget that connect 4 function. Apart from being unnecessarily cryptic, checking for a win in connect 4 is more complex than in tac-tac-toe.

In tic-tac-toe there are eight lines to check for - three rows, three columns and two diagonals. The first thing I'm going to suggest is using a single-dimensional array for the board, so the array indexes are as follows...

+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 3 | 4 | 5 |
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+

The reason for using a two-dimensional array would be to make it easier to identify locations and easier to loop over them. In this case, I'm going to argue that because the board is so small, it's actually easier to avoid the two dimensions issue. I'm also going to avoid loops, at least for a first attempt, since the scale of the problem is small enough to allow that. So...

bool line_is_full (Board* p_board, char p_player, int p1, int p2, int p3)
{
  return (   (p_board [p1] == p_player)
          && (p_board [p2] == p_player)
          && (p_board [p3] == p_player));
}

bool board_has_win (Board* p_board, char p_player)
{
  return (   line_is_full (p_board, p_player, 0, 1, 2)
          || line_is_full (p_board, p_player, 3, 4, 5)
          || line_is_full (p_board, p_player, 6, 7, 8)

          || line_is_full (p_board, p_player, 0, 3, 6)
          || line_is_full (p_board, p_player, 1, 4, 7)
          || line_is_full (p_board, p_player, 2, 5, 8)

          || line_is_full (p_board, p_player, 0, 4, 8)

          || line_is_full (p_board, p_player, 2, 4, 6));
}

Only checking for one player winning is valid because the only player you need to check for is the player who has just made a move. I'm also not checking for a draw here - just keep count of how many moves have been made to handle that.

Obvious things that could be improved...

1. The blank lines in board_has_win are there to emphasize groups of similar cases. You could have a loop over the three rows and a loop over the three columns.

2. Alternatively, board_has_win is an "unwound" loop over all eight lines. There are several ways this could be expressed using a loop. Possibly the most sensible is to have a data table (giving the three cell numbers for each of the eight lines), so you can directly loop over the eight lines.

3. line_is_full could obviously be rewritten as a loop over the three cells if only those cells were passed as an array.

4. Alternatively, for each line (given the way I've specified them), (p2-p1) == (p3-p2) - there's a constant stepping distance between cells. Also (p1+p3)/2 == p2 - the position of the middle cell is the average of the two end cells. That means given any two cells (provided you know which two) you can determine the first and the stepping distance and loop over all three.

Personally I'd ignore points 3 and 4 - having a loop rather than three cases isn't really worth even that small amount of extra complexity. I'd probably focus on point 2 - that table of cell-numbers for each row could have other uses in the program.

Here's a tip I think I first saw back in ye olden days when computer magazines would print listings in BASIC. Each of the lines has three cells. What happens if you assign O the value 1 and X the value 4 (and zero for empty)? Consider the total of the values for the three cells in a line - here's a table...

 0 .... All three cells empty
 1 .... One O, two empty cells
 2 .... Two Os, one empty cell
 3 .... Three Os - O wins

 4 .... One X, two empty cells
 5 .... One X, one O, one empty cell
 6 .... One X, two Os
 7 .... Impossible

 8 .... Two Xs, one empty cell
 9 .... Two Xs, one O
10 .... Impossible
11 .... Impossible

12 .... Three Xs - X wins
13+ ... Impossible

This is a kind of special-case hash table. This is useful not only for spotting a win but also for a very simple AI.