Expected Work Search: Combining Win Rate and Proof Size Estimation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909196564299776 |
|---|---|
| author | Randall, Owen Müller, Martin Wei, Ting Han Hayward, Ryan |
| author_facet | Randall, Owen Müller, Martin Wei, Ting Han Hayward, Ryan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_05594 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Expected Work Search: Combining Win Rate and Proof Size Estimation Randall, Owen Müller, Martin Wei, Ting Han Hayward, Ryan Artificial Intelligence 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. |
| title | Expected Work Search: Combining Win Rate and Proof Size Estimation |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2405.05594 |