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