Synthesizing human-friendly optimal strategies in board games

Thomas Bolander, Jacob Pjetursson

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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 languageEnglish
Title of host publicationProceedings of 2020 IEEE Conference on Games
PublisherIEEE
Publication date2020
Pages112-119
ISBN (Print)9781728145334
DOIs
Publication statusPublished - 2020
Event2020 IEEE Conference on Games - Virtual event, Osaka, Japan
Duration: 24 Aug 202027 Aug 2020

Conference

Conference2020 IEEE Conference on Games
LocationVirtual event
CountryJapan
CityOsaka
Period24/08/202027/08/2020
Series2018 Ieee Conference on Computational Intelligence and Games (cig)
ISSN2325-4289

Fingerprint Dive into the research topics of 'Synthesizing human-friendly optimal strategies in board games'. Together they form a unique fingerprint.

Cite this