Summary of Expected Work Search: Combining Win Rate and Proof Size Estimation, by Owen Randall et al.
Expected Work Search: Combining Win Rate and Proof Size Estimation
by Owen Randall, Martin Müller, Ting Han Wei, Ryan Hayward
First submitted to arxiv on: 9 May 2024
Categories
- Main: Artificial Intelligence (cs.AI)
- Secondary: None
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary Medium Difficulty summary: This paper proposes a new game-solving algorithm called Expected Work Search (EWS), which combines win rate estimation from Monte Carlo Tree Search with proof size estimation from Proof Number Search. The algorithm’s search efficiency stems from minimizing the expected work required to solve a position, as predicted by a novel notion of Expected Work. EWS outperforms traditional solving algorithms on Go and Hex games, including solving the empty 5×5 Go board with positional superko ruleset for the first time. Additionally, it solves the empty 8×8 Hex board in under 4 minutes. The algorithm’s success is demonstrated both with and without extensive domain-specific knowledge. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary Low Difficulty summary: This paper presents a new way to solve games like chess and checkers. It’s called Expected Work Search (EWS). EWS uses two different methods to try to find the best move. One method helps guess how likely you are to win, while the other method tries to figure out how much work it will take to win. By combining these two methods, EWS is able to solve games more efficiently than other algorithms. In fact, it’s able to solve some games that other algorithms couldn’t even try to solve! This new algorithm has been tested on games like Go and Hex, and it works well both with or without prior knowledge of the game. |
