Glop is a software developed to compute the winning strategies of combinatorial games. The current 2.2 version, released on October 21st 2011, is able to compute the winning strategies of three games: Sprouts, Cram, and Dots and Boxes.
We provide on this site the source code and binaries of Glop, along with our databases of results.
-
-
-
-
Older versions, information about compiling the source code :
download
-
We have obtained the following computation records with Glop:
October 2011: score of Dots-and-Boxes 4×5 icelandic board and 5×5 swedish board.
February 2011: outcome of Sprouts up to 44 spots and misère Sprouts up to 20 spots.
August 2010: outcome of the 7×7 Cram board, nimber of the 5×8 Cram board.
August 2009: outcome of misère Sprouts with 17 spots.
November 2008: Glop is the first program able to compute Sprouts positions on a Torus or a Klein Bottle.
April 2007: outcome of Sprouts up to 32 spots, and some values up to 47 spots.
All the computed values for Sprouts support the conjecture of Applegate, Jacobson and Sleator : in the n-spot game, the first player loses if and only if n is 0, 1 or 2 modulo 6.
More details can be found on the page of records.
We have released the following articles about Glop and our work on combinatorial games:
Nimbers are inevitable, released in August 2010. We prove a simple and powerful theorem: from the proof tree for the outcome of a sum of impartial games, it is possible to deduce the nimber of one component. It implies that in some way nimbers are inevitable, even when trying to compute outcomes, and justifies the efficiency of the algorithms detailed at the end of the article. Finally, we detail the results obtained on two impartial games, Sprouts and Cram.
-
Sprouts game on compact surfaces, released in November 2008, updated in March 2009. We detail the theory needed to play Sprouts on compact surfaces (like a Torus, a projective plane, a Klein Botttle ...), and how we have extended Glop in order to compute the outcome of Sprouts positions on any compact surface.
Computer analysis of Sprouts with nimbers. First released in April 2007 under the title
A further computer analysis of Sprouts. Updated and released on arxiv under the new title in August 2010. It contains details about the representation of Sprouts positions, the algorithms based on the central idea of nimbers, and a description of some interesting features of the first version of Glop, like drawing the proof tree or interacting in real-time with the computation.
Here is our Ph.D. dissertation (in french) : Méthodes algorithmiques et programme modulaire pour la résolution des jeux combinatoires (preview version of october 2011).
Glop is an open source free software, distributed under licence GPL v.2.
It was developed with :
C++ language for program’s main part.
Qt4 library for the graphical interface.
Subversion for revision control of the source code.
-
MinGW for compilation on Windows platform.
UPX to compress binaries.
-
Supported OS : Linux, Windows.