  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.
