Abstract
We present a tool for synthesizing and verifying optimal game playing strategies represented by compact fast-and-frugal trees, i.e., prioritized lists of strategic rules. The purpose of the tool is to create human-friendly optimal strategies for simple board games, e.g. for teaching a human player to play optimally, or to assess the difficulty of a given board game in terms of the length of the generated strategy. The tool supports arbitrary one-or two-player zero-sum games with perfect information specified through the game description language GDL within general game playing. When synthesizing a strategy, the game is initially solved, the solution is turned into a fast-and-frugal tree, and the tree is then minimized. We illustrate the use of the tool to synthesize compact optimal strategies for Tic-tac-toe, Nim, and Sim, which leads us to provide an even shorter optimal strategy for Tic-tac-toe than the well-known Simon & Newell strategy. Additionally, we have developed a visual tool enabling users to build and verify manually crafted fast-and-frugal strategies.
Original language | English |
---|---|
Title of host publication | Proceedings of 2020 IEEE Conference on Games |
Publisher | IEEE |
Publication date | 2020 |
Pages | 112-119 |
ISBN (Print) | 9781728145334 |
DOIs | |
Publication status | Published - 2020 |
Event | 2020 IEEE Conference on Games - Virtual event, Osaka, Japan Duration: 24 Aug 2020 → 27 Aug 2020 https://ieee-cog.org/2020/program |
Conference
Conference | 2020 IEEE Conference on Games |
---|---|
Location | Virtual event |
Country/Territory | Japan |
City | Osaka |
Period | 24/08/2020 → 27/08/2020 |
Internet address |