:glop-362x165.png

Combinatorial games solver

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.

Screenshots

Capture GLOP

Main computation records

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.

Articles and Ph.D. dissertation

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.
  • Analysis of misere Sprouts game with reduced canonical trees, released in August 2009. We explain the concept of reduced canonical tree, how to implement it efficiently, and how it can be used to accelerate Sprouts computation in the misere version.
  • 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).

Development tools

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.
  • Inkscape and The GIMP for images.
  • MinGW for compilation on Windows platform.
  • UPX to compress binaries.
  • Web site is powered by Dokuwiki and hosted by Tuxfamily.

Supported OS : Linux, Windows.

About us

Glop is developed by Julien Lemoine and Simon Viennot.

From 2008 to 2011, Glop was the subject of a PhD thesis in computer science under the direction of Jean-Paul Delahaye and Tristan Cazenave, at the Computer Science Laboratory of Lille 1 University.

You can contact us by Email :

Julien Lemoine Email
Simon Viennot Email

 
home.txt · Last modified: 2011/11/25 13:23 by yukito
 
Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki Hosted by TuxFamily