Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>The source code from the <a href="https://github.com/qu1j0t3/fhourstones" rel="nofollow noreferrer">Fhourstones Benchmark</a> from John Tromp uses a fascinating algorithm for testing a connect four game for a win. The algorithm uses following <a href="http://en.wikipedia.org/wiki/Bitboard" rel="nofollow noreferrer">bitboard</a> representation of the game:</p> <pre><code>. . . . . . . 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 </code></pre> <p>There is one bitboard for the red player and one for the yellow player. <code>0</code> represents a empty cell, <code>1</code> 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 <code>0</code>.</p> <p>The algorithm is:</p> <pre class="lang-cpp prettyprint-override"><code>// return whether 'board' includes a win bool haswon(unsigned __int64 board) { unsigned __int64 y = board &amp; (board &gt;&gt; 6); if (y &amp; (y &gt;&gt; 2 * 6)) // check \ diagonal return true; y = board &amp; (board &gt;&gt; 7); if (y &amp; (y &gt;&gt; 2 * 7)) // check horizontal return true; y = board &amp; (board &gt;&gt; 8); if (y &amp; (y &gt;&gt; 2 * 8)) // check / diagonal return true; y = board &amp; (board &gt;&gt; 1); if (y &amp; (y &gt;&gt; 2)) // check vertical return true; return false; } </code></pre> <p>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 <a href="https://stackoverflow.com/questions/7044670/how-to-determine-game-end-in-tic-tac-toe/7046415#7046415">answer to the question "How to determine game end, in tic-tac-toe?"</a>.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload