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.

8
  • Do you want to check after many plays have already occurred, or check play by play?
    – PengOne
    Aug 11, 2011 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, 2011 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, 2011 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, 2011 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, 2011 at 9:07

3 Answers 3

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

5
  • 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, 2011 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. Sure you have no built in 64 bit integer data type, but the type long with unlimited precision should work. Aug 15, 2011 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, 2011 at 14:08
  • 2
    This is... simply AWESOME! :D
    – XDnl
    Apr 25, 2014 at 19:40
  • 1
    @ChristianAmmer Can you also determine how many "connections" are in a row?
    – voytek
    Oct 15, 2015 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.

2
  • 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, 2011 at 11:22
  • implemented your aglorithm and it really fits my need.
    – naeg
    Sep 2, 2011 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!

7
  • 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, 2011 at 21:48
  • I don't see how that answer is related to this question. Aug 11, 2011 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, 2011 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, 2011 at 21:59
  • @naeg, why bother with a string when you can just count up matching adjacent fields?
    – MSN
    Aug 11, 2011 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.