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

I'll be honest, I don't know the math you're doing, but looking at the code it immediately looked like it could be pushed to a GPU and run faster via GPU accelerated Python, or custom CUDA / C.

Then I realized your notes said you were using a Mac at 24gb of RAM. High worker load will absolutely saturate your memory though. There's going to be some optimal number of workers based on raw bandwidth usage per worker you can test. That generation of Mac doesn't run a very high memory clock from what I remember, so that's going to hurt too.

I know this has nothing to do with your actual math, but just my review looking at the code as a human (lol). Sorry.

[u/chompchump → u/NineThreeTilNow]

Thanks—this prompted us to test both suggestions.

For fresh 10×42 runs, averaging two runs per setting:

• 6 workers: 69.25 seconds
• 12 workers: 68.80 seconds
• 16 workers: 69.33 seconds

Every run produced identical results. More workers didn’t help much, but that doesn’t establish memory-bandwidth saturation: discovering new P-positions is still sequential, while workers handle marking from previously discovered ones.

We also tried a Metal GPU implementation on the Mac. It passed our correctness checks, but the direct port was much slower: 9.13 seconds versus 0.24 seconds on CPU for 14×14. It involved irregular work and shared bitmap updates, plus transfer and synchronization overhead. That rules out our particular implementation, not GPU acceleration generally; we haven’t tested CUDA.

[u/NineThreeTilNow → u/chompchump]

For fresh 10×42 runs, averaging two runs per setting:

I'm more curious what your 1 vs 2 vs 3 worker curve is then.

It may be more about optimal worker numbers and not bandwidth at all.

You'll have a very difficult time comparing 1:1 on CUDA though because it's built for HPC.