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