algorithm to check a connect four field

Question

I'm wondering what's the best way to check for a winner on a connect four field.

I'm interested in what you guys think and whether there is some "well-known" algorithm for this sort of problems?

Solution:

I implemented Ardavan's hash-table solution in Python.

I let the algorithm run over every field once. The best checking time with my implementation was 0.047 ms, the worst 0.154 ms and the average 0.114 ms on my Intel(R) Core(TM)2 Duo CPU T9600 @ 2.80GHz. This is fast enough for my needs, and the algorithm seems neat to me.

Answer 1

The source code from the Fhourstones Benchmark from John Tromp uses a fascinating algorithm for testing a connect four game for a win. The algorithm uses following bitboard representation of the game:

.  .  .  .  .  .  .  TOP
5 12 19 26 33 40 47
4 11 18 25 32 39 46
3 10 17 24 31 38 45
2  9 16 23 30 37 44
1  8 15 22 29 36 43
0  7 14 21 28 35 42  BOTTOM

There is one bitboard for the red player and one for the yellow player. 0 represents a empty cell, 1 represents a filled cell. The bitboard is stored in an unsigned 64 bit integer variable. The bits 6, 13, 20, 27, 34, 41, >= 48 have to be 0.

The algorithm is:

// return whether 'board' includes a win
bool haswon(unsigned __int64 board)
{
    unsigned __int64 y = board & (board >> 6);
    if (y & (y >> 2 * 6))     // check \ diagonal
        return true;
    y = board & (board >> 7);
    if (y & (y >> 2 * 7))     // check horizontal
        return true;
    y = board & (board >> 8);
    if (y & (y >> 2 * 8))     // check / diagonal
        return true;
    y = board & (board >> 1);
    if (y & (y >> 2))         // check vertical
        return true;
    return false;
}

You have to call the function for the bitboard of the player who did the last move. I try to explain the algorithm in my answer to the question "How to determine game end, in tic-tac-toe?".

Answer 2

Each cell can only attribute to a maximum number of 12 winning combinations. (4 horizontal, 4 vertical and 4 diagonal). Each combination would have 4 cells including the one under consideration. And these numbers are going to be much lower for the cells closer to the sides. So it would make sense to pre-compile these combinations and store a hash of hash of related cells which can make a single play a winner. This way after each cell is player you simply pull out the related combinations/cells to check if it's a winner.