Searching for Primes: A Neural AlphaZero Approach to a Factoring Game
In the authors' words
We study a one-player token game on an board where tokens slide along diagonals or duplicate onto neighbouring ones to form a combinatorial rectangle . A conserved integer weight and a strict monovariant guarantee -length solutions, placing the game in . We prove that reaching a final position factors this -bit into two -bit factors that encode the rectangle's rows and columns. Consequently, solving the game for a balanced-semiprime target is equivalent to integer factoring. However, if the target rectangle is known, the solution reduces to two polynomial-time steps: a forced downward chip-flow and a -polynomial factorisation leveraging Cohn's theorem. The game's entire difficulty is thus isolated to the initial number-theoretic split. Supplying the popcounts of the factors as a promise preserves this asymptotic hardness but bounds the target search space. We exploit this constrained space using a learned policy/value network and an AlphaZero-style Monte-Carlo tree search, empirically probing the limits of neural look-ahead on a factoring-equivalent environment.
Appeared: Tuesday, September 22. arXiv. Preprint, not yet peer-reviewed.