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