1. Introduction

Euclide is a software designed to solve exactly orthodox proofgames given a position and a number of halfmoves. It has not been designed to do anything else, where anything else even includes user-friendliness.

It is distributed as freeware in the hope that it will help proofgame composers check the validity of their problems, i.e. verify the uniqueness of the intended solution.

2. What's New

Version 1.10 adds new fetaures:

Version 0.99 has two minor improvements:

Version 0.95 showcases the following major improvements:

Version 0.92 had the following improvements:

The initial released version was labelled 0.90. Versions 0.91, 0.93, 0.94, 0.96, 0.97, 0.98, 1.00 and 1.01 are bug fix releases.

3. Setup

Execute euclide-setup.exe to install the software. A folder will be created in your startup menu with everything needed to run Euclide. You may choose the language of the software by executing one of the script in the Language Files subfolder. If installing over a previous version, the setup program will prompt you before overwriting the input file.

4. Creating an input file

Euclide accepts as input a text file containing one or more problems. Each problem is described by a diagram in Forsythe notation (FEN, also EPD) and a number of halfmoves, followed by optional contraints. Contraints are documented below, in section 4.1. Here is a simple example, my first proofgame :

Étienne Dupuis
Probleemblad, May-June 1999

The input file can contain comments or additional information. Euclide will ignore them as long as the next line does not start by a digit (or white spaces followed by a digit). Natch's input file can thus be feed to Euclide and Euclide's to Natch. However, note that Euclide does not perform strong typechecking; a position containing an error may be interpreted as correct and thus analyzed.

The input can be specified in one of four languages :

Language group King Queen Rook Bishop Knight Pawn
EnglishKQRBN, SP

4.1 User Defined Constraints

This section is intended for advanced users.

Starting with version 1.10 of Euclide, user constraints may be appended to the number of half moves. Constraints are strings describing piece's arrival, promotion or capture squares. For each strategy considered plausible by Euclide, a string describing the strategy is built, against which the constraints are mathced. This string description constains, for each of the 32 pieces, the following information: Piece[=Promoition]->Square[(Capture)], where Piece is the piece type and initial position, Promotion is the promotion type and square, Square is the piece's final square and Capture is the capturing piece type and initial square, followed by an 'x' and the captured piece's initial square. Examples:

For each user defined constraint prefixed with a '+' (plus) sign, the strategy will be skipped if the description does not contain the constraint, i.e. the constraint must be satisfied for the strategy to be considered. For each user defined constraint prefixed with a '-' (minus) sign, the strategy will be skipped if the description does contain the constraint, i.e. the constraint shall not be satisfied fot the strategy to be considered.

Here are some examples of constraints, for the same input:

Étienne Dupuis
Probleemblad, July-August
55 +Ph2=Rh8->h1
Étienne Dupuis
Probleemblad, July-August
55 +Ph2=Rh8->h1 -Pa2=Ra8->a8
Étienne Dupuis
Probleemblad, July-August
55 +Rh8->h1 -Ra8->a8
Note that the third example requires that a rook h8 ends on h1; it could be the black rook or a promoted white pawn, as Rh8->h1 is a substring of Ph2=Rh8->h1 and thus will match.

Although user constraints are a powerful feature, extreme care must be taken while using it. If too many or incorrect constraints are given, Euclide may fail to find a cook. In any case, a problem solved using user constraints should not be considered to be C+.

5. Running the program

The program can be run directly from Windows by using the shortcuts created in the start menu. Assuming you have not changed Euclide's installation folder, the input file is C:\Program Files\Euclide\Input.txt and the output file C:\Program Files\Euclide\Output.txt. They can be edited with Notepad or any text editor.

From the DOS command prompt, the program can be run in two ways:

  Euclide <inputfile> [<outputfile>] [options]

  Euclide <position> <halfmoves> [<outputfile>] [options]

If no output file is given, file Output.txt will be used.

Available options are:

When solving a problem, Euclide can be interrupted by pressing Escape. Alternatively, if Euclide is deeply searching the move tree of a strategy which you think will yield no solution, you may press S to skip the current strategy. Euclide will stop working on the strategy and move on the next one. Note that the software may take some time before responding to key presses, hence do not hit Escape or S more than once before getting any reaction. If Euclide is searching very deeply into permutation trees or move trees, you may need to press Ctrl-F4 to interrupt the program by brutally closing the DOS window.

If Euclide is interrupted while solving a problem, for any reason whatsoever, relaunch Euclide with the same problem to continue the resolution where it was stopped. It is in fact an automatic use of option -s. The solver should pay attention to the fact that if one solution has been found before Euclide was interrupted, this solution will not be found when the resolution continues. The output file will contain information about the first strategy analysed when analysis does not start from scratch.

Euclide stops solving a problem either when it has been cooked (one or a few duals were found) or when it has been verified to have one, two or more unique solutions. Euclide considers a problem cooked if it finds more than one solution for the same strategy, hence problems with two different unique solutions will not be considered as cooked. This should almost always agree with the author's intention. Note that Euclide considers cooked a problem where the two solutions differ only by which piece executes a captureless circuit.

If given an input file, Euclide will ask after each problem if it should proceed to the next one in the file. Press Escape or the character X to quit, and any other key to continue.

Euclide writes all solutions found in a text file called Output.txt, unless a different name has been provided on the command line. The file is reset each time Euclide is launched, hence make a copy if you wish to keep its content. You may of course open it with any text editor and paste it's content in your email program for example.

6. Bugs

Euclide has fairly complex builtin algorithms, hence bugs will certainly show up. Moreover, it has not been extensively tested.

User interface bugs should not occur, as Euclide has very limited input/ouput. However, I have already noted that the Escape key is not correctly trapped under Windows NT. Use X instead.

Algoritmic bugs will produce one of the following four results:

  1. A crash;
  2. An internal error, which will be displayed;
  3. An invalid (illegal) solution;
  4. No solution for a valid problem. Please carefully check the diagram position and the intended solution to make sure this event is not simply a mistake from your part.
In all cases, the author would be grateful if you could
  1. Verify on the web, on Euclide's home page if there is a newer version that includes a correction;
  2. Send the problem, along with the solution, to euclide@lestourtereaux.fr.

7. Linux

Official Linux supports for Euclide has been introduced with version 0.95. However, as the author does not master this environment, there is no installation package. Linux users are invited to follow these steps to get Euclide working on Linux :

  1. Install the following packages : svn, g++ and libncursesw5-dev. The first is required to retrieve the source code, the second is a C++ compiler while the third is a library required for compilation.
  2. Get the source code : svn checkout https://github.com/svart-riddare/euclide/branches/archives euclide.
  3. Compile the source code : make in folder euclide/Project Files. This will create a file named euclide in the parent folder.
  4. Run it, for example ./euclide Input.txt Output.txt.
There are almost no differences with the Windows implementation.

8. Mac OS X

Official Mac OS X support for Euclide has been introduced with version 0.97. However, as the author does not master this environment, there is no installation package. Using Euclide requires to use the terminal window as opposed to Apple's user friendly applications. Mac OS X users are invited to follow these steps to get Euclide working on Mac OS X :

  1. Install Xcode, an integrated development environment for Apple's operating systems. Xcode can be found here.
  2. Using the Finder, create a folder where Euclide will be installed.
  3. Open a terminal and execute the following command in the folder just created above : svn checkout https://github.com/svart-riddare/euclide/branches/archives . Note the final dot which is part of the command. This will download Euclide's source code.
  4. Going back to the finder, locate, in Euclide's folder, Project Files. In this folder, launch Euclide.xcodeproj. This will launch Xcode.
  5. In the top left corner of the Xcode project window that appears, there is a small drow down menu to select compiler configuration. Choose Release configuration.
  6. Build the program, using Build menu. The build process takes less than 10 seconds; you should see a Build succeeded message in the status bar when the process in complete. You may then exit Xcode.
  7. An executable called Euclide should then be available at the top level folder. Run Euclide to test that all is working correctly : ./Euclide Input.txt.
Note that the above steps have been tested on Mac OS X 10.6, known as Snow Leopard. The above steps are probably difficult for a casual Mac user but they nevertheless allow Euclide to be run for those that can follow them.

9. Random notes

Euclide is divided in four major parts. The first one, called the preliminary analysis, tries to make obvious deductions directly from the position. The second part builds all possible strategies by going through a large number of permutations. These permutations include which piece is which, which captured which, which promoted where, etc. The possible permutations are built from data provided by the preliminary analysis, without further analysis. As I understand it, Natch does these two parts simultaneously. The reason why Euclide is so slow at finding strategies for problems involving a fair number of captured promoted pieces is a side effect of the separation of these two parts.

Then, for each strategy found, we apply the third and fourth part of the analysis. The third part, unique to Euclide, consists in the partial analysis of move dependencies. The sofwtare is sometimes able to reconstruct pieces of the proofgame and order moves within these fragments. The underlying code is fairly tricky, and can certainly be improved tremendously. You may think as this part as being Natch's option -k builtin. Finally, the fourth part simply plays, from the initial position, moves until solutions are found or the move tree is exhausted. The computations of the third part are carefully used to truncate huge branches of moves. This truncation explains the relatively fast solution found to Unto Heinonen's problem given on Euclide's home page. However, if not much was deduced from the third part, a great deal of speed is lost as compared to Natch.

Most of the development of Euclide took place at the end of summer 2000, when I was (eagerly) waiting for my VISA for France. A second burst of activity to finish the third part occurred in January 2001, between two projects at the company where I was working then, before moving on to Cryo Networks and the Dune Generations team at the end of January. The easier fourth part was programmed sporadically, maybe one Sunday each three week, from February to May 2001.

Note also that the code has not been speed optimized at all, and that this version will never be optimized; it would be a waste of time, as some crucial deduction algorithms (in particular the first two parts) must be entirely rewritten.

10. Acknowledgments

Pascal Wassong deserves the first place, as Euclide has been inspired by carefully watching Natch working. I met him in December 2000 in Paris (I moved from Hull, Québec to Paris in October of the same year) to discuss of how we built our software. It is then for example that in one sentence from Pascal I understood what the hashtables were for. Who knows if I would have thought of them otherwise? Pascal also sent many test problems and bug reports when I completed the third part.

Peter van den Heuvel, Joost de Heer, Gianni Donati, Reto Aschwanden & Michel Caillaud carefully tested the program and (unfortunately!) sent many bug reports. Joost de Heer (Dutch), Thomas Brand (German), Juraj Lörinc (Slovak) and others provided translations.

Christian Poisson then provided hundreds of proofgames taken from WinChloé's database. It provided an invaluable reference set to find one terrible bug and a few minor ones.

The installation program was created with Inno Setup, by Russel Jordan, and with ISTool, by Bjømar Hender.

Étienne Dupuis, euclide@lestourtereaux.fr