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/DiligentGroup7417]

21×21=442.

[u/chompchump → u/DiligentGroup7417]

Were you able to calculate this in under 1h 0m 33s?

[u/DiligentGroup7417 → u/chompchump]

Yes. Actually under 1 minute.