Research map / Probabilistic and scientific modeling / Molecules and proteins
Implicit Search via Discrete Diffusion: A Study on Chess
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DiffuSearch, a discrete-diffusion policy that internalizes future state-action prediction for implicit search in chess, outperforming searchless and MCTS-enhanced policies without explicit search at inference.
Problem
Policies trained by next-token prediction lack long-term planning and rely on explicit search (e.g., MCTS) with costly, error-prone value models; the question is whether a policy can learn to predict and use the future itself without explicit search at inference.
Approach
Train a small GPT-2-style decoder with full attention and discrete absorbing diffusion to jointly denoise the next action plus a future sequence of states and actions (S-ASA format) labeled by Stockfish 16, so that the best action is chosen from the jointly sampled future rather than by explicit tree search.
Key results
- DiffuSearch (100k games) reaches 48.66% action accuracy vs 36.58% for Transformer S-A, and 58.46% puzzle accuracy with 1995 Elo.
- With 10k games, DiffuSearch outperforms the 100-simulation MCTS Transformer by 14 points in action accuracy (41.31 vs 27.34) and 1728 vs 1186 Elo.
- Stockfish 16 oracle (0.05s) attains 2689 Elo and 99.10% puzzle accuracy, far above all learned policies.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace the one-step policy with DiffuSearch implicit search | Chess policy · Chess action test | Action accuracy: 19.2% | Helped |
| replace the MCTS-enhanced policy with DiffuSearch | Chess policy · Chess action test | Action accuracy: 14% | Helped |
| replace explicit search-based policies with DiffuSearch | Chess policy · Chess puzzles | Puzzle accuracy: 30% | Helped |
| replace the MCTS-enhanced policy with DiffuSearch | Chess policy · Chess tournament | Tournament Elo: 540 Elo | Helped |
| add future states to future-action modeling (ablation) | DiffuSearch S-AA · Chess, horizon 4 | Action accuracy: 15.07 -> 41.31 | Helped |
| add future states to S-AVAV future representation (ablation) | DiffuSearch S-AVAV · Chess, horizon 4 | Action accuracy: 17.63 -> 40.69 | Helped |
| add value tokens to the S-ASA future representation (ablation) | DiffuSearch · Chess, horizon 4 | Action accuracy | No clear effect |
| use random state-action sequences instead of Stockfish future supervision (ablation) | DiffuSearch S-ASA · Chess, 10k games | Action accuracy: 41.31 -> 22.69 | Hurt |
| use random actions with resulting states instead of Stockfish actions (ablation) | DiffuSearch S-ASA · Chess, 10k games | Action accuracy: 41.31 -> 39.47 | Hurt |
| replace diffusion with direct full-sequence prediction (ablation) | DiffuSearch S-ASA · Chess, 10k games | Action accuracy: 27.39 -> 20.61 | Hurt |
| replace discrete diffusion with Gaussian diffusion (ablation) | DiffuSearch S-ASA · Chess, 10k games | Action accuracy: 31.91 -> 41.31 | Hurt |
| use linear rather than reciprocal loss weighting in absorbing diffusion (ablation) | DiffuSearch S-ASA · Chess, 10k games | Action accuracy: 39.07 -> 41.31 | Helped |
Surprising findings
- Directly predicting the full future sequence without diffusion (Direct) lowers accuracy to 20.61%, below the autoregressive S-ASA variant, and future action-only prediction (S-AA) hurts DiffuSearch relative to the one-step policy.
- Random future actions with consistent world-model states give no gain over the no-future baseline, while random world+policy futures barely help (22.69 vs 22.10).
Limitations
- Relies on Stockfish as an oracle for future supervision; no self-play training.
- Deeper search is achieved by extending context length, and performance degrades for lookahead beyond the training horizon with the single RoPE model.
- Trained on a relatively small dataset (up to 100k games) compared with prior work using around 10M games.
Experimental setup
Datasets: Lichess games (February 2023) Lichess puzzles
Benchmarks: Lichess puzzles (10k, Elo 399-2867) held-out Lichess action test set (1k games)
Metrics: action accuracy puzzle accuracy tournament Elo (BayesElo)
Baselines: Transformer S-A Transformer S-V Transformer SA-V Transformer with 100 MCTS simulations Stockfish 16
Builds on: D3PM AlphaZero Multinomial diffusion RoPE
Closest papers by meaning
- Mastering Board Games by External and Internal Planning with Language Models (ICML 2025 · similarity 0.92)
- Amortized Planning with Large-Scale Transformers: A Case Study on Chess (NeurIPS 2024 · similarity 0.88)
- The Algorithm Is Not the Behavior: Learned Priors Override Look-Ahead in a Chess-Playing Neural Network (NeurIPS 2026 · similarity 0.88)
- Human-Aligned Chess With a Bit of Search (ICLR 2025 · similarity 0.86)
- Chess-World-Model: A 10M-Game Benchmark for Exact State Tracking from Chess Move Sequences (NeurIPS 2026 · similarity 0.86)
- Evidence of Learned Look-Ahead in a Chess-Playing Neural Network (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.