PNpncnmnp·Feb 25, 2024Submission
38 points · Open discussiondenkspuren
BitboardC4
OPEN SOURCE2018–2024
denkspuren / BitboardC4
BitboardC4
The Design of Bitboards for use in Connect Four
2Distinct people
5Mentions
0Explicit recommenders
65GitHub stars
What to know before exploring
What it is
The Design of Bitboards for use in Connect Four
GitHub
Where it is used
No documented product use has been verified yet.
What people are saying
No recommendation phrase was found in the indexed comments.
No classified warning is attached to this page. Read the discussions before treating silence as approval.
Also in these discussions
No other repository is repeatedly linked in the same discussions.
This week on Hacker News
Nov 7–Nov 14 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/14/2026, 5:04:57 PM UTC.
No direct repository links were found in the indexed HN discussions over the past seven days. Older discussions are available below.
Mentions over time
HN mentions by year5 dated mentions
Observed mentions: 2018-04-17 18:33:15 UTC to 2024-02-25 21:01:03 UTC.
Counts come from the repository’s dated source evidence. Index cutoff: 2026-11-02 08:16:59 UTC.
View mention counts and date ranges
| Period | Start (UTC) | End (exclusive, UTC) | Mentions | Submissions | Comments |
|---|---|---|---|---|---|
| 2018 | 2018-01-01 00:00:00 UTC | 2019-01-01 00:00:00 UTC | 1 | 0 | 1 |
| 2019 | 2019-01-01 00:00:00 UTC | 2020-01-01 00:00:00 UTC | 0 | 0 | 0 |
| 2020 | 2020-01-01 00:00:00 UTC | 2021-01-01 00:00:00 UTC | 0 | 0 | 0 |
| 2021 | 2021-01-01 00:00:00 UTC | 2022-01-01 00:00:00 UTC | 0 | 0 | 0 |
| 2022 | 2022-01-01 00:00:00 UTC | 2023-01-01 00:00:00 UTC | 1 | 0 | 1 |
| 2023 | 2023-01-01 00:00:00 UTC | 2024-01-01 00:00:00 UTC | 0 | 0 | 0 |
| 2024 | 2024-01-01 00:00:00 UTC | 2025-01-01 00:00:00 UTC | 3 | 2 | 1 |
What Hacker News says
5 sourcesGoing off on a bit of a tangent here (thought it might be interesting!) - I first came across this topic in one of Russ Cox's blog posts (https://research.swtch.com/tictactoe). In TAOCP Volume 4A, Knuth discusses how optimal tic-tac-toe moves can be represented using boolean logic.
I just went over the section again, and I'll do my best to break down his algorithm:
He starts by picturing 2 3x3 grids - one for the X’s and another for the O’s. This setup introduces 18 boolean variables - x1 to x9 for the X's, and o1 to o9 for the O's. I think this can be neatly represented as a bit array (see https://github.com/denkspuren/BitboardC4/blob/master/Bitboar...).
Now, creating a full-scale truth table for these 18 variables means we would be looking at 2^18, or 262,144 rows. However, it turns out only 4520 of those are legal inputs. So, the quest
Read the rest
ion becomes, how do we find patterns in this boolean chain to build our tic-tac-toe strategies.
Knuth simplifies it by considering only the following strategies -
(a.) winning - when putting an X in a cell wins the game - like when two cells in any line already have X's.
(b.) blocking - when putting an X in a cell stops the other player from winning - like when two cells in any line have O's.
(c.) forking - when putting an X in a cell opens up multiple winning moves - you store all the winning line possibilities (horizontal, vertical, and diagonal lines - all 9) in a set, and for each winning line (say {i, j, k}), you place an X on i, leave k empty, and see if a move on j creates two win chances.
(d.) defending - similar, when putting an X in a cell stops the other player from creating multiple win chances.
(e.) And just making any legal move - when a cell does not have an X or an O.
The priority order of moves follows the order above. There's also a bit of priority within the legal moves - like the middle spot is best since it's part of more winning lines, while the edges are the last choice.
As I am writing all this, I think it might not seem all that cool until you actually check out the boolean equations for yourself! Pretty neat stuff.
In the game of Connect-4, bit twiddling allows amazing efficiency in board representation, board hashing, and win detection [1].
[1] https://github.com/denkspuren/BitboardC4/blob/master/Bitboar...
In Bit Twiddling Hacks (2005)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/