Implementation of Sprouts: a graph drawing game

DOI10.1007/978-3-030-92931-2_28arXiv2108.07671MaRDI QIDQ6375438FDOQ6375438

Publication date: 17 August 2021

Abstract: 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.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

This page was built for publication: Implementation of Sprouts: a graph drawing game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6375438)