book_format.html

   1 <html>
   2 <head>
   3 <title>Polyglot book format</title>
   4 </head>
   5 <body>
   6 <h1>Polyglot book format</h1>
   7 The following description of the Polyglot book format is obtained
   8 by inspecting the freely available source code of Polyglot.
   9 <h2>A note on copyright</h2> I believe that the algorithm described
  10 below may be freely implemented by all GUIs, adapters and engines,
  11 including closed source ones. Polyglot itself is GPL but the GPL only
  12 covers actual code and not algorithms.
  13 <p>
  14 The array of 781 random numbers is of course taken from the Polyglot
  15 source code but I am pretty sure that a table of random numbers
  16 cannot be covered by copyright.
  17 <p>
  18 Look below for some sample code which is released
  19 in the public domain.
  20 <p>
  21 At the end of this document we discuss an extension of the Polyglot
  22 opening book format for Chess960. This extension is implemented in
  23 upcoming versions of xboard/winboard.
  24 <h2>Outline</h2>
  25 A Polyglot book is a series of "entries" of 16 bytes
  26 <p>
  27 <pre>
  28 key    uint64
  29 move   uint16
  30 weight uint16
  31 learn  uint32
  32 </pre>
  33 <p>
  34 All integers are stored highest byte first (regardless of size)
  35 <p>
  36 The entries are ordered according to key. Lowest key first.
  37 <p>
  38 <h2>key</h2>
  39 "key" is a 64 bit hash of a board position. Its computation
  40 is explained below.
  41 <p>
  42 The starting point is given by the following declaration
  43
  44 <pre>
  45
  46 #ifdef _MSC_VER
  47 #  define U64(u) (u##ui64)
  48 #else
  49 #  define U64(u) (u##ULL)
  50 #endif
  51
  52 const uint64 Random64[781] = {
  53    U64(0x9D39247E33776D41), U64(0x2AF7398005AAA5C7), U64(0x44DB015024623547), U64(0x9C15F73E62A76AE2),
  54    U64(0x75834465489C0C89), U64(0x3290AC3A203001BF), U64(0x0FBBAD1F61042279), U64(0xE83A908FF2FB60CA),
  55    U64(0x0D7E765D58755C10), U64(0x1A083822CEAFE02D), U64(0x9605D5F0E25EC3B0), U64(0xD021FF5CD13A2ED5),
  56    U64(0x40BDF15D4A672E32), U64(0x011355146FD56395), U64(0x5DB4832046F3D9E5), U64(0x239F8B2D7FF719CC),
  57    U64(0x05D1A1AE85B49AA1), U64(0x679F848F6E8FC971), U64(0x7449BBFF801FED0B), U64(0x7D11CDB1C3B7ADF0),
  58    U64(0x82C7709E781EB7CC), U64(0xF3218F1C9510786C), U64(0x331478F3AF51BBE6), U64(0x4BB38DE5E7219443),
  59    U64(0xAA649C6EBCFD50FC), U64(0x8DBD98A352AFD40B), U64(0x87D2074B81D79217), U64(0x19F3C751D3E92AE1),
  60    U64(0xB4AB30F062B19ABF), U64(0x7B0500AC42047AC4), U64(0xC9452CA81A09D85D), U64(0x24AA6C514DA27500),
  61    U64(0x4C9F34427501B447), U64(0x14A68FD73C910841), U64(0xA71B9B83461CBD93), U64(0x03488B95B0F1850F),
  62    U64(0x637B2B34FF93C040), U64(0x09D1BC9A3DD90A94), U64(0x3575668334A1DD3B), U64(0x735E2B97A4C45A23),
  63    U64(0x18727070F1BD400B), U64(0x1FCBACD259BF02E7), U64(0xD310A7C2CE9B6555), U64(0xBF983FE0FE5D8244),
  64    U64(0x9F74D14F7454A824), U64(0x51EBDC4AB9BA3035), U64(0x5C82C505DB9AB0FA), U64(0xFCF7FE8A3430B241),
  65    U64(0x3253A729B9BA3DDE), U64(0x8C74C368081B3075), U64(0xB9BC6C87167C33E7), U64(0x7EF48F2B83024E20),
  66    U64(0x11D505D4C351BD7F), U64(0x6568FCA92C76A243), U64(0x4DE0B0F40F32A7B8), U64(0x96D693460CC37E5D),
  67    U64(0x42E240CB63689F2F), U64(0x6D2BDCDAE2919661), U64(0x42880B0236E4D951), U64(0x5F0F4A5898171BB6),
  68    U64(0x39F890F579F92F88), U64(0x93C5B5F47356388B), U64(0x63DC359D8D231B78), U64(0xEC16CA8AEA98AD76),
  69    U64(0x5355F900C2A82DC7), U64(0x07FB9F855A997142), U64(0x5093417AA8A7ED5E), U64(0x7BCBC38DA25A7F3C),
  70    U64(0x19FC8A768CF4B6D4), U64(0x637A7780DECFC0D9), U64(0x8249A47AEE0E41F7), U64(0x79AD695501E7D1E8),
  71    U64(0x14ACBAF4777D5776), U64(0xF145B6BECCDEA195), U64(0xDABF2AC8201752FC), U64(0x24C3C94DF9C8D3F6),
  72    U64(0xBB6E2924F03912EA), U64(0x0CE26C0B95C980D9), U64(0xA49CD132BFBF7CC4), U64(0xE99D662AF4243939),
  73    U64(0x27E6AD7891165C3F), U64(0x8535F040B9744FF1), U64(0x54B3F4FA5F40D873), U64(0x72B12C32127FED2B),
  74    U64(0xEE954D3C7B411F47), U64(0x9A85AC909A24EAA1), U64(0x70AC4CD9F04F21F5), U64(0xF9B89D3E99A075C2),
  75    U64(0x87B3E2B2B5C907B1), U64(0xA366E5B8C54F48B8), U64(0xAE4A9346CC3F7CF2), U64(0x1920C04D47267BBD),
  76    U64(0x87BF02C6B49E2AE9), U64(0x092237AC237F3859), U64(0xFF07F64EF8ED14D0), U64(0x8DE8DCA9F03CC54E),
  77    U64(0x9C1633264DB49C89), U64(0xB3F22C3D0B0B38ED), U64(0x390E5FB44D01144B), U64(0x5BFEA5B4712768E9),
  78    U64(0x1E1032911FA78984), U64(0x9A74ACB964E78CB3), U64(0x4F80F7A035DAFB04), U64(0x6304D09A0B3738C4),
  79    U64(0x2171E64683023A08), U64(0x5B9B63EB9CEFF80C), U64(0x506AACF489889342), U64(0x1881AFC9A3A701D6),
  80    U64(0x6503080440750644), U64(0xDFD395339CDBF4A7), U64(0xEF927DBCF00C20F2), U64(0x7B32F7D1E03680EC),
  81    U64(0xB9FD7620E7316243), U64(0x05A7E8A57DB91B77), U64(0xB5889C6E15630A75), U64(0x4A750A09CE9573F7),
  82    U64(0xCF464CEC899A2F8A), U64(0xF538639CE705B824), U64(0x3C79A0FF5580EF7F), U64(0xEDE6C87F8477609D),
  83    U64(0x799E81F05BC93F31), U64(0x86536B8CF3428A8C), U64(0x97D7374C60087B73), U64(0xA246637CFF328532),
  84    U64(0x043FCAE60CC0EBA0), U64(0x920E449535DD359E), U64(0x70EB093B15B290CC), U64(0x73A1921916591CBD),
  85    U64(0x56436C9FE1A1AA8D), U64(0xEFAC4B70633B8F81), U64(0xBB215798D45DF7AF), U64(0x45F20042F24F1768),
  86    U64(0x930F80F4E8EB7462), U64(0xFF6712FFCFD75EA1), U64(0xAE623FD67468AA70), U64(0xDD2C5BC84BC8D8FC),
  87    U64(0x7EED120D54CF2DD9), U64(0x22FE545401165F1C), U64(0xC91800E98FB99929), U64(0x808BD68E6AC10365),
  88    U64(0xDEC468145B7605F6), U64(0x1BEDE3A3AEF53302), U64(0x43539603D6C55602), U64(0xAA969B5C691CCB7A),
  89    U64(0xA87832D392EFEE56), U64(0x65942C7B3C7E11AE), U64(0xDED2D633CAD004F6), U64(0x21F08570F420E565),
  90    U64(0xB415938D7DA94E3C), U64(0x91B859E59ECB6350), U64(0x10CFF333E0ED804A), U64(0x28AED140BE0BB7DD),
  91    U64(0xC5CC1D89724FA456), U64(0x5648F680F11A2741), U64(0x2D255069F0B7DAB3), U64(0x9BC5A38EF729ABD4),
  92    U64(0xEF2F054308F6A2BC), U64(0xAF2042F5CC5C2858), U64(0x480412BAB7F5BE2A), U64(0xAEF3AF4A563DFE43),
  93    U64(0x19AFE59AE451497F), U64(0x52593803DFF1E840), U64(0xF4F076E65F2CE6F0), U64(0x11379625747D5AF3),
  94    U64(0xBCE5D2248682C115), U64(0x9DA4243DE836994F), U64(0x066F70B33FE09017), U64(0x4DC4DE189B671A1C),
  95    U64(0x51039AB7712457C3), U64(0xC07A3F80C31FB4B4), U64(0xB46EE9C5E64A6E7C), U64(0xB3819A42ABE61C87),
  96    U64(0x21A007933A522A20), U64(0x2DF16F761598AA4F), U64(0x763C4A1371B368FD), U64(0xF793C46702E086A0),
  97    U64(0xD7288E012AEB8D31), U64(0xDE336A2A4BC1C44B), U64(0x0BF692B38D079F23), U64(0x2C604A7A177326B3),
  98    U64(0x4850E73E03EB6064), U64(0xCFC447F1E53C8E1B), U64(0xB05CA3F564268D99), U64(0x9AE182C8BC9474E8),
  99    U64(0xA4FC4BD4FC5558CA), U64(0xE755178D58FC4E76), U64(0x69B97DB1A4C03DFE), U64(0xF9B5B7C4ACC67C96),
 100    U64(0xFC6A82D64B8655FB), U64(0x9C684CB6C4D24417), U64(0x8EC97D2917456ED0), U64(0x6703DF9D2924E97E),
 101    U64(0xC547F57E42A7444E), U64(0x78E37644E7CAD29E), U64(0xFE9A44E9362F05FA), U64(0x08BD35CC38336615),
 102    U64(0x9315E5EB3A129ACE), U64(0x94061B871E04DF75), U64(0xDF1D9F9D784BA010), U64(0x3BBA57B68871B59D),
 103    U64(0xD2B7ADEEDED1F73F), U64(0xF7A255D83BC373F8), U64(0xD7F4F2448C0CEB81), U64(0xD95BE88CD210FFA7),
 104    U64(0x336F52F8FF4728E7), U64(0xA74049DAC312AC71), U64(0xA2F61BB6E437FDB5), U64(0x4F2A5CB07F6A35B3),
 105    U64(0x87D380BDA5BF7859), U64(0x16B9F7E06C453A21), U64(0x7BA2484C8A0FD54E), U64(0xF3A678CAD9A2E38C),
 106    U64(0x39B0BF7DDE437BA2), U64(0xFCAF55C1BF8A4424), U64(0x18FCF680573FA594), U64(0x4C0563B89F495AC3),
 107    U64(0x40E087931A00930D), U64(0x8CFFA9412EB642C1), U64(0x68CA39053261169F), U64(0x7A1EE967D27579E2),
 108    U64(0x9D1D60E5076F5B6F), U64(0x3810E399B6F65BA2), U64(0x32095B6D4AB5F9B1), U64(0x35CAB62109DD038A),
 109    U64(0xA90B24499FCFAFB1), U64(0x77A225A07CC2C6BD), U64(0x513E5E634C70E331), U64(0x4361C0CA3F692F12),
 110    U64(0xD941ACA44B20A45B), U64(0x528F7C8602C5807B), U64(0x52AB92BEB9613989), U64(0x9D1DFA2EFC557F73),
 111    U64(0x722FF175F572C348), U64(0x1D1260A51107FE97), U64(0x7A249A57EC0C9BA2), U64(0x04208FE9E8F7F2D6),
 112    U64(0x5A110C6058B920A0), U64(0x0CD9A497658A5698), U64(0x56FD23C8F9715A4C), U64(0x284C847B9D887AAE),
 113    U64(0x04FEABFBBDB619CB), U64(0x742E1E651C60BA83), U64(0x9A9632E65904AD3C), U64(0x881B82A13B51B9E2),
 114    U64(0x506E6744CD974924), U64(0xB0183DB56FFC6A79), U64(0x0ED9B915C66ED37E), U64(0x5E11E86D5873D484),
 115    U64(0xF678647E3519AC6E), U64(0x1B85D488D0F20CC5), U64(0xDAB9FE6525D89021), U64(0x0D151D86ADB73615),
 116    U64(0xA865A54EDCC0F019), U64(0x93C42566AEF98FFB), U64(0x99E7AFEABE000731), U64(0x48CBFF086DDF285A),
 117    U64(0x7F9B6AF1EBF78BAF), U64(0x58627E1A149BBA21), U64(0x2CD16E2ABD791E33), U64(0xD363EFF5F0977996),
 118    U64(0x0CE2A38C344A6EED), U64(0x1A804AADB9CFA741), U64(0x907F30421D78C5DE), U64(0x501F65EDB3034D07),
 119    U64(0x37624AE5A48FA6E9), U64(0x957BAF61700CFF4E), U64(0x3A6C27934E31188A), U64(0xD49503536ABCA345),
 120    U64(0x088E049589C432E0), U64(0xF943AEE7FEBF21B8), U64(0x6C3B8E3E336139D3), U64(0x364F6FFA464EE52E),
 121    U64(0xD60F6DCEDC314222), U64(0x56963B0DCA418FC0), U64(0x16F50EDF91E513AF), U64(0xEF1955914B609F93),
 122    U64(0x565601C0364E3228), U64(0xECB53939887E8175), U64(0xBAC7A9A18531294B), U64(0xB344C470397BBA52),
 123    U64(0x65D34954DAF3CEBD), U64(0xB4B81B3FA97511E2), U64(0xB422061193D6F6A7), U64(0x071582401C38434D),
 124    U64(0x7A13F18BBEDC4FF5), U64(0xBC4097B116C524D2), U64(0x59B97885E2F2EA28), U64(0x99170A5DC3115544),
 125    U64(0x6F423357E7C6A9F9), U64(0x325928EE6E6F8794), U64(0xD0E4366228B03343), U64(0x565C31F7DE89EA27),
 126    U64(0x30F5611484119414), U64(0xD873DB391292ED4F), U64(0x7BD94E1D8E17DEBC), U64(0xC7D9F16864A76E94),
 127    U64(0x947AE053EE56E63C), U64(0xC8C93882F9475F5F), U64(0x3A9BF55BA91F81CA), U64(0xD9A11FBB3D9808E4),
 128    U64(0x0FD22063EDC29FCA), U64(0xB3F256D8ACA0B0B9), U64(0xB03031A8B4516E84), U64(0x35DD37D5871448AF),
 129    U64(0xE9F6082B05542E4E), U64(0xEBFAFA33D7254B59), U64(0x9255ABB50D532280), U64(0xB9AB4CE57F2D34F3),
 130    U64(0x693501D628297551), U64(0xC62C58F97DD949BF), U64(0xCD454F8F19C5126A), U64(0xBBE83F4ECC2BDECB),
 131    U64(0xDC842B7E2819E230), U64(0xBA89142E007503B8), U64(0xA3BC941D0A5061CB), U64(0xE9F6760E32CD8021),
 132    U64(0x09C7E552BC76492F), U64(0x852F54934DA55CC9), U64(0x8107FCCF064FCF56), U64(0x098954D51FFF6580),
 133    U64(0x23B70EDB1955C4BF), U64(0xC330DE426430F69D), U64(0x4715ED43E8A45C0A), U64(0xA8D7E4DAB780A08D),
 134    U64(0x0572B974F03CE0BB), U64(0xB57D2E985E1419C7), U64(0xE8D9ECBE2CF3D73F), U64(0x2FE4B17170E59750),
 135    U64(0x11317BA87905E790), U64(0x7FBF21EC8A1F45EC), U64(0x1725CABFCB045B00), U64(0x964E915CD5E2B207),
 136    U64(0x3E2B8BCBF016D66D), U64(0xBE7444E39328A0AC), U64(0xF85B2B4FBCDE44B7), U64(0x49353FEA39BA63B1),
 137    U64(0x1DD01AAFCD53486A), U64(0x1FCA8A92FD719F85), U64(0xFC7C95D827357AFA), U64(0x18A6A990C8B35EBD),
 138    U64(0xCCCB7005C6B9C28D), U64(0x3BDBB92C43B17F26), U64(0xAA70B5B4F89695A2), U64(0xE94C39A54A98307F),
 139    U64(0xB7A0B174CFF6F36E), U64(0xD4DBA84729AF48AD), U64(0x2E18BC1AD9704A68), U64(0x2DE0966DAF2F8B1C),
 140    U64(0xB9C11D5B1E43A07E), U64(0x64972D68DEE33360), U64(0x94628D38D0C20584), U64(0xDBC0D2B6AB90A559),
 141    U64(0xD2733C4335C6A72F), U64(0x7E75D99D94A70F4D), U64(0x6CED1983376FA72B), U64(0x97FCAACBF030BC24),
 142    U64(0x7B77497B32503B12), U64(0x8547EDDFB81CCB94), U64(0x79999CDFF70902CB), U64(0xCFFE1939438E9B24),
 143    U64(0x829626E3892D95D7), U64(0x92FAE24291F2B3F1), U64(0x63E22C147B9C3403), U64(0xC678B6D860284A1C),
 144    U64(0x5873888850659AE7), U64(0x0981DCD296A8736D), U64(0x9F65789A6509A440), U64(0x9FF38FED72E9052F),
 145    U64(0xE479EE5B9930578C), U64(0xE7F28ECD2D49EECD), U64(0x56C074A581EA17FE), U64(0x5544F7D774B14AEF),
 146    U64(0x7B3F0195FC6F290F), U64(0x12153635B2C0CF57), U64(0x7F5126DBBA5E0CA7), U64(0x7A76956C3EAFB413),
 147    U64(0x3D5774A11D31AB39), U64(0x8A1B083821F40CB4), U64(0x7B4A38E32537DF62), U64(0x950113646D1D6E03),
 148    U64(0x4DA8979A0041E8A9), U64(0x3BC36E078F7515D7), U64(0x5D0A12F27AD310D1), U64(0x7F9D1A2E1EBE1327),
 149    U64(0xDA3A361B1C5157B1), U64(0xDCDD7D20903D0C25), U64(0x36833336D068F707), U64(0xCE68341F79893389),
 150    U64(0xAB9090168DD05F34), U64(0x43954B3252DC25E5), U64(0xB438C2B67F98E5E9), U64(0x10DCD78E3851A492),
 151    U64(0xDBC27AB5447822BF), U64(0x9B3CDB65F82CA382), U64(0xB67B7896167B4C84), U64(0xBFCED1B0048EAC50),
 152    U64(0xA9119B60369FFEBD), U64(0x1FFF7AC80904BF45), U64(0xAC12FB171817EEE7), U64(0xAF08DA9177DDA93D),
 153    U64(0x1B0CAB936E65C744), U64(0xB559EB1D04E5E932), U64(0xC37B45B3F8D6F2BA), U64(0xC3A9DC228CAAC9E9),
 154    U64(0xF3B8B6675A6507FF), U64(0x9FC477DE4ED681DA), U64(0x67378D8ECCEF96CB), U64(0x6DD856D94D259236),
 155    U64(0xA319CE15B0B4DB31), U64(0x073973751F12DD5E), U64(0x8A8E849EB32781A5), U64(0xE1925C71285279F5),
 156    U64(0x74C04BF1790C0EFE), U64(0x4DDA48153C94938A), U64(0x9D266D6A1CC0542C), U64(0x7440FB816508C4FE),
 157    U64(0x13328503DF48229F), U64(0xD6BF7BAEE43CAC40), U64(0x4838D65F6EF6748F), U64(0x1E152328F3318DEA),
 158    U64(0x8F8419A348F296BF), U64(0x72C8834A5957B511), U64(0xD7A023A73260B45C), U64(0x94EBC8ABCFB56DAE),
 159    U64(0x9FC10D0F989993E0), U64(0xDE68A2355B93CAE6), U64(0xA44CFE79AE538BBE), U64(0x9D1D84FCCE371425),
 160    U64(0x51D2B1AB2DDFB636), U64(0x2FD7E4B9E72CD38C), U64(0x65CA5B96B7552210), U64(0xDD69A0D8AB3B546D),
 161    U64(0x604D51B25FBF70E2), U64(0x73AA8A564FB7AC9E), U64(0x1A8C1E992B941148), U64(0xAAC40A2703D9BEA0),
 162    U64(0x764DBEAE7FA4F3A6), U64(0x1E99B96E70A9BE8B), U64(0x2C5E9DEB57EF4743), U64(0x3A938FEE32D29981),
 163    U64(0x26E6DB8FFDF5ADFE), U64(0x469356C504EC9F9D), U64(0xC8763C5B08D1908C), U64(0x3F6C6AF859D80055),
 164    U64(0x7F7CC39420A3A545), U64(0x9BFB227EBDF4C5CE), U64(0x89039D79D6FC5C5C), U64(0x8FE88B57305E2AB6),
 165    U64(0xA09E8C8C35AB96DE), U64(0xFA7E393983325753), U64(0xD6B6D0ECC617C699), U64(0xDFEA21EA9E7557E3),
 166    U64(0xB67C1FA481680AF8), U64(0xCA1E3785A9E724E5), U64(0x1CFC8BED0D681639), U64(0xD18D8549D140CAEA),
 167    U64(0x4ED0FE7E9DC91335), U64(0xE4DBF0634473F5D2), U64(0x1761F93A44D5AEFE), U64(0x53898E4C3910DA55),
 168    U64(0x734DE8181F6EC39A), U64(0x2680B122BAA28D97), U64(0x298AF231C85BAFAB), U64(0x7983EED3740847D5),
 169    U64(0x66C1A2A1A60CD889), U64(0x9E17E49642A3E4C1), U64(0xEDB454E7BADC0805), U64(0x50B704CAB602C329),
 170    U64(0x4CC317FB9CDDD023), U64(0x66B4835D9EAFEA22), U64(0x219B97E26FFC81BD), U64(0x261E4E4C0A333A9D),
 171    U64(0x1FE2CCA76517DB90), U64(0xD7504DFA8816EDBB), U64(0xB9571FA04DC089C8), U64(0x1DDC0325259B27DE),
 172    U64(0xCF3F4688801EB9AA), U64(0xF4F5D05C10CAB243), U64(0x38B6525C21A42B0E), U64(0x36F60E2BA4FA6800),
 173    U64(0xEB3593803173E0CE), U64(0x9C4CD6257C5A3603), U64(0xAF0C317D32ADAA8A), U64(0x258E5A80C7204C4B),
 174    U64(0x8B889D624D44885D), U64(0xF4D14597E660F855), U64(0xD4347F66EC8941C3), U64(0xE699ED85B0DFB40D),
 175    U64(0x2472F6207C2D0484), U64(0xC2A1E7B5B459AEB5), U64(0xAB4F6451CC1D45EC), U64(0x63767572AE3D6174),
 176    U64(0xA59E0BD101731A28), U64(0x116D0016CB948F09), U64(0x2CF9C8CA052F6E9F), U64(0x0B090A7560A968E3),
 177    U64(0xABEEDDB2DDE06FF1), U64(0x58EFC10B06A2068D), U64(0xC6E57A78FBD986E0), U64(0x2EAB8CA63CE802D7),
 178    U64(0x14A195640116F336), U64(0x7C0828DD624EC390), U64(0xD74BBE77E6116AC7), U64(0x804456AF10F5FB53),
 179    U64(0xEBE9EA2ADF4321C7), U64(0x03219A39EE587A30), U64(0x49787FEF17AF9924), U64(0xA1E9300CD8520548),
 180    U64(0x5B45E522E4B1B4EF), U64(0xB49C3B3995091A36), U64(0xD4490AD526F14431), U64(0x12A8F216AF9418C2),
 181    U64(0x001F837CC7350524), U64(0x1877B51E57A764D5), U64(0xA2853B80F17F58EE), U64(0x993E1DE72D36D310),
 182    U64(0xB3598080CE64A656), U64(0x252F59CF0D9F04BB), U64(0xD23C8E176D113600), U64(0x1BDA0492E7E4586E),
 183    U64(0x21E0BD5026C619BF), U64(0x3B097ADAF088F94E), U64(0x8D14DEDB30BE846E), U64(0xF95CFFA23AF5F6F4),
 184    U64(0x3871700761B3F743), U64(0xCA672B91E9E4FA16), U64(0x64C8E531BFF53B55), U64(0x241260ED4AD1E87D),
 185    U64(0x106C09B972D2E822), U64(0x7FBA195410E5CA30), U64(0x7884D9BC6CB569D8), U64(0x0647DFEDCD894A29),
 186    U64(0x63573FF03E224774), U64(0x4FC8E9560F91B123), U64(0x1DB956E450275779), U64(0xB8D91274B9E9D4FB),
 187    U64(0xA2EBEE47E2FBFCE1), U64(0xD9F1F30CCD97FB09), U64(0xEFED53D75FD64E6B), U64(0x2E6D02C36017F67F),
 188    U64(0xA9AA4D20DB084E9B), U64(0xB64BE8D8B25396C1), U64(0x70CB6AF7C2D5BCF0), U64(0x98F076A4F7A2322E),
 189    U64(0xBF84470805E69B5F), U64(0x94C3251F06F90CF3), U64(0x3E003E616A6591E9), U64(0xB925A6CD0421AFF3),
 190    U64(0x61BDD1307C66E300), U64(0xBF8D5108E27E0D48), U64(0x240AB57A8B888B20), U64(0xFC87614BAF287E07),
 191    U64(0xEF02CDD06FFDB432), U64(0xA1082C0466DF6C0A), U64(0x8215E577001332C8), U64(0xD39BB9C3A48DB6CF),
 192    U64(0x2738259634305C14), U64(0x61CF4F94C97DF93D), U64(0x1B6BACA2AE4E125B), U64(0x758F450C88572E0B),
 193    U64(0x959F587D507A8359), U64(0xB063E962E045F54D), U64(0x60E8ED72C0DFF5D1), U64(0x7B64978555326F9F),
 194    U64(0xFD080D236DA814BA), U64(0x8C90FD9B083F4558), U64(0x106F72FE81E2C590), U64(0x7976033A39F7D952),
 195    U64(0xA4EC0132764CA04B), U64(0x733EA705FAE4FA77), U64(0xB4D8F77BC3E56167), U64(0x9E21F4F903B33FD9),
 196    U64(0x9D765E419FB69F6D), U64(0xD30C088BA61EA5EF), U64(0x5D94337FBFAF7F5B), U64(0x1A4E4822EB4D7A59),
 197    U64(0x6FFE73E81B637FB3), U64(0xDDF957BC36D8B9CA), U64(0x64D0E29EEA8838B3), U64(0x08DD9BDFD96B9F63),
 198    U64(0x087E79E5A57D1D13), U64(0xE328E230E3E2B3FB), U64(0x1C2559E30F0946BE), U64(0x720BF5F26F4D2EAA),
 199    U64(0xB0774D261CC609DB), U64(0x443F64EC5A371195), U64(0x4112CF68649A260E), U64(0xD813F2FAB7F5C5CA),
 200    U64(0x660D3257380841EE), U64(0x59AC2C7873F910A3), U64(0xE846963877671A17), U64(0x93B633ABFA3469F8),
 201    U64(0xC0C0F5A60EF4CDCF), U64(0xCAF21ECD4377B28C), U64(0x57277707199B8175), U64(0x506C11B9D90E8B1D),
 202    U64(0xD83CC2687A19255F), U64(0x4A29C6465A314CD1), U64(0xED2DF21216235097), U64(0xB5635C95FF7296E2),
 203    U64(0x22AF003AB672E811), U64(0x52E762596BF68235), U64(0x9AEBA33AC6ECC6B0), U64(0x944F6DE09134DFB6),
 204    U64(0x6C47BEC883A7DE39), U64(0x6AD047C430A12104), U64(0xA5B1CFDBA0AB4067), U64(0x7C45D833AFF07862),
 205    U64(0x5092EF950A16DA0B), U64(0x9338E69C052B8E7B), U64(0x455A4B4CFE30E3F5), U64(0x6B02E63195AD0CF8),
 206    U64(0x6B17B224BAD6BF27), U64(0xD1E0CCD25BB9C169), U64(0xDE0C89A556B9AE70), U64(0x50065E535A213CF6),
 207    U64(0x9C1169FA2777B874), U64(0x78EDEFD694AF1EED), U64(0x6DC93D9526A50E68), U64(0xEE97F453F06791ED),
 208    U64(0x32AB0EDB696703D3), U64(0x3A6853C7E70757A7), U64(0x31865CED6120F37D), U64(0x67FEF95D92607890),
 209    U64(0x1F2B1D1F15F6DC9C), U64(0xB69E38A8965C6B65), U64(0xAA9119FF184CCCF4), U64(0xF43C732873F24C13),
 210    U64(0xFB4A3D794A9A80D2), U64(0x3550C2321FD6109C), U64(0x371F77E76BB8417E), U64(0x6BFA9AAE5EC05779),
 211    U64(0xCD04F3FF001A4778), U64(0xE3273522064480CA), U64(0x9F91508BFFCFC14A), U64(0x049A7F41061A9E60),
 212    U64(0xFCB6BE43A9F2FE9B), U64(0x08DE8A1C7797DA9B), U64(0x8F9887E6078735A1), U64(0xB5B4071DBFC73A66),
 213    U64(0x230E343DFBA08D33), U64(0x43ED7F5A0FAE657D), U64(0x3A88A0FBBCB05C63), U64(0x21874B8B4D2DBC4F),
 214    U64(0x1BDEA12E35F6A8C9), U64(0x53C065C6C8E63528), U64(0xE34A1D250E7A8D6B), U64(0xD6B04D3B7651DD7E),
 215    U64(0x5E90277E7CB39E2D), U64(0x2C046F22062DC67D), U64(0xB10BB459132D0A26), U64(0x3FA9DDFB67E2F199),
 216    U64(0x0E09B88E1914F7AF), U64(0x10E8B35AF3EEAB37), U64(0x9EEDECA8E272B933), U64(0xD4C718BC4AE8AE5F),
 217    U64(0x81536D601170FC20), U64(0x91B534F885818A06), U64(0xEC8177F83F900978), U64(0x190E714FADA5156E),
 218    U64(0xB592BF39B0364963), U64(0x89C350C893AE7DC1), U64(0xAC042E70F8B383F2), U64(0xB49B52E587A1EE60),
 219    U64(0xFB152FE3FF26DA89), U64(0x3E666E6F69AE2C15), U64(0x3B544EBE544C19F9), U64(0xE805A1E290CF2456),
 220    U64(0x24B33C9D7ED25117), U64(0xE74733427B72F0C1), U64(0x0A804D18B7097475), U64(0x57E3306D881EDB4F),
 221    U64(0x4AE7D6A36EB5DBCB), U64(0x2D8D5432157064C8), U64(0xD1E649DE1E7F268B), U64(0x8A328A1CEDFE552C),
 222    U64(0x07A3AEC79624C7DA), U64(0x84547DDC3E203C94), U64(0x990A98FD5071D263), U64(0x1A4FF12616EEFC89),
 223    U64(0xF6F7FD1431714200), U64(0x30C05B1BA332F41C), U64(0x8D2636B81555A786), U64(0x46C9FEB55D120902),
 224    U64(0xCCEC0A73B49C9921), U64(0x4E9D2827355FC492), U64(0x19EBB029435DCB0F), U64(0x4659D2B743848A2C),
 225    U64(0x963EF2C96B33BE31), U64(0x74F85198B05A2E7D), U64(0x5A0F544DD2B1FB18), U64(0x03727073C2E134B1),
 226    U64(0xC7F6AA2DE59AEA61), U64(0x352787BAA0D7C22F), U64(0x9853EAB63B5E0B35), U64(0xABBDCDD7ED5C0860),
 227    U64(0xCF05DAF5AC8D77B0), U64(0x49CAD48CEBF4A71E), U64(0x7A4C10EC2158C4A6), U64(0xD9E92AA246BF719E),
 228    U64(0x13AE978D09FE5557), U64(0x730499AF921549FF), U64(0x4E4B705B92903BA4), U64(0xFF577222C14F0A3A),
 229    U64(0x55B6344CF97AAFAE), U64(0xB862225B055B6960), U64(0xCAC09AFBDDD2CDB4), U64(0xDAF8E9829FE96B5F),
 230    U64(0xB5FDFC5D3132C498), U64(0x310CB380DB6F7503), U64(0xE87FBB46217A360E), U64(0x2102AE466EBB1148),
 231    U64(0xF8549E1A3AA5E00D), U64(0x07A69AFDCC42261A), U64(0xC4C118BFE78FEAAE), U64(0xF9F4892ED96BD438),
 232    U64(0x1AF3DBE25D8F45DA), U64(0xF5B4B0B0D2DEEEB4), U64(0x962ACEEFA82E1C84), U64(0x046E3ECAAF453CE9),
 233    U64(0xF05D129681949A4C), U64(0x964781CE734B3C84), U64(0x9C2ED44081CE5FBD), U64(0x522E23F3925E319E),
 234    U64(0x177E00F9FC32F791), U64(0x2BC60A63A6F3B3F2), U64(0x222BBFAE61725606), U64(0x486289DDCC3D6780),
 235    U64(0x7DC7785B8EFDFC80), U64(0x8AF38731C02BA980), U64(0x1FAB64EA29A2DDF7), U64(0xE4D9429322CD065A),
 236    U64(0x9DA058C67844F20C), U64(0x24C0E332B70019B0), U64(0x233003B5A6CFE6AD), U64(0xD586BD01C5C217F6),
 237    U64(0x5E5637885F29BC2B), U64(0x7EBA726D8C94094B), U64(0x0A56A5F0BFE39272), U64(0xD79476A84EE20D06),
 238    U64(0x9E4C1269BAA4BF37), U64(0x17EFEE45B0DEE640), U64(0x1D95B0A5FCF90BC6), U64(0x93CBE0B699C2585D),
 239    U64(0x65FA4F227A2B6D79), U64(0xD5F9E858292504D5), U64(0xC2B5A03F71471A6F), U64(0x59300222B4561E00),
 240    U64(0xCE2F8642CA0712DC), U64(0x7CA9723FBB2E8988), U64(0x2785338347F2BA08), U64(0xC61BB3A141E50E8C),
 241    U64(0x150F361DAB9DEC26), U64(0x9F6A419D382595F4), U64(0x64A53DC924FE7AC9), U64(0x142DE49FFF7A7C3D),
 242    U64(0x0C335248857FA9E7), U64(0x0A9C32D5EAE45305), U64(0xE6C42178C4BBB92E), U64(0x71F1CE2490D20B07),
 243    U64(0xF1BCC3D275AFE51A), U64(0xE728E8C83C334074), U64(0x96FBF83A12884624), U64(0x81A1549FD6573DA5),
 244    U64(0x5FA7867CAF35E149), U64(0x56986E2EF3ED091B), U64(0x917F1DD5F8886C61), U64(0xD20D8C88C8FFE65F),
 245    U64(0x31D71DCE64B2C310), U64(0xF165B587DF898190), U64(0xA57E6339DD2CF3A0), U64(0x1EF6E6DBB1961EC9),
 246    U64(0x70CC73D90BC26E24), U64(0xE21A6B35DF0C3AD7), U64(0x003A93D8B2806962), U64(0x1C99DED33CB890A1),
 247    U64(0xCF3145DE0ADD4289), U64(0xD0E4427A5514FB72), U64(0x77C621CC9FB3A483), U64(0x67A34DAC4356550B),
 248    U64(0xF8D626AAAF278509),
 249 };
 250 </pre>
 251 The array Random64 is in fact a concatenation of four subarrays
 252 <pre>
 253 RandomPiece     (offset:   0, length: 768)
 254 RandomCastle    (offset: 768, length:   4)
 255 RandomEnPassant (offset: 772, length:   8)
 256 RandomTurn      (offset: 780, length:   1)
 257 </pre>
 258 "key" is a so-called "Zobrist hash function". In other words it is
 259 the <b>exclusive or</b> of entries taken from each of the
 260 subarrays described above.
 261
 262 Thus we have
 263 <pre>
 264 key=piece^castle^enpassant^turn;
 265 </pre>
 266
 267 <h3>piece</h3>
 268 "piece" is the exclusive or of entries from
 269 RandomPiece, one for each piece on the board. The offset of the entry
 270 in RandomPiece corresponding to a piece is computed as follows.
 271 <pre>
 272 offset_piece=64*kind_of_piece+8*row+file;
 273 </pre>
 274 "row" and "file" are counted from 0 to 7. With this convention one has
 275 <pre>
 276 square      file   row
 277 ======================
 278 a1             0     0
 279 h1             7     0
 280 a8             0     7
 281 h8             7     7
 282 </pre>
 283
 284 "kind_of_piece" is encoded as follows
 285 <pre>
 286 black pawn    0
 287 white pawn    1
 288 black knight  2
 289 white knight  3
 290 black bishop  4
 291 white bishop  5
 292 black rook    6
 293 white rook    7
 294 black queen   8
 295 white queen   9
 296 black king   10
 297 white king   11
 298 </pre>
 299
 300 <h3>castle</h3>
 301 "castle" is the exclusive or of entries from
 302 RandomCastle. The offsets are computed as follows.
 303 <pre>
 304 white can castle short     0
 305 white can castle long      1
 306 black can castle short     2
 307 black can castle long      3
 308 </pre>
 309 If none of these flags apply then castle=0.
 310 <p>
 311 Note that these flags represent "potential future castling" as in the
 312 FEN standard even if such castling is currently not possible due to blocking
 313 pieces or enemy attacks.
 314 <p>
 315 In other words these flags are all true in the starting position and are
 316 only updated after the appropriate king, rook or castling moves.
 317
 318
 319
 320 <h3>en passant</h3> If the opponent has performed a double pawn push
 321 and there is now a pawn next to it belonging to the player to move then
 322 "enpassant" is the entry from RandomEnPassant whose offset is the file
 323 of the pushed pawn (counted from 0(=a) to 7(=h)). If this does not
 324 apply then enpassant=0.
 325 <p>
 326 Note that this is <b>different from the FEN standard</b>. In the FEN standard
 327 the presence of an "en passant target square" after a double pawn push
 328 is unconditional.
 329 <p> Also note that it is irrelevant if the potential en passant
 330 capturing move is legal or not (examples where it would not be legal are
 331 when the capturing pawn is pinned or when the double pawn push was a
 332 discovered check).
 333
 334
 335 <h3>turn</h3>
 336 If white is to move then "turn" is the sole entry of RandomTurn.
 337 If not then "turn" is zero.
 338
 339 <h3>Test data</h3>
 340 Here are some test keys. They were computed using Toga II
 341 and checked using the algorithm described above.
 342
 343 <pre>
 344 starting position
 345 FEN=rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
 346 key=463b96181691fc9c
 347
 348 position after e2e4
 349 FEN=rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1
 350 key=823c9b50fd114196
 351
 352 position after e2e4 d75
 353 FEN=rnbqkbnr/ppp1pppp/8/3p4/4P3/8/PPPP1PPP/RNBQKBNR w KQkq d6 0 2
 354 key=0756b94461c50fb0
 355
 356 position after e2e4 d7d5 e4e5
 357 FEN=rnbqkbnr/ppp1pppp/8/3pP3/8/8/PPPP1PPP/RNBQKBNR b KQkq - 0 2
 358 key=662fafb965db29d4
 359
 360 position after e2e4 d7d5 e4e5 f7f5
 361 FEN=rnbqkbnr/ppp1p1pp/8/3pPp2/8/8/PPPP1PPP/RNBQKBNR w KQkq f6 0 3
 362 key=22a48b5a8e47ff78
 363
 364 position after e2e4 d7d5 e4e5 f7f5 e1e2
 365 FEN=rnbqkbnr/ppp1p1pp/8/3pPp2/8/8/PPPPKPPP/RNBQ1BNR b kq - 0 3
 366 key=652a607ca3f242c1
 367
 368 position after e2e4 d7d5 e4e5 f7f5 e1e2 e8f7
 369 FEN=rnbq1bnr/ppp1pkpp/8/3pPp2/8/8/PPPPKPPP/RNBQ1BNR w - - 0 4
 370 key=00fdd303c946bdd9
 371
 372 position after a2a4 b7b5 h2h4 b5b4 c2c4
 373 FEN=rnbqkbnr/p1pppppp/8/8/PpP4P/8/1P1PPPP1/RNBQKBNR b KQkq c3 0 3
 374 key=3c8123ea7b067637
 375
 376 position after a2a4 b7b5 h2h4 b5b4 c2c4 b4c3 a1a3
 377 FEN=rnbqkbnr/p1pppppp/8/8/P6P/R1p5/1P1PPPP1/1NBQKBNR b Kkq - 0 4
 378 key=5c3f9b829b279560
 379 </pre>
 380
 381
 382 <h2>move</h2>
 383 "move" is a bit field with the following meaning (bit 0 is the least
 384 significant bit)
 385 <pre>
 386 bits                meaning
 387 ===================================
 388 0,1,2               to file
 389 3,4,5               to row
 390 6,7,8               from file
 391 9,10,11             from row
 392 12,13,14            promotion piece
 393 </pre>
 394 "promotion piece" is encoded as follows
 395 <pre>
 396 none       0
 397 knight     1
 398 bishop     2
 399 rook       3
 400 queen      4
 401 </pre>
 402 If the move is "0" (a1a1) then it should simply be ignored. It seems to me that
 403 in that case one might as well delete the entry from the book.
 404
 405 <h3>Castling moves</h3> Castling moves are represented somewhat
 406 unconventially as follows (this convention is related to Chess960, see
 407 below).
 408 <pre>
 409 white short      e1h1
 410 white long       e1a1
 411 black short      e8h8
 412 black long       e8a8
 413 </pre>
 414 It is technically possible that these moves are legal non-castling
 415 moves. So before deciding that these are really castling moves the
 416 implementation may for example verify that there is really a king
 417 present on e1/e8.
 418 <h2>weight</h2>
 419 In the Polyglot source code this field is called "count" but it is in fact
 420 a measure for the quality of the move.
 421 <p>
 422 The Polyglot book generator sets it to 2*(wins)+(draws), globally
 423 scaled to fit into 16 bits. A move with a weight of zero is deleted
 424 from the book. This is just a convention and  book authors
 425 are free to set this field according to their taste.
 426 <p>
 427 If random play is enabled in Polyglot then the probability that
 428 a move is selected is its weight divided by the sum of the weights
 429 of all the moves in the given position.
 430 In XBoard, which also supports Polyglot books, the weight can be raised
 431 to a power N (0 <= N <= infinity) before doing the probability calculation,
 432 enhancing or completely destroying the effect of the weights.
 433 <h3>A note on zero weights</h3>
 434 Note that older Polyglot versions are defective as to the use of zero weights,
 435 (meaning the move should never be played),
 436 and crash when they encounter them.
 437 This because of a misplaced internal consistency check,
 438 which really only made sense during book building
 439 (wich deletes all entries with zero weight from the book).
 440
 441 Yet hand-tuning of a book often leads to the desire to completely disable a move,
 442 without deleting it. Some software approximates an entry with zero weight
 443 by giving it very low probability. This is for instance what Scid does,
 444 but it means the move will still occasionally be played.
 445 With XBoard you can edit Polyglot books to set the weight to exactly zero,
 446 as well as delete or add moves.
 447
 448 <h2>learn</h2> "learn" is set to zero by the Polyglot book generator.
 449 If you set "BookLearn=true" in polyglot.ini then this field
 450 is used to record learning information. From Polyglot 2.0 on, Polyglot
 451 can also use this learn information for modulating the playing probabilities
 452 of the book moves, based on how often they were played and with
 453 how much success they met. To use this feature Polyglot should
 454 have write access to the opening book which on Unix systems will probably
 455 not be the case if the book has been installed centrally.
 456 Note that for the book to be opened for write access, the option
 457 BookLearn will have to be set before the book file is specified!
 458 <p>
 459 <h2>Sample code</h2>
 460 The following sample code is released in the public domain.
 461 <ul>
 462 <li>
 463 <a href=pg_key.c>pg_key.c</a>: This little utility computes the PG key
 464 of a FEN. Note that it does ZERO error checking on the legality
 465 of the FEN and hence will segfault if something is wrong.
 466 </li>
 467 <li>
 468 <a href=pg_show.c>pg_show.c</a>: This utility looks up a PG key in a PG book
 469 and prints out the moves and their (relative) weights.
 470 </li>
 471 </ul>
 472 <h2>Utilities</h2>
 473 Here are a few utilities: <a href=pg_utils-0.2.tar.gz>pg_utils-0.2.tar.gz</a>. They are released under the FreeBSD license.
 474 <H2>Extension to Chess960</H2>
 475 We assume that the reader is familar
 476 with the rules of Chess960 (also called Fisher Random Chess or
 477 FRC). See e.g.
 478 <a href=http://en.wikipedia.org/wiki/Fischer_Random_Chess>http://en.wikipedia.org/wiki/Fischer_Random_Chess</a>.
 479 <p>
 480 The Zobrist hash function used in Polyglot does not keep track of
 481 which rook has castling rights if there are multiple rooks present on
 482 the same side of the king. However it is rather unlikely that this
 483 situation would occur in the opening. So the ambiguity can be resolved
 484 in a satisfactory way by making the following convention.
 485 <p>
 486 <b> Positions in which a rook has castling rights which is not an outer
 487 rook (closest to a or h file) should not be included in the book. </b>
 488 <p>
 489 Nonetheless this is an unsatisfactory situation. Therefore the
 490 upcoming versions of xboard/winboard extend the Polyglot hash function
 491 in such a way that it takes into account the full castling rights in
 492 Chess960, therefore
 493 <b>removing the need of the above disambiguating convention</b>.  This is done in a backward compatible way. I.e. ordinary
 494 chess positions or Chess960 positions in which there is no castling
 495 ambiguity will keep their old hash key.
 496 <p>
 497 The above declaration of RandomCastle is replaced by
 498 <pre>
 499 const uint64 RandomCastle[16]={
 500 &lt; to be filled in &gt;
 501 }
 502 </pre>
 503 In this case "castle" will be the exclusive or of entries taken from
 504 RandomCastle, one for each rook that has castling rights (so at most
 505 four offsets).
 506
 507 The offset for a rook that has castling rights is computed as follows.
 508 <ul>
 509 <li> If the rook is an outer rook (i.e. closest to the a or h file) then
 510 the offset is
 511 <pre>
 512 0    if the rook is white and on the king side
 513 1    if the rook is white and on the queen side
 514 2    if the rook is black and on the king side
 515 3    if the rook is black and on the queen side
 516 </pre>
 517 (this is like in ordinary chess)
 518 </li>
 519 <li> If the rook is not an outer rook then the offset is
 520 <pre>
 521 3+file    if the rook is white
 522 9+file    if the rook is black
 523 </pre>
 524 where "file" denotes the file the rook is on, encoded in the usual way, i.e.
 525 b=1,c=2,d=3,e=4,f=5,g=6.
 526 </li>
 527 </ul>
 528 <h3>Encoding of moves</h3> A castling move is encoded as a usual move
 529 (see above) in which the "from square" is the position of the king and
 530 the "to square" is the position of the rook. This is to maintain
 531 compatibility with various Fruit derivatives.
 532
 533 <h2>Extension to other variants</h2>
 534 Polyglot does not support any Chess variants other than Mad Queen and Chess960.
 535 XBoard, however, does, and has extended the definition of the Polyglot book format to cover such variants.
 536 To generalize to various board formats, it also numbers the board square in raster-scan fashion.
 537 So in Xiangqi, which has a 9x10 board, the square number equals 9*row+file, and can run upto 90.
 538 The piece numbering is also extended beyond King, keeping the alternation of
 539 white and black pieces of the same type, to accomodate unorthodox piece types.
 540 How unorthodox pieces should be mapped on numbers is not yet subject to an official standard.
 541 But variants that only the orthodox pieces (e.g. Suicide, Atomic) do not suffer from that.
 542 <p>
 543 To map a (piece, square) combination to a hash key, however,
 544 only the square number modulo 64 and the piece number modulo 12 is used as index in the key table.
 545 The square number divided by 64 and piece number divided by 12 is then used to decide
 546 how the retreived key should be (bit-wise) rotated to get the actual key.
 547 Square numbers in the range 64-127 rotate the key left by 8 bits,
 548 while piece values in the ranges 12-23, 24-35 and 36-47 rotate left by an additional 16, 32 or 48 bits, respectively.
 549 This is sufficient to handle boards of upto 128 squares, and up to 24 piece types.
 550 <p>
 551 A number derived from the variant can be XORed to the overall key,
 552 to prevent positions from variants with equal board and piece types (e.g. suicide, losers or atomic)
 553 to map to the same key, and invalidates books made for one of those for accidental use by any of the others.
 554 The table below defines the number that should be used for some common variants.
 555 Note that some variants that are mutually compatible use the same number,
 556 so that they can use the same opening book.
 557 <pre>
 558  0    standard Chess (aka Mad Queen), WildCastle, NoCastle, Fischer Random Chess (aka Chess960),
 559  0    Xiangqi (Chinese Chess),
 560  6    Crazyhouse,
 561  7    Losers Chess,
 562  8    Suicide Chess, Giveaway Chess,
 563 10    TwoKings,
 564 12    Atomic Chess,
 565 13    3Check,
 566 14    Shatranj,
 567 23    Shogi (Japanese Chess),
 568 25    Courier Chess,
 569 26    Gothic Chess, Capablanca Chess, Capablanca Random Chess,
 570 28    Knightmate,
 571 30    Cylinder Chess,
 572 31    Falcon Chess,
 573 33    Berolina Chess,
 574 34    Janus Chess,
 575 35    Superchess,
 576 36    Great Shatranj,
 577 38    Makruk (Thai Chess),
 578 39    S-Chess (aka Seirawan Chess),
 579 40    Grand Chess,
 580 41    Spartan Chess,
 581 </pre>
 582 <p>
 583 For variants with holdings from which pieces can be brought (back) in play (e.g. Crazyhouse, Shogi, S-Chess),
 584 the holdings are also part of the game state, and must be encoded in the key.
 585 To do this, the holdings are considered as a single off-board square with the next available number
 586 (so square number 64 in Crazyhouse).
 587 The (piece type, square number) pair is than mapped onto a key in the same way as for on-board pieces.
 588 A complication here is that multiple pieces, possibly of the same type, can be on this 'holdings square',
 589 so that XORing the corresponding key into the total will not work.
 590 (Having two pieces of a certain type would then be indistinguishable from having none, as A XOR A equals 0 for any A!)
 591 Therefore the holdings keys are not XORed but added to the total key,
 592 after all other key terms have been taken into account through XOR.
 593 <p>
 594 The move encoding on non-8x8 boards is generalized to fromSquare*boardSize + toSquare + boardSize*boardSize*promotionType
 595 (where boardSize = boardLength*boardWidth).
 596 For large boards this might leave a shortage of promotion types,
 597 but fortunately promotions are not very common in opening theory.
 598 The meaning of the promotionType code can be variant-dependent.
 599 Especially if there is a shortage of codes, the most common promotions should receive the lowest codes.
 600 (E.g. in Grand Chess the board is 10x10, so the promotion-type multiplier is 10,000,
 601 while the 16-bit move encoding only runs upto 65,535.
 602 So there is only room for 6 promotion types, while 7 would be needed for the 6 possible piece types and non-promotion.)
 603 In asymmetric variants (e.g. Spartan Chess) the same code needs not indicate the same piece type for both sides.
 604 <p>
 605 Special moves are indicated by using a (non-existent) promotion choice as an 'escape',
 606 in which case the from-square number isn't really a from-square, but identifies the special move.
 607 This system is used (with promotionType = 9, when available) for drops, where the from-square contains the ID of the piece to be dropped
 608 (A=1, B=2 etc.).
 609 It is also used to indicate double-moves of a Chu-Shogi Lion (promotionType = 10, when available, but 2 in Chu Shogi),
 610 where every combination of first and second step gets a unique code 0-63, which is then stored in the from-square.
 611 </p>
 612 <p>
 613 For really large boards (say larger than 144 squares) a more compact encoding system should be used,
 614 which indicates the from-square relative to the to-square in polar coordinates:
 615 toSquare + boardSize*directionCode + 4*boardSize*distanceCode.
 616 Here boardLength is the largest linear dimension of the board (be it height or width),
 617 and the distanceCodes &lt; boardLength-1 indicate the distance along the indicated ray to the from-square,
 618 such that the move goes in the direction forward, right, right-forward or left-forward as seen from the player that makes the move.
 619 When this lies off-board, the distanceCode should be subtracted from boardLength+1 to obtain the distance in the opposite direction.
 620 The rayCodes 0-3 represent the directions vertical, horizontal, diagonal and anti-diagonal (N, E, NE, SE), respectively.
 621 The remaining distanceCodes (>= boardLength-1) represent oblique moves, special moves and promotions.
 622 They always start with the two Knight jumps landing just right of the ray, in the positive and negative direction,
 623 followed by two (1,3) and two (2,3) jumps.
 624 </p><p>
 625 After the Knight jumps the meaning of the distanceCodes becomes variant dependent.
 626 By default they would contain promotions to various piece types,
 627 in the order of their piece code (i.e. N, B, R, Q, K, other) in so far they participate in the variant.
 628 These codes imply a single step in the forward direction along the ray.
 629 In variants with Shogi-like promotions, where all pieces can promote, but the only choice is promote or not,
 630 the entire range of distanceCode meanings will be repeated, this time meaning the move will be accompanied by a promotion.
 631 </p><p>
 632 The meaning of these variant-dependent distanceCodes can be overruled through the book header.
 633 After a line with the word "Special" in this header,
 634 a number of lines can follow, specifying the move as it would be for the vertical ray in the forward direction, starting from e4.
 635
 636
 637 After that follow codes to indicate additional oblique moves: a pair of Camel jumps, a pair of Zebra jumps, etc.
 638 With Shogi-like promotions, the 16 promotion choices instead code for two-step Lion moves that start off along the ray.
 639 Promotions are indicated by adding a number to the distanceCode one larger than the highest code used to indicate any oblique move.
 640 E.g. for Tenjiku Shogi with its 16x16 board codes 0-14 indicate true (positiove and negative) distances along the ray,
 641 15 & 16 are Knight jumps, 17-32 are Lion double moves, 33-36 are C and Z jumps (for the area moves),
 642 and promotions add 37.
 643 As the board has 256 squares, there are only 64 distance codes available,
 644 so the highest code for which a promoted version is available is 26 (26 + 37 = 63).
 645 So there is no room to specify promotion on C and Z jumps, and with part of the Lion double-moves.
 646 But the only pieces in Tenjiku Shogi that can make C and Z moves do not promote,
 647 and the Lion double-moves can be ordered such that only the backward moves cannot promote.
 648 </p><p>
 649 For Maka Dai Dai Shogi the 8 codes after the Lion double moves
 650 (36-43, as the board is 19x19 there, shifting up everything 3 places compared to Tenjiku)
 651 specify Lion Dog linear triple-moves,
 652 (2-out-1-in, 2+1-out, 1+2-out and 1+1+1-out in both directions along the ray)
 653 and 44 specifies the moves was made by a 'Universal Leaper' (the ray number indicating which one).
 654 The latter necessitates the decoding routine to find the corresponding piece on the board.
 655 ('Universal Leaper' in this context means a piece that is not bound to rays,
 656 and can move almost anywhere, such as Hook Mover, encoded in ray 0, Capricorn (ray 1) or Emperor (ray 2).)
 657 With 45 distance codes, 4 rays and 361 board squares all available 16-bit codes ar almost used up,
 658 so there is no way to indicate promotion.
 659 This is serious, as this variant has promotion on capture,
 660 making promotion early in the opening quite common.
 661 Fortunately the pieces are clearly divided into those that promote to upward-compatible pieces
 662 (replacing all step moves by unlimited sliding in that direction),
 663 for which you would always promote,
 664 and those that 'promote' to a worthless Gold, which you would virtually never promote.
 665 So promotion / deferral is decided by which class the piece belongs to,
 666 and only moves that do the opposite from what you would normally do cannot be incorporated in the book.
 667 This again need consulting of the board position before the move can be decoded.
 668 </p>
 669 <iframe src="cgi-bin/count.cgi?H=9" width="130" height="40"></iframe>
 670 </body>
 671