How to determine game end, in tic-tac-toe?

Question

I'm developing tic-tac-toe game, and I need algorithm to check when game ends(and who win). In 3x3 game I would check each possible win-situation(there is 8 capabilities). But in 7x7(needed 4 signs in a row or collumn, or diagonal)is a lot of possible win patterns.

Answer 1

While a very basic approach is to look at runs in all the directions from every single cell, here are an approach then only ever checks a cell in a single "line" once. A "line" is a row, column, or diagonal that can possibly win, like in a Vegas slot machine :)

1. For each "line", move to start of that "line" and;
2. Set counter to 0.
3. For each cell in the "line" (traversing the line in order):
   • If the cell is P1 and counter is >= 0, add one to counter
     • If counter = 4 then P1 wins.
   • If the cell is P1 and counter is negative, set counter to 0
   • If the cell is P2 and counter is <= 0, subtract one from counter
     • If counter = -4 then P2 wins
   • If the cell is P2 and counter is positive, set counter to 0

Important Edit: If the cell contains neither P1 or P2, reset counter to 0 (doh!). I omitted this trivial but required step. Otherwise "11-11" would be counted as a win.

The "lines" can be traversed given a starting point and row/column offset per iteration (e.g. start at (0,0) and advance (1,1) for longest diagonal from NW to SE). Diagonals with lengths less than 4 can avoid being checked entirely, of course.

Happy coding.

Answer 2

loop though all positions. For each position check the four fields down diagonal-down-right and right (always including the field itself). Put in apropriate checks to avoid blowing up you app when you are checking fields that don't exist.

Answer 3

If you are using a bitboard for each player, you can use bit shift operations to test a board for a win.

The bitboard would have following structure:

6 14 22 30 38 46 54
5 13 21 29 37 45 53
4 12 20 28 36 44 52
3 11 19 27 35 43 51
2 10 18 26 34 42 50
1  9 17 25 33 41 49
0  8 16 24 32 40 48

If the player occupies a position in the game board, then the associated bit would be 1 otherwise 0 (notice that bits 7, 15, 23, ... are 0). To check if the player has a winning board you could use following function:

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;
}

With the help of a example I will try to explain: The following bitboard of one player includes beside vertical and diagonal wins a winning combination in the first row.

0101010
1110111
0111011
1101110
0001000
1010101
0011110 ... four occupied positions --> winning board

The steps for the horizontal check are:

1. y = board & (board >> 8)

   0101010   0010101   0000000
   1110111   0111011   0110011
   0111011   0011101   0011001
   1101110 & 0110111 = 0100110
   0001000   0000100   0000000
   1010101   0101010   0000000
   0011110   0001111   0001110

2. y & (y >> 2 * 8)

   0000000   0000000   0000000
   0110011   0001100   0000000
   0011001   0000110   0000000
   0100110 & 0001001 = 0000000
   0000000   0000000   0000000
   0000000   0000000   0000000
   0001110   0000011   0000010

The horizontal check results in a board with one bit set, this means the board includes a win and the function returns true.

I have used a similar function to check a connect four game for a win. I saw this fascinating function in the sources to The Fhourstones Benchmark from John Tromp.

Answer 4

Simple. Make 4 for loops, for all rows, columns, increasing diagonals, decreasing diagonals. In each, test if there are 4 consecutive pieces.