TRtromp·Apr 17, 2018
Bitboards also work fabulously on connect-4,
encoding a 7x6 position in 7x(6+1)=49 bits [1] and
allowing for a win test with 8 shifts/ands:
// return whether newboard includes a win
final boolean haswon(long newboard)
{
long y = newboard & (newboard>>HEIGHT);
if ((y & (y >> 2*HEIGHT)) != 0) // check diagonal \
return true;
y = newboard & (newboard>>H1);
if ((y & (y >> 2*H1)) != 0) // check horizontal -
return true;
y = newboard & (newboard>>H2); // check diagonal /
if ((y & (y >> 2*H2)) != 0)
return true;
y = newboard & (newboard>>1); // check vertical |
return (y & (y >> 2)) != 0;
}
Dominikus Herzberg offers a more detailed explanation [2] for the benefit of his students.
[1] http://tromp.github.io/c4/Connect4.java
[2] https://github.com/denkspuren/