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