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.

提出了一种新的游戏求解算法 Expected Work Search (EWS)，结合了蒙特卡洛树搜索中使用的胜率估计和证明数搜索中使用的证明大小估计。EWS 的搜索效率源于最小化一种新颖的预期工作概念，其预测解决一个位置所需的期望计算量。在围棋和六边形游戏中，EWS 的性能优于传统的求解算法。对于围棋，我们首次解决了常用的位置超级禁令规则集下的空 5x5 棋盘问题。对于六边形游戏，我们的算法在不到 4 分钟内解决了空 8x8 棋盘问题。实验证明，EWS 不仅在有大量领域特定知识的情况下取得成功，而且在没有大量领域特定知识的情况下也能成功。