book.c

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