See: http://kirill-kryukov.com/chess/discussion-board/search.php?author_id=1271&sr=posts for improvements to algorithm. Old article follows Computing endgames with few men Urban Koistinen, 1 April 2001 Copyright (c) 2001 Urban Koistinen. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; with no Invariant Sections, with no Front-Cover Texts, and with no Back-Cover. A copy of the license is included in the section entitled "GNU Free Documentation License". Last change, 10 April 2001 Abstract The author presents a better way of computing endgame databases with a new indexing scheme and a new way to compute minimax in parallel on a standard computer. What should the result be once an endgame has been computed? For any position in the endgame, the following should be quickly (1 second, not cost more than a few seeks) computable: Is the position a win, loss or draw? A move that wins the won or draws the drawn. Lost positions may be played any way. In order to make the computation possible on modest hardware I split it into smaller computations. Compute only white wins. (To get result where black win, reverse the colour of all pieces.) g50 is the counter for the game 50 rule that states that when both sides have made 50 moves without capture or pawn move the position is a draw (unless it is check mate). g50=0 when there are no half moves left to be made and 100 after a capture or pawn move. Compute (one bit per position): t0 Black in checkmate t1 White win with g50=1 t2 Black lose with g50=2 t3 White win with g50=3 t4 Black lose with g50=4 ... t100 Black lose with g50=100 To make the computation quicker/simpler an additional table is used d The position is legal with black to move and not stalemate and black has no capture or pawn move that avoids loss For t0, t2, ..., black is to move. For t1, t3, ..., white is to move. As it is seems very unlikely that there are any positions with few pieces where the value would be different for white to move and g50=100 than g50=99 I don't bother to compute them. (A position with that property to be included here if/when it becomes known to the author) Illegal positions are stored as 0 for black to move (useless for white) and as 1 for white to move (useless for black) t0 does not depend on any other tables t1 depends on t0 and all tables that can be reached by capture or pawn move t2 depends on t1 and d t3 depends on t2 and t1 (better than the complicated dependancy of t1) t4 depends on t3 and d t5 depends on t4 and t3 (better to use t3 than t1 for reasons below) ... t100 depends on t99 and d Now there would be 102 tables with 1 bit/position. To reduce the storage requirements, all tables are removed when they are no longer needed and the difference between t(2n-1) and t(2n+1) is stored. As the odd tables never resets bits set in previous odd tables the differences have a very limited number of bits set and can be stored simple distance between bits encoding that is guaranteed to use at most 10 bits/bit instead of the 50 bits that would be needed to store them directly. (Encoding scheme: (0: add 255 to next code) (1-255: offset of next set bit)) (A further small saving can be made by not storing the illegal positions) Once all the tables have been calculated the stored differences can be combined to a table with 6 bits per position. The tables that should then be kept are t99 and t100. Indexing The indexing scheme I would use is: For pawnless endgames: Black king most significant in a1..d1..d4 triangle (10 squares) White king least significant, regular bitboard The pieces position index is split in two parts, where only the second is affected when the board is mirrored. 8 64 04 14 24 26 16 06 66 7 05 65 34 44 46 36 67 07 6 15 35 74 54 56 76 37 17 5 25 45 55 75 77 57 47 27 4 21 41 51 71 73 53 43 23 3 11 31 70 50 52 72 33 13 2 01 61 30 40 42 32 63 03 1 60 00 10 20 22 12 02 62 a b c d e f g h With the sample board above you might satisfy yourself that only the second digit of each piece position index change when the position is mirrored. The bits of the piece position indexes are merged into a position index. Example: The index of QN vs RB could look like this: (capital letters for white pieces) k3Q5k2Q4k1Q3k0N5r5N4r4N3r3b543Q210r210b210Q210K543210 3 3 3 3 2 2 2 2 2 2 2 2 2 211 111 111 11 3 2 1 0 9 8 7 6 5 4 3 2 1 098 765 432 109 876 543210 When black is moving, bits 32, 30, 28, 26, 24, 22 can be used to divide the problem into 64 separate computations, each requiring only 2*10*2^24 bits = 40 megabytes of ram while allowing i/o to be done with a block size of 2^22 bits = 512 kilobytes. When white is moving, bits 33, 31, 29, 27, 25, 23, 21 can be used to divide the problem into 80 separate computations, each requiring only 2*2^27 bits = 32 megabytes of ram while allowing i/o to be done with a block size of 2^21 bits = 256 kilobytes. When memory size doubles, block size quadrouples. As all i/o is done in fairly large blocks, they might be compressed by not storing illegal positions or mirrored positions. (All the mirroring is done with the last bits). When white is moving, no mirroring is done so the mirroring part of black pieces index may be used to divide the computation. (ie for RBN vs Q) For QRBN vs nothing, partitioning the problem is trickier. I would recommend computing the reachable positions for two groups of white pieces separately. It might be doable to combine one of those computations together with the black moves but as there are not so many positions of that type a simple halfspeed solution would be ok. The same problem would occur with Q vs RBN but then there is also the possibility of switching the white and black kings indexing so that a fullspeed solution is reasonable. 7-man such as QRN vs QN should be doable with 320+ megabytes of ram. If one side has 0-1 pieces the halfspeed solution needs to be used. For endgames with pawns the partitioning is simpler as no mirroring is needed and the pawn moves only need to be checked expensively once. (cheaply for checkmate) For the double move I would filter with en passant when evaluating the move rather than store the ep condition in the table. Similarly, castling need not be stored as an endgame where castling is possible would have 512 times fewer possible positions. Now that the computation has been divided into managable chunks it is time to process them. For each chunk For each moving piece For each configuration of the other pieces Load all positions that the mover can reach (in bitboards) Compute the result for the movers every position Store/merge result The white kings reachable positions would be a bitboard and the computation would be something like: (C-like notation) b1 = (not_line_h&(bb<<1)) | (not_line_a&(bb>>1)); b2 = b1 | bb; Result = b1 | (not_rank_8&(b2<<8)) | (not_rank_1&(b2>>8)); The black kings reachable positions would be the positions reachable from the a1..d1..d4 triangle (22 positions). When loading the reachable positions some bitboards need to be mirrored. Also, some 5 versions of the piece indexes need to be used to reflect the mirroring. Mirroring code: /* d1-d8 */ b1 = (rank_1234&(bb>>32)) | (rank_5678&(bb<<32)); b2 = (rank_1256&(b1>>16)) | (rank_3478&(b1<<16)); Result = (rank_1357&(b2>>8)) | (rank_2468&(b1<<8)); /* d1-e1 */ b1 = (file_abcd&(bb>>4)) | (file_efgh&(bb<<4)); b2 = (file_abef&(b1>>2)) | (file_cdgh&(b1<<2)); Result = (file_aceg&(b2>>1)) | (file_bdfh&(b2<<1)); /* d1-a4 */ b1 = (quads_4_even&bb) | (quads_4_odd_up&(bb<<(32-4))) | (quads_4_odd_down&(bb>>(32-4))); b2 = (quads_2_even&b1) | (quads_2_odd_up&(b1<<(16-2))) | (quads_2_odd_down&(b1>>(16-2))); Result = (quads_1_even&b2) | (quads_1_odd_up&(b2<<(8-1))) | (quads_1_odd_down&(b2>>(8-1))); quads_4_even: 00001111 00001111 00001111 00001111 11110000 11110000 11110000 11110000 quads_4_odd_up = rank_5678&~quads_4_even; quads_4_odd_down = rank_1234&~quads_4_even; quads_2_even: 00110011 00110011 11001100 11001100 00110011 00110011 11001100 11001100 quads_2_odd_up = rank_3478&~quads_2_even; quads_2_odd_down = rank_1256&~quads_2_even; quads_1_even: 01010101 10101010 01010101 10101010 01010101 10101010 01010101 10101010 quads_1_odd_up = rank_2468&~quads_1_even; quads_1_odd_down = rank_1357&~quads_1_even; The computation is done simply as: { int i_rank, i_file; for each i_rank, i_file in a1..d1..d4 triangle do { bb = all_ones; /* ones mean lost, useless for black */ if (i_rank>0) { if (i_file>0) bb &= reachable[(i_file-1)+(i_rank-1)*8]; bb &= reachable[(i_file)+(i_rank-1)*8]; if (i_file<7) bb &= reachable[(i_file+1)+(i_rank-1)*8]; } if (i_file>0) bb &= reachable[(i_file-1)+(i_rank)*8]; if (i_file<7) bb &= reachable[(i_file+1)+(i_rank)*8]; if (i_rank<7) { if (i_file>0) bb &= reachable[(i_file-1)+(i_rank+1)*8]; bb &= reachable[(i_file)+(i_rank+1)*8]; if (i_file<7) bb &= reachable[(i_file+1)+(i_rank+1)*8]; } } } Which can be unrolled into Result[0] = reachable[1] & reachable[8] & reachable[9]; ... Result[27] = reachable[18] & reachable[19] & reackable[20] & reachable[26] & reachable[28] & reachable[33] & reachable[34] & reachable[35]; which the compiler should be able to optimize further. Knights are dealt with in the same manner. White pieces moving use all_zeroes and | as zeroes are useless to white. Handling sweeping pieces require knowing what squares are occupied. Otherwise they could be handled the same way and that would be good enough. There is however an optimization. /* example with white rook */ Set all of Result[] to all_zeroes /* this can be optimized away */ /* moves a1..h1 */ bb = reachable[0]; Result[1] |= bb; if (is_occupied(1)) bb = all_zeroes; else bb &= ~bit_b1; /* this last is not needed for black movers (check illegal) */ bb |= reachable[1]; Result[2] |= bb; ... if (is_occupied(6)) bb = all_zeroes; else bb &= ~bit_g1; /* this last is not needed for black movers (check illegal) */ bb |= reachable[6]; Result[7] |= bb; /* moves h1..a1 */ bb = reachable[7]; Result[6] |= bb; if (is_occupied(6)) bb = all_zeroes; else bb &= ~bit_g1; /* this last is not needed for black movers (check illegal) */ bb |= reachable[6]; Result[2] |= bb; ... if (is_occupied(1)) bb = all_zeroes; else bb &= ~bit_b1; /* this last is not needed for black movers (check illegal) */ bb |= reachable[1]; Result[7] |= bb; /* + same thing for other ranks and lines */ Bishops and queens can be handled in the same way. Conclusion It should be possible to compute endgames at a cost of about: 102*3 + 20+6 = 332 bits of i/o and 14 bits of storage per position. A 6-man has 10*2^30 positions (including illegal and diagonally mirrored positions that might be optimized away). A regular hard disk can do at least 40 Mbit/s so the i/o of a 6-man endgame should take no more than 332*10*2^30/(40*2^20) = 83*2^10 s is approximately 24 hours. As the moves are examined for 64*64 positions at a time, examining all moves should take no more than 2 instructions/position meaning the total number of instructions to be executed should be no more than 102*2*10*2^30 is approximately 2^41 and should take about 2^12 s (less than an hour) on a 500 MHz Pentium II. The total time is then about 25 hours. To compare it with Nalimovs (implemented) scheme, it needs to be doubled as my scheme only computes the value for one side winning. The amount of disk space needed would be about 14*10*2^30 bits is approximately 18 Gbyte. To do a 7-man would take a factor 64 more of everything but ram where a factor 8 could be enough. I hope this is enough to get all 6-man and a few 7-man done this year. Urban Koistinen GNU Free Documentation License Version 1.1, March 2000 Copyright (C) 2000 Free Software Foundation, Inc. 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. 0. PREAMBLE The purpose of this License is to make a manual, textbook, or other written document "free" in the sense of freedom: to assure everyone the effective freedom to copy and redistribute it, with or without modifying it, either commercially or noncommercially. Secondarily, this License preserves for the author and publisher a way to get credit for their work, while not being considered responsible for modifications made by others. This License is a kind of "copyleft", which means that derivative works of the document must themselves be free in the same sense. It complements the GNU General Public License, which is a copyleft license designed for free software. We have designed this License in order to use it for manuals for free software, because free software needs free documentation: a free program should come with manuals providing the same freedoms that the software does. But this License is not limited to software manuals; it can be used for any textual work, regardless of subject matter or whether it is published as a printed book. We recommend this License principally for works whose purpose is instruction or reference. 1. APPLICABILITY AND DEFINITIONS This License applies to any manual or other work that contains a notice placed by the copyright holder saying it can be distributed under the terms of this License. The "Document", below, refers to any such manual or work. Any member of the public is a licensee, and is addressed as "you". A "Modified Version" of the Document means any work containing the Document or a portion of it, either copied verbatim, or with modifications and/or translated into another language. A "Secondary Section" is a named appendix or a front-matter section of the Document that deals exclusively with the relationship of the publishers or authors of the Document to the Document's overall subject (or to related matters) and contains nothing that could fall directly within that overall subject. (For example, if the Document is in part a textbook of mathematics, a Secondary Section may not explain any mathematics.) The relationship could be a matter of historical connection with the subject or with related matters, or of legal, commercial, philosophical, ethical or political position regarding them. The "Invariant Sections" are certain Secondary Sections whose titles are designated, as being those of Invariant Sections, in the notice that says that the Document is released under this License. The "Cover Texts" are certain short passages of text that are listed, as Front-Cover Texts or Back-Cover Texts, in the notice that says that the Document is released under this License. A "Transparent" copy of the Document means a machine-readable copy, represented in a format whose specification is available to the general public, whose contents can be viewed and edited directly and straightforwardly with generic text editors or (for images composed of pixels) generic paint programs or (for drawings) some widely available drawing editor, and that is suitable for input to text formatters or for automatic translation to a variety of formats suitable for input to text formatters. A copy made in an otherwise Transparent file format whose markup has been designed to thwart or discourage subsequent modification by readers is not Transparent. A copy that is not "Transparent" is called "Opaque". Examples of suitable formats for Transparent copies include plain ASCII without markup, Texinfo input format, LaTeX input format, SGML or XML using a publicly available DTD, and standard-conforming simple HTML designed for human modification. Opaque formats include PostScript, PDF, proprietary formats that can be read and edited only by proprietary word processors, SGML or XML for which the DTD and/or processing tools are not generally available, and the machine-generated HTML produced by some word processors for output purposes only. The "Title Page" means, for a printed book, the title page itself, plus such following pages as are needed to hold, legibly, the material this License requires to appear in the title page. For works in formats which do not have any title page as such, "Title Page" means the text near the most prominent appearance of the work's title, preceding the beginning of the body of the text. 2. VERBATIM COPYING You may copy and distribute the Document in any medium, either commercially or noncommercially, provided that this License, the copyright notices, and the license notice saying this License applies to the Document are reproduced in all copies, and that you add no other conditions whatsoever to those of this License. You may not use technical measures to obstruct or control the reading or further copying of the copies you make or distribute. However, you may accept compensation in exchange for copies. If you distribute a large enough number of copies you must also follow the conditions in section 3. You may also lend copies, under the same conditions stated above, and you may publicly display copies. 3. COPYING IN QUANTITY If you publish printed copies of the Document numbering more than 100, and the Document's license notice requires Cover Texts, you must enclose the copies in covers that carry, clearly and legibly, all these Cover Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on the back cover. Both covers must also clearly and legibly identify you as the publisher of these copies. The front cover must present the full title with all words of the title equally prominent and visible. You may add other material on the covers in addition. Copying with changes limited to the covers, as long as they preserve the title of the Document and satisfy these conditions, can be treated as verbatim copying in other respects. If the required texts for either cover are too voluminous to fit legibly, you should put the first ones listed (as many as fit reasonably) on the actual cover, and continue the rest onto adjacent pages. If you publish or distribute Opaque copies of the Document numbering more than 100, you must either include a machine-readable Transparent copy along with each Opaque copy, or state in or with each Opaque copy a publicly-accessible computer-network location containing a complete Transparent copy of the Document, free of added material, which the general network-using public has access to download anonymously at no charge using public-standard network protocols. If you use the latter option, you must take reasonably prudent steps, when you begin distribution of Opaque copies in quantity, to ensure that this Transparent copy will remain thus accessible at the stated location until at least one year after the last time you distribute an Opaque copy (directly or through your agents or retailers) of that edition to the public. It is requested, but not required, that you contact the authors of the Document well before redistributing any large number of copies, to give them a chance to provide you with an updated version of the Document. 4. MODIFICATIONS You may copy and distribute a Modified Version of the Document under the conditions of sections 2 and 3 above, provided that you release the Modified Version under precisely this License, with the Modified Version filling the role of the Document, thus licensing distribution and modification of the Modified Version to whoever possesses a copy of it. In addition, you must do these things in the Modified Version: A. Use in the Title Page (and on the covers, if any) a title distinct from that of the Document, and from those of previous versions (which should, if there were any, be listed in the History section of the Document). You may use the same title as a previous version if the original publisher of that version gives permission. B. List on the Title Page, as authors, one or more persons or entities responsible for authorship of the modifications in the Modified Version, together with at least five of the principal authors of the Document (all of its principal authors, if it has less than five). C. State on the Title page the name of the publisher of the Modified Version, as the publisher. D. Preserve all the copyright notices of the Document. E. Add an appropriate copyright notice for your modifications adjacent to the other copyright notices. F. Include, immediately after the copyright notices, a license notice giving the public permission to use the Modified Version under the terms of this License, in the form shown in the Addendum below. G. Preserve in that license notice the full lists of Invariant Sections and required Cover Texts given in the Document's license notice. H. Include an unaltered copy of this License. I. Preserve the section entitled "History", and its title, and add to it an item stating at least the title, year, new authors, and publisher of the Modified Version as given on the Title Page. If there is no section entitled "History" in the Document, create one stating the title, year, authors, and publisher of the Document as given on its Title Page, then add an item describing the Modified Version as stated in the previous sentence. J. Preserve the network location, if any, given in the Document for public access to a Transparent copy of the Document, and likewise the network locations given in the Document for previous versions it was based on. These may be placed in the "History" section. You may omit a network location for a work that was published at least four years before the Document itself, or if the original publisher of the version it refers to gives permission. K. In any section entitled "Acknowledgements" or "Dedications", preserve the section's title, and preserve in the section all the substance and tone of each of the contributor acknowledgements and/or dedications given therein. L. Preserve all the Invariant Sections of the Document, unaltered in their text and in their titles. Section numbers or the equivalent are not considered part of the section titles. M. Delete any section entitled "Endorsements". Such a section may not be included in the Modified Version. N. Do not retitle any existing section as "Endorsements" or to conflict in title with any Invariant Section. If the Modified Version includes new front-matter sections or appendices that qualify as Secondary Sections and contain no material copied from the Document, you may at your option designate some or all of these sections as invariant. To do this, add their titles to the list of Invariant Sections in the Modified Version's license notice. These titles must be distinct from any other section titles. You may add a section entitled "Endorsements", provided it contains nothing but endorsements of your Modified Version by various parties--for example, statements of peer review or that the text has been approved by an organization as the authoritative definition of a standard. You may add a passage of up to five words as a Front-Cover Text, and a passage of up to 25 words as a Back-Cover Text, to the end of the list of Cover Texts in the Modified Version. Only one passage of Front-Cover Text and one of Back-Cover Text may be added by (or through arrangements made by) any one entity. If the Document already includes a cover text for the same cover, previously added by you or by arrangement made by the same entity you are acting on behalf of, you may not add another; but you may replace the old one, on explicit permission from the previous publisher that added the old one. The author(s) and publisher(s) of the Document do not by this License give permission to use their names for publicity for or to assert or imply endorsement of any Modified Version. 5. COMBINING DOCUMENTS You may combine the Document with other documents released under this License, under the terms defined in section 4 above for modified versions, provided that you include in the combination all of the Invariant Sections of all of the original documents, unmodified, and list them all as Invariant Sections of your combined work in its license notice. The combined work need only contain one copy of this License, and multiple identical Invariant Sections may be replaced with a single copy. If there are multiple Invariant Sections with the same name but different contents, make the title of each such section unique by adding at the end of it, in parentheses, the name of the original author or publisher of that section if known, or else a unique number. Make the same adjustment to the section titles in the list of Invariant Sections in the license notice of the combined work. In the combination, you must combine any sections entitled "History" in the various original documents, forming one section entitled "History"; likewise combine any sections entitled "Acknowledgements", and any sections entitled "Dedications". You must delete all sections entitled "Endorsements." 6. COLLECTIONS OF DOCUMENTS You may make a collection consisting of the Document and other documents released under this License, and replace the individual copies of this License in the various documents with a single copy that is included in the collection, provided that you follow the rules of this License for verbatim copying of each of the documents in all other respects. You may extract a single document from such a collection, and distribute it individually under this License, provided you insert a copy of this License into the extracted document, and follow this License in all other respects regarding verbatim copying of that document. 7. AGGREGATION WITH INDEPENDENT WORKS A compilation of the Document or its derivatives with other separate and independent documents or works, in or on a volume of a storage or distribution medium, does not as a whole count as a Modified Version of the Document, provided no compilation copyright is claimed for the compilation. Such a compilation is called an "aggregate", and this License does not apply to the other self-contained works thus compiled with the Document, on account of their being thus compiled, if they are not themselves derivative works of the Document. If the Cover Text requirement of section 3 is applicable to these copies of the Document, then if the Document is less than one quarter of the entire aggregate, the Document's Cover Texts may be placed on covers that surround only the Document within the aggregate. Otherwise they must appear on covers around the whole aggregate. 8. TRANSLATION Translation is considered a kind of modification, so you may distribute translations of the Document under the terms of section 4. Replacing Invariant Sections with translations requires special permission from their copyright holders, but you may include translations of some or all Invariant Sections in addition to the original versions of these Invariant Sections. You may include a translation of this License provided that you also include the original English version of this License. In case of a disagreement between the translation and the original English version of this License, the original English version will prevail. 9. TERMINATION You may not copy, modify, sublicense, or distribute the Document except as expressly provided for under this License. Any other attempt to copy, modify, sublicense or distribute the Document is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance. 10. FUTURE REVISIONS OF THIS LICENSE The Free Software Foundation may publish new, revised versions of the GNU Free Documentation License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. See http://www.gnu.org/copyleft/. Each version of the License is given a distinguishing version number. If the Document specifies that a particular numbered version of this License "or any later version" applies to it, you have the option of following the terms and conditions either of that specified version or of any later version that has been published (not as a draft) by the Free Software Foundation. If the Document does not specify a version number of this License, you may choose any version ever published (not as a draft) by the Free Software Foundation. ADDENDUM: How to use this License for your documents To use this License in a document you have written, include a copy of the License in the document and put the following copyright and license notices just after the title page: Copyright (c) YEAR YOUR NAME. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; with the Invariant Sections being LIST THEIR TITLES, with the Front-Cover Texts being LIST, and with the Back-Cover Texts being LIST. A copy of the license is included in the section entitled "GNU Free Documentation License". If you have no Invariant Sections, write "with no Invariant Sections" instead of saying which ones are invariant. If you have no Front-Cover Texts, write "no Front-Cover Texts" instead of "Front-Cover Texts being LIST"; likewise for Back-Cover Texts. If your document contains nontrivial examples of program code, we recommend releasing these examples in parallel under your choice of free software license, such as the GNU General Public License, to permit their use in free software.