algorithm to check a connect four field

by

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

More Related Contents:

  1. Algorithm to beat Strassen’s Algorithm
  2. What does O(log n) mean exactly?
  3. How do I search for a number in a 2d array sorted left to right and top to bottom?
  4. Generate an integer that is not among four billion given ones
  5. Find duplicates in an array, without using any extra space
  6. How to generate Sudoku boards with unique solutions
  7. Time complexity of Euclid’s Algorithm
  8. Quick sort Worst case
  9. How to round floats to integers while preserving their sum?
  10. Modulus power of big numbers
  11. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  12. Maximize the rectangular area under Histogram
  13. Fast algorithm implementation to sort very small list
  14. Compute social distance between two users
  15. Efficient algorithm for ordering different types of objects
  16. O(nlogn) Algorithm – Find three evenly spaced ones within binary string
  17. How to find two most distant points?
  18. Smooth spectrum for Mandelbrot Set rendering
  19. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  20. Sorting an array with minimal number of comparisons
  21. Determining if two line segments intersect? [duplicate]
  22. Write a program to find 100 largest numbers out of an array of 1 billion numbers
  23. How to find distance from the latitude and longitude of two locations?
  24. Algorithm for sampling without replacement?
  25. Bits counting algorithm (Brian Kernighan) in an integer time complexity
  26. Non-Recursive Merge Sort
  27. Reversing CRC32
  28. The intersection of all combinations of n sets
  29. Efficient algorithm for finding all maximal subsets
  30. Iterative tree walking

Leave a Comment