book.c

   1 /*
   2  * book.c -- code for probing Polyglot opening books
   3  *
   4  * This code was first released in the public domain by Michel Van den Bergh.
   5  * The array Random64 is taken from the Polyglot source code.
   6  * I am pretty sure that a table of random numbers is never protected
   7  * by copyright.
   8  *
   9  * It s adapted by H.G. Muller for working with xboard / Winboard
  10  *
  11  * The following terms apply to the enhanced version of XBoard distributed
  12  * by the Free Software Foundation:
  13  * ------------------------------------------------------------------------
  14  *
  15  * GNU XBoard is free software: you can redistribute it and/or modify
  16  * it under the terms of the GNU General Public License as published by
  17  * the Free Software Foundation, either version 3 of the License, or (at
  18  * your option) any later version.
  19  *
  20  * GNU XBoard is distributed in the hope that it will be useful, but
  21  * WITHOUT ANY WARRANTY; without even the implied warranty of
  22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  23  * General Public License for more details.
  24  *
  25  * You should have received a copy of the GNU General Public License
  26  * along with this program. If not, see http://www.gnu.org/licenses/.  *
  27  *
  28  * ------------------------------------------------------------------------
  29  */
  30
  31 #include "config.h"
  32
  33 #include <stdio.h>
  34 #include <string.h>
  35 #include <time.h>
  36 #include <stdlib.h>
  37 #include <math.h>
  38
  39 #include "common.h"
  40 #include "frontend.h"
  41 #include "backend.h"
  42 #include "moves.h"
  43 #include "gettext.h"
  44
  45 #ifdef ENABLE_NLS
  46 # define  _(s) gettext (s)
  47 # define N_(s) gettext_noop (s)
  48 #else
  49 # define  _(s) (s)
  50 # define N_(s)  s
  51 #endif
  52
  53 #ifdef _MSC_VER
  54   typedef unsigned __int64 uint64;
  55 #else
  56   typedef unsigned long long int uint64;
  57 #endif
  58
  59 #ifdef _MSC_VER
  60 #  define U64(u) (u##ui64)
  61 #else
  62 #  define U64(u) (u##ULL)
  63 #endif
  64
  65 typedef unsigned char uint8;
  66 typedef unsigned short uint16;
  67 typedef unsigned int uint32;
  68
  69 typedef struct {
  70     uint64 key;
  71     uint16 move;
  72     uint16 weight;
  73     uint16 learnPoints;
  74     uint16 learnCount;
  75 } entry_t;
  76
  77 entry_t entry_none = {
  78     0, 0, 0, 0
  79 };
  80
  81 char *promote_pieces=" nbrqac=+";
  82
  83 uint64 Random64[781] = {
  84    U64(0x9D39247E33776D41), U64(0x2AF7398005AAA5C7), U64(0x44DB015024623547), U64(0x9C15F73E62A76AE2),
  85    U64(0x75834465489C0C89), U64(0x3290AC3A203001BF), U64(0x0FBBAD1F61042279), U64(0xE83A908FF2FB60CA),
  86    U64(0x0D7E765D58755C10), U64(0x1A083822CEAFE02D), U64(0x9605D5F0E25EC3B0), U64(0xD021FF5CD13A2ED5),
  87    U64(0x40BDF15D4A672E32), U64(0x011355146FD56395), U64(0x5DB4832046F3D9E5), U64(0x239F8B2D7FF719CC),
  88    U64(0x05D1A1AE85B49AA1), U64(0x679F848F6E8FC971), U64(0x7449BBFF801FED0B), U64(0x7D11CDB1C3B7ADF0),
  89    U64(0x82C7709E781EB7CC), U64(0xF3218F1C9510786C), U64(0x331478F3AF51BBE6), U64(0x4BB38DE5E7219443),
  90    U64(0xAA649C6EBCFD50FC), U64(0x8DBD98A352AFD40B), U64(0x87D2074B81D79217), U64(0x19F3C751D3E92AE1),
  91    U64(0xB4AB30F062B19ABF), U64(0x7B0500AC42047AC4), U64(0xC9452CA81A09D85D), U64(0x24AA6C514DA27500),
  92    U64(0x4C9F34427501B447), U64(0x14A68FD73C910841), U64(0xA71B9B83461CBD93), U64(0x03488B95B0F1850F),
  93    U64(0x637B2B34FF93C040), U64(0x09D1BC9A3DD90A94), U64(0x3575668334A1DD3B), U64(0x735E2B97A4C45A23),
  94    U64(0x18727070F1BD400B), U64(0x1FCBACD259BF02E7), U64(0xD310A7C2CE9B6555), U64(0xBF983FE0FE5D8244),
  95    U64(0x9F74D14F7454A824), U64(0x51EBDC4AB9BA3035), U64(0x5C82C505DB9AB0FA), U64(0xFCF7FE8A3430B241),
  96    U64(0x3253A729B9BA3DDE), U64(0x8C74C368081B3075), U64(0xB9BC6C87167C33E7), U64(0x7EF48F2B83024E20),
  97    U64(0x11D505D4C351BD7F), U64(0x6568FCA92C76A243), U64(0x4DE0B0F40F32A7B8), U64(0x96D693460CC37E5D),
  98    U64(0x42E240CB63689F2F), U64(0x6D2BDCDAE2919661), U64(0x42880B0236E4D951), U64(0x5F0F4A5898171BB6),
  99    U64(0x39F890F579F92F88), U64(0x93C5B5F47356388B), U64(0x63DC359D8D231B78), U64(0xEC16CA8AEA98AD76),
 100    U64(0x5355F900C2A82DC7), U64(0x07FB9F855A997142), U64(0x5093417AA8A7ED5E), U64(0x7BCBC38DA25A7F3C),
 101    U64(0x19FC8A768CF4B6D4), U64(0x637A7780DECFC0D9), U64(0x8249A47AEE0E41F7), U64(0x79AD695501E7D1E8),
 102    U64(0x14ACBAF4777D5776), U64(0xF145B6BECCDEA195), U64(0xDABF2AC8201752FC), U64(0x24C3C94DF9C8D3F6),
 103    U64(0xBB6E2924F03912EA), U64(0x0CE26C0B95C980D9), U64(0xA49CD132BFBF7CC4), U64(0xE99D662AF4243939),
 104    U64(0x27E6AD7891165C3F), U64(0x8535F040B9744FF1), U64(0x54B3F4FA5F40D873), U64(0x72B12C32127FED2B),
 105    U64(0xEE954D3C7B411F47), U64(0x9A85AC909A24EAA1), U64(0x70AC4CD9F04F21F5), U64(0xF9B89D3E99A075C2),
 106    U64(0x87B3E2B2B5C907B1), U64(0xA366E5B8C54F48B8), U64(0xAE4A9346CC3F7CF2), U64(0x1920C04D47267BBD),
 107    U64(0x87BF02C6B49E2AE9), U64(0x092237AC237F3859), U64(0xFF07F64EF8ED14D0), U64(0x8DE8DCA9F03CC54E),
 108    U64(0x9C1633264DB49C89), U64(0xB3F22C3D0B0B38ED), U64(0x390E5FB44D01144B), U64(0x5BFEA5B4712768E9),
 109    U64(0x1E1032911FA78984), U64(0x9A74ACB964E78CB3), U64(0x4F80F7A035DAFB04), U64(0x6304D09A0B3738C4),
 110    U64(0x2171E64683023A08), U64(0x5B9B63EB9CEFF80C), U64(0x506AACF489889342), U64(0x1881AFC9A3A701D6),
 111    U64(0x6503080440750644), U64(0xDFD395339CDBF4A7), U64(0xEF927DBCF00C20F2), U64(0x7B32F7D1E03680EC),
 112    U64(0xB9FD7620E7316243), U64(0x05A7E8A57DB91B77), U64(0xB5889C6E15630A75), U64(0x4A750A09CE9573F7),
 113    U64(0xCF464CEC899A2F8A), U64(0xF538639CE705B824), U64(0x3C79A0FF5580EF7F), U64(0xEDE6C87F8477609D),
 114    U64(0x799E81F05BC93F31), U64(0x86536B8CF3428A8C), U64(0x97D7374C60087B73), U64(0xA246637CFF328532),
 115    U64(0x043FCAE60CC0EBA0), U64(0x920E449535DD359E), U64(0x70EB093B15B290CC), U64(0x73A1921916591CBD),
 116    U64(0x56436C9FE1A1AA8D), U64(0xEFAC4B70633B8F81), U64(0xBB215798D45DF7AF), U64(0x45F20042F24F1768),
 117    U64(0x930F80F4E8EB7462), U64(0xFF6712FFCFD75EA1), U64(0xAE623FD67468AA70), U64(0xDD2C5BC84BC8D8FC),
 118    U64(0x7EED120D54CF2DD9), U64(0x22FE545401165F1C), U64(0xC91800E98FB99929), U64(0x808BD68E6AC10365),
 119    U64(0xDEC468145B7605F6), U64(0x1BEDE3A3AEF53302), U64(0x43539603D6C55602), U64(0xAA969B5C691CCB7A),
 120    U64(0xA87832D392EFEE56), U64(0x65942C7B3C7E11AE), U64(0xDED2D633CAD004F6), U64(0x21F08570F420E565),
 121    U64(0xB415938D7DA94E3C), U64(0x91B859E59ECB6350), U64(0x10CFF333E0ED804A), U64(0x28AED140BE0BB7DD),
 122    U64(0xC5CC1D89724FA456), U64(0x5648F680F11A2741), U64(0x2D255069F0B7DAB3), U64(0x9BC5A38EF729ABD4),
 123    U64(0xEF2F054308F6A2BC), U64(0xAF2042F5CC5C2858), U64(0x480412BAB7F5BE2A), U64(0xAEF3AF4A563DFE43),
 124    U64(0x19AFE59AE451497F), U64(0x52593803DFF1E840), U64(0xF4F076E65F2CE6F0), U64(0x11379625747D5AF3),
 125    U64(0xBCE5D2248682C115), U64(0x9DA4243DE836994F), U64(0x066F70B33FE09017), U64(0x4DC4DE189B671A1C),
 126    U64(0x51039AB7712457C3), U64(0xC07A3F80C31FB4B4), U64(0xB46EE9C5E64A6E7C), U64(0xB3819A42ABE61C87),
 127    U64(0x21A007933A522A20), U64(0x2DF16F761598AA4F), U64(0x763C4A1371B368FD), U64(0xF793C46702E086A0),
 128    U64(0xD7288E012AEB8D31), U64(0xDE336A2A4BC1C44B), U64(0x0BF692B38D079F23), U64(0x2C604A7A177326B3),
 129    U64(0x4850E73E03EB6064), U64(0xCFC447F1E53C8E1B), U64(0xB05CA3F564268D99), U64(0x9AE182C8BC9474E8),
 130    U64(0xA4FC4BD4FC5558CA), U64(0xE755178D58FC4E76), U64(0x69B97DB1A4C03DFE), U64(0xF9B5B7C4ACC67C96),
 131    U64(0xFC6A82D64B8655FB), U64(0x9C684CB6C4D24417), U64(0x8EC97D2917456ED0), U64(0x6703DF9D2924E97E),
 132    U64(0xC547F57E42A7444E), U64(0x78E37644E7CAD29E), U64(0xFE9A44E9362F05FA), U64(0x08BD35CC38336615),
 133    U64(0x9315E5EB3A129ACE), U64(0x94061B871E04DF75), U64(0xDF1D9F9D784BA010), U64(0x3BBA57B68871B59D),
 134    U64(0xD2B7ADEEDED1F73F), U64(0xF7A255D83BC373F8), U64(0xD7F4F2448C0CEB81), U64(0xD95BE88CD210FFA7),
 135    U64(0x336F52F8FF4728E7), U64(0xA74049DAC312AC71), U64(0xA2F61BB6E437FDB5), U64(0x4F2A5CB07F6A35B3),
 136    U64(0x87D380BDA5BF7859), U64(0x16B9F7E06C453A21), U64(0x7BA2484C8A0FD54E), U64(0xF3A678CAD9A2E38C),
 137    U64(0x39B0BF7DDE437BA2), U64(0xFCAF55C1BF8A4424), U64(0x18FCF680573FA594), U64(0x4C0563B89F495AC3),
 138    U64(0x40E087931A00930D), U64(0x8CFFA9412EB642C1), U64(0x68CA39053261169F), U64(0x7A1EE967D27579E2),
 139    U64(0x9D1D60E5076F5B6F), U64(0x3810E399B6F65BA2), U64(0x32095B6D4AB5F9B1), U64(0x35CAB62109DD038A),
 140    U64(0xA90B24499FCFAFB1), U64(0x77A225A07CC2C6BD), U64(0x513E5E634C70E331), U64(0x4361C0CA3F692F12),
 141    U64(0xD941ACA44B20A45B), U64(0x528F7C8602C5807B), U64(0x52AB92BEB9613989), U64(0x9D1DFA2EFC557F73),
 142    U64(0x722FF175F572C348), U64(0x1D1260A51107FE97), U64(0x7A249A57EC0C9BA2), U64(0x04208FE9E8F7F2D6),
 143    U64(0x5A110C6058B920A0), U64(0x0CD9A497658A5698), U64(0x56FD23C8F9715A4C), U64(0x284C847B9D887AAE),
 144    U64(0x04FEABFBBDB619CB), U64(0x742E1E651C60BA83), U64(0x9A9632E65904AD3C), U64(0x881B82A13B51B9E2),
 145    U64(0x506E6744CD974924), U64(0xB0183DB56FFC6A79), U64(0x0ED9B915C66ED37E), U64(0x5E11E86D5873D484),
 146    U64(0xF678647E3519AC6E), U64(0x1B85D488D0F20CC5), U64(0xDAB9FE6525D89021), U64(0x0D151D86ADB73615),
 147    U64(0xA865A54EDCC0F019), U64(0x93C42566AEF98FFB), U64(0x99E7AFEABE000731), U64(0x48CBFF086DDF285A),
 148    U64(0x7F9B6AF1EBF78BAF), U64(0x58627E1A149BBA21), U64(0x2CD16E2ABD791E33), U64(0xD363EFF5F0977996),
 149    U64(0x0CE2A38C344A6EED), U64(0x1A804AADB9CFA741), U64(0x907F30421D78C5DE), U64(0x501F65EDB3034D07),
 150    U64(0x37624AE5A48FA6E9), U64(0x957BAF61700CFF4E), U64(0x3A6C27934E31188A), U64(0xD49503536ABCA345),
 151    U64(0x088E049589C432E0), U64(0xF943AEE7FEBF21B8), U64(0x6C3B8E3E336139D3), U64(0x364F6FFA464EE52E),
 152    U64(0xD60F6DCEDC314222), U64(0x56963B0DCA418FC0), U64(0x16F50EDF91E513AF), U64(0xEF1955914B609F93),
 153    U64(0x565601C0364E3228), U64(0xECB53939887E8175), U64(0xBAC7A9A18531294B), U64(0xB344C470397BBA52),
 154    U64(0x65D34954DAF3CEBD), U64(0xB4B81B3FA97511E2), U64(0xB422061193D6F6A7), U64(0x071582401C38434D),
 155    U64(0x7A13F18BBEDC4FF5), U64(0xBC4097B116C524D2), U64(0x59B97885E2F2EA28), U64(0x99170A5DC3115544),
 156    U64(0x6F423357E7C6A9F9), U64(0x325928EE6E6F8794), U64(0xD0E4366228B03343), U64(0x565C31F7DE89EA27),
 157    U64(0x30F5611484119414), U64(0xD873DB391292ED4F), U64(0x7BD94E1D8E17DEBC), U64(0xC7D9F16864A76E94),
 158    U64(0x947AE053EE56E63C), U64(0xC8C93882F9475F5F), U64(0x3A9BF55BA91F81CA), U64(0xD9A11FBB3D9808E4),
 159    U64(0x0FD22063EDC29FCA), U64(0xB3F256D8ACA0B0B9), U64(0xB03031A8B4516E84), U64(0x35DD37D5871448AF),
 160    U64(0xE9F6082B05542E4E), U64(0xEBFAFA33D7254B59), U64(0x9255ABB50D532280), U64(0xB9AB4CE57F2D34F3),
 161    U64(0x693501D628297551), U64(0xC62C58F97DD949BF), U64(0xCD454F8F19C5126A), U64(0xBBE83F4ECC2BDECB),
 162    U64(0xDC842B7E2819E230), U64(0xBA89142E007503B8), U64(0xA3BC941D0A5061CB), U64(0xE9F6760E32CD8021),
 163    U64(0x09C7E552BC76492F), U64(0x852F54934DA55CC9), U64(0x8107FCCF064FCF56), U64(0x098954D51FFF6580),
 164    U64(0x23B70EDB1955C4BF), U64(0xC330DE426430F69D), U64(0x4715ED43E8A45C0A), U64(0xA8D7E4DAB780A08D),
 165    U64(0x0572B974F03CE0BB), U64(0xB57D2E985E1419C7), U64(0xE8D9ECBE2CF3D73F), U64(0x2FE4B17170E59750),
 166    U64(0x11317BA87905E790), U64(0x7FBF21EC8A1F45EC), U64(0x1725CABFCB045B00), U64(0x964E915CD5E2B207),
 167    U64(0x3E2B8BCBF016D66D), U64(0xBE7444E39328A0AC), U64(0xF85B2B4FBCDE44B7), U64(0x49353FEA39BA63B1),
 168    U64(0x1DD01AAFCD53486A), U64(0x1FCA8A92FD719F85), U64(0xFC7C95D827357AFA), U64(0x18A6A990C8B35EBD),
 169    U64(0xCCCB7005C6B9C28D), U64(0x3BDBB92C43B17F26), U64(0xAA70B5B4F89695A2), U64(0xE94C39A54A98307F),
 170    U64(0xB7A0B174CFF6F36E), U64(0xD4DBA84729AF48AD), U64(0x2E18BC1AD9704A68), U64(0x2DE0966DAF2F8B1C),
 171    U64(0xB9C11D5B1E43A07E), U64(0x64972D68DEE33360), U64(0x94628D38D0C20584), U64(0xDBC0D2B6AB90A559),
 172    U64(0xD2733C4335C6A72F), U64(0x7E75D99D94A70F4D), U64(0x6CED1983376FA72B), U64(0x97FCAACBF030BC24),
 173    U64(0x7B77497B32503B12), U64(0x8547EDDFB81CCB94), U64(0x79999CDFF70902CB), U64(0xCFFE1939438E9B24),
 174    U64(0x829626E3892D95D7), U64(0x92FAE24291F2B3F1), U64(0x63E22C147B9C3403), U64(0xC678B6D860284A1C),
 175    U64(0x5873888850659AE7), U64(0x0981DCD296A8736D), U64(0x9F65789A6509A440), U64(0x9FF38FED72E9052F),
 176    U64(0xE479EE5B9930578C), U64(0xE7F28ECD2D49EECD), U64(0x56C074A581EA17FE), U64(0x5544F7D774B14AEF),
 177    U64(0x7B3F0195FC6F290F), U64(0x12153635B2C0CF57), U64(0x7F5126DBBA5E0CA7), U64(0x7A76956C3EAFB413),
 178    U64(0x3D5774A11D31AB39), U64(0x8A1B083821F40CB4), U64(0x7B4A38E32537DF62), U64(0x950113646D1D6E03),
 179    U64(0x4DA8979A0041E8A9), U64(0x3BC36E078F7515D7), U64(0x5D0A12F27AD310D1), U64(0x7F9D1A2E1EBE1327),
 180    U64(0xDA3A361B1C5157B1), U64(0xDCDD7D20903D0C25), U64(0x36833336D068F707), U64(0xCE68341F79893389),
 181    U64(0xAB9090168DD05F34), U64(0x43954B3252DC25E5), U64(0xB438C2B67F98E5E9), U64(0x10DCD78E3851A492),
 182    U64(0xDBC27AB5447822BF), U64(0x9B3CDB65F82CA382), U64(0xB67B7896167B4C84), U64(0xBFCED1B0048EAC50),
 183    U64(0xA9119B60369FFEBD), U64(0x1FFF7AC80904BF45), U64(0xAC12FB171817EEE7), U64(0xAF08DA9177DDA93D),
 184    U64(0x1B0CAB936E65C744), U64(0xB559EB1D04E5E932), U64(0xC37B45B3F8D6F2BA), U64(0xC3A9DC228CAAC9E9),
 185    U64(0xF3B8B6675A6507FF), U64(0x9FC477DE4ED681DA), U64(0x67378D8ECCEF96CB), U64(0x6DD856D94D259236),
 186    U64(0xA319CE15B0B4DB31), U64(0x073973751F12DD5E), U64(0x8A8E849EB32781A5), U64(0xE1925C71285279F5),
 187    U64(0x74C04BF1790C0EFE), U64(0x4DDA48153C94938A), U64(0x9D266D6A1CC0542C), U64(0x7440FB816508C4FE),
 188    U64(0x13328503DF48229F), U64(0xD6BF7BAEE43CAC40), U64(0x4838D65F6EF6748F), U64(0x1E152328F3318DEA),
 189    U64(0x8F8419A348F296BF), U64(0x72C8834A5957B511), U64(0xD7A023A73260B45C), U64(0x94EBC8ABCFB56DAE),
 190    U64(0x9FC10D0F989993E0), U64(0xDE68A2355B93CAE6), U64(0xA44CFE79AE538BBE), U64(0x9D1D84FCCE371425),
 191    U64(0x51D2B1AB2DDFB636), U64(0x2FD7E4B9E72CD38C), U64(0x65CA5B96B7552210), U64(0xDD69A0D8AB3B546D),
 192    U64(0x604D51B25FBF70E2), U64(0x73AA8A564FB7AC9E), U64(0x1A8C1E992B941148), U64(0xAAC40A2703D9BEA0),
 193    U64(0x764DBEAE7FA4F3A6), U64(0x1E99B96E70A9BE8B), U64(0x2C5E9DEB57EF4743), U64(0x3A938FEE32D29981),
 194    U64(0x26E6DB8FFDF5ADFE), U64(0x469356C504EC9F9D), U64(0xC8763C5B08D1908C), U64(0x3F6C6AF859D80055),
 195    U64(0x7F7CC39420A3A545), U64(0x9BFB227EBDF4C5CE), U64(0x89039D79D6FC5C5C), U64(0x8FE88B57305E2AB6),
 196    U64(0xA09E8C8C35AB96DE), U64(0xFA7E393983325753), U64(0xD6B6D0ECC617C699), U64(0xDFEA21EA9E7557E3),
 197    U64(0xB67C1FA481680AF8), U64(0xCA1E3785A9E724E5), U64(0x1CFC8BED0D681639), U64(0xD18D8549D140CAEA),
 198    U64(0x4ED0FE7E9DC91335), U64(0xE4DBF0634473F5D2), U64(0x1761F93A44D5AEFE), U64(0x53898E4C3910DA55),
 199    U64(0x734DE8181F6EC39A), U64(0x2680B122BAA28D97), U64(0x298AF231C85BAFAB), U64(0x7983EED3740847D5),
 200    U64(0x66C1A2A1A60CD889), U64(0x9E17E49642A3E4C1), U64(0xEDB454E7BADC0805), U64(0x50B704CAB602C329),
 201    U64(0x4CC317FB9CDDD023), U64(0x66B4835D9EAFEA22), U64(0x219B97E26FFC81BD), U64(0x261E4E4C0A333A9D),
 202    U64(0x1FE2CCA76517DB90), U64(0xD7504DFA8816EDBB), U64(0xB9571FA04DC089C8), U64(0x1DDC0325259B27DE),
 203    U64(0xCF3F4688801EB9AA), U64(0xF4F5D05C10CAB243), U64(0x38B6525C21A42B0E), U64(0x36F60E2BA4FA6800),
 204    U64(0xEB3593803173E0CE), U64(0x9C4CD6257C5A3603), U64(0xAF0C317D32ADAA8A), U64(0x258E5A80C7204C4B),
 205    U64(0x8B889D624D44885D), U64(0xF4D14597E660F855), U64(0xD4347F66EC8941C3), U64(0xE699ED85B0DFB40D),
 206    U64(0x2472F6207C2D0484), U64(0xC2A1E7B5B459AEB5), U64(0xAB4F6451CC1D45EC), U64(0x63767572AE3D6174),
 207    U64(0xA59E0BD101731A28), U64(0x116D0016CB948F09), U64(0x2CF9C8CA052F6E9F), U64(0x0B090A7560A968E3),
 208    U64(0xABEEDDB2DDE06FF1), U64(0x58EFC10B06A2068D), U64(0xC6E57A78FBD986E0), U64(0x2EAB8CA63CE802D7),
 209    U64(0x14A195640116F336), U64(0x7C0828DD624EC390), U64(0xD74BBE77E6116AC7), U64(0x804456AF10F5FB53),
 210    U64(0xEBE9EA2ADF4321C7), U64(0x03219A39EE587A30), U64(0x49787FEF17AF9924), U64(0xA1E9300CD8520548),
 211    U64(0x5B45E522E4B1B4EF), U64(0xB49C3B3995091A36), U64(0xD4490AD526F14431), U64(0x12A8F216AF9418C2),
 212    U64(0x001F837CC7350524), U64(0x1877B51E57A764D5), U64(0xA2853B80F17F58EE), U64(0x993E1DE72D36D310),
 213    U64(0xB3598080CE64A656), U64(0x252F59CF0D9F04BB), U64(0xD23C8E176D113600), U64(0x1BDA0492E7E4586E),
 214    U64(0x21E0BD5026C619BF), U64(0x3B097ADAF088F94E), U64(0x8D14DEDB30BE846E), U64(0xF95CFFA23AF5F6F4),
 215    U64(0x3871700761B3F743), U64(0xCA672B91E9E4FA16), U64(0x64C8E531BFF53B55), U64(0x241260ED4AD1E87D),
 216    U64(0x106C09B972D2E822), U64(0x7FBA195410E5CA30), U64(0x7884D9BC6CB569D8), U64(0x0647DFEDCD894A29),
 217    U64(0x63573FF03E224774), U64(0x4FC8E9560F91B123), U64(0x1DB956E450275779), U64(0xB8D91274B9E9D4FB),
 218    U64(0xA2EBEE47E2FBFCE1), U64(0xD9F1F30CCD97FB09), U64(0xEFED53D75FD64E6B), U64(0x2E6D02C36017F67F),
 219    U64(0xA9AA4D20DB084E9B), U64(0xB64BE8D8B25396C1), U64(0x70CB6AF7C2D5BCF0), U64(0x98F076A4F7A2322E),
 220    U64(0xBF84470805E69B5F), U64(0x94C3251F06F90CF3), U64(0x3E003E616A6591E9), U64(0xB925A6CD0421AFF3),
 221    U64(0x61BDD1307C66E300), U64(0xBF8D5108E27E0D48), U64(0x240AB57A8B888B20), U64(0xFC87614BAF287E07),
 222    U64(0xEF02CDD06FFDB432), U64(0xA1082C0466DF6C0A), U64(0x8215E577001332C8), U64(0xD39BB9C3A48DB6CF),
 223    U64(0x2738259634305C14), U64(0x61CF4F94C97DF93D), U64(0x1B6BACA2AE4E125B), U64(0x758F450C88572E0B),
 224    U64(0x959F587D507A8359), U64(0xB063E962E045F54D), U64(0x60E8ED72C0DFF5D1), U64(0x7B64978555326F9F),
 225    U64(0xFD080D236DA814BA), U64(0x8C90FD9B083F4558), U64(0x106F72FE81E2C590), U64(0x7976033A39F7D952),
 226    U64(0xA4EC0132764CA04B), U64(0x733EA705FAE4FA77), U64(0xB4D8F77BC3E56167), U64(0x9E21F4F903B33FD9),
 227    U64(0x9D765E419FB69F6D), U64(0xD30C088BA61EA5EF), U64(0x5D94337FBFAF7F5B), U64(0x1A4E4822EB4D7A59),
 228    U64(0x6FFE73E81B637FB3), U64(0xDDF957BC36D8B9CA), U64(0x64D0E29EEA8838B3), U64(0x08DD9BDFD96B9F63),
 229    U64(0x087E79E5A57D1D13), U64(0xE328E230E3E2B3FB), U64(0x1C2559E30F0946BE), U64(0x720BF5F26F4D2EAA),
 230    U64(0xB0774D261CC609DB), U64(0x443F64EC5A371195), U64(0x4112CF68649A260E), U64(0xD813F2FAB7F5C5CA),
 231    U64(0x660D3257380841EE), U64(0x59AC2C7873F910A3), U64(0xE846963877671A17), U64(0x93B633ABFA3469F8),
 232    U64(0xC0C0F5A60EF4CDCF), U64(0xCAF21ECD4377B28C), U64(0x57277707199B8175), U64(0x506C11B9D90E8B1D),
 233    U64(0xD83CC2687A19255F), U64(0x4A29C6465A314CD1), U64(0xED2DF21216235097), U64(0xB5635C95FF7296E2),
 234    U64(0x22AF003AB672E811), U64(0x52E762596BF68235), U64(0x9AEBA33AC6ECC6B0), U64(0x944F6DE09134DFB6),
 235    U64(0x6C47BEC883A7DE39), U64(0x6AD047C430A12104), U64(0xA5B1CFDBA0AB4067), U64(0x7C45D833AFF07862),
 236    U64(0x5092EF950A16DA0B), U64(0x9338E69C052B8E7B), U64(0x455A4B4CFE30E3F5), U64(0x6B02E63195AD0CF8),
 237    U64(0x6B17B224BAD6BF27), U64(0xD1E0CCD25BB9C169), U64(0xDE0C89A556B9AE70), U64(0x50065E535A213CF6),
 238    U64(0x9C1169FA2777B874), U64(0x78EDEFD694AF1EED), U64(0x6DC93D9526A50E68), U64(0xEE97F453F06791ED),
 239    U64(0x32AB0EDB696703D3), U64(0x3A6853C7E70757A7), U64(0x31865CED6120F37D), U64(0x67FEF95D92607890),
 240    U64(0x1F2B1D1F15F6DC9C), U64(0xB69E38A8965C6B65), U64(0xAA9119FF184CCCF4), U64(0xF43C732873F24C13),
 241    U64(0xFB4A3D794A9A80D2), U64(0x3550C2321FD6109C), U64(0x371F77E76BB8417E), U64(0x6BFA9AAE5EC05779),
 242    U64(0xCD04F3FF001A4778), U64(0xE3273522064480CA), U64(0x9F91508BFFCFC14A), U64(0x049A7F41061A9E60),
 243    U64(0xFCB6BE43A9F2FE9B), U64(0x08DE8A1C7797DA9B), U64(0x8F9887E6078735A1), U64(0xB5B4071DBFC73A66),
 244    U64(0x230E343DFBA08D33), U64(0x43ED7F5A0FAE657D), U64(0x3A88A0FBBCB05C63), U64(0x21874B8B4D2DBC4F),
 245    U64(0x1BDEA12E35F6A8C9), U64(0x53C065C6C8E63528), U64(0xE34A1D250E7A8D6B), U64(0xD6B04D3B7651DD7E),
 246    U64(0x5E90277E7CB39E2D), U64(0x2C046F22062DC67D), U64(0xB10BB459132D0A26), U64(0x3FA9DDFB67E2F199),
 247    U64(0x0E09B88E1914F7AF), U64(0x10E8B35AF3EEAB37), U64(0x9EEDECA8E272B933), U64(0xD4C718BC4AE8AE5F),
 248    U64(0x81536D601170FC20), U64(0x91B534F885818A06), U64(0xEC8177F83F900978), U64(0x190E714FADA5156E),
 249    U64(0xB592BF39B0364963), U64(0x89C350C893AE7DC1), U64(0xAC042E70F8B383F2), U64(0xB49B52E587A1EE60),
 250    U64(0xFB152FE3FF26DA89), U64(0x3E666E6F69AE2C15), U64(0x3B544EBE544C19F9), U64(0xE805A1E290CF2456),
 251    U64(0x24B33C9D7ED25117), U64(0xE74733427B72F0C1), U64(0x0A804D18B7097475), U64(0x57E3306D881EDB4F),
 252    U64(0x4AE7D6A36EB5DBCB), U64(0x2D8D5432157064C8), U64(0xD1E649DE1E7F268B), U64(0x8A328A1CEDFE552C),
 253    U64(0x07A3AEC79624C7DA), U64(0x84547DDC3E203C94), U64(0x990A98FD5071D263), U64(0x1A4FF12616EEFC89),
 254    U64(0xF6F7FD1431714200), U64(0x30C05B1BA332F41C), U64(0x8D2636B81555A786), U64(0x46C9FEB55D120902),
 255    U64(0xCCEC0A73B49C9921), U64(0x4E9D2827355FC492), U64(0x19EBB029435DCB0F), U64(0x4659D2B743848A2C),
 256    U64(0x963EF2C96B33BE31), U64(0x74F85198B05A2E7D), U64(0x5A0F544DD2B1FB18), U64(0x03727073C2E134B1),
 257    U64(0xC7F6AA2DE59AEA61), U64(0x352787BAA0D7C22F), U64(0x9853EAB63B5E0B35), U64(0xABBDCDD7ED5C0860),
 258    U64(0xCF05DAF5AC8D77B0), U64(0x49CAD48CEBF4A71E), U64(0x7A4C10EC2158C4A6), U64(0xD9E92AA246BF719E),
 259    U64(0x13AE978D09FE5557), U64(0x730499AF921549FF), U64(0x4E4B705B92903BA4), U64(0xFF577222C14F0A3A),
 260    U64(0x55B6344CF97AAFAE), U64(0xB862225B055B6960), U64(0xCAC09AFBDDD2CDB4), U64(0xDAF8E9829FE96B5F),
 261    U64(0xB5FDFC5D3132C498), U64(0x310CB380DB6F7503), U64(0xE87FBB46217A360E), U64(0x2102AE466EBB1148),
 262    U64(0xF8549E1A3AA5E00D), U64(0x07A69AFDCC42261A), U64(0xC4C118BFE78FEAAE), U64(0xF9F4892ED96BD438),
 263    U64(0x1AF3DBE25D8F45DA), U64(0xF5B4B0B0D2DEEEB4), U64(0x962ACEEFA82E1C84), U64(0x046E3ECAAF453CE9),
 264    U64(0xF05D129681949A4C), U64(0x964781CE734B3C84), U64(0x9C2ED44081CE5FBD), U64(0x522E23F3925E319E),
 265    U64(0x177E00F9FC32F791), U64(0x2BC60A63A6F3B3F2), U64(0x222BBFAE61725606), U64(0x486289DDCC3D6780),
 266    U64(0x7DC7785B8EFDFC80), U64(0x8AF38731C02BA980), U64(0x1FAB64EA29A2DDF7), U64(0xE4D9429322CD065A),
 267    U64(0x9DA058C67844F20C), U64(0x24C0E332B70019B0), U64(0x233003B5A6CFE6AD), U64(0xD586BD01C5C217F6),
 268    U64(0x5E5637885F29BC2B), U64(0x7EBA726D8C94094B), U64(0x0A56A5F0BFE39272), U64(0xD79476A84EE20D06),
 269    U64(0x9E4C1269BAA4BF37), U64(0x17EFEE45B0DEE640), U64(0x1D95B0A5FCF90BC6), U64(0x93CBE0B699C2585D),
 270    U64(0x65FA4F227A2B6D79), U64(0xD5F9E858292504D5), U64(0xC2B5A03F71471A6F), U64(0x59300222B4561E00),
 271    U64(0xCE2F8642CA0712DC), U64(0x7CA9723FBB2E8988), U64(0x2785338347F2BA08), U64(0xC61BB3A141E50E8C),
 272    U64(0x150F361DAB9DEC26), U64(0x9F6A419D382595F4), U64(0x64A53DC924FE7AC9), U64(0x142DE49FFF7A7C3D),
 273    U64(0x0C335248857FA9E7), U64(0x0A9C32D5EAE45305), U64(0xE6C42178C4BBB92E), U64(0x71F1CE2490D20B07),
 274    U64(0xF1BCC3D275AFE51A), U64(0xE728E8C83C334074), U64(0x96FBF83A12884624), U64(0x81A1549FD6573DA5),
 275    U64(0x5FA7867CAF35E149), U64(0x56986E2EF3ED091B), U64(0x917F1DD5F8886C61), U64(0xD20D8C88C8FFE65F),
 276    U64(0x31D71DCE64B2C310), U64(0xF165B587DF898190), U64(0xA57E6339DD2CF3A0), U64(0x1EF6E6DBB1961EC9),
 277    U64(0x70CC73D90BC26E24), U64(0xE21A6B35DF0C3AD7), U64(0x003A93D8B2806962), U64(0x1C99DED33CB890A1),
 278    U64(0xCF3145DE0ADD4289), U64(0xD0E4427A5514FB72), U64(0x77C621CC9FB3A483), U64(0x67A34DAC4356550B),
 279    U64(0xF8D626AAAF278509),
 280 };
 281
 282 uint64 *RandomPiece     =Random64;
 283 uint64 *RandomCastle    =Random64+768;
 284 uint64 *RandomEnPassant =Random64+772;
 285 uint64 *RandomTurn      =Random64+780;
 286
 287
 288 uint64
 289 hash (int moveNr)
 290 {
 291     int r, f, p_enc, squareNr, pieceGroup;
 292     uint64 key=0, holdingsKey=0, Zobrist;
 293     VariantClass v = gameInfo.variant;
 294
 295     switch(v) {
 296         case VariantNormal:
 297         case VariantFischeRandom: // compatible with normal
 298         case VariantNoCastle:
 299         case VariantXiangqi: // for historic reasons; does never collide anyway because of other King type
 300             break;
 301         case VariantGiveaway: // in opening same as suicide
 302             key += VariantSuicide;
 303             break;
 304         case VariantGothic: // these are special cases of CRC, and can share book
 305         case VariantCapablanca:
 306             v = VariantCapaRandom;
 307         default:
 308             key += v; // variant type incorporated in key to allow mixed books without collisions
 309     }
 310
 311     for(f=0; f<BOARD_WIDTH; f++){
 312         for(r=0; r<BOARD_HEIGHT;r++){
 313             ChessSquare p = boards[moveNr][r][f];
 314             if(f == BOARD_LEFT-1 || f == BOARD_RGHT) continue; // between board and holdings
 315             if(p != EmptySquare){
 316                     int j = (int)p, promoted = 0;
 317                     j -= (j >= (int)BlackPawn) ? (int)BlackPawn :(int)WhitePawn;
 318                     if(j >= CHUPROMOTED WhitePawn) promoted++, j -= CHUPROMOTED WhitePawn;
 319                     if(j > (int)WhiteQueen) j++;  // make space for King
 320                     if(j > (int) WhiteKing) j = (int)WhiteQueen + 1;
 321                     p_enc = 2*j + ((int)p < (int)BlackPawn);
 322                     // holdings squares get nmbers immediately after board; first left, then right holdings
 323                     if(f == BOARD_LEFT-2) squareNr = (BOARD_RGHT - BOARD_LEFT)*BOARD_HEIGHT + r; else
 324                     if(f == BOARD_RGHT+1) squareNr = (BOARD_RGHT - BOARD_LEFT + 1)*BOARD_HEIGHT + r; else
 325                     squareNr = (BOARD_RGHT - BOARD_LEFT)*r + (f - BOARD_LEFT);
 326                     // note that in normal Chess squareNr < 64 and p_enc < 12. The following code
 327                     // maps other pieces and squares in this range, and then modify the corresponding
 328                     // Zobrist random by rotating its bitpattern according to what the piece really was.
 329                     pieceGroup = p_enc / 12;
 330                     p_enc      = p_enc % 12;
 331                     Zobrist = RandomPiece[64*p_enc + (squareNr & 63)];
 332                     if(pieceGroup & 4) Zobrist *= 987654321;
 333                     switch(pieceGroup & 3) {
 334                         case 1: // pieces 5-10 (FEACWM)
 335                                 Zobrist = (Zobrist << 16) ^ (Zobrist >> 48);
 336                                 break;
 337                         case 2: // pieces 11-16 (OHIJGD)
 338                                 Zobrist = (Zobrist << 32) ^ (Zobrist >> 32);
 339                                 break;
 340                         case 3: // pieces 17-20 (VLSU)
 341                                 Zobrist = (Zobrist << 48) ^ (Zobrist >> 16);
 342                                 break;
 343                     }
 344                     if(promoted) Zobrist ^= 123456789*RandomPiece[squareNr & 63];
 345                     if(squareNr &  64) Zobrist = (Zobrist << 8) ^ (Zobrist >> 56);
 346                     if(squareNr & 128) Zobrist = (Zobrist << 4) ^ (Zobrist >> 60);
 347                     // holdings have separate (additive) key, to encode presence of multiple pieces on same square
 348                     if(f == BOARD_LEFT-2) holdingsKey += Zobrist * boards[moveNr][r][f+1]; else
 349                     if(f == BOARD_RGHT+1) holdingsKey += Zobrist * boards[moveNr][r][f-1]; else
 350                 key ^= Zobrist;
 351             }
 352         }
 353     }
 354
 355     if(boards[moveNr][CASTLING][2] != NoRights) {
 356         if(boards[moveNr][CASTLING][0] != NoRights) key^=RandomCastle[0];
 357         if(boards[moveNr][CASTLING][1] != NoRights) key^=RandomCastle[1];
 358     }
 359     if(boards[moveNr][CASTLING][5] != NoRights) {
 360         if(boards[moveNr][CASTLING][3] != NoRights) key^=RandomCastle[2];
 361         if(boards[moveNr][CASTLING][4] != NoRights) key^=RandomCastle[3];
 362     }
 363
 364     f = boards[moveNr][EP_STATUS];
 365     if(f >= 0 && f < 8){
 366         if(!WhiteOnMove(moveNr)){
 367             // the test for neighboring Pawns might not be needed,
 368             // as epStatus already kept track of it, but better safe than sorry.
 369             if((f>0 && boards[moveNr][3][f-1]==BlackPawn)||
 370                (f<7 && boards[moveNr][3][f+1]==BlackPawn)){
 371                 key^=RandomEnPassant[f];
 372             }
 373         }else{
 374             if((f>0 && boards[moveNr][4][f-1]==WhitePawn)||
 375                (f<7 && boards[moveNr][4][f+1]==WhitePawn)){
 376                 key^=RandomEnPassant[f];
 377             }
 378         }
 379     }
 380
 381     if(WhiteOnMove(moveNr)){
 382         key^=RandomTurn[0];
 383     }
 384     return key + holdingsKey;
 385 }
 386
 387 #define MOVE_BUF 100
 388
 389 // fs routines read from memory buffer if no file specified
 390
 391 static unsigned char *memBuf, *memPtr;
 392 static int bufSize;
 393 Boolean mcMode;
 394
 395 int
 396 fsseek (FILE *f, int n, int mode)
 397 {
 398     if(f) return fseek(f, n, mode);
 399     if(mode == SEEK_SET) memPtr = memBuf + n; else
 400     if(mode == SEEK_END) memPtr = memBuf + 16*bufSize + n;
 401     return memPtr < memBuf || memPtr > memBuf + 16*bufSize;
 402 }
 403
 404 int
 405 fstell (FILE *f)
 406 {
 407   if(f) return ftell(f);
 408   return memPtr - memBuf;
 409 }
 410
 411 int
 412 fsgetc (FILE *f)
 413 {
 414   if(f) return fgetc(f);
 415   if(memPtr >= memBuf + 16*bufSize) return EOF;
 416   return *memPtr++ ;
 417 }
 418
 419 int
 420 int_from_file (FILE *f, int l, uint64 *r)
 421 {
 422     int i,c;
 423     for(i=0;i<l;i++){
 424         c=fsgetc(f);
 425         if(c==EOF){
 426             return 1;
 427         }
 428         (*r)=((*r)<<8)+c;
 429     }
 430     return 0;
 431 }
 432
 433 int
 434 entry_from_file (FILE *f, entry_t *entry)
 435 {
 436     int ret;
 437     uint64 r;
 438     if(!f) { *entry = *(entry_t*) memPtr; memPtr += 16; return 0; }
 439     ret=int_from_file(f,8,&r);
 440     if(ret) return 1;
 441     entry->key=r;
 442     ret=int_from_file(f,2,&r);
 443     if(ret) return 1;
 444     entry->move=r;
 445     ret=int_from_file(f,2,&r);
 446     if(ret) return 1;
 447     entry->weight=r;
 448     ret=int_from_file(f,2,&r);
 449     if(ret) return 1;
 450     entry->learnCount=r;
 451     ret=int_from_file(f,2,&r);
 452     if(ret) return 1;
 453     entry->learnPoints=r;
 454     return 0;
 455 }
 456
 457 int
 458 find_key (FILE *f, uint64 key, entry_t *entry)
 459 {
 460     int first, last, middle;
 461     entry_t last_entry,middle_entry;
 462     first=-1;
 463     if(fsseek(f,-16,SEEK_END)){
 464         *entry=entry_none;
 465         entry->key=key+1; //hack
 466         return -1;
 467     }
 468     last=fstell(f)/16;
 469     entry_from_file(f,&last_entry);
 470     while(1){
 471         if(last-first==1){
 472             *entry=last_entry;
 473             return last;
 474         }
 475         middle=(first+last)/2;
 476         fsseek(f,16*middle,SEEK_SET);
 477         entry_from_file(f,&middle_entry);
 478         if(key<=middle_entry.key){
 479             last=middle;
 480             last_entry=middle_entry;
 481         }else{
 482             first=middle;
 483         }
 484     }
 485 }
 486
 487 void
 488 move_to_string (char move_s[6], uint16 move)
 489 {
 490     int f,fr,ff,t,tr,tf,p;
 491     int width = BOARD_RGHT - BOARD_LEFT, size; // allow for alternative board formats
 492
 493     size = width * BOARD_HEIGHT;
 494     p    = move / (size*size);
 495     move = move % (size*size);
 496     f  = move / size;
 497     fr = f / width;
 498     ff = f % width;
 499     t  = move % size;
 500     tr = t / width;
 501     tf = t % width;
 502     move_s[0] = ff + 'a';
 503     move_s[1] = fr + '1' - (BOARD_HEIGHT == 10);
 504     move_s[2] = tf + 'a';
 505     move_s[3] = tr + '1' - (BOARD_HEIGHT == 10);
 506
 507     if(IS_SHOGI(gameInfo.variant) && p) {
 508         if(p == 2) p = 10;     // Lion moves, for boards so big that 10 is out of range
 509         else if(p != 7) p = 8; // use '+' for all others that do not explicitly defer
 510     }
 511
 512     // kludge: encode drops as special promotion code
 513     if(gameInfo.holdingsSize && p == 9) {
 514         move_s[0] = f + '@'; // from square encodes piece type
 515         move_s[1] = '@';     // drop symbol
 516         p = 0;
 517     } else if(p == 10) { // decode Lion move
 518
 519         p = 0;
 520     }
 521
 522     // add promotion piece, if any
 523     if(p){
 524         move_s[4] = promote_pieces[p];
 525         move_s[5] = '\0';
 526     }else{
 527         move_s[4] = '\0';
 528     }
 529
 530     if(gameInfo.variant != VariantNormal) return;
 531
 532     // correct FRC-style castlings in variant normal.
 533     // [HGM] This is buggy code! e1h1 could very well be a normal R or Q move.
 534     if(!strcmp(move_s,"e1h1")){
 535       safeStrCpy(move_s,"e1g1", 6);
 536     }else  if(!strcmp(move_s,"e1a1")){
 537       safeStrCpy(move_s,"e1c1", 6);
 538     }else  if(!strcmp(move_s,"e8h8")){
 539       safeStrCpy(move_s,"e8g8", 6);
 540     }else  if(!strcmp(move_s,"e8a8")){
 541       safeStrCpy(move_s,"e8c8", 6);
 542     }
 543 }
 544
 545 int
 546 GetBookMoves (FILE *f, int moveNr, entry_t entries[], int max)
 547 {   // retrieve all entries for given position from book in 'entries', return number.
 548     entry_t entry;
 549     int offset;
 550     uint64 key;
 551     int count;
 552     int ret;
 553
 554     key = hash(moveNr);
 555     if(appData.debugMode) fprintf(debugFP, "book key = %08x%08x\n", (unsigned int)(key>>32), (unsigned int)key);
 556
 557     offset=find_key(f, key, &entry);
 558     if(entry.key != key) {
 559           return FALSE;
 560     }
 561     entries[0] = entry;
 562     count=1;
 563     fsseek(f, 16*(offset+1), SEEK_SET);
 564     while(1){
 565         ret=entry_from_file(f, &entry);
 566         if(ret){
 567             break;
 568         }
 569         if(entry.key != key){
 570             break;
 571         }
 572         if(count == max) break;
 573         entries[count++] = entry;
 574     }
 575     return count;
 576 }
 577
 578 static int dirty;
 579
 580 int
 581 ReadFromBookFile (int moveNr, char *book, entry_t entries[])
 582 {   // retrieve all entries for given position from book in 'entries', return number.
 583     static FILE *f = NULL;
 584     static char curBook[MSG_SIZ];
 585
 586     if(book == NULL) return -1;
 587     if(dirty) { if(f) fclose(f); dirty = 0; f = NULL; }
 588     if(!f || strcmp(book, curBook)){ // keep book file open until book changed
 589         strncpy(curBook, book, MSG_SIZ);
 590         if(f) fclose(f);
 591         f = fopen(book,"rb");
 592     }
 593     if(!f){
 594         DisplayError(_("Polyglot book not valid"), 0);
 595         appData.usePolyglotBook = FALSE;
 596         return -1;
 597     }
 598
 599     return GetBookMoves(f, moveNr, entries, MOVE_BUF);
 600 }
 601
 602 // next three made into subroutines to facilitate future changes in storage scheme (e.g. 2 x 3 bytes)
 603
 604 static int
 605 wins(entry_t *e)
 606 {
 607     return e->learnPoints;
 608 }
 609
 610 static int
 611 losses(entry_t *e)
 612 {
 613     return e->learnCount;
 614 }
 615
 616 static void
 617 CountMove (entry_t *e, int result)
 618 {
 619     switch(result) {
 620       case 0: e->learnCount ++; break;
 621       case 1: e->learnCount ++; // count draw as win + loss
 622       case 2: e->learnPoints ++; break;
 623     }
 624 }
 625
 626 #define MERGESIZE 2048
 627 #define HASHSIZE  1024*1024*4
 628
 629 entry_t *memBook, *hashTab, *mergeBuf;
 630 int bookSize=1, mergeSize=1, mask = HASHSIZE-1;
 631
 632 void
 633 InitMemBook ()
 634 {
 635     static int initDone = FALSE;
 636     if(initDone) return;
 637     memBook  = (entry_t *) calloc(1024*1024, sizeof(entry_t));
 638     hashTab  = (entry_t *) calloc(HASHSIZE,  sizeof(entry_t));
 639     mergeBuf = (entry_t *) calloc(MERGESIZE+5, sizeof(entry_t));
 640     memBook[0].key  = -1LL;
 641     mergeBuf[0].key = -1LL;
 642     initDone = TRUE;
 643 }
 644
 645 char *
 646 MCprobe (moveNr)
 647 {
 648     int count, count2, games, i, choice=0;
 649     entry_t entries[MOVE_BUF];
 650     float nominal[MOVE_BUF], tot, deficit, max, min;
 651     static char move_s[6];
 652
 653     InitMemBook();
 654     memBuf = (unsigned char*) memBook; bufSize = bookSize;   // in MC mode book resides in memory
 655     count = GetBookMoves(NULL, moveNr, entries, MOVE_BUF);
 656     if(count < 0) count = 0; // don't care about miss yet
 657     memBuf = (unsigned char*) mergeBuf; bufSize = mergeSize; // there could be moves still waiting to be merged
 658     count2 = count + GetBookMoves(NULL, moveNr, entries+count, MOVE_BUF - count);
 659     if(appData.debugMode) fprintf(debugFP, "MC probe: %d/%d (%d+%d)\n", count, count2,bookSize,mergeSize);
 660     if(!count2) return NULL;
 661     tot = games = 0;
 662     for(i=0; i<count2; i++) {
 663         float w = wins(entries+i) + 10., l = losses(entries+i) + 10.;
 664         float h = (w*w*w*w + 22500.*w*w) / (l*l*l*l + 22500.*l*l);
 665         tot += nominal[i] = h;
 666         games += wins(entries+i) + losses(entries+i);
 667     }
 668     tot = games / tot; max = min = 0;
 669     for(i=0; i<count2; i++) {
 670         nominal[i] *= tot; // normalize so they sum to games
 671         deficit = nominal[i] - (wins(entries+i) + losses(entries+i));
 672         if(deficit > max) max = deficit, choice = i;
 673         if(deficit < min) min = deficit;
 674     } // note that a single move will never be underplayed
 675     if(max - min > 0.5*sqrt(nominal[choice])) { // if one of the listed moves is significantly under-played, play it now.
 676         move_to_string(move_s, entries[choice].move);
 677         if(appData.debugMode) fprintf(debugFP, "book move field = %d\n", entries[choice].move);
 678         return move_s;
 679     }
 680     return NULL; // otherwise fake book miss to force engine think, hoping for hitherto unplayed move.
 681 }
 682
 683 char
 684 *ProbeBook (int moveNr, char *book)
 685 {   //
 686     entry_t entries[MOVE_BUF];
 687     int count;
 688     int i, j;
 689     static char move_s[6];
 690     int total_weight;
 691
 692     if(moveNr >= 2*appData.bookDepth) return NULL;
 693     if(mcMode) return MCprobe(moveNr);
 694
 695     if((count = ReadFromBookFile(moveNr, book, entries)) <= 0) return NULL; // no book, or no hit
 696
 697     if(appData.bookStrength != 50) { // transform weights
 698         double power = 0, maxWeight = 0.0;
 699         if(appData.bookStrength) power = (100.-appData.bookStrength)/appData.bookStrength;
 700         for(i=0; i<count; i++) if(entries[i].weight > maxWeight) maxWeight = entries[i].weight;
 701         for(i=0; i<count; i++){
 702             double weight = entries[i].weight / maxWeight;
 703               if(weight > 0)
 704                 entries[i].weight = appData.bookStrength || weight == 1.0 ? 1e4*exp(power * log(weight)) + 0.5 : 0.0;
 705         }
 706     }
 707     total_weight = 0;
 708     for(i=0; i<count; i++){
 709         total_weight += entries[i].weight;
 710     }
 711     if(total_weight == 0) return NULL; // force book miss rather than playing moves with weight 0.
 712     j = (random() & 0xFFF) * total_weight >> 12; // create random < total_weight
 713     total_weight = 0;
 714     for(i=0; i<count; i++){
 715         total_weight += entries[i].weight;
 716         if(total_weight > j) break;
 717     }
 718     if(i >= count) DisplayFatalError(_("Book Fault"), 0, 1); // safety catch, cannot happen
 719     move_to_string(move_s, entries[i].move);
 720     if(appData.debugMode) fprintf(debugFP, "book move field = %d\n", entries[i].move);
 721
 722     return move_s;
 723 }
 724
 725 extern char yy_textstr[];
 726 entry_t lastEntries[MOVE_BUF];
 727
 728 char *
 729 MovesToText(int count, entry_t *entries)
 730 {
 731         int i, totalWeight = 0;
 732         char algMove[12];
 733         char *p = (char*) malloc(40*count+1);
 734         for(i=0; i<count; i++) totalWeight += entries[i].weight;
 735         *p = 0;
 736         for(i=0; i<count; i++) {
 737             char buf[MSG_SIZ];
 738             move_to_string(algMove, entries[i].move);
 739             buf[0] = NULLCHAR;
 740             if(entries[i].learnCount || entries[i].learnPoints)
 741                 snprintf(buf, MSG_SIZ, " {%d/%d}", entries[i].learnPoints, entries[i].learnCount);
 742             snprintf(p+strlen(p), 40, "%5.1f%% %5d %s%s\n", 100*entries[i].weight/(totalWeight+0.001),
 743                                         entries[i].weight, algMove, buf);
 744 //lastEntries[i] = entries[i];
 745         }
 746         return p;
 747 }
 748
 749 static int
 750 CoordsToMove (int fromX, int fromY, int toX, int toY, char promoChar)
 751 {
 752     int i, width = BOARD_RGHT - BOARD_LEFT;
 753     int to = toX - BOARD_LEFT + toY * width;
 754     int from = fromX - BOARD_LEFT + fromY * width;
 755     for(i=0; promote_pieces[i]; i++) if(promote_pieces[i] == promoChar) break;
 756     if(!promote_pieces[i]) i = 0;
 757     else if(i == 9 && gameInfo.variant == VariantChu) i = 1; // on 12x12 only 3 promotion codes available, so use 1 to indicate promotion
 758     if(fromY == DROP_RANK) i = 9, from = ToUpper(PieceToChar(fromX)) - '@';
 759     return to + (i * width * BOARD_HEIGHT + from) * width * BOARD_HEIGHT;
 760 }
 761
 762 int
 763 TextToMoves (char *text, int moveNum, entry_t *entries)
 764 {
 765         int i, w, count=0;
 766         uint64 hashKey = hash(moveNum);
 767         int  fromX, fromY, toX, toY;
 768         ChessMove  moveType;
 769         char promoChar, valid;
 770         float dummy;
 771
 772         entries[0].key = hashKey; // make sure key is returned even if no moves
 773         while((i=sscanf(text, "%f%%%d", &dummy, &w))==2 || (i=sscanf(text, "%d", &w))==1) {
 774             if(i == 2) text = strchr(text, '%') + 1;  // skip percentage
 775             if(w == 1) text = strstr(text, "1 ") + 2; // skip weight that could be recognized as move number one
 776             valid = ParseOneMove(text, moveNum, &moveType, &fromX, &fromY, &toX, &toY, &promoChar);
 777             text = strstr(text, yy_textstr) + strlen(yy_textstr); // skip what we parsed
 778             if(!valid || moveType != NormalMove && moveType != WhiteDrop && moveType != BlackDrop
 779                                                 && moveType != WhitePromotion && moveType != BlackPromotion
 780                                                 && moveType != WhiteCapturesEnPassant && moveType != BlackCapturesEnPassant
 781                                                 && moveType != WhiteKingSideCastle && moveType != BlackKingSideCastle
 782                                                 && moveType != WhiteQueenSideCastle && moveType != BlackQueenSideCastle
 783                                                 && moveType != WhiteNonPromotion && moveType != BlackNonPromotion) continue;
 784             if(*text == ' ' && sscanf(text+1, "{%hd/%hd}", &entries[count].learnPoints, &entries[count].learnCount) == 2) {
 785                 text = strchr(text+1, '}') + 1;
 786             } else {
 787                 entries[count].learnPoints = 0;
 788                 entries[count].learnCount  = 0;
 789             }
 790             entries[count].move = CoordsToMove(fromX, fromY, toX, toY, promoChar);
 791             entries[count].key  = hashKey;
 792             entries[count].weight = w;
 793             count++;
 794         }
 795         return count;
 796 }
 797
 798 Boolean bookUp;
 799 int currentCount;
 800
 801 Boolean
 802 DisplayBook (int moveNr)
 803 {
 804     entry_t entries[MOVE_BUF];
 805     int count;
 806     char *p;
 807     if(!bookUp) return FALSE;
 808     count = currentCount = ReadFromBookFile(moveNr, appData.polyglotBook, entries);
 809     if(count < 0) return FALSE;
 810     p = MovesToText(count, entries);
 811     EditTagsPopUp(p, NULL);
 812     free(p);
 813     addToBookFlag = FALSE;
 814     return TRUE;
 815 }
 816
 817 void
 818 EditBookEvent()
 819 {
 820       bookUp = TRUE;
 821         bookUp = DisplayBook(currentMove);
 822 }
 823
 824 void
 825 int_to_file (FILE *f, int l, uint64 r)
 826 {
 827     int i;
 828     for(i=l-1;i>=0;i--) fputc(r>>8*i & 255, f);
 829 }
 830
 831 void
 832 entry_to_file (FILE *f, entry_t *entry)
 833 {
 834     int_to_file(f,8,entry->key);
 835     int_to_file(f,2,entry->move);
 836     int_to_file(f,2,entry->weight);
 837     int_to_file(f,2,entry->learnCount);
 838     int_to_file(f,2,entry->learnPoints);
 839 }
 840
 841 char buf1[4096], buf2[4096];
 842
 843 void
 844 SaveToBook (char *text)
 845 {
 846     entry_t entries[MOVE_BUF], entry;
 847     int count = TextToMoves(text, currentMove, entries);
 848     int offset, i, len1=0, len2, readpos=0, writepos=0;
 849     FILE *f;
 850     if(!count && !currentCount) return;
 851     f=fopen(appData.polyglotBook, "rb+");
 852     if(!f){     DisplayError(_("Polyglot book not valid"), 0); return; }
 853     offset=find_key(f, entries[0].key, &entry);
 854     if(entries[0].key != entry.key && currentCount) {
 855           DisplayError(_("Hash keys are different"), 0);
 856           fclose(f);
 857           return;
 858     }
 859     if(count != currentCount) {
 860         readpos = 16*(offset + currentCount);
 861         writepos = 16*(offset + count);
 862         fsseek(f, readpos, SEEK_SET);
 863         readpos += len1 = fread(buf1, 1, 4096 - 16*currentCount, f); // salvage some entries immediately behind change
 864     }
 865     fsseek(f, 16*(offset), SEEK_SET);
 866     for(i=0; i<count; i++) entry_to_file(f, entries + i); // save the change
 867     if(count != currentCount) {
 868         do {
 869             for(i=0; i<len1; i++) buf2[i] = buf1[i]; len2 = len1;
 870             if(readpos > writepos) {
 871                 fsseek(f, readpos, SEEK_SET);
 872                 readpos += len1 = fread(buf1, 1, 4096, f);
 873             } else len1 = 0; // wrote already past old EOF
 874             fsseek(f, writepos, SEEK_SET);
 875             fwrite(buf2, 1, len2, f);
 876             writepos += len2;
 877         } while(len1);
 878     }
 879     dirty = 1;
 880     fclose(f);
 881 }
 882
 883 void
 884 NewEntry (entry_t *e, uint64 key, int move, int result)
 885 {
 886     e->key = key;
 887     e->move = move;
 888     e->learnPoints = 0;
 889     e->learnCount = 0;
 890     CountMove(e, result);
 891 }
 892
 893 void
 894 Merge ()
 895 {
 896     int i;
 897
 898     if(appData.debugMode) fprintf(debugFP, "book merge %d moves (old size %d)\n", mergeSize, bookSize);
 899
 900     bookSize += --mergeSize;
 901     for(i=bookSize-1; mergeSize; i--) {
 902         while(mergeSize && (i < mergeSize || mergeBuf[mergeSize-1].key >= memBook[i-mergeSize].key))
 903             memBook[i--] = mergeBuf[--mergeSize];
 904         if(i < 0) break;
 905         memBook[i] = memBook[i-mergeSize];
 906     }
 907     if(mergeSize) DisplayFatalError("merge error", 0, 0); // impossible
 908     mergeSize = 1;
 909     mergeBuf[0].key = -1LL;
 910 }
 911
 912 void
 913 AddToBook (int moveNr, int result)
 914 {
 915     entry_t entry;
 916     int offset, start, move;
 917     uint64 key;
 918     int i, j, fromY, toY;
 919     char fromX, toX, promo;
 920 extern char moveList[][MOVE_LEN];
 921
 922     if(!moveList[moveNr][0] || moveList[moveNr][0] == '\n') return; // could be terminal position
 923
 924     if(appData.debugMode) fprintf(debugFP, "add move %d to book %s", moveNr, moveList[moveNr]);
 925
 926     // calculate key and book representation of move
 927     key = hash(moveNr);
 928     if(moveList[moveNr][1] == '@') {
 929         sscanf(moveList[moveNr], "%c@%c%d", &promo, &toX, &toY);
 930         fromX = CharToPiece(WhiteOnMove(moveNr) ? ToUpper(promo) : ToLower(promo));
 931         fromY = DROP_RANK; promo = NULLCHAR;
 932     } else sscanf(moveList[moveNr], "%c%d%c%d%c", &fromX, &fromY, &toX, &toY, &promo), fromX -= AAA, fromY -= ONE - '0';
 933     move = CoordsToMove(fromX, fromY, toX-AAA, toY-ONE+'0', promo);
 934
 935     // if move already in book, just add count
 936     memBuf = (unsigned char*) memBook; bufSize = bookSize;   // in MC mode book resides in memory
 937     offset = find_key(NULL, key, &entry);
 938     while(memBook[offset].key == key) {
 939         if(memBook[offset].move == move) {
 940             CountMove(memBook+offset, result); return;
 941         } else offset++;
 942     }
 943     // move did not occur in the main book
 944     memBuf = (unsigned char*) mergeBuf; bufSize = mergeSize; // it could be amongst moves still waiting to be merged
 945     start = offset = find_key(NULL, key, &entry);
 946     while(mergeBuf[offset].key == key) {
 947         if(mergeBuf[offset].move == move) {
 948             if(appData.debugMode) fprintf(debugFP, "found in book merge buf @ %d\n", offset);
 949             CountMove(mergeBuf+offset, result); return;
 950         } else offset++;
 951     }
 952     if(start != offset) { // position was in mergeBuf, but move is new
 953         if(appData.debugMode) fprintf(debugFP, "add in book merge buf @ %d\n", offset);
 954         for(i=mergeSize++; i>offset; i--) mergeBuf[i] = mergeBuf[i-1]; // make room
 955         NewEntry(mergeBuf+offset, key, move, result);
 956         return;
 957     }
 958     // position was not in mergeBuf; look in hash table
 959     i = (key & mask); offset = -1;
 960     while(hashTab[i].key) { // search in hash table (necessary because sought item could be re-hashed)
 961         if(hashTab[i].key == 1 && offset < 0) offset = i; // remember first invalidated entry we pass
 962         if(!((hashTab[i].key - key) & ~1)) { // hit
 963             if(hashTab[i].move == move) {
 964                 CountMove(hashTab+i, result);
 965                 for(j=mergeSize++; j>start; j--) mergeBuf[j] = mergeBuf[j-1];
 966             } else {
 967                 // position already in hash now occurs with different move; move both moves to mergeBuf
 968                 for(j=mergeSize+1; j>start+1; j--) mergeBuf[j] = mergeBuf[j-2];
 969                 NewEntry(mergeBuf+start+1, key, move, result); mergeSize += 2;
 970             }
 971             hashTab[i].key = 1; // kludge to invalidate hash entry
 972             mergeBuf[start] = hashTab[i]; mergeBuf[start].key = key;
 973             if(mergeSize >= MERGESIZE) Merge();
 974             return;
 975         }
 976         i = i+1 & mask; // wrap!
 977     }
 978     // position did not yet occur in hash table. Put it there
 979     if(offset < 0) offset = i;
 980     NewEntry(hashTab+offset, key, move, result);
 981     if(appData.debugMode)
 982         fprintf(debugFP, "book hash @ %d (%d-%d)\n", offset, hashTab[offset].learnPoints, hashTab[offset].learnCount);
 983 }
 984
 985 void
 986 AddGameToBook (int always)
 987 {
 988     int i, result;
 989
 990     if(!mcMode && !always) return;
 991
 992     InitMemBook();
 993     switch(gameInfo.result) {
 994       case GameIsDrawn: result = 1; break;
 995       case WhiteWins:   result = 2; break;
 996       case BlackWins:   result = 0; break;
 997       default: return; // don't treat games with unknown result
 998     }
 999
1000     if(appData.debugMode) fprintf(debugFP, "add game to book (%d-%d)\n", backwardMostMove, forwardMostMove);
1001     for(i=backwardMostMove; i<forwardMostMove && i < 2*appData.bookDepth; i++)
1002         AddToBook(i, WhiteOnMove(i) ? result : 2-result); // flip result when black moves
1003 }
1004
1005 void
1006 PlayBookMove(char *text, int index)
1007 {
1008     char *start = text+index, *end = start;
1009     while(start > text && start[-1] != ' ' && start[-1] != '\t') start--;
1010     while(*end && *++end != ' ' && *end != '\n'); *end = NULLCHAR; // find clicked word
1011     if(start != end) TypeInDoneEvent(start); // fake it was typed in move type-in
1012 }
1013
1014 void
1015 FlushBook ()
1016 {
1017     FILE *f;
1018     int i;
1019
1020     InitMemBook();
1021     Merge(); // flush merge buffer to memBook
1022
1023     if(f = fopen(appData.polyglotBook, "wb")) {
1024         for(i=0; i<bookSize; i++) {
1025             entry_t entry = memBook[i];
1026             entry.weight = entry.learnPoints;
1027 //          entry.learnPoints = 0;
1028 //          entry.learnCount  = 0;
1029             entry_to_file(f, &entry);
1030         }
1031     } else DisplayError(_("Could not create book"), 0);
1032 }