4

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.

icepopo
  • 1,617
  • 4
  • 16
  • 13

4 Answers4

39

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.

Christian Ammer
  • 7,464
  • 6
  • 51
  • 108
  • Aren't you actually doing a `(row >> 1)` for y? Because `0011110 == 30` and `30 >> 8 == 0`. Whereas `30 >> 1 == 15 == 0001111` – naeg Sep 13 '12 at 13:24
  • 1
    @naeg: Actually the whole board gets shifted, to get one row shifted by one bit the whole board needs to be shifted by 8. Therefore I edited the anser because `row` is misleading. – Christian Ammer Sep 13 '12 at 14:36
  • Is it possible to modify this algorithm to find out whether a player has 3 or 2 coins in a row on the same board? My first thought was to check for 3 in a row one had to do the bit-shifting twice with 8 (instead of one with 2*8). Then you only shift that far to overlap 3 coins. And in order to check for 2 in a row simply do the bit-shifting once with 8. It seems to work like that when trying around, but the harder I try to understand that algorithm, the less I really understand. My goal is to use this algorithm in a heuristic function. – naeg Apr 11 '13 at 21:14
  • @naeg: Yes, the 2 and 3 coins modification would work the way you described it. It should also be possible to make a 5 or 6 coin modification. The easiest way to verify is to only shift 8 bits each step. The 2 * 8 bit shift in the algorithm above is because it is possible to split the 4 coin check. But if you shift more then 8 bits in one step, you have to be carful not to shift into the next column (that's the reason why the 8 bit shift was done before the 16 bit shift in the algorithm above). – Christian Ammer Apr 12 '13 at 06:56
  • 1
    The algorithm looks fantastic but I think the bitfield you described at first doesn't match your examples. When I right-bitshift by 8, the column with the most significant bits should be 0 (which is the rightmost column in your bitfield, not the leftmost). Still an awesome answer though. – Gerrit-K Jul 11 '14 at 06:28
  • 1
    Would this work for every kind of board? Like an 8x8 or 6x4 or 5x8? (connect four) – shinzou Apr 14 '16 at 06:47
4

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.

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.

Jens Schauder
  • 77,657
  • 34
  • 181
  • 348
  • One method is to use recursion to "move from" the starting position during the checks. –  Aug 12 '11 at 18:37
0

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

Tomas
  • 57,621
  • 49
  • 238
  • 373