Implementation of Sprouts: A Graph Drawing Game
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Implementation of Sprouts: A Graph Drawing Game
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GA21-32817S" target="_blank" >GA21-32817S: Algorithmic, structural and complexity aspects of geometric configurations</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Graph Drawing and Network Visualization
ISBN
978-3-030-92930-5
ISSN
0302-9743
e-ISSN
1611-3349
Number of pages
15
Pages from-to
391-405
Publisher name
Springer, Cham
Place of publication
neuveden
Event location
Tubingen
Event date
Sep 14, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—