  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.
