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 != WhiteNonPromotion && moveType != BlackNonPromotion) continue;
 763             if(*text == ' ' && sscanf(text+1, "{%hd/%hd}", &entries[count].learnPoints, &entries[count].learnCount) == 2) {
 764                 text = strchr(text+1, '}') + 1;
 765             } else {
 766                 entries[count].learnPoints = 0;
 767                 entries[count].learnCount  = 0;
 768             }
 769             entries[count].move = CoordsToMove(fromX, fromY, toX, toY, promoChar);
 770             entries[count].key  = hashKey;
 771             entries[count].weight = w;
 772             count++;
 773         }
 774         return count;
 775 }
 776
 777 Boolean bookUp;
 778 int currentCount;
 779
 780 Boolean
 781 DisplayBook (int moveNr)
 782 {
 783     entry_t entries[MOVE_BUF];
 784     int count;
 785     char *p;
 786     if(!bookUp) return FALSE;
 787     count = currentCount = ReadFromBookFile(moveNr, appData.polyglotBook, entries);
 788     if(count < 0) return FALSE;
 789     p = MovesToText(count, entries);
 790     EditTagsPopUp(p, NULL);
 791     free(p);
 792     return TRUE;
 793 }
 794
 795 void
 796 EditBookEvent()
 797 {
 798       bookUp = TRUE;
 799         bookUp = DisplayBook(currentMove);
 800 }
 801
 802 void
 803 int_to_file (FILE *f, int l, uint64 r)
 804 {
 805     int i;
 806     for(i=l-1;i>=0;i--) fputc(r>>8*i & 255, f);
 807 }
 808
 809 void
 810 entry_to_file (FILE *f, entry_t *entry)
 811 {
 812     int_to_file(f,8,entry->key);
 813     int_to_file(f,2,entry->move);
 814     int_to_file(f,2,entry->weight);
 815     int_to_file(f,2,entry->learnCount);
 816     int_to_file(f,2,entry->learnPoints);
 817 }
 818
 819 char buf1[4096], buf2[4096];
 820
 821 void
 822 SaveToBook (char *text)
 823 {
 824     entry_t entries[MOVE_BUF], entry;
 825     int count = TextToMoves(text, currentMove, entries);
 826     int offset, i, len1=0, len2, readpos=0, writepos=0;
 827     FILE *f;
 828     if(!count && !currentCount) return;
 829     f=fopen(appData.polyglotBook, "rb+");
 830     if(!f){     DisplayError(_("Polyglot book not valid"), 0); return; }
 831     offset=find_key(f, entries[0].key, &entry);
 832     if(entries[0].key != entry.key && currentCount) {
 833           DisplayError(_("Hash keys are different"), 0);
 834           fclose(f);
 835           return;
 836     }
 837     if(count != currentCount) {
 838         readpos = 16*(offset + currentCount);
 839         writepos = 16*(offset + count);
 840         fsseek(f, readpos, SEEK_SET);
 841         readpos += len1 = fread(buf1, 1, 4096 - 16*currentCount, f); // salvage some entries immediately behind change
 842     }
 843     fsseek(f, 16*(offset), SEEK_SET);
 844     for(i=0; i<count; i++) entry_to_file(f, entries + i); // save the change
 845     if(count != currentCount) {
 846         do {
 847             for(i=0; i<len1; i++) buf2[i] = buf1[i]; len2 = len1;
 848             if(readpos > writepos) {
 849                 fsseek(f, readpos, SEEK_SET);
 850                 readpos += len1 = fread(buf1, 1, 4096, f);
 851             } else len1 = 0; // wrote already past old EOF
 852             fsseek(f, writepos, SEEK_SET);
 853             fwrite(buf2, 1, len2, f);
 854             writepos += len2;
 855         } while(len1);
 856     }
 857     fclose(f);
 858 }
 859
 860 void
 861 NewEntry (entry_t *e, uint64 key, int move, int result)
 862 {
 863     e->key = key;
 864     e->move = move;
 865     e->learnPoints = 0;
 866     e->learnCount = 0;
 867     CountMove(e, result);
 868 }
 869
 870 void
 871 Merge ()
 872 {
 873     int i;
 874
 875     if(appData.debugMode) fprintf(debugFP, "book merge %d moves (old size %d)\n", mergeSize, bookSize);
 876
 877     bookSize += --mergeSize;
 878     for(i=bookSize-1; mergeSize; i--) {
 879         while(mergeSize && (i < mergeSize || mergeBuf[mergeSize-1].key >= memBook[i-mergeSize].key))
 880             memBook[i--] = mergeBuf[--mergeSize];
 881         if(i < 0) break;
 882         memBook[i] = memBook[i-mergeSize];
 883     }
 884     if(mergeSize) DisplayFatalError("merge error", 0, 0); // impossible
 885     mergeSize = 1;
 886     mergeBuf[0].key = -1LL;
 887 }
 888
 889 void
 890 AddToBook (int moveNr, int result)
 891 {
 892     entry_t entry;
 893     int offset, start, move;
 894     uint64 key;
 895     int i, j, fromY, toY;
 896     char fromX, toX, promo;
 897 extern char moveList[][MOVE_LEN];
 898
 899     if(!moveList[moveNr][0] || moveList[moveNr][0] == '\n') return; // could be terminal position
 900
 901     if(appData.debugMode) fprintf(debugFP, "add move %d to book %s", moveNr, moveList[moveNr]);
 902
 903     // calculate key and book representation of move
 904     key = hash(moveNr);
 905     if(moveList[moveNr][1] == '@') {
 906         sscanf(moveList[moveNr], "%c@%c%d", &promo, &toX, &toY);
 907         fromX = CharToPiece(WhiteOnMove(moveNr) ? ToUpper(promo) : ToLower(promo));
 908         fromY = DROP_RANK; promo = NULLCHAR;
 909     } else sscanf(moveList[moveNr], "%c%d%c%d%c", &fromX, &fromY, &toX, &toY, &promo), fromX -= AAA, fromY -= ONE - '0';
 910     move = CoordsToMove(fromX, fromY, toX-AAA, toY-ONE+'0', promo);
 911
 912     // if move already in book, just add count
 913     memBuf = (unsigned char*) memBook; bufSize = bookSize;   // in MC mode book resides in memory
 914     offset = find_key(NULL, key, &entry);
 915     while(memBook[offset].key == key) {
 916         if(memBook[offset].move == move) {
 917             CountMove(memBook+offset, result); return;
 918         } else offset++;
 919     }
 920     // move did not occur in the main book
 921     memBuf = (unsigned char*) mergeBuf; bufSize = mergeSize; // it could be amongst moves still waiting to be merged
 922     start = offset = find_key(NULL, key, &entry);
 923     while(mergeBuf[offset].key == key) {
 924         if(mergeBuf[offset].move == move) {
 925             if(appData.debugMode) fprintf(debugFP, "found in book merge buf @ %d\n", offset);
 926             CountMove(mergeBuf+offset, result); return;
 927         } else offset++;
 928     }
 929     if(start != offset) { // position was in mergeBuf, but move is new
 930         if(appData.debugMode) fprintf(debugFP, "add in book merge buf @ %d\n", offset);
 931         for(i=mergeSize++; i>offset; i--) mergeBuf[i] = mergeBuf[i-1]; // make room
 932         NewEntry(mergeBuf+offset, key, move, result);
 933         return;
 934     }
 935     // position was not in mergeBuf; look in hash table
 936     i = (key & mask); offset = -1;
 937     while(hashTab[i].key) { // search in hash table (necessary because sought item could be re-hashed)
 938         if(hashTab[i].key == 1 && offset < 0) offset = i; // remember first invalidated entry we pass
 939         if(!((hashTab[i].key - key) & ~1)) { // hit
 940             if(hashTab[i].move == move) {
 941                 CountMove(hashTab+i, result);
 942                 for(j=mergeSize++; j>start; j--) mergeBuf[j] = mergeBuf[j-1];
 943             } else {
 944                 // position already in hash now occurs with different move; move both moves to mergeBuf
 945                 for(j=mergeSize+1; j>start+1; j--) mergeBuf[j] = mergeBuf[j-2];
 946                 NewEntry(mergeBuf+start+1, key, move, result); mergeSize += 2;
 947             }
 948             hashTab[i].key = 1; // kludge to invalidate hash entry
 949             mergeBuf[start] = hashTab[i]; mergeBuf[start].key = key;
 950             if(mergeSize >= MERGESIZE) Merge();
 951             return;
 952         }
 953         i = i+1 & mask; // wrap!
 954     }
 955     // position did not yet occur in hash table. Put it there
 956     if(offset < 0) offset = i;
 957     NewEntry(hashTab+offset, key, move, result);
 958     if(appData.debugMode)
 959         fprintf(debugFP, "book hash @ %d (%d-%d)\n", offset, hashTab[offset].learnPoints, hashTab[offset].learnCount);
 960 }
 961
 962 void
 963 AddGameToBook (int always)
 964 {
 965     int i, result;
 966
 967     if(!mcMode && !always) return;
 968
 969     InitMemBook();
 970     switch(gameInfo.result) {
 971       case GameIsDrawn: result = 1; break;
 972       case WhiteWins:   result = 2; break;
 973       case BlackWins:   result = 0; break;
 974       default: return; // don't treat games with unknown result
 975     }
 976
 977     if(appData.debugMode) fprintf(debugFP, "add game to book (%d-%d)\n", backwardMostMove, forwardMostMove);
 978
 979     for(i=backwardMostMove; i<forwardMostMove && i < 2*appData.bookDepth; i++)
 980         AddToBook(i, WhiteOnMove(i) ? result : 2-result); // flip result when black moves
 981 }
 982
 983 void
 984 FlushBook ()
 985 {
 986     FILE *f;
 987     int i;
 988
 989     InitMemBook();
 990     Merge(); // flush merge buffer to memBook
 991
 992     if(f = fopen(appData.polyglotBook, "wb")) {
 993         for(i=0; i<bookSize; i++) {
 994             entry_t entry = memBook[i];
 995             entry.weight = entry.learnPoints;
 996 //          entry.learnPoints = 0;
 997 //          entry.learnCount  = 0;
 998             entry_to_file(f, &entry);
 999         }
1000     } else DisplayError(_("Could not create book"), 0);
1001 }