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

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.