# Expected Work Search: Combining Win Rate and Proof Size Estimation

arXiv: https://arxiv.org/abs/2405.05594 · HTML: https://mlsanity.com/paper/2405.05594/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 34 references that are in the map.
- First posted on arXiv 9 May 2024.

## Builds on (most cited first, 3 of 3)

- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [A Novel Approach to Solving Goal-Achieving Problems for Board Games](https://mlsanity.com/paper/2112.02563/) (2021)
- [Proof Number Based Monte-Carlo Tree Search](https://mlsanity.com/paper/2303.09449/) (2023)

## Built on by (most cited first, 1 of 1)

- [Generalized Proof-Number Monte-Carlo Tree Search](https://mlsanity.com/paper/2506.13249/) (2025)

## Abstract (arXiv)

We propose Expected Work Search (EWS), a new game solving algorithm. EWS combines win rate estimation, as used in Monte Carlo Tree Search, with proof size estimation, as used in Proof Number Search. The search efficiency of EWS stems from minimizing a novel notion of Expected Work, which predicts the expected computation required to solve a position. EWS outperforms traditional solving algorithms on the games of Go and Hex. For Go, we present the first solution to the empty 5x5 board with the commonly used positional superko ruleset. For Hex, our algorithm solves the empty 8x8 board in under 4 minutes. Experiments show that EWS succeeds both with and without extensive domain-specific knowledge.