An Introduction to FEG and Endgame Databases Table of Contents SECTION ONE -- INTRODUCTION I - Introduction to the Introduction II - For Those Who Cannot Wait III - What is FEG? IV - What does FEG do? V - An Endgame Database FAQ SECTION TWO -- HOW TO VI - Your First Attempt to run FEG VII - The Next 4 Runs (3-Men Example) VIII - Which Files Depend on Which IX - Dependency Resolution (4-Men Example) X - The Other Output Files XI - Building 5-Men Files XII - Commandline Options XIII - Sample Run Times SECTION THREE -- ADVANCED INFORMATION XIII - Considerations about 6-Men XIV - Statistics Lines Explained XV - Why the FEG Format? XVI - Credits ========================================================================= SECTION ONE -- INTRODUCTION ========================================================================= I. INTRODUCTION TO THE INTRODUCTION ===================================== This document is intended for Chessmaster 9000 users who are both highly knowledgeable of computer chess and who are also comfortable running DOS programs from a Command Prompt window. This document is fairly complex in describing the what/why/how/where of Endgame Databases (EGDBs). It is STRONGLY suggested that, if you are not the kind of Chessmaster user described above, that you exercise extreme caution if you attempt to run FEG to generate your own EGDB files. And, actually, even if you ARE the kind of Chessmaster user described above, the Chessmaster development team STILL strongly suggest that you thoroughly read this document before attempting to generate your own EGDB files. Improper or incautious use of FEG can result in quite a bit of wasted time and hard drive space. This document is organized in three sections: Introduction, How To, and Advanced Information. If you are very familiar with EGDBs, you might feel comfortable jumping to the How To section, which begins with Chapter V. However, reading this entire document is still a good idea, because there are many subtle differences between the file format used in Chessmaster, and other file formats that are commonly known (Nalimov and Thompson). If you have questions or difficulty running FEG, please note that this is an unsupported add-on feature for Chessmaster 9000. Ubi Soft Technical Support will not be able to help you resolve any problems you may have from running FEG. However, you may address any questions to chessmaster@ubisoft.com, and they will be addressed in a (hopefully) timely manner. Finally, you should once again make sure that you installed FEG to the "My Documents\Chessmaster 9000\EGDB" folder on your hard drive. If FEG.EXE (as well as the file that you are reading now) are NOT in that folder, then they should be moved there IMMEDIATELY. Running FEG in any other folder will just be a waste of time. II. FOR THOSE WHO CANNOT WAIT =========================================== If you are one of those brave souls who just cannot be bothered to read all this wonderful documentation that was carefully laid out in such a precise manner as to give its readers the best possible information about FEG and EGDBs, we provide this "somewhat quick and dirty" chapter. Most of this information is included later in this document, in greater detail, but some of it you will only find in this section. Here is the minimum you need to know/remember: 1. You MUST run FEG in the folder on your hard drive where Chessmaster installed several other EGDB files. This is most likely "My Documents\Chessmaster 9000\EGDB". If FEG is not in that folder, copy it there NOW. Note: The complete 3, 4 and 5-man files take up approximately 5.6 GB of hard drive space. If there is not going to be enough room in the folder mentioned above, there IS an option to change the folder where Chessmaster 9000 looks for the EGDB files. You can do this by editing the "CM.INI" file that is in your Chessmaster 9000 installation folder (the one that you specified during installation as the target folder). Look for the [settings] group and you will see an item that says: EGDBPath=.... And it will most likely be followed by the folder mentioned above. You can change this to be any folder that you like, as long as you specify the FULL PATH to that folder, including drive letter. Just make sure to copy/move all of the EGDB files that were installed on your hard drive to the folder that you specify, or else you'll just be wasting hard drive space. Chessmaster 9000 will only look in ONE folder for ALL of its EGDB files, and it will be the folder that is specified in the "EGDBPath" setting. 2. The way to build a single file with FEG is to open up a DOS command prompt window, navigate to the folder where FEG lives, and type: FEG -b KQK This will build the most basic endgame, King and Queen vs. King. FEG can build any combination of 3 to 6 pieces. 3. When building EGDBs, one important point to remember is that many files cannot be built if other files are not already present in the same folder. This is called "dependency". There are two main rules to remember. The first rule is that before you can build a 4-man EGDB set, ALL of the 3-man files must already exist. This is because a 4-man piece configuration can become a 3-man configuration after a capture. The same is true for 5-man files, in that all of the 4-man files must already exist. The same equation applies to 6-man files as well. The second rule is that if you are building a file with pawns in it, then all of the piece configurations that can result from pawn promotions must already exist. This one is a little harder to resolve in your head. For this reason, several MS-DOS batch files were also installed with FEG that handle all of these dependencies for you. If you want to build ALL of the 3, 4 and 5-man files, just run MakeAll.BAT, and don't bother coming back to your computer for several days. Additionally, you can run: FEG -d KRPKR to see all of the dependencies of the King, Rook and Pawn vs. King and Rook file set. 4. When FEG is done building a single set, the files that are used within Chessmaster 9000 will have either a .J00 or a .JIX extension. Additionally, when FEG is done building a single set, there are several files that are created only for informational purposes and are not used by Chessmaster 9000. These all have a .LOG, .LOF or .LOS file extension. If necessary, they can all be deleted. 5. Finally, you should know that Chessmaster 9000 installed all of the 3 and 4-man EGDB files on your hard drive. If you chose the "Complete" installation option, then many of the most useful 5-man files were also installed. However, because of CD space issues, only half of the data was actually copied to your hard drive. FEG splits the complete data for an EGDB file set into two main files, one for White to move (wtm) and the other for Black to move (btm). It is possible to delete one of these two files and still have Chessmaster work properly, so in the case of the 5-man files that were installed, none of them came with the wtm data. Chessmaster 9000 knows how to handle this. Unfortunately, if you are planning on building any 5-man files, you will need to rebuild the files that were copied during installation, because FEG needs both the wtm and btm data to resolve dependency issues. III. WHAT IS FEG? ======================================================= The name FEG stands for Final Endgame Generator. It allows you to (surprisingly), generate Endgame Databases for use in Chessmaster 9000. "Final" means that this is the final version -- we hope.... IV. WHAT DOES FEG DO? =================================================== Now to the important question: how does it work? One run of FEG generates the solutions to one material configuration of chess pieces (including both Kings). Material configurations are denoted as KQKR (for a King and Queen vs King and Rook combination of pieces). The solutions are stored in two files, one file for White to move (wtm), and the other one for Black to move (btm). Actually these 2 files are compressed, and the compressor makes at least 2 files on disk for each of them. Summarizing and starting at the start, the command: FEG -b KQK will solve the most basic endgame (King and Queen vs King). The resulting files will be: KQK____W.JIX // wtm, index file KQK____W.J00 // blocks file volume 0 KQK____B.JIX // btm KQK____B.J00 (plus some more output to be explained later) The main data files have the .J00 extension. The index files, which have the .JIX extension are needed for fast seeking into the .J00 files. IV. AN ENDGAME DATABASE FAQ ============================================= Q: What is an EGDB? A: It's an Endgame Database, aka Tablebase. A database that contains perfect knowledge for all positions with very few pieces (3, 4, and 5 pieces are currently common). This perfect knowledge can then be used to deduce perfect play. Q: What does it look like? A: The most used approach is an array of [64][64][64]... where each index represents a square. As an example, in KPK (King + Pawn versus King) the array would be addressed [WK_sqr][WP_sqr][BK_sqr]. The value would then be a measure of "goodness" of that position. The piece types (WKing, WPawn, BKing) are usually not stored in the array, but are hard coded, or designated by the array's filename, as well as the side to move. The "goodness" is usually coded as the distance to win from a position, or not, or lose, or illegal. With 3 pieces there's five possible material configurations, though KBK and KNK are pretty boring: the game is always a draw so there is no mate possible. With 4 pieces, there are many more configurations. Just one of them, KQKR would be an array of 64^4 = 16MB, with each byte coding for mate in 1...35 or "don't know" or worse. Q: That sounds huge, considering there's more than just KQKR. A: It is huge, but there is some relief. In practice, the space 64^n is condensed by eliminating mirrors and impossibilities like pawns at rank 1 or 8, Kings attacking one another, or whatever the designer likes to eliminate. Besides, the resulting arrays are usually compressed to save a factor of 10 or so on disk space. Nevertheless, all material configurations with 3, 4 and 5 pieces and either side to move can take up over 5.7 GB of hard drive space, and that is after compression! Q: What can we do with this collection of "perfect data"? A: We can convert it to information. The distance to win can be used to deduce the best move from a position by looking up all of its children, meaning all of the positions that can arise from the legal moves of the current position. Q: Is that the reason for storing bytes, rather than win/draw/loss? A: Exactly. Using W/D/L (or win/not win) has been proven useful for some games, but in chess many endgames are just too tough to find the winning move by simple knowledge. As an example, simple cases like KQKR and KBNK cannot be won "naturally" by a chess program without dedicated knowledge. And they're not easy for humans either. Q: So we're stuck with the 5.7 GB of hard drive space, not to mention 6 pieces? A: Forget about 6 pieces, at least for now. For 5 pieces we can save some space by omitting either White to move (wtm) or Black to move (btm). The search for best move must then be extended from 1 ply to 2 ply. This will cause much more random access, but is still doable in about 1 second. It will reduce storage to less than half (using the smallest files of either wtm or btm). Q: And we could leave out the boring configurations, right? A: Sure, we could ignore KQQQK, KQQKN and the like. But we'd better not ignore KQRKR and KQPKN, since these can result from KRPKR and KPPKN respectively. If these follow-ups are missing, the data-to-information conversion code has a problem. That problem can be avoided simply by just including all boring files. After all, the boring ones compress quite well. And there is definitely merit (or, at least, less frustration) in having a complete set of files at your disposal. Q: So what is a reasonable file set? A: Let's summarize. 4 piece KxyK + KxKy 23 MB 5 piece KxyzK 1.25 GB 5 piece KxyKz 3.47 GB 5 piece KxKyz 1.04 GB Some notes. - KxyzK are really boring, and can be left out. - These numbers apply to the De Koning format. The numbers may differ slightly from Nalimov's, which are generally larger. - The numbers designate the full set. For simple lookup the half set will do (either wtm or btm). The half set is somewhat smaller than half of the full set. - Nalimov's format has KxyKz and KzKxy merged. Eg in KRBKQ the wins for white (with RB) are stored as well as the losses for white. In Thompson's and De Koning's white can only win or not win. - Thompsons data is smaller, as explained later. Q: I got the picture now, don't I? A: Let's hope so, because it's time to elaborate. Above was mentioned the distance to win, without defining a win. A win can be a checkmate, it can be a capture or promotion into a won position, it can be a pawn push to avoid 50 moves rule. The state of the art is that these considerations were ignored, though mentioned and theoreticised. The EGDBs that have actually been historically built used either distance to conversion (DTC = mate,capture,promotion) or distance to mate (DTM). Neither DTM nor DTC takes into account the 50 moves rule, but DTC has smaller values, hence copmresses better and takes less time to build. The alternative of building DTZ (zeroing 50-counter) won't help because there may be trouble beyond the zeroing move. More elaborate schemes have been proposed, but will remain theory for a while. Q: What EGDBs have actually been built? A: In the 1970's there was quite some reasearch on the topic. However, it became interesting after Ken Thompson dedicated a machine for several years to produce most of the interesting 5 piece EGDBs (DTC), and eventually made them available on CD for free. In the early 90's Stiller did some work on a massive parallel system on 6 pieces, but he couldn't save the data. In the meanwhile Edwards redid the 5 pieces for DTM but mainly for research, without compression. Nalimov redid them again, but used compression (better than Thompson's, but still larger because of DTM). Nalimov's have been widely used since 1999. This is all public knowledge. Not public were the Koning & Kuijf experments, done since 1995. These experiments were targeted at building EGDBs fast, and succeeded in being fast. Though the actual data is more or less the same as Nalimov's. Q: If we forget the theory and look at it from the average user's perspective, wouldn't DTM be the cleanest option? A: Yes it would, in the sense that only *one* caveat has to be explained: mate positions > 50 *might* be drawn by 50 moves. Though quite rare with 5 pieces (let's forget 6 pieces again), there is the infamous KNNKP position that takes some 100 moves to mate without any captures or pawn pushes! Q: Should I be scared off by these imperfections? A: Not yet. Q: Then what should I do with this quasi-perfect information? A: Do what others do. (a) Present it to the user as information (like the Coach window in Chessmaster 9000). (b) Use it as an alternative move source (similar to an opening book -- the Chessmaster and Grandmaster personalities in Chessmaster 9000 do this by default). (c) Have it used by the engine deep in the search (like Crafty). Q: Certainly (c) would be the coolest, wouldn't it? A: It would definitely be cool for the engine to find a deep combination resulting in a perfect Mate in 60 and then report "Mate in 72" to the GUI. But there are some drawbacks. For one thing, this Mate in 72 might as well be a 50-move draw after 62 moves. Therefore the engine needs some work-arounds to handle semi-perfect mate scores. Worse than that, the engine must know if and where which files are, and allocate serious amounts of RAM for buffering and caching. Not to mention the fact the both wtm and btm are required (until expermentation shows that either will suffice). Q: Hmmm, but (b) would still increase endgame strength, right? A: The EGDBs would come into play only when the board position is reduced to 5 pieces or less. That is not often compared to (c). Still it would make sense to use the EGDBs if they're available anyway. Stated differently, if (a) is implemented it looks silly if an engine still plays non-optimal moves. Nevertheless, the 50-move-draw problems of (c) still apply to (b). Q: Fine, but would it help? A: If you're looking for scoring more points: not much. Most endgames are screwed up by the engine long before the board is reduced to 5 pieces. Even (c) won't help against choosing the wrong strategy (or, worse yet, no strategy!). Tactics are rare in real life endgames. But the important thing is that *if* EGDBs come into play, it is really nice, or even exciting, to have perfect play or information. Q: I'm wondering, would (a) be better than nothing at all? A: The advantage of (a) is that nothing depends on it. Data that is available can be displayed. Data that isn't available can be ignored. Time is not an issue. File persistence is not an issue. State of the GUI is not an issue. Q: I STILL can't forget 6 pieces. A: You still should. A single configuration results in more than 1 GB compressed. Of course there are small ones, but again the small ones will be mostly boring. Estimates for the full set of KxyKpq range from 1 TB to several TB. Of course we don't need all of them, but even a few interesting ones will defy distribution or download. Not to mention the fact that a single one takes several days to build. There is however the interesting idea of putting them on a server. That also applies to 5 pieces, but with the current (summer 2002) average hardware the sluggishness of online retrieval would outweigh the loss of a few GB disk space. Q: Where can I find out more about EGDBs? A: An excellent website devoted entirely to EGDBs is Aaron Tay's "Guide to Endgame Tablebases". Just point your browser to: www.chesskit.com/aarontay/Winboard/egtb.html. ========================================================================= SECTION TWO -- HOW TO ========================================================================= V. YOUR FIRST ATTEMPT TO RUN FEG ======================================== This might be a good moment to run FEG. Simply run "FEG -b KQK" from a Command Prompt. (Warning: If you do NOT know how to launch a Command Prompt in Windows, then you should probably not continue reading this file until you are more familiar with a DOS command prompt!) VI. THE NEXT 4 RUNS (3-MEN EXAMPLE) ===================================== Well, that was easy, and rather fast! You have now built the complete KQK 3-men EGDB file set. Chessmaster will now be able to play this endgame perfectly (although it could do this one without the EGDB files -- this is just a quick example), and will also be able to report the exact number of moves to mate in the "Chess Coach" window's "Advice" tab, if there are only two Kings and a Rook left on the board. The next steps are rather simple: FEG -b KRK // slightly more useful than KQK.... FEG -b KBK // boring -- always a draw! FEG -b KNK // boring -- always a draw! FEG -b KPK // interesting -- could be win or draw! And now we've generated all five of the 3-men EGDBs! Note that the generation of KPK depends on the previous 4 since the pawn can promote to any of (QRBN), so the generator needs to know the results of all possible promotions to accurately calculate the data for positions with pawns in them. This also applies to captures. Hence the 4-men KQKR depends on the 3-men KQK, and KPKP depends on a lot of predecessors. VII. WHICH FILES DEPEND ON WHICH ======================================== You might be wondering why KQKR does not depend on KKR (or mirrored KRK). The answer is simple: FEG searches only for wins for White. All positions that are not proven to be won by White are stored as unknown. These unknowns might be draws, or lost by White, or (in large numbers) illegal. This explains why KRKQ is part of the 4-men set: some KQKR positions are won by Black, and can be resolved by looking up the mirrored position in KRKQ. VIII. DEPENDENCY RESOLUTION (4-MEN EXAMPLE) ============================= The next step is generating 4-men files. However, before you do this, you should know that the typical Chessmaster 9000 installation option already put ALL of these files (as well as all of the 3-men files) on your hard drive, in the "My Documents\Chessmaster 9000\EGDB" folder. So you do not NEED to build them. But, if you want to see how FEG works (and don't want to spend a lot of time doing it), then go ahead and rebuild some (or all) of the 4-men files. Obviously we can start KQQK and KQKR right away, but there are 40 4-men EGDBs, and some of them depend on other 4-men EGDBs. To keep things simple, there is a fail-safe order to avoid dependency trouble: always count down from Q to P, and the rightmost piece (i.e. non-K character) counts fastest (just like a numerical sequence). KQQK, KQRK, KQBK, KQNK, KQPK, KRRK, KRBK, KRNK, KRPK, // KRQK already as KQRK KBBK, KBNK, KBPK, KNNK, KNPK, KPPK // done with all WW combinations KQKQ, KQKR, KQKB, KQKN, KQKP, KRKQ, KRKR, KRKB, KRKN, KRKP, KBKQ, KBKR, KBKB, KBKN, KBKP, KNKQ, KNKR, KNKB, KNKN, KNKP, KPKQ, KPKR, KPKB, KPKN, KPKP // done with all WB combinations You might find it quite amusing and educational to run all these manually, and watch the screen (preferably in a 50-line display mode or better) and the directory listing simultaneously. After all, these 4-men files will only take an average of a minute each on a fast enough machine (example: On a 1.5GHz machine, building all 4-men files should take less than a half an hour). However, depending on the speed of your computer, this whole step might take as much as a few hours. To help save you some typing (if you want to do it all in one step), an MS-DOS batch file named "MakeAll4.bat" was included in this add-on package and is also in the same folder as this document that you are reading. Just running "MakeAll4" from the commandline prompt will build all 40 of the 4-men EGDB files, one at a time. IX. THE OTHER OUTPUT FILES ============================================== By now, if you have made all 3-men and 4-men file sets, you should have 45 EGDBs finished (five 3-men sets and forty 4-men sets). That makes 180 *.J* files, and some junk. One part of the junk is: EGDBname\ the directory in which all the temp files are created and then removed. When an EGDB is finished, only RUN should be left in there. The other part of the junk is: EGDBname.LOF EGDBname.LOG EGDBname.LOS These are log files, and are pretty valuable or interesting for statistical purposes, but are not needed by the Chessmaster program: .LOF lists statistics and uses "physical" numbers, .LOG uses official numbers, (i.e. full-board counts disregarding mirroring), .LOS lists system calls, which can be useful for debugging. Summarized, the actual data is the *.J* files (4 for each EGDB), but the *.LO? files are worth keeping as a reference. X. BUILDING 5-MEN FILES ================================================= The next step is generating 5-men stuff. In the amusement/education department there is "FEG -b KQQKQ". Less amusing is the fact that building this single file set takes as long as all the 4-men files combined! But then again, thanks to some more MS-DOS batch files that were included in this add-on package (specifically "MakeAllWWW", "MakeAllWWB" and "MakeAllWBB"), the machine can generate lots of them while you're being entertained by other things. Or, if you just want to generate all 3-men, 4-men AND 5-men files with one command, just run "MakeAll" and take a nice vacation away from your computer for a while. You should note, though, that if you performed the "Complete" installation option when you installed Chessmaster 9000, some of the most useful 5-men files were installed onto your machine. Specifically, the KRPKR and KQPQK files (and all of their dependents), as well as the more obscure but still useful KBBKN and KNNKP files. HOWEVER, only the btm files were installed due to CD space issues. Although Chessmaster knows how to account for the lack of the corresponding wtm files, FEG will always build both the wtm and btm files. And both the wtm and btm files are required if they are predecessors for any other files. So, it may be necessary to rebuild these files anyway, if you plan on building other files that did not come with Chessmaster 9000. The benefit, of course, is that having both the wtm and btm files will result in a speed increase when determining the value or best move of a given position. (Aside: If you're a quick thinker, you might have deduced that it is possible, after generating the complete 5-man set of files, to DELETE the wtm files in order to save hard drive space. This is a perfectly reasonable option, if you find it necessary. A "half-complete" set of all 3, 4 and 5-man files, with ONLY the btm files present, takes up only about 2.7 GB of hard drive space, close to 3.0 GB less than a complete set. However, it will take Chessmaster a fair bit longer, in some cases, to use any EGDB files that do not have both the wtm and btm data. If both files are there, the value for just about any position can be completely resolved for all of its legal moves in less than one second. If the wtm files are not present, the time can be noticeably longer. This is not an issue if you are merely doing analysis of a position. But if a computer personality is playing an endgame under time pressure at a fast time control, this might prove significant.) Of course, dependencies are much more of a concern with 5-man files. There are two potential problems, which we call the KRPKR problem and the KRRKQ problem. The first of these involves Chessmaster 9000 having access to the KRPKR data, but not all of its dependents (KRQKR, KRRKR, etc.). In Chessmaster 9000, if any of a file's dependents are missing, then the program will not be able to find the optimum move for positions of that file's configuration. The second problem involves the "mirroring" that was mentioned above in the section titled "Which Files Depend on Which". Remember that only wins for the left side (ie KRR in KRRKQ) are generated, not losses. The losses are resolved by looking up the mirrored position in KQKRR. So KRRKQ is not complete without KQKRR. The easiest way to avoid partial (confusing) information in all cases is to simply generate all the 5-men EGDBs. If you are intending on building the complete 5-man file set (all 5.6 GB worth) and find that the hard drive (or partition) on which you installed Chessmaster 9000 does not have enough free space, you have another option. By editing the CM.INI file, found in the Chessmaster 9000 program folder (most likely "Program Files\Ubi Soft\Chessmaster 9000"), you can tell Chessmaster 9000 to look for the EGDB files in a different folder, and even a different hard drive. Open the CM.INI file for editing and look for the [settings] section. In it, there will be an entry that says "EGDBPath=", followed by the current location of your EGDB files (most likely "My Documents\Chessmaster 9000\EGDB"). You can edit this line to point to any folder on your computer that you like. If you do this, though, you should either move all of the files in the old EGDB folder to the new one, or make sure to rebuild all of the 3 and 4-man files before you start to build 5-man files. As mentioned before, FEG only does one EGDB set at a time. With 140 of them to do to complete the 5-men set, that seems a bit tedious. For example, on a PIII-600, with little else to do, generating the entire set of 5-men files can take close to two weeks or more! But, on a much faster computer, say a 1.5Ghz machine, it should take less than 5 days. Fortunately, there are several options to take it to a higher level.... XI. COMMANDLINE OPTIONS ================================================= This might be a good moment to explain some details of FEG. When run without commandline arguments it shows these cryptic hints (and a few others which are not useful to a user). FEG -b bname builds a specific database This one you already know about. Example: FEG -b KPPK BTW: is NOT case sensitive. FEG -d bname [depth] creates a dependency list This one is more fun than useful, since the "MakeAll" batch files are in your EGDB folder. But you may find it interesting to see how the dependencies work for certain file sets. Example: FEG -d kppk. FEG -e w...b... enumerate databases, eg wwb List all databases with specified number of White and Black pieces. Useful to create script or project files. To list all 3-men, 4-men, 5-men try FEG -e w ww wb www wwb wbb. FEG -ll bname len log len-ply positions Write all position won/lost in ply to OUT.LOG file. It might be fun to try FEG -ll kpk 56, but any other attempt will result most likely in a huge log file. FEG -sum [path [path... summarize LOF files Collect summary lines from [path\]*.LOF. Cool to quickly see used time and space. This output goes to the screen, so pipe it to a log file if you want to save the data. Finally, pressing ESC while FEG is running will abort the program. XII. SAMPLE RUN TIMES =================================================== To prepare yourself for how long some of the files will take to build, here are some sample run times for a few of the more common 5-man files, built on an AMD1300 processor. You can find complete run times for all 5-man files in the file called 5Man.TXT, which was included in this download. Additionally, there are a few 6-man run times included in the file called 6Man.TXT. KQPKQ -- 2 hours, 22 minutes (this is one of the longest ones to build) KRPKR -- 1 hour, 49 minutes KRRKQ -- 18 minutes KQQKQ -- 22 minutes KQRKR -- 27 minutes KBBKN -- 38 minutes ========================================================================= SECTION THREE -- ADVANCED INFORMATION ========================================================================= XII. CONSIDERATIONS ABOUT 6 MEN ========================================= The next step, if you are particularly adventurous and have LOTS of time and hard drive space, might be generating 6-men files. Though this is not important at the moment (summer 2002), it is certainly possible with FEG. In fact the main reason for developing FEG was to do something new. Several years ago the goal was building EGDBs with pawns on both sides. Since anything up to KPPKP is now common practice, the next goal would be to generate 6-men EGDBs with a pawn. Or just all 6-men if resources are available. An estimate of all WWWB, WWBB, WBBB is AT LEAST 1 TB (1 Terabyte or 1024 Gigabytes!) of storage, and over a year of 1.5GHz CPU time. The WWWW set is too boring to build, but would be possible with 300 MB of free RAM. All others still require only 13 MB RAM. There are a few additional concerns about 6-man files that you should be aware of. The de Koning format stores only 8 bits of information regarding the result of the position. This means that positions with Mates in more than 254 moves (don't laugh, there are several that are already known for some 6-man configurations) are stored as "Mate in 254" in the file. This won't be a huge problem (apart from the high potential for a 50-move draw with best play, but this can happen with 5-man files as well), except that for positions where there are more than one move with a Mate in 254+, and at least one of those moves would be considered "best play". In these cases (and we are speaking theoretically here -- there are no known cases of this at this time), Chessmaster 9000 will not necessarily be able to determine the "best" move. It will choose one of the "Mate in 254" moves and hope for the best. XIII. STATISTICS LINES EXPLAINED ======================================== Some brief comments about the statistics, for the very curious, the VERY technically aware, or for those who simply enjoy staring at their monitor while lots of numbers go scrolling by.... Two example lines: | KQPKQ +007 2006.4 0129.4 10,297818 181,656146 3.000 0027.0 0025.7 | KQPKQ +008 2078.4 0072.0 246934 100,155881 2.000 0002.4 ------ Column1: the name of the EGDB under construction. Column2: the current pass. The pass is basically the plies-to-win for which all position are resolved. An optinal '+' indicates that best captures/promotions (bcp) with this win-length are processed. These are looked up during the initial 2 passes. If the '+' is a '*' it means the bcp files are being purged. Column3: total time so far. Column4: time for this pass. Column5: #positions that are resolved in this pass. Column6: #positions that are not resolved by any pass yet. Both #s are for wtm or btm alternating. Column7: percentage of the work completed for this pass. During init and final stages it runs from 0 to 1, as expected. During "normal" passes it runs from 1 to 2 in the sorting stage, and from 2 to 3 in the flipping stage (wtm only). Column8: time spent in the sorting stage after the resolving stage. If the #resolved is large (roughly > 5M) more then 1 merge is needed, and the progress is shown on screen only. Column9: time spent in the flipping stage after sorting (wtm only). Explaining what flipping is could take another page or two, but anyway, it is needed by the subsquent btm pass. Progress is shown on screen only. During initialization things are slightly different: | KQPKQ -01 0821.1 0821.1 337,569499 199,301413 1.000 221082k 65760 | KQPKQ -01 0871.8 0050.7 337,569499 199,301413 1.000 ------ ------ Column5: #resolved, in this case illegal positions (2 pieces on 1 square, pawn on rank 1 or 8, black king in take, etc). Column8: #captures/promotions looked up in existing EGDBs. Column9: #cache loads needed for these lookups. The second line reports about the initialization of the flipping file. | KQPKQ 000 1503.2 0631.3 435,797687 101,073225 1.000 128101k 448 | KQPKQ 000 1505.2 0002.1 215721 100,857504 1.000 0002.1 ------ Column5: #resolved, for btm that includes positions where Black can capture/promote his way to a draw. The second line reports about the collection of mate in 0 positions. During finalization it looks like this: | collect 001 013659 0208.3 114,885027 421,985885 1.000 ------ ------ | collect 041 013748 0089.1 10,515851 526,355061 1.000 ------ ------ MORE ... | collect 241 014038 0025.5 92 536,870820 1.000 ------ ------ | KQPKQ 901 016396 2357.9 136,304160 400,566752 1.000 ------ ------ First, the results of all passes are collected in chunks of 20 files. Then the results of all chunks are collected to the final EGDB file. In this pass mirroring of equal pieces is applied, so column5 might not add up if white has eg 2 queens. Also maximum compression is applied, which is pretty expensive. XIV. WHY THE FEG FORMAT? ================================================ Perhaps, after reading all of this, you are wondering why Chessmaster 9000 does not use either of the more commonly used EGDB formats, namely those created by Eugene Nalimov or Ken Thompson (both of which bear the names of their creators). There are many reasons for this: 1. FEG data is slightly (about 20%) smaller. 2. FEG generation is much faster and doesn't need a huge amount of free RAM to create a set of files. 3. FEG can do any 6-men files on a 32-bit platform. 4. The Thompson format is not a complete set (especially pawns on both sides are lacking). 5. The Thompson format stores DTC (Distance to Conversion) values, meaning that it stores the number of moves to either mate OR to a capture/promotion, and will play whichever move has the smallest winning value. This can result in silly moves (a capture that leads to a mate in eight moves instead of a non-capture that leads to mate in three moves). XV. CREDITS ============================================================= FEG: The Final Endgame Generator version 3.02, copyright 1998-2002 by Johan M de Koning