Skip to content

Late filters: every check that works, works too late

A filter added to the row scan can save at most the bits its depth allows, and the checks that refute nearly all wrong boards only start to bite at depths 144 to 192, past the widest level of the tree (158). A perfect free cut at depth 144 would save 2.4 bits of the 134.4 the scan costs, so no late filter closes the gap. The ceiling table is derived arithmetic on a measured profile, not an experiment.

by Raphaël Anjou

conceptanalysismeasuredrefutedReduce the searchBacktrackingUpdated 2026-11-14
Reproducedeterministic: reproduces byte-for-bytereruns the searchBudget: Ceiling table: seconds. The level profile it reads took about 32 s per repetition at N = 1e6 particles.
Hardware & run
Native runCPU only
0.0089core-hours
Cores
1
CPU
10-core Apple laptop
Machine
Laptop; the ceiling script is stdlib Python and runs in seconds
Budget
Ceiling table: seconds. The level profile it reads took about 32 s per repetition at N = 1e6 particles.
Start
The ceiling table is deterministic given the committed profile file
Reproduce this result

deterministic: reproduces byte-for-byte

just experiments approach-pricing

Reprints the ceiling table (depths 52 to 158) from the committed level profile in seconds. It does not rerun the profile, the census tilt or the arc-consistency shares; those come from the two experiments linked under sources.

Keep exploring

Referenced by

Page sourceView as Markdown