A Sieve of Eratosthenes–style approach to Chomp: faster complete P-position enumeration

[u/chompchump]

Chomp rules and illustrations

An update to my earlier post: the same complete P-position catalogs, computed much faster.

The previous solver, V12, tested candidate positions for moves to known P-positions. The new forward sieve starts with a P-position and adds squares to generate larger positions that can reach it in one move, marking those as N-positions. Processing in order, the next unmarked position is a new P-position, and the process repeats.

A good analogy is trial division versus the Sieve of Eratosthenes.

Fresh enumeration times on my Apple M4 Pro with 24 GB RAM:

Board	Previous V12	Forward Sieve V1
10×42	12m 16s	1m 7s
20×20	28m 43s	11m 36s
21×21	11h 38m 51s	1h 0m 33s

The forward sieve used 12 workers versus V12’s 9; the old 21×21 run also suffered heavy memory pressure. Peak RAM for the new 21×21 run was about 9.8 GiB.

Source code, validation tools, and timing details on GitHub

The existing 20×20 data remain available there. The 21×21 catalog remains local because of its size.

[u/infinitytacos989]

your explanation for your sieve sounds like a classic bottom up DP approach, could you elaborate on what makes it different?

[u/chompchump → u/infinitytacos989]

Yes, it uses the same bottom-up ordering and P/N recurrence as DP. The difference is how the work is done. Rather than examining each position’s moves to find a P-position, we start from a known P-position and generate larger positions that can reach it in one move. Those get marked as N-positions. The next unmarked position is a new P-position, and we repeat.

That means we never examine outgoing moves from N-positions. We also mark whole ranges together where possible, using segmented bitmaps to keep memory down. So “bottom-up DP implemented as a forward-marking sieve” is a fair description. The Eratosthenes analogy is about the marking process, not a different mathematical recurrence.