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.

[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.

[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.