16

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.

animuson
  • 53,861
  • 28
  • 137
  • 147
naeg
  • 3,944
  • 3
  • 24
  • 29
  • Do you want to check after many plays have already occurred, or check play by play? – PengOne Aug 11 '11 at 21:38
  • I'm a bit unsure about your question, but I think since it's connect four you have to check after every turn, don't you? Maybe not in the first 6, but at least in the 7th round. – naeg Aug 11 '11 at 21:40
  • Yes, but checking as a piece is played is more constrained than checking the entire board after the game has ended. – PengOne Aug 11 '11 at 21:42
  • After reading the first answer, I understand what you mean. I guess the better approach would be turn by turn, instead of whole field over and over again. – naeg Aug 11 '11 at 21:47
  • The algorithm, in this case, depends a lot on the language you use. If your language supports it, you would use: pattern matching, list comprehensions, rotations, pointers, etc. – Eelvex Aug 12 '11 at 09:07
  • It's not correct if you join all the fields into one string. For example: row 1 = xxooo , row 2 = ooxxx. When you concatenate them, we have xxoooooxx, which contain ooooo :D – Chan Le Aug 12 '11 at 11:18
  • I may was a bit unclear. With "join all fields" I meant joining each cell of a row, which would e.g. result in "xxxoooo" – naeg Aug 12 '11 at 11:25
  • @naeg Could you provide the answer please? – N2M Jul 15 '21 at 11:51

3 Answers3

28

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?".

Community
  • 1
  • 1
Christian Ammer
  • 7,464
  • 6
  • 51
  • 108
  • That algorithm is great, but since I'll be using Python, and I don't want to use Cython or something similiar for now, it's not the way to go for me. +1 anyway, it's extremely efficient! – naeg Aug 15 '11 at 16:58
  • I have not written Python code yet, but the algorithm should be applicable to any language with bit manipulation capabilities. I did a google search: The operators `>>, *, &` have the [same meaning in Python](http://docs.python.org/library/stdtypes.html#bit-string-operations-on-integer-types). Sure you have no built in 64 bit integer data type, but the type `long` with unlimited precision should work. – Christian Ammer Aug 15 '11 at 21:11
  • True, I never used/needed bit operations when programming Python. But the algorithm will most likely be far less performant in Python than in C or Assembly. Currently, I tend to use the hash table solution because it's more pythonic and clear to me. – naeg Aug 16 '11 at 14:08
  • 2
    This is... simply AWESOME! :D – XDnl Apr 25 '14 at 19:40
  • 1
    @ChristianAmmer Can you also determine how many "connections" are in a row? – voytek Oct 15 '15 at 16:29
7

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.

Ardavan
  • 1,896
  • 1
  • 13
  • 8
  • If I calculated that right, there are a total amount of 69 winning combinations. For each row there are 4 possible combinations, there are 6 rows => 24. For each column there are 3 possible combinations, there are 7 columns => 21. For each diagonal and anti-diagonal you have 12 combinations => 24. Resulting in a total of 69. Unsure whether storing all those in a hash table is more performant than checking them by hand? I guess hash tables are faster, but I think I have to try it out. – naeg Aug 12 '11 at 11:22
  • implemented your aglorithm and it really fits my need. – naeg Sep 02 '11 at 12:04
1

This is related to this question: How to find the winner of a tic-tac-toe game of any size?

The twist is the 7x6 board with 4 in a row winning rather than a NxN board with N in a row winning. But it is trivial to adapt the solution to NxN tic tac toe to connect 4.

EDIT: Actually, it's not quite trivial to adapt the other solution to this one. But you can get there with a little bit of extra work.

Store a count for each player for every row, column, diagonal and anti-diagonal that could ever have 4 pieces in a row. When that count hits 4 or more for either player, check to see if that row/column/diagonal/anti-diagonal has the four pieces in a row. If it does, that player wins!

Community
  • 1
  • 1
MSN
  • 53,214
  • 7
  • 75
  • 105
  • Just to make clear I understood that right: I create two counters(player1 and player2) for each row, column and diagonal. If a counter for one player reaches 4 on a row/column/diagonal he has won. Is that correct or can the solution be achieved even better? – naeg Aug 11 '11 at 21:48
  • I don't see how that answer is related to this question. – Karoly Horvath Aug 11 '11 at 21:50
  • @yi_H, it's almost related, but you are right; I should have added the additional check to see if four are actually in a row. – MSN Aug 11 '11 at 21:55
  • that check for four in row, is best achieved with my string approach? Or is there a better one? – naeg Aug 11 '11 at 21:59
  • @naeg, why bother with a string when you can just count up matching adjacent fields? – MSN Aug 11 '11 at 22:00
  • becaue I already think in Python, and it would be elegant to do something like: `"oooo" in field[0]` (assume field[0] is e.g. the first row) – naeg Aug 11 '11 at 22:49
  • @naeg, if your definition of elegant is "I can write code without loops", then yes, it's elegant. – MSN Aug 11 '11 at 23:01