← Blog

Black Hole

Here are the rules for a simple pencil-and-paper game created by Walter Joris. I learned about it from a book called Math Games with Bad Drawings by Ben Orlin.

First, draw a pyramid made of 21 circles.

The two players take turns writing their own numbers, from 1 to 10 in order, in any empty spot. Here’s a finished game.

2456767459110183102398

After the second 10 is played, the last empty spot becomes the eponymous “Black Hole”. It sucks in any adjacent numbers and the players lose those points. The winner is the person with more points left.

In the game above, player 1 loses 11 points (1 + 10) and player 2 loses 12 points (2 + 10). That makes it 44 points for player 1 and 43 for player 2, so player 1 wins.

Orlin had this to say about the game’s strategy:

Simple as the game is, I’ve found it hard to develop strategic intuitions. You can’t “reserve” spots for your high numbers, or your opponent will simply fill them. Somehow, you must leave spots that your opponent doesn’t want to fill (perhaps because they’d protect your own numbers). But don’t leave too many spots like this, or one of them will spell your defeat.

That intrigued me, and the game itself seemed small enough that I decided to build an AI for it and get some intuition (these two goals didn’t actually turn out to go hand-in-hand).

First Try

My first naive approach was just to believe in the power of lots of training. The game has twenty-one cells, so I gave a small neural network twenty-one numbers (positive for one player’s pieces, negative for the other’s, zero for empty) and let reinforcement learning do the rest. At first, I didn’t even tell it which moves were legal; it just got penalized for playing on a filled cell.1 Surely it could deduce how everything works?

Even after adding action masking (so the model couldn’t make illegal moves), it was incredibly easy to beat. I wanted to give the model a decent opponent to train against, so I took a step back to what I knew and built a single-position solver. It used a basic minimax algorithm to pick the best move for the current player. The first version would take hours to pick a move for an empty board, but I was able to use the first version to pick moves once the board was almost full, starting at player 1’s “8”.

Over time, the performance improved, and eventually it was fast enough that a training opponent could use it from player 1’s “4” onward. That opponent was pretty slow, though.

I used the solver in training, and it helped a little, but after a few more rounds of training, I realized my model design was all wrong.

Second Try

My second approach acknowledged that the game is a grid and tried to give the model a little more help. The new model laid the board out like an image, with a separate layer for each piece number, and handed it to the kind of network that’s good at images.2 Later I also marked which pieces were already safe from the black hole.

It was a little better, but anyone who played it beat it easily. There isn’t much more to say, other than that I needed to do more research before I could make something that worked.

Saving Time

Black Hole has a lot of symmetry. If you have a strategy for a certain position, then you can apply that same strategy to any board that can rotate or flip into the same position.

The code needs a fixed rule for picking which version counts as the “real” board. It just needs to always pick the same one. The example rule below puts the pieces as close to the top as it can, then as far left as it can. Place a few numbers, press Standardize, and watch the board turn into that version.

Click empty cells to play moves, then press Standardize to turn the board into its standard version.

The other trick is that once a number has no empty cells next to it, its points are safe, so you can just add them to that player’s score and forget where they sit. Try it out below. Make a move that creates a safe cell and watch the value fly to its player’s score.

3546576P1 10P2 3
Already-locked pieces start banked (dimmed). Click an empty cell to play a move; any piece that becomes surrounded scores for its owner.

These two rules reduce the work during solving. Solving any position solves up to 5 others. The safe-piece rule doesn’t start helping until move 5.

Moves played Boards After symmetry After symmetry + safe pieces Reduction
1 21 5 5 4.2×
2 420 73 73 5.75×
3 7,980 1,333 1,333 6.0×
4 143,640 23,940 23,940 6.0×
5 2,441,880 406,980 406,920 6.0×
6 39,070,080 6,511,680 6,505,800 6.0×

Full Solve

I wanted to know if perfect Black Hole players would end their games in a draw or if one of the players had an advantage. I stopped working on neural networks and started working on finding the best move from any position in the game.

Fortunately, the minimax solver was fast enough to search through every move after player 1 had played their 4 (move 7).

To keep the first seven moves fast, we need to know the best move for 6,938,072 positions. That’s the total number of possible positions for every game with up to 6 pieces, after using symmetry to combine equivalent ones.

It’s a long story involving first writing a Go solver, then porting it to Rust, and eventually realizing that the last six moves didn’t need a search at all: they have a closed-form answer.3 After all that, I knew the best move for any position in the first 7 moves, along with the best score you can get against a perfect opponent.

Unfair Game?

As the solver worked its way through the positions, an interesting pattern started to appear: player 1 had the advantage. I couldn’t be sure until the solver finished running, but once it did, the result was clear. Player 1 can start off with any move they like. Corners, edges, and interior moves all win the game for player 1 as long as they make the right moves afterward.4 That may or may not surprise you, but it’s not true for all games. Checkers and tic-tac-toe both end in a draw if both sides play perfectly.

Here’s a small exploration of what this means. It starts with every unique starting move (remember, the other 16 moves can all be turned into one of these moves by flipping and rotating the board), then plays every unique player 2 move. Every move after that is the best possible move for each player.

I took this solver and used it to make Nightmare. Not only does it win, it makes the move that limits the other player’s options the most possible.

AlphaVoid

With that done, I went back to deep learning and did some reading about AlphaZero. I learned that it still uses search, like my minimax solver. But a different kind of search: Monte Carlo tree search (MCTS), guided by a neural network. Instead of searching the whole tree, the network suggests which moves look promising and who’s ahead, so the search spends its time on those branches. After up to 2,000 simulations, the algorithm picks the most promising move and makes it.

I created a new model called AlphaVoid, which learned its strategy by playing against itself.5 It’s now pretty hard to beat. Against the perfect minimax solver, it plays a perfect game about four times out of five, and when it slips, it usually gives up just a point.

You can see how each of the networks saw the game.

First try: one integer per cell, the signed piece value (player 1 positive, player 2 negative, 0 empty), in triangle order. The input to a 2×128 MLP.

2456764511323
02142536475-6607-48-59010111012-113014315016017-218-3190200
Cell 0 is the top of the triangle; then row by row, left to right.

AlphaVoid vs Nightmare

Why did I make AlphaVoid if Nightmare already plays perfectly? Aside from the fact that I was curious if I could do it, Nightmare needs a 97 MB opening book: 6.9 million solved positions, boiled down from about 3.4 GB of raw solver output.6 AlphaVoid’s whole network is 270 KB.7

They play differently as well. Nightmare goes for the biggest margin it can get,8 while AlphaVoid mostly cares about winning.9

Human Intuition

None of this work resulted in a great human strategy for winning. Analysis of Nightmare and AlphaVoid hasn’t yet revealed any patterns that make the game much easier for a person.

If you find a good strategy by playing against Nightmare or AlphaVoid, I’d love to hear about it.

Try It

Head over to Play Black Hole and try it out. You can play against the minimax solver (“Nightmare”) or AlphaVoid itself. To try and get a feel for the strategy, you can turn on hints or use the Review feature after a game.

Footnotes

  1. The observation was 21 integers, one per cell, holding the signed piece value (positive for player 1, negative for player 2). The model was a MaskablePPO (sb3-contrib) MLP policy with separate policy and value networks of two 128-unit hidden layers each. The only reward was the final margin, at the end of the game, and the opponent was a pool of earlier snapshots. Before action masking, an illegal move truncated the episode with a −0.5 reward. That lasted about an afternoon before I switched to masking, so the network only ever chooses among empty cells. ↩

  2. The triangle sat in the corner of a 6×6 grid as 23 binary planes: a one-hot encoding of the pieces (one plane per player and piece value, 20 in all), an empty-cell mask, an on-board mask, and a side-to-move plane. The network was three same-padded 3×3 convolutions (64, 128 and 128 channels, ReLU), flattened into a 256-unit fully connected layer shared by MaskablePPO’s policy and value heads. Like the first approach, each episode was played in one of the triangle’s six symmetries, chosen at random, with observations, actions and masks all mapped through it. The later version had 26 planes: pieces with no empty neighbors moved off the value planes into one binary “safe” plane per player, plus a constant plane holding the banked margin divided by 55. ↩

  3. The solver is alpha-beta minimax with a lock-free transposition table of packed 64-bit entries. Its key is a Zobrist hash maintained incrementally for all six orientations of the board, taking the minimum as the canonical key, with locked-in pieces hashed as a generic “safe” marker plus the banked score. The book was built with Google Cloud Batch on spot VMs. Porting the worker from Go to Rust made it 1.7× faster; the Rust worker solved all but 22 of the 10,173 ply-5 tasks, and every ply-6 task. Using the transposition table’s best move for move ordering, including from fail-low entries, saved another 21%. Bounds pruning based on the empty cells cut 8.6% of the nodes but cost more time than it saved, so I reverted it. The ply-5 layer (406,920 positions) took about 2,350 machine-hours. What made ply 6 practical was a closed-form solver for the last six plies: once 15 pieces are down, every remaining piece value is fixed, so the result can be computed directly from the six empty cells, with no board updates, hashing or table lookups. A benchmark position went from 118 s (500M nodes) to 2.8 s (15M), and the 6.5 million ply-6 positions took about 634 machine-hours. Later, for Nightmare’s live search, the table turned out to hurt from the 14th move on. Those subtrees are only one or two moves from the closed-form solver, so hashing six orientations and probing costs more than searching them again, and their entries (over 90% of all stores) evicted more valuable shallow ones. Skipping the table once 13 pieces are down cut its memory traffic by about 93%. ↩

  4. That’s specific to this board size. On a 5-row board (15 cells, each player placing 1 through 7), perfect play is a draw: all 15 first moves lead to a 0-point game. The site has that version too, against a perfect opponent. ↩

  5. An AlphaZero-style loop from random initialization, with no opening book or human games. The only labels that don’t come from its own games are exact values for positions with 6 or fewer empty cells, computed by brute force from the rules. Network: three 3×3 convolutions (48 channels, ReLU, no normalization) over the triangle laid in a 6×6 grid; a 1×1-convolution policy head with one logit per cell, masked to legal moves; and a value head (1×1 convolution to 8 channels, a 48-unit fully connected layer, tanh) predicting the mover’s tanh(margin / 2). About 68k parameters, 272 KB as float32. Input: 28 planes from the mover’s point of view: one-hot planes for each player’s pieces that are still exposed (10 values each), empty and on-board masks, seat, next piece value, binary locked-in planes for each side, a signed plane of exposed piece values, and the mover’s banked score. Search: PUCT (c = 1.6) with MCTS-Solver proof propagation, proven-child pruning, first-play urgency of parent Q − 0.2, and a cache of network evaluations shared across transpositions. Self-play: 45 generations of 2,000 games (90,000 games, 1.8M positions) with playout-cap randomization: a quarter of moves get a 200-simulation search with Dirichlet root noise (α = 0.8, ε = 0.25) and record a policy target, the rest a 50-simulation search that only records value. The first 6 plies are sampled from the root visit distribution (temperature 1) for opening diversity; after that, the search’s choice is played (the most-visited move, or a proven-optimal one). Value targets are the final margin. Training: a sliding window of the last 400k positions, each sampled about 4 times with a random rotation or reflection; policy cross-entropy against the visit distribution plus value MSE; AdamW (batch 512, weight decay 1e-4) at a learning rate of 2e-3, stepped down to 5e-4 at generation 26 and 1e-4 at generation 36. On the site: 2,000 simulations per move, capped at 5 seconds, with no solver except at the last empty cell. ↩

  6. The web book is a compact binary format: one record per canonical position (symmetry-reduced, with locked-in pieces folded into the banked score), holding a 4-bit exact value for every legal move. Records are sharded by the low bits of the position hash into about 4,400 files of roughly 22 KB, and the browser fetches only the shards a game reaches. ↩

  7. Both bots run in the same Go solver compiled to WebAssembly: 4.2 MB, 1.5 MB gzipped. It holds Nightmare’s exact endgame search and AlphaVoid’s search, with the network weights embedded and a hand-written forward pass. ↩

  8. For the first seven moves Nightmare reads exact move values from the opening book. From move 8 it runs an exact alpha-beta search in the browser, with a transposition table keyed on a symmetry-canonical Zobrist hash (skipped from ply 13 on, where hashing costs more than it saves) and a closed-form evaluation of the last six plies. In the opening, among equally good moves it plays the one that leaves the opponent the fewest replies that keep their best result. On a slow device it has time limits: after 10 seconds it settles for any move it has proven wins, and after 30 it plays its best move so far. ↩

  9. AlphaVoid’s value head is trained on tanh(margin / 2) targets. That makes a 1-point win worth 0.46, a 2-point win 0.76, a 3-point win 0.91 and a 6-point win 0.995 (losses are the same, negated). Turning a draw into a win, or a 1-point win into a 2-point win, matters a lot; points beyond that barely register. ↩