nullprogram.com/blog/2022/10/12/
I’ve been reading Math Games with Bad Drawings, a great book
well-aligned to my interests. It’s given me a lot of new, interesting
programming puzzles to consider. The first to truly nerd snipe me was
Dandelions (full rules), an asymmetric paper-and-pencil game
invented by the book’s author, Ben Orlin. Just as with British Square two
years ago — and essentially following the same technique — I wrote a
program that explores the game tree sufficiently to play either side
perfectly, “solving” the game in its standard 5-by-5 configuration.
The source: dandelions.c
The game is played on a 5-by-5 grid where one player plays the dandelions,
the other plays the wind. Players alternate, dandelions placing flowers
and wind blowing in one of the eight directions, spreading seeds from all
flowers along the direction of the wind. Each side gets seven moves, and
the wind cannot blow in the same direction twice. The dandelions’ goal is
to fill the grid with seeds, and the wind’s goal is to prevent this.
Try playing a few rounds with a friend, and you will probably find that
dandelions is difficult, at least in your first games, as though it cannot
be won. However, my engine proves the opposite: The dandelions always
win with perfect play. In fact, it’s so lopsided that the dandelions’
first move is irrelevant. Every first move is winnable. If the dandelions
blunder, typically wind has one narrow chance to seize control, after
which wind probably wins with any (or almost any) move.
For reasons I’ll discuss later, I only solved the 5-by-5 game, and the
situation may be different for the 6-by-6 variant. Also, unlike British
Square, my engine does not exhaustively explore the entire game tree
because it’s far too large. Instead it does a minimax search to the bottom
of the tree and stops when it finds a branch where all leaves are wins for
the current player. Because of this, it cannot maximize the outcome —
winning as early as possible as dandelions or maximizing the number of
empty grid spaces as wind. I also can’t quantify the exact size of tree.
Like with British Square, my game engine only has a crude user interface
for interactively exploring the game tree. While you can “play” it in a
sense, it’s not intended to be played. It also takes a few seconds to
initially explore the game tree, so wait for the >> prompt.
Bitboard seeding
I used bitboards of course: a 25-bit bitboard for flowers, a 25-bit
bitboard for seeds, and an 8-bit set to track which directions the wind
has blown. It’s especially well-suited for this game since seeds can be
spread in parallel using bitwise operations. Shift the flower bitboard in
the direction of the wind four times, ORing it into the seeds bitboard
on each shift:
int wind;
uint32_t seeds, flowers;
flowers >>= wind; seeds |= flowers;
flowers >>= wind; seeds |= flowers;
flowers >>= wind; seeds |= flowers;
flowers >>= wind; seeds |= flowers;
Of course it’s a little more complicated than this. The flowers must be
masked to keep them from wrapping around the grid, and wind may require
shifting in the other direction. In order to “negative shift” I actually
use a rotation (notated with >>> below). Consider, to rotate an N-bit
integer left by R, one can right-rotate it by N-R — ex. on a 32-bit
integer, a left-rotate by 1 is the same as a right-rotate by 31. So for a
negative wind that goes in the other direction:
With such a “programmable shift” I can implement the bulk of the game
rules using a couple of tables and no branches:
// clockwise, east is zero
static int8_t rot[] = {-1, -6, -5, -4, +1, +6, +5, +4};
static uint32_t mask[] = {
0x0f7bdef, 0x007bdef, 0x00fffff, 0x00f7bde,
0x1ef7bde, 0x1ef7bc0, 0x1ffffe0, 0x0f7bde0
};
f &= mask[dir]; f >>>= rot[i] & 31; s |= f;
f &= mask[dir]; f >>>= rot[i] & 31; s |= f;
f &= mask[dir]; f >>>= rot[i] & 31; s |= f;
f &= mask[dir]; f >>>= rot[i] & 31; s |= f;
The masks clear out the column/row about to be shifted “out” so that it
doesn’t wrap around. Viewed in base-2, they’re 5-bit patterns repeated 5
times.
Bitboard packing and canonicalization
The entire game state is two 25-bit bitboards and an 8-bit set. That’s 58
bits, which fits in a 64-bit integer with bits to spare. How incredibly
convenient! So I represent the game state using a 64-bit integer, using a
packing like I did with British Square. The bottom 25 bits are the seeds,
the next 25 bits are the flowers, and the next 8 is the wind set.
000000 WWWWWWWW FFFFFFFFFFFFFFFFFFFFFFFFF SSSSSSSSSSSSSSSSSSSSSSSSS
Even more convenient, I could reuse my bitboard canonicalization code from
British Square, also a 5-by-5 grid packed in the same way, saving me the
trouble of working out all the bit sieves. I only had to figure out how to
transpose and flip the wind bitset. Turns out that’s pretty easy, too.
Here’s how I represent the 8 wind directions:
Flipping this vertically I get:
Unroll these to show how old maps onto new:
old: 01234567
new: 07654321
The new is just the old rotated and reversed. Transposition is the same
story, just a different rotation. I use a small lookup table to reverse
the bits, and then an 8-bit rotation. (See revrot.)
To determine how many moves have been made, popcount the flower bitboard
and wind bitset.
int moves = POPCOUNT64(g & 0x3fffffffe000000);
To test if dandelions have won:
int win = (g&0x1ffffff) == 0x1ffffff;
Since the plan is to store all the game states in a big hash table — an
MSI double hash in this case — I’d like to reserve the zero value
as a “null” board state. This lets me zero-initialize the hash table. To
do this, I invert the wind bitset such that a 1 indicates the direction is
still available. So the initial game state looks like this (in the real
program this is accounted for in the previously-discussed turn popcount):
#define GAME_INIT ((uint64_t)255 << 50)
The remaining 6 bits can be used to cache information about the rest of
tree under this game state, namely who wins from this position, and this
serves as the “value” in the hash table. Turns out the bitboards are
already noisy enough that a single xorshift makes for a great hash
function. The hash table, including hash function, is under a dozen lines
of code.
// Find the hash table slot for the given game state.
uint64_t *lookup(uint64_t *ht, uint64_t g)
{
uint64_t hash = g ^ g>>32;
size_t mask = (1L << HASHTAB_EXP) - 1;
size_t step = hash>>(64 - HASHTAB_EXP) | 1;
for (size_t i = hash;;) {
i = (i + step)&mask;
if (!ht[i] || ht[i]&0x3ffffffffffffff == g) {
return ht + i;
}
}
}
To explore a 6-by-6 grid I’d need to change my representation, which is
part of why I didn’t do it. I can’t fit two 36-bit bitboards in a 64-bit
integer, so I’d need to double my storage requirements, which are already
strained.
Computational limitations
Due to the way seeds spread, game states resulting from different moves
rarely converge back to a common state later in the tree, so the hash
table isn’t doing much deduplication. Exhaustively exploring the entire
game tree, even cutting it down to an 8th using canonicalization, requires
substantial computing resources, more than I personally have available for
this project. So I had to stop at the slightly weaker form, find a winning
branch rather than maximizing a “score.”
I configure the program to allocate 2GiB for the hash table, but if you
run just a few dozen games off the same table (same program instance),
each exploring different parts of the game tree, you’ll exhaust this
table. A 6-by-6 doubles the memory requirements just to represent the
game, but it also slows the search and substantially increases the width
of the tree, which grows 44% faster. I’m sure it can be done, but it’s
just beyond the resources available to me.
Dandelion Puzzles
As a side effect, I wrote a small routine to randomly play out games in
search for “mate-in-two”-style puzzles. The dandelions have two flowers to
place and can force a win with two specific placements — and only those
two placements — regardless of how the wind blows. Here are two of the
better ones, each involving a small trick that I won’t give away here
(note: arrowheads indicate directions wind can still blow):
There are a variety of potential single-player puzzles of this form.
- Cooperative: place a dandelion and pick the wind direction
- Avoidance: don’t seed a particular tile
- Hard ground: certain tiles can’t grow flowers (but still get seeded)
- Weeding: as wind, figure out which flower to remove before blowing
There could be a whole “crossword book” of such dandelion puzzles.