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.
Version 1.10 adds new features:
Version 0.99 has two minor improvements:
Version 0.95 showcases the following major improvements:
Version 0.92 had the following improvements:
S key is trapped to skip the current strategy.
The initial released version was labelled 0.90. Versions 0.91, 0.93, 0.94, 0.96, 0.97, 0.98, 1.00, 1.01 and 1.11 are bug fix releases.
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 scripts in the Language Files subfolder.
If installing over a previous version, the setup program will prompt you before overwriting the 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. Constraints are documented below, in section 4.1. Here is a simple example, my first proofgame :
Étienne Dupuis Probleemblad, May-June 1999 1cfdrfc1/pp1pp2p/7p/3p4/8/3P4/PPP1PP1P/TC1DRFCT 22
The input file can contain comments or additional information. Euclide will ignore them as long as the next line does not start with a digit (or white spaces followed by a digit). Natch's input file can thus be fed 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 |
|---|---|---|---|---|---|---|
| English | K | Q | R | B | N, S | P |
| French | R | D | T | F | C | P |
| German | K | D | T | L | S | B |
| Italian | R | D | T | A | C | P |
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 contains, 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 for the strategy to be considered.
Here are some examples of constraints, for the same input:
Étienne Dupuis Probleemblad, July-August R6R/2ppp2b/1p2rkp1/1p1Q1p2/nrP1q2n/2NBPPN1/2PP2p1/R5KR 55 +Ph2=Rh8->h1
Étienne Dupuis Probleemblad, July-August R6R/2ppp2b/1p2rkp1/1p1Q1p2/nrP1q2n/2NBPPN1/2PP2p1/R5KR 55 +Ph2=Rh8->h1 -Pa2=Ra8->a8
Étienne Dupuis Probleemblad, July-August R6R/2ppp2b/1p2rkp1/1p1Q1p2/nrP1q2n/2NBPPN1/2PP2p1/R5KR 55 +Rh8->h1 -Ra8->a8Note 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+.
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
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
Available options are:
-b or --batch will instruct Euclide not to wait for user input between problems.-sn, where n is a positive integer, will instruct Euclide to start solving from the nth strategy.
Note that reaching this strategy may take a substantial amount of time.-mn, where n is a positive integer, will instruct Euclide to allocate 2n bytes of memory for hashtables.
When this option is not used, Euclide automatically sets this parameter according to the amount of free memory available.
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 its content in your email program for example.
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.
Algorithmic bugs will produce one of the following four results:
Official Linux support 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 :
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.svn checkout https://github.com/svart-riddare/euclide/branches/archives euclide.make in folder euclide/Project Files.
This will create a file named euclide in the parent folder../euclide Input.txt Output.txt.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 :
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.Euclide.xcodeproj. This will launch Xcode.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.Euclide should then be available at the top level folder.
Run Euclide to test that all is working correctly : ./Euclide Input.txt.Euclide is divided into 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 software 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 every third 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.
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.