Implementation of Sprouts: A Graph Drawing Game

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10436876" target="_blank" >RIV/00216208:11320/21:10436876 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-030-92931-2_28" target="_blank" >https://doi.org/10.1007/978-3-030-92931-2_28</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-92931-2_28" target="_blank" >10.1007/978-3-030-92931-2_28</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Implementation of Sprouts: A Graph Drawing Game

Popis výsledku v původním jazyce

Sprouts is a two-player pencil-and-paper game invented by John Conway and Michael Paterson in 1967. In the game, the players take turns in joining dots by curves according to simple rules, until one player cannot make a move. The game of Sprouts is very popular and simple-looking, so it may come as a surprise that there are essentially no AI Sprouts players available. This lack of computer opponents is caused by the fact that the game hides a surprisingly high combinatorial complexity and implementing it involves fascinating programming challenges. We overcome all the implementation barriers and create the first user-friendly Sprouts application with a strong artificial intelligence after more than 50 years of the existence of the game. In particular, we combine results from the theory of nimbers with new methods based on Delaunay triangulations and crossing-preserving force-directed algorithms to develop an AI Sprouts player which plays a perfect game on~up~to~11~spots.

Název v anglickém jazyce

Implementation of Sprouts: A Graph Drawing Game

Popis výsledku anglicky

Sprouts is a two-player pencil-and-paper game invented by John Conway and Michael Paterson in 1967. In the game, the players take turns in joining dots by curves according to simple rules, until one player cannot make a move. The game of Sprouts is very popular and simple-looking, so it may come as a surprise that there are essentially no AI Sprouts players available. This lack of computer opponents is caused by the fact that the game hides a surprisingly high combinatorial complexity and implementing it involves fascinating programming challenges. We overcome all the implementation barriers and create the first user-friendly Sprouts application with a strong artificial intelligence after more than 50 years of the existence of the game. In particular, we combine results from the theory of nimbers with new methods based on Delaunay triangulations and crossing-preserving force-directed algorithms to develop an AI Sprouts player which plays a perfect game on~up~to~11~spots.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA21-32817S" target="_blank" >GA21-32817S: Algoritmické, strukturální a složitostní aspekty geometrických konfigurací</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Graph Drawing and Network Visualization

ISBN

978-3-030-92930-5

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

15

Strana od-do

391-405

Název nakladatele

Springer, Cham

Místo vydání

neuveden

Místo konání akce

Tubingen

Datum konání akce

14. 9. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—