Felicity EGTB generators and probers

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
phhnguyen
Posts: 1454
Joined: Wed Apr 21, 2010 4:58 am
Location: Australia
Full name: Nguyen Hong Pham

Re: Felicity EGTB generators and probers

Post by phhnguyen »

hgm wrote: Sat Apr 27, 2024 5:53 pm I did 3 vs 0 for three pawns quite some time ago, so it cannot be that hard on modern hardware. I am a bit out of touch, so are there any other 3 vs 0 end-games that are of interest? Perhaps H+2P and C+2P?
You are right, we may add a few Pawns too.
Since Rook + any attacker (RX vs 0) are sure and easy wins we may ignore them, but the rest are hard wins and will be interested. Thus it’s good and useful if you generate any of them.
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
User avatar
phhnguyen
Posts: 1454
Joined: Wed Apr 21, 2010 4:58 am
Location: Australia
Full name: Nguyen Hong Pham

Re: Felicity EGTB - Attempt 10: index space for Xiangqi

Post by phhnguyen »

Attempt 10: index space for Xiangqi

If we ignore all two attackers with Rooks, then all attackers 2-vs-0 should be generating are: CC, CN, NN, CP, NP, PP. The below table shows all 729 endgames with those attackers + all configurations of defenders.

The largest index space is kcnaabbkaabb, almost 9 G. Supposedly we need 1 byte for each side to store one index information so we need 9 GB or 18 GB for both sides. When generating we need to store those information in the memory, including some extra information and some sub-table information (say, kcaabbkaabb, kcnaabbkaab…) thus a computer with 32 GB of memory will be fine.

All those endgames have about 167 G indexes, or 167 x 2 sides x 1 byte = 334 GB for both sides. Suppose we compress them with the ratio about 4 times 0.25) then we need 334/4 = 83.5 GB (about 84 GB) hard disk to store.

We need some good computers with 32 GB memory to generate them. They are not very cheap but affordable for the majority of chess lovers. 84 GB is not a problem to store nowadays. However, that size is still a challenge to share/download online.

Code: Select all

All interesting sub-endgames with 2 attackers (order - name - index size):
  1)              kpk            2'511
  2)             kpkb           17'298
  3)             kpka           11'160
  4)            kpkbb           51'057
  5)            kpkab           76'725
  6)            kpkaa           19'530
  7)           kpkabb          225'990
  8)           kpkaab          133'920
  9)          kpkaabb          393'390
 10)             kpbk           17'298
 11)            kpbkb          119'164
 12)            kpbka           76'880
 13)           kpbkbb          351'726
 14)           kpbkab          528'550
 15)           kpbkaa          134'540
 16)          kpbkabb        1'556'820
 17)          kpbkaab          922'560
 18)         kpbkaabb        2'710'020
 19)             kpak           11'160
 20)            kpakb           76'880
 21)            kpaka           49'600
 22)           kpakbb          226'920
 23)           kpakab          341'000
 24)           kpakaa           86'800
 25)          kpakabb        1'004'400
 26)          kpakaab          595'200
 27)         kpakaabb        1'748'400
 28)            kpbbk           51'057
 29)           kpbbkb          351'726
 30)           kpbbka          226'920
 31)          kpbbkbb        1'038'159
 32)          kpbbkab        1'560'075
 33)          kpbbkaa          397'110
 34)         kpbbkabb        4'595'130
 35)         kpbbkaab        2'723'040
 36)        kpbbkaabb        7'998'930
 37)            kpabk           76'725
 38)           kpabkb          528'550
 39)           kpabka          341'000
 40)          kpabkbb        1'560'075
 41)          kpabkab        2'344'375
 42)          kpabkaa          596'750
 43)         kpabkabb        6'905'250
 44)         kpabkaab        4'092'000
 45)        kpabkaabb       12'020'250
 46)            kpaak           19'530
 47)           kpaakb          134'540
 48)           kpaaka           86'800
 49)          kpaakbb          397'110
 50)          kpaakab          596'750
 51)          kpaakaa          151'900
 52)         kpaakabb        1'757'700
 53)         kpaakaab        1'041'600
 54)        kpaakaabb        3'059'700
 55)           kpabbk          225'990
 56)          kpabbkb        1'556'820
 57)          kpabbka        1'004'400
 58)         kpabbkbb        4'595'130
 59)         kpabbkab        6'905'250
 60)         kpabbkaa        1'757'700
 61)        kpabbkabb       20'339'100
 62)        kpabbkaab       12'052'800
 63)       kpabbkaabb       35'405'100
 64)           kpaabk          133'920
 65)          kpaabkb          922'560
 66)          kpaabka          595'200
 67)         kpaabkbb        2'723'040
 68)         kpaabkab        4'092'000
 69)         kpaabkaa        1'041'600
 70)        kpaabkabb       12'052'800
 71)        kpaabkaab        7'142'400
 72)       kpaabkaabb       20'980'800
 73)          kpaabbk          393'390
 74)         kpaabbkb        2'710'020
 75)         kpaabbka        1'748'400
 76)        kpaabbkbb        7'998'930
 77)        kpaabbkab       12'020'250
 78)        kpaabbkaa        3'059'700
 79)       kpaabbkabb       35'405'100
 80)       kpaabbkaab       20'980'800
 81)      kpaabbkaabb       61'631'100
 82)              knk            4'050
 83)             knkb           27'900
 84)             knka           18'000
 85)            knkbb           82'350
 86)            knkab          123'750
 87)            knkaa           31'500
 88)           knkabb          364'500
 89)           knkaab          216'000
 90)          knkaabb          634'500
 91)             knbk           27'900
 92)            knbkb          192'200
 93)            knbka          124'000
 94)           knbkbb          567'300
 95)           knbkab          852'500
 96)           knbkaa          217'000
 97)          knbkabb        2'511'000
 98)          knbkaab        1'488'000
 99)         knbkaabb        4'371'000
100)             knak           18'000
101)            knakb          124'000
102)            knaka           80'000
103)           knakbb          366'000
104)           knakab          550'000
105)           knakaa          140'000
106)          knakabb        1'620'000
107)          knakaab          960'000
108)         knakaabb        2'820'000
109)            knbbk           82'350
110)           knbbkb          567'300
111)           knbbka          366'000
112)          knbbkbb        1'674'450
113)          knbbkab        2'516'250
114)          knbbkaa          640'500
115)         knbbkabb        7'411'500
116)         knbbkaab        4'392'000
117)        knbbkaabb       12'901'500
118)            knabk          123'750
119)           knabkb          852'500
120)           knabka          550'000
121)          knabkbb        2'516'250
122)          knabkab        3'781'250
123)          knabkaa          962'500
124)         knabkabb       11'137'500
125)         knabkaab        6'600'000
126)        knabkaabb       19'387'500
127)            knaak           31'500
128)           knaakb          217'000
129)           knaaka          140'000
130)          knaakbb          640'500
131)          knaakab          962'500
132)          knaakaa          245'000
133)         knaakabb        2'835'000
134)         knaakaab        1'680'000
135)        knaakaabb        4'935'000
136)           knabbk          364'500
137)          knabbkb        2'511'000
138)          knabbka        1'620'000
139)         knabbkbb        7'411'500
140)         knabbkab       11'137'500
141)         knabbkaa        2'835'000
142)        knabbkabb       32'805'000
143)        knabbkaab       19'440'000
144)       knabbkaabb       57'105'000
145)           knaabk          216'000
146)          knaabkb        1'488'000
147)          knaabka          960'000
148)         knaabkbb        4'392'000
149)         knaabkab        6'600'000
150)         knaabkaa        1'680'000
151)        knaabkabb       19'440'000
152)        knaabkaab       11'520'000
153)       knaabkaabb       33'840'000
154)          knaabbk          634'500
155)         knaabbkb        4'371'000
156)         knaabbka        2'820'000
157)        knaabbkbb       12'901'500
158)        knaabbkab       19'387'500
159)        knaabbkaa        4'935'000
160)       knaabbkabb       57'105'000
161)       knaabbkaab       33'840'000
162)      knaabbkaabb       99'405'000
163)              kck            4'050
164)             kckb           27'900
165)             kcka           18'000
166)            kckbb           82'350
167)            kckab          123'750
168)            kckaa           31'500
169)           kckabb          364'500
170)           kckaab          216'000
171)          kckaabb          634'500
172)             kcbk           27'900
173)            kcbkb          192'200
174)            kcbka          124'000
175)           kcbkbb          567'300
176)           kcbkab          852'500
177)           kcbkaa          217'000
178)          kcbkabb        2'511'000
179)          kcbkaab        1'488'000
180)         kcbkaabb        4'371'000
181)             kcak           18'000
182)            kcakb          124'000
183)            kcaka           80'000
184)           kcakbb          366'000
185)           kcakab          550'000
186)           kcakaa          140'000
187)          kcakabb        1'620'000
188)          kcakaab          960'000
189)         kcakaabb        2'820'000
190)            kcbbk           82'350
191)           kcbbkb          567'300
192)           kcbbka          366'000
193)          kcbbkbb        1'674'450
194)          kcbbkab        2'516'250
195)          kcbbkaa          640'500
196)         kcbbkabb        7'411'500
197)         kcbbkaab        4'392'000
198)        kcbbkaabb       12'901'500
199)            kcabk          123'750
200)           kcabkb          852'500
201)           kcabka          550'000
202)          kcabkbb        2'516'250
203)          kcabkab        3'781'250
204)          kcabkaa          962'500
205)         kcabkabb       11'137'500
206)         kcabkaab        6'600'000
207)        kcabkaabb       19'387'500
208)            kcaak           31'500
209)           kcaakb          217'000
210)           kcaaka          140'000
211)          kcaakbb          640'500
212)          kcaakab          962'500
213)          kcaakaa          245'000
214)         kcaakabb        2'835'000
215)         kcaakaab        1'680'000
216)        kcaakaabb        4'935'000
217)           kcabbk          364'500
218)          kcabbkb        2'511'000
219)          kcabbka        1'620'000
220)         kcabbkbb        7'411'500
221)         kcabbkab       11'137'500
222)         kcabbkaa        2'835'000
223)        kcabbkabb       32'805'000
224)        kcabbkaab       19'440'000
225)       kcabbkaabb       57'105'000
226)           kcaabk          216'000
227)          kcaabkb        1'488'000
228)          kcaabka          960'000
229)         kcaabkbb        4'392'000
230)         kcaabkab        6'600'000
231)         kcaabkaa        1'680'000
232)        kcaabkabb       19'440'000
233)        kcaabkaab       11'520'000
234)       kcaabkaabb       33'840'000
235)          kcaabbk          634'500
236)         kcaabbkb        4'371'000
237)         kcaabbka        2'820'000
238)        kcaabbkbb       12'901'500
239)        kcaabbkab       19'387'500
240)        kcaabbkaa        4'935'000
241)       kcaabbkabb       57'105'000
242)       kcaabbkaab       33'840'000
243)      kcaabbkaabb       99'405'000
244)             kppk           61'965
245)            kppkb          426'870
246)            kppka          275'400
247)           kppkbb        1'259'955
248)           kppkab        1'893'375
249)           kppkaa          481'950
250)          kppkabb        5'576'850
251)          kppkaab        3'304'800
252)         kppkaabb        9'707'850
253)            kppbk          426'870
254)           kppbkb        2'940'660
255)           kppbka        1'897'200
256)          kppbkbb        8'679'690
257)          kppbkab       13'043'250
258)          kppbkaa        3'320'100
259)         kppbkabb       38'418'300
260)         kppbkaab       22'766'400
261)        kppbkaabb       66'876'300
262)            kppak          275'400
263)           kppakb        1'897'200
264)           kppaka        1'224'000
265)          kppakbb        5'599'800
266)          kppakab        8'415'000
267)          kppakaa        2'142'000
268)         kppakabb       24'786'000
269)         kppakaab       14'688'000
270)        kppakaabb       43'146'000
271)           kppbbk        1'259'955
272)          kppbbkb        8'679'690
273)          kppbbka        5'599'800
274)         kppbbkbb       25'619'085
275)         kppbbkab       38'498'625
276)         kppbbkaa        9'799'650
277)        kppbbkabb      113'395'950
278)        kppbbkaab       67'197'600
279)       kppbbkaabb      197'392'950
280)           kppabk        1'893'375
281)          kppabkb       13'043'250
282)          kppabka        8'415'000
283)         kppabkbb       38'498'625
284)         kppabkab       57'853'125
285)         kppabkaa       14'726'250
286)        kppabkabb      170'403'750
287)        kppabkaab      100'980'000
288)       kppabkaabb      296'628'750
289)           kppaak          481'950
290)          kppaakb        3'320'100
291)          kppaaka        2'142'000
292)         kppaakbb        9'799'650
293)         kppaakab       14'726'250
294)         kppaakaa        3'748'500
295)        kppaakabb       43'375'500
296)        kppaakaab       25'704'000
297)       kppaakaabb       75'505'500
298)          kppabbk        5'576'850
299)         kppabbkb       38'418'300
300)         kppabbka       24'786'000
301)        kppabbkbb      113'395'950
302)        kppabbkab      170'403'750
303)        kppabbkaa       43'375'500
304)       kppabbkabb      501'916'500
305)       kppabbkaab      297'432'000
306)      kppabbkaabb      873'706'500
307)          kppaabk        3'304'800
308)         kppaabkb       22'766'400
309)         kppaabka       14'688'000
310)        kppaabkbb       67'197'600
311)        kppaabkab      100'980'000
312)        kppaabkaa       25'704'000
313)       kppaabkabb      297'432'000
314)       kppaabkaab      176'256'000
315)      kppaabkaabb      517'752'000
316)         kppaabbk        9'707'850
317)        kppaabbkb       66'876'300
318)        kppaabbka       43'146'000
319)       kppaabbkbb      197'392'950
320)       kppaabbkab      296'628'750
321)       kppaabbkaa       75'505'500
322)      kppaabbkabb      873'706'500
323)      kppaabbkaab      517'752'000
324)     kppaabbkaabb    1'520'896'500
325)             knpk          222'750
326)            knpkb        1'534'500
327)            knpka          990'000
328)           knpkbb        4'529'250
329)           knpkab        6'806'250
330)           knpkaa        1'732'500
331)          knpkabb       20'047'500
332)          knpkaab       11'880'000
333)         knpkaabb       34'897'500
334)            knpbk        1'534'500
335)           knpbkb       10'571'000
336)           knpbka        6'820'000
337)          knpbkbb       31'201'500
338)          knpbkab       46'887'500
339)          knpbkaa       11'935'000
340)         knpbkabb      138'105'000
341)         knpbkaab       81'840'000
342)        knpbkaabb      240'405'000
343)            knpak          990'000
344)           knpakb        6'820'000
345)           knpaka        4'400'000
346)          knpakbb       20'130'000
347)          knpakab       30'250'000
348)          knpakaa        7'700'000
349)         knpakabb       89'100'000
350)         knpakaab       52'800'000
351)        knpakaabb      155'100'000
352)           knpbbk        4'529'250
353)          knpbbkb       31'201'500
354)          knpbbka       20'130'000
355)         knpbbkbb       92'094'750
356)         knpbbkab      138'393'750
357)         knpbbkaa       35'227'500
358)        knpbbkabb      407'632'500
359)        knpbbkaab      241'560'000
360)       knpbbkaabb      709'582'500
361)           knpabk        6'806'250
362)          knpabkb       46'887'500
363)          knpabka       30'250'000
364)         knpabkbb      138'393'750
365)         knpabkab      207'968'750
366)         knpabkaa       52'937'500
367)        knpabkabb      612'562'500
368)        knpabkaab      363'000'000
369)       knpabkaabb    1'066'312'500
370)           knpaak        1'732'500
371)          knpaakb       11'935'000
372)          knpaaka        7'700'000
373)         knpaakbb       35'227'500
374)         knpaakab       52'937'500
375)         knpaakaa       13'475'000
376)        knpaakabb      155'925'000
377)        knpaakaab       92'400'000
378)       knpaakaabb      271'425'000
379)          knpabbk       20'047'500
380)         knpabbkb      138'105'000
381)         knpabbka       89'100'000
382)        knpabbkbb      407'632'500
383)        knpabbkab      612'562'500
384)        knpabbkaa      155'925'000
385)       knpabbkabb    1'804'275'000
386)       knpabbkaab    1'069'200'000
387)      knpabbkaabb    3'140'775'000
388)          knpaabk       11'880'000
389)         knpaabkb       81'840'000
390)         knpaabka       52'800'000
391)        knpaabkbb      241'560'000
392)        knpaabkab      363'000'000
393)        knpaabkaa       92'400'000
394)       knpaabkabb    1'069'200'000
395)       knpaabkaab      633'600'000
396)      knpaabkaabb    1'861'200'000
397)         knpaabbk       34'897'500
398)        knpaabbkb      240'405'000
399)        knpaabbka      155'100'000
400)       knpaabbkbb      709'582'500
401)       knpaabbkab    1'066'312'500
402)       knpaabbkaa      271'425'000
403)      knpaabbkabb    3'140'775'000
404)      knpaabbkaab    1'861'200'000
405)     knpaabbkaabb    5'467'275'000
406)             knnk          165'645
407)             kcpk          222'750
408)            kcpkb        1'534'500
409)            knnkb        1'141'110
410)            kcpka          990'000
411)            knnka          736'200
412)           knnkbb        3'368'115
413)           kcpkbb        4'529'250
414)           knnkab        5'061'375
415)           kcpkab        6'806'250
416)           kcpkaa        1'732'500
417)           knnkaa        1'288'350
418)          kcpkabb       20'047'500
419)          knnkabb       14'908'050
420)          kcpkaab       11'880'000
421)          knnkaab        8'834'400
422)         kcpkaabb       34'897'500
423)         knnkaabb       25'951'050
424)            kcpbk        1'534'500
425)            knnbk        1'141'110
426)           knnbkb        7'860'980
427)           kcpbkb       10'571'000
428)           kcpbka        6'820'000
429)           knnbka        5'071'600
430)          kcpbkbb       31'201'500
431)          knnbkbb       23'202'570
432)          knnbkab       34'867'250
433)          kcpbkab       46'887'500
434)          kcpbkaa       11'935'000
435)          knnbkaa        8'875'300
436)         knnbkabb      102'699'900
437)         kcpbkabb      138'105'000
438)         knnbkaab       60'859'200
439)         kcpbkaab       81'840'000
440)        knnbkaabb      178'773'900
441)        kcpbkaabb      240'405'000
442)            knnak          736'200
443)            kcpak          990'000
444)           knnakb        5'071'600
445)           kcpakb        6'820'000
446)           knnaka        3'272'000
447)           kcpaka        4'400'000
448)          knnakbb       14'969'400
449)          kcpakbb       20'130'000
450)          kcpakab       30'250'000
451)          knnakab       22'495'000
452)          knnakaa        5'726'000
453)          kcpakaa        7'700'000
454)         kcpakabb       89'100'000
455)         knnakabb       66'258'000
456)         kcpakaab       52'800'000
457)         knnakaab       39'264'000
458)        knnakaabb      115'338'000
459)        kcpakaabb      155'100'000
460)           knnbbk        3'368'115
461)           kcpbbk        4'529'250
462)          kcpbbkb       31'201'500
463)          knnbbkb       23'202'570
464)          knnbbka       14'969'400
465)          kcpbbka       20'130'000
466)         knnbbkbb       68'485'005
467)         kcpbbkbb       92'094'750
468)         knnbbkab      102'914'625
469)         kcpbbkab      138'393'750
470)         kcpbbkaa       35'227'500
471)         knnbbkaa       26'196'450
472)        kcpbbkabb      407'632'500
473)        knnbbkabb      303'130'350
474)        kcpbbkaab      241'560'000
475)        knnbbkaab      179'632'800
476)       kcpbbkaabb      709'582'500
477)       knnbbkaabb      527'671'350
478)           knnabk        5'061'375
479)           kcpabk        6'806'250
480)          knnabkb       34'867'250
481)          kcpabkb       46'887'500
482)          knnabka       22'495'000
483)          kcpabka       30'250'000
484)         knnabkbb      102'914'625
485)         kcpabkbb      138'393'750
486)         kcpabkab      207'968'750
487)         knnabkab      154'653'125
488)         kcpabkaa       52'937'500
489)         knnabkaa       39'366'250
490)        knnabkabb      455'523'750
491)        kcpabkabb      612'562'500
492)        knnabkaab      269'940'000
493)        kcpabkaab      363'000'000
494)       kcpabkaabb    1'066'312'500
495)       knnabkaabb      792'948'750
496)           knnaak        1'288'350
497)           kcpaak        1'732'500
498)          kcpaakb       11'935'000
499)          knnaakb        8'875'300
500)          kcpaaka        7'700'000
501)          knnaaka        5'726'000
502)         knnaakbb       26'196'450
503)         kcpaakbb       35'227'500
504)         knnaakab       39'366'250
505)         kcpaakab       52'937'500
506)         knnaakaa       10'020'500
507)         kcpaakaa       13'475'000
508)        kcpaakabb      155'925'000
509)        knnaakabb      115'951'500
510)        knnaakaab       68'712'000
511)        kcpaakaab       92'400'000
512)       kcpaakaabb      271'425'000
513)       knnaakaabb      201'841'500
514)          kcpabbk       20'047'500
515)          knnabbk       14'908'050
516)         knnabbkb      102'699'900
517)         kcpabbkb      138'105'000
518)         kcpabbka       89'100'000
519)         knnabbka       66'258'000
520)        knnabbkbb      303'130'350
521)        kcpabbkbb      407'632'500
522)        kcpabbkab      612'562'500
523)        knnabbkab      455'523'750
524)        knnabbkaa      115'951'500
525)        kcpabbkaa      155'925'000
526)       knnabbkabb    1'341'724'500
527)       kcpabbkabb    1'804'275'000
528)       knnabbkaab      795'096'000
529)       kcpabbkaab    1'069'200'000
530)      knnabbkaabb    2'335'594'500
531)      kcpabbkaabb    3'140'775'000
532)          knnaabk        8'834'400
533)          kcpaabk       11'880'000
534)         kcpaabkb       81'840'000
535)         knnaabkb       60'859'200
536)         knnaabka       39'264'000
537)         kcpaabka       52'800'000
538)        kcpaabkbb      241'560'000
539)        knnaabkbb      179'632'800
540)        knnaabkab      269'940'000
541)        kcpaabkab      363'000'000
542)        kcpaabkaa       92'400'000
543)        knnaabkaa       68'712'000
544)       kcpaabkabb    1'069'200'000
545)       knnaabkabb      795'096'000
546)       knnaabkaab      471'168'000
547)       kcpaabkaab      633'600'000
548)      knnaabkaabb    1'384'056'000
549)      kcpaabkaabb    1'861'200'000
550)         kcpaabbk       34'897'500
551)         knnaabbk       25'951'050
552)        knnaabbkb      178'773'900
553)        kcpaabbkb      240'405'000
554)        knnaabbka      115'338'000
555)        kcpaabbka      155'100'000
556)       kcpaabbkbb      709'582'500
557)       knnaabbkbb      527'671'350
558)       knnaabbkab      792'948'750
559)       kcpaabbkab    1'066'312'500
560)       kcpaabbkaa      271'425'000
561)       knnaabbkaa      201'841'500
562)      knnaabbkabb    2'335'594'500
563)      kcpaabbkabb    3'140'775'000
564)      kcpaabbkaab    1'861'200'000
565)      knnaabbkaab    1'384'056'000
566)     knnaabbkaabb    4'065'664'500
567)     kcpaabbkaabb    5'467'275'000
568)             kcnk          364'500
569)            kcnkb        2'511'000
570)            kcnka        1'620'000
571)           kcnkbb        7'411'500
572)           kcnkab       11'137'500
573)           kcnkaa        2'835'000
574)          kcnkabb       32'805'000
575)          kcnkaab       19'440'000
576)         kcnkaabb       57'105'000
577)            kcnbk        2'511'000
578)           kcnbkb       17'298'000
579)           kcnbka       11'160'000
580)          kcnbkbb       51'057'000
581)          kcnbkab       76'725'000
582)          kcnbkaa       19'530'000
583)         kcnbkabb      225'990'000
584)         kcnbkaab      133'920'000
585)        kcnbkaabb      393'390'000
586)            kcnak        1'620'000
587)           kcnakb       11'160'000
588)           kcnaka        7'200'000
589)          kcnakbb       32'940'000
590)          kcnakab       49'500'000
591)          kcnakaa       12'600'000
592)         kcnakabb      145'800'000
593)         kcnakaab       86'400'000
594)        kcnakaabb      253'800'000
595)           kcnbbk        7'411'500
596)          kcnbbkb       51'057'000
597)          kcnbbka       32'940'000
598)         kcnbbkbb      150'700'500
599)         kcnbbkab      226'462'500
600)         kcnbbkaa       57'645'000
601)        kcnbbkabb      667'035'000
602)        kcnbbkaab      395'280'000
603)       kcnbbkaabb    1'161'135'000
604)           kcnabk       11'137'500
605)          kcnabkb       76'725'000
606)          kcnabka       49'500'000
607)         kcnabkbb      226'462'500
608)         kcnabkab      340'312'500
609)         kcnabkaa       86'625'000
610)        kcnabkabb    1'002'375'000
611)        kcnabkaab      594'000'000
612)       kcnabkaabb    1'744'875'000
613)           kcnaak        2'835'000
614)          kcnaakb       19'530'000
615)          kcnaaka       12'600'000
616)         kcnaakbb       57'645'000
617)         kcnaakab       86'625'000
618)         kcnaakaa       22'050'000
619)        kcnaakabb      255'150'000
620)        kcnaakaab      151'200'000
621)       kcnaakaabb      444'150'000
622)          kcnabbk       32'805'000
623)         kcnabbkb      225'990'000
624)         kcnabbka      145'800'000
625)        kcnabbkbb      667'035'000
626)        kcnabbkab    1'002'375'000
627)        kcnabbkaa      255'150'000
628)       kcnabbkabb    2'952'450'000
629)       kcnabbkaab    1'749'600'000
630)      kcnabbkaabb    5'139'450'000
631)          kcnaabk       19'440'000
632)         kcnaabkb      133'920'000
633)         kcnaabka       86'400'000
634)        kcnaabkbb      395'280'000
635)        kcnaabkab      594'000'000
636)        kcnaabkaa      151'200'000
637)       kcnaabkabb    1'749'600'000
638)       kcnaabkaab    1'036'800'000
639)      kcnaabkaabb    3'045'600'000
640)         kcnaabbk       57'105'000
641)        kcnaabbkb      393'390'000
642)        kcnaabbka      253'800'000
643)       kcnaabbkbb    1'161'135'000
644)       kcnaabbkab    1'744'875'000
645)       kcnaabbkaa      444'150'000
646)      kcnaabbkabb    5'139'450'000
647)      kcnaabbkaab    3'045'600'000
648)     kcnaabbkaabb    8'946'450'000
649)             kcck          165'645
650)            kcckb        1'141'110
651)            kccka          736'200
652)           kcckbb        3'368'115
653)           kcckab        5'061'375
654)           kcckaa        1'288'350
655)          kcckabb       14'908'050
656)          kcckaab        8'834'400
657)         kcckaabb       25'951'050
658)            kccbk        1'141'110
659)           kccbkb        7'860'980
660)           kccbka        5'071'600
661)          kccbkbb       23'202'570
662)          kccbkab       34'867'250
663)          kccbkaa        8'875'300
664)         kccbkabb      102'699'900
665)         kccbkaab       60'859'200
666)        kccbkaabb      178'773'900
667)            kccak          736'200
668)           kccakb        5'071'600
669)           kccaka        3'272'000
670)          kccakbb       14'969'400
671)          kccakab       22'495'000
672)          kccakaa        5'726'000
673)         kccakabb       66'258'000
674)         kccakaab       39'264'000
675)        kccakaabb      115'338'000
676)           kccbbk        3'368'115
677)          kccbbkb       23'202'570
678)          kccbbka       14'969'400
679)         kccbbkbb       68'485'005
680)         kccbbkab      102'914'625
681)         kccbbkaa       26'196'450
682)        kccbbkabb      303'130'350
683)        kccbbkaab      179'632'800
684)       kccbbkaabb      527'671'350
685)           kccabk        5'061'375
686)          kccabkb       34'867'250
687)          kccabka       22'495'000
688)         kccabkbb      102'914'625
689)         kccabkab      154'653'125
690)         kccabkaa       39'366'250
691)        kccabkabb      455'523'750
692)        kccabkaab      269'940'000
693)       kccabkaabb      792'948'750
694)           kccaak        1'288'350
695)          kccaakb        8'875'300
696)          kccaaka        5'726'000
697)         kccaakbb       26'196'450
698)         kccaakab       39'366'250
699)         kccaakaa       10'020'500
700)        kccaakabb      115'951'500
701)        kccaakaab       68'712'000
702)       kccaakaabb      201'841'500
703)          kccabbk       14'908'050
704)         kccabbkb      102'699'900
705)         kccabbka       66'258'000
706)        kccabbkbb      303'130'350
707)        kccabbkab      455'523'750
708)        kccabbkaa      115'951'500
709)       kccabbkabb    1'341'724'500
710)       kccabbkaab      795'096'000
711)      kccabbkaabb    2'335'594'500
712)          kccaabk        8'834'400
713)         kccaabkb       60'859'200
714)         kccaabka       39'264'000
715)        kccaabkbb      179'632'800
716)        kccaabkab      269'940'000
717)        kccaabkaa       68'712'000
718)       kccaabkabb      795'096'000
719)       kccaabkaab      471'168'000
720)      kccaabkaabb    1'384'056'000
721)         kccaabbk       25'951'050
722)        kccaabbkb      178'773'900
723)        kccaabbka      115'338'000
724)       kccaabbkbb      527'671'350
725)       kccaabbkab      792'948'750
726)       kccaabbkaa      201'841'500
727)      kccaabbkabb    2'335'594'500
728)      kccaabbkaab    1'384'056'000
729)     kccaabbkaabb    4'065'664'500

Total files: 729, total size: 167'077'730'106
More details at https://banksiagui.com/forums/viewtopic.php?p=642#p642
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
User avatar
phhnguyen
Posts: 1454
Joined: Wed Apr 21, 2010 4:58 am
Location: Australia
Full name: Nguyen Hong Pham

Re: Felicity EGTB Attempt 11: calculate 5-men Index space for chess

Post by phhnguyen »

Attempt 11: calculate 5-men Index space for chess

Below is the table of all endgames of 5 men for chess. They are a total of 149 endgames and their index space is near 21 G. Suppose we store information of one index within 1 byte and we need to store information of both sides, total size = 21 G x 2 sides x 1 byte = 42 GB. Suppose we compress them with a ratio of 4 times (0.25), the size will be 42 x 0.25 = 10.5 GB (over 10 GB).

Compared with current existing EGTBs, our one (uncompressed 42 GB) is better than Edward's (uncompressed, 56 GB estimated), but it is worse, compared with Gaviota (6.5 GB vs 10.5 GB). Especially, it is not on the same level to be compared with Syzygy 5 men (0.9 GB vs 10.5 GB)!

However, our size is just an estimate, we hope the real compress ratio is a bit better or be improved. We may reduce the size but omit some unnecessary endgames (such as kqqqk, krrrk…).

The largest endgames are just 355 M (kqbkp). They will take about 710 MB to allocate in memory (for 2 sides, using only 1 byte to store information for each index). That size is fine to store in the memory of modern computers. The total size of 10 GB is fine too for downloading and storing.

Code: Select all

All interesting 5 men endgames (order - name - index size)
  1)              knk           36'096
  2)             knkn        2'310'144
  3)              kbk           36'096
  4)             kbkn        2'310'144
  5)             kbkb        2'310'144
  6)              krk           36'096
  7)             krkn        2'310'144
  8)             krkb        2'310'144
  9)             krkr        2'310'144
 10)            krknn       72'769'536
 11)              kqk           36'096
 12)             kqkn        2'310'144
 13)             kqkb        2'310'144
 14)             kqkr        2'310'144
 15)            kqknn       72'769'536
 16)            kqkbn      147'849'216
 17)            kqkbb       72'769'536
 18)            kqkrn      147'849'216
 19)            kqkrb      147'849'216
 20)            kqkrr       72'769'536
 21)             kqkq        2'310'144
 22)             knnk        1'137'024
 23)            knnkn       72'769'536
 24)            knnkb       72'769'536
 25)            knnkr       72'769'536
 26)             kbnk        2'310'144
 27)            kbnkn      147'849'216
 28)            kbnkb      147'849'216
 29)            kbnkr      147'849'216
 30)             kbbk        1'137'024
 31)             krnk        2'310'144
 32)            kbbkn       72'769'536
 33)            krnkn      147'849'216
 34)            krnkb      147'849'216
 35)            kbbkb       72'769'536
 36)            kbbkr       72'769'536
 37)            krnkr      147'849'216
 38)             krbk        2'310'144
 39)            krbkn      147'849'216
 40)            krbkb      147'849'216
 41)            krbkr      147'849'216
 42)             krrk        1'137'024
 43)            krrkn       72'769'536
 44)            krrkb       72'769'536
 45)            krrkr       72'769'536
 46)             kqnk        2'310'144
 47)            kqnkn      147'849'216
 48)            kqnkb      147'849'216
 49)            kqnkr      147'849'216
 50)            kqnkq      147'849'216
 51)             kqbk        2'310'144
 52)            kqbkn      147'849'216
 53)            kqbkb      147'849'216
 54)            kqbkr      147'849'216
 55)            kqbkq      147'849'216
 56)             kqrk        2'310'144
 57)            kqrkn      147'849'216
 58)            kqrkb      147'849'216
 59)            kqrkr      147'849'216
 60)            kqrkq      147'849'216
 61)             kqqk        1'137'024
 62)            kqqkn       72'769'536
 63)            kqqkb       72'769'536
 64)            kqqkr       72'769'536
 65)            kqqkq       72'769'536
 66)            knnnk       23'498'496
 67)            kbnnk       72'769'536
 68)            kbbnk       72'769'536
 69)            krnnk       72'769'536
 70)            kbbbk       23'498'496
 71)            krbnk      147'849'216
 72)            krrnk       72'769'536
 73)            krbbk       72'769'536
 74)            krrbk       72'769'536
 75)            krrrk       23'498'496
 76)            kqnnk       72'769'536
 77)            kqbnk      147'849'216
 78)            kqrnk      147'849'216
 79)            kqbbk       72'769'536
 80)            kqrbk      147'849'216
 81)            kqrrk       72'769'536
 82)            kqqnk       72'769'536
 83)            kqqbk       72'769'536
 84)            kqqrk       72'769'536
 85)            kqqqk       23'498'496
 86)              kpk           86'688
 87)             knkp        5'548'032
 88)             kbkp        5'548'032
 89)            kbknp      355'074'048
 90)             krkp        5'548'032
 91)            krknp      355'074'048
 92)            krkbp      355'074'048
 93)             kqkp        5'548'032
 94)            kqknp      355'074'048
 95)            kqkbp      355'074'048
 96)            kqkrp      355'074'048
 97)             knpk        5'548'032
 98)            knpkn      355'074'048
 99)            knpkb      355'074'048
100)             kbpk        5'548'032
101)            knnkp      174'763'008
102)            kbpkn      355'074'048
103)            kbpkb      355'074'048
104)            kbpkr      355'074'048
105)             krpk        5'548'032
106)            kbnkp      355'074'048
107)            krpkn      355'074'048
108)            krpkb      355'074'048
109)            krpkr      355'074'048
110)            krnkp      355'074'048
111)            kbbkp      174'763'008
112)            krbkp      355'074'048
113)            krrkp      174'763'008
114)             kqpk        5'548'032
115)            kqpkn      355'074'048
116)            kqpkb      355'074'048
117)            kqpkr      355'074'048
118)            kqpkq      355'074'048
119)            kqnkp      355'074'048
120)            kqbkp      355'074'048
121)            kqrkp      355'074'048
122)            kqqkp      174'763'008
123)            knnpk      174'763'008
124)            kbnpk      355'074'048
125)            kbbpk      174'763'008
126)            krnpk      355'074'048
127)            krbpk      355'074'048
128)            krrpk      174'763'008
129)            kqnpk      355'074'048
130)            kqbpk      355'074'048
131)            kqrpk      355'074'048
132)            kqqpk      174'763'008
133)             kpkp        4'161'024
134)            knkpp      130'378'752
135)            kbkpp      130'378'752
136)            krkpp      130'378'752
137)            kqkpp      130'378'752
138)             kppk        2'037'168
139)            kppkn      130'378'752
140)            knpkp      266'305'536
141)            kbpkp      266'305'536
142)            krpkp      266'305'536
143)            kqpkp      266'305'536
144)            knppk      130'378'752
145)            kbppk      130'378'752
146)            krppk      130'378'752
147)            kqppk      130'378'752
148)            kppkp       97'784'064
149)            kpppk       31'236'576

Total files: 149, total size: 20'854'389'552
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
User avatar
hgm
Posts: 27896
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Felicity EGTB generators and probers

Post by hgm »

An impoartnt question that must be asked: what the goal of this endeavor? Is it just academic curiosity, to know exactly how many positions have a certain distance to mate, or are the EGT supposed to be used for some task, and if so, what task? That matters a lot for how one should design them.

For instance, if they are intended for detecting certain wins in an engine search it would be sufficient to just store WDL information. If you don't require the engine to indicate exact DTM, but are happy with a 'mate-in-unknown' score. If you want the engine to play a winning move instantly, it also depends on whether you require it to take the move to the fastest mate, or just one that will certainly lead it to a win. In Chess a popular EGT flavor is DTZ. Playing by it guaratees any position that can be won will be won. But not in the fastest way; it tries to make a winning capture or pawn push as quickly as possible, without caring whether that will bring the checkmate closer or not. And it cannot give you the DTM. In Xiangqi the DTM can be a murky concept anyway: should it count pointless checks by the losing player, and try to minimize those?

With the DTZ for Chess in mind, it seems perfectly acceptable to formulate sub-goals that bring you closer to mate, and then take the fastest route to the next sub-goal, rather than the fastest way to reach checkmate. In Xiangqi it could be a sub-goal to 'liberate' your King and attackers: move defenders that would block them to locations where they cannot do that anymore.

The point is that many 1-0 and 2-0 end-games are certain wins, where timing is of no importance. Xiangqi does not have a 50-move rule. So you can afford to first move any obstructing defenders out of the way, and only then start playing for the mate. The advantage is that you can then use the EGT for that where white has no defenders, and only the King file is of importance. The EGT required for the checkmating phase is then some 1200 times smaller than an EGT that also includes all possible constellations. The idea is that it would be much faster to both probe an EGT of size N and one of size M, then do a single probe to an EGT of size N*M.

In somewhat more detail: you would first probe an EGT which tells you how many moves you are removed from fully liberating your King, and bringing your attackers across the River, and play by that. (Let's caal that DTA = Distance To Attack.)If this is already realized (the probe returns 0), you would look whether the attacking pieces are already on the enemy half or not. If they are, you can start playing from the checkmating EGT, ignoring the redundant defenders. So you will only ever use EGT where either the winning or the losing player is the only one that has defending pieces, never both.

Now the question is what to do when timing is important, such as in the infamous KRKAAEE. Liberating your King without further thought then could bungle a win, giving the weak player the opportunity to reorganize is defense. This could be solved by having a separate table, which contains the 'Distance To Draw', i.e. the number of moves you can afford to pass your turn before the position turns into a drawn one. When this DTD is larger than the number of moves you need to remove the obstructing defenders, there is no problem, and you can do that first.

When the DTD <= DTA, your only hope would be that there is method for forcing an increase of the DTD with a King that is still blocked. In KRxKAAEE this is often possible. You could have an EGT for that, which tells you how many moves you are removed from a position with the maximum DTD that you could force without King help (DTP = Distance To Progress.). If that reaches 0, you have done all that you could, and if at that point still DTD <= DTA the game cannot be won. But if DTD > DTA you can play a move according to the DTA table. The losing player could renew the threat to escape by his move, (i.e. lower the DTD). In that case you would fall back on the DTP table to crank up the DTD again, etc.

So apart from a DTM table this would require also DTA, DTD and DTP tables. But each of these tables will be far smaller (like 1200 or 3600 times) than a table that allows both players to have a full set of defenders, while effectively achieving the same thing (= forcing a win through probing EFT only, never searching deeper than 1 ply).
User avatar
hgm
Posts: 27896
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Felicity EGTB generators and probers

Post by hgm »

Code: Select all

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

typedef long int int_ptr;

#define BWIDTH 9
#define BSIZE  BWIDTH*5
#define STRIDEE 1
#define STRIDEP (STRIDEE*29)
#define STRIDER (STRIDEP*119)
#define STRIDEK (STRIDER*BSIZE)
#define b (board + 2*BSIZE + BWIDTH)
#define SEC (1./CLOCKS_PER_SEC)

#define ASSERT(X, MSG) { if(!(X)) printf("Assert %s\n", MSG), exit(0); }

#define HORSE

/*
 *  Some macros to define often-used control constructs
 */

// loop through all moves of given piece. capts indicates which captures will be accepted

#define FOR_ALL_MOVES(movelist, from, index, capts) \
  { int r, f;                                       \
    for(r=movelist; f=flags[r]; r++) {              \
      int v=steps[r], to=from, nwind=index;         \
      while(b[to+=v] <= capts) {                    \
        nwind += isteps[r];                         \

#define NEXT_MOVE               \
        if(b[to] || f&4) break; \
      }                         \
    }                           \
  }

// scan through tablebase and update 0x88 board in lockstep

#define SCAN(p, index, start, stride)                              \
  for(nr[p]=0, index=start; nr[p]<BSIZE; nr[p]++, index+=stride) { \
    pos[p] = Ox88[nr[p]];                                          \
    if(b[pos[p]]) continue; /* skip broken positions */            \
    b[pos[p]] = p+1;

#define NEXT(p)    \
    b[pos[p]] = 0; \
  }

/*
 *  Global variables: board & piece-list, move-gen and auxiliary tables
 */

unsigned int Ox88[BSIZE];              // raster-scan square nr to 0x88 square nr translation table
unsigned int sqrNr[2*BSIZE];           // 0x88 to square number
unsigned char board[6*BSIZE + BWIDTH]; // raw 0x88 board with generous guard band
int pos[11]; // piece locations on 0x88 board;
int nr[11];  // piece locations as raster-scan number;
int first[11], firstCapts[11]; // indicate first entry in move table for each piece.
int N, wcnt, todo;
unsigned char *EGT, *map;
signed int steps[128], blocks[128], flags[128];
int isteps[128], cnt[256], ptr;

// char array[1500*1000*1000];

/*
 * XQ section: encoding and decoding tables for treating Palace and Elephant constellations as pseudo-pieces
 */

#define K  7
#define A1 8
#define A2 9
#define E1 7
#define E2 8
#define EBLOCK (7+2)
#define UNCAPT 5
#define EYE    4*BWIDTH+4 /* Elephants and Kings can collide on this square   */
#define ABSENT 5*BWIDTH+2 /* lies off board, beyond reach of any board square */

//                                  ENCODING / DECODING SCHEME
//                  (board)
//                   kCodes                                           pDelta
//                  aeCodes               eEncode                     eDelta
//                   ----->               pEncode                      ---->    move & drop index steps
//   square numbers          square codes  ---->  constellation number
//             ^     <-----                              |             ---->    blocking-square numbers
//             |    aSquares                             |            palace    move & drop target-const. numbers
//             |    eSquares                   elephants |           elephants
//             |    kSquares                    palace   |
//             `-----------------------------------------'   

// square code to square number for King, Advisors and Elephants
unsigned char kSquares[9] = { 3, 4, 5, 2*BWIDTH+3, 2*BWIDTH+4, 2*BWIDTH+5, 4*BWIDTH+3, EYE, 4*BWIDTH+5 };
unsigned char aSquares[6] = { ABSENT, 3, 5, 2*BWIDTH+4, 4*BWIDTH+3, 4*BWIDTH+5 };
unsigned char eSquares[8] = { ABSENT, 2, 6, 4*BWIDTH, 4*BWIDTH+8, 8*BWIDTH+2, 8*BWIDTH+6, EYE }; // EYE is last
// constellation number to piece locations / move-target const. number / drop-target const. number
unsigned char palace[120][7+3+5];
unsigned char elephants[30][7+2+6+7];
// square-code combination to constellation number
unsigned char pEncode[324]; // 6 x 6 x 9, indexed by A1 + 6*A2 + 36*K
unsigned char eEncode[64];  // 8 x 8,     indexed by E1 + 8*E2
// square number to (offsetted) square code (Elephant squares have 8 added)
unsigned char aeCodes[2*BSIZE], kCodes[2*BSIZE];

void ProbeInit()
{
  int p1, p2, k, i, j, n;

  // tabulate Elephant constellations, and create reverse lookup table to get constellation number
  for(p1=0, i=1; p1<8; p1++) for(p2=p1; p2<8; p2++) {
    if(p1 && p1 == p2) continue;     // only (0,0) can have p1 == p2 (both ABSENT)
    ASSERT(i < 30, "e-overflow")
    elephants[i][E1] = eSquares[p2]; // p2>p1, so only E1 can be on EYE
    elephants[i][E2] = eSquares[p1]; // and E1 is only ABSENT if E2 is ABSENT as well
    eEncode[p2 + 8*p1] = i;
    eEncode[p1 + 8*p2] = i;
    i++;
  }
  ASSERT(i == 30, "e-states")
  // tabulate Palace constellations, and create reverse lookup table to get constellation number
  for(p1=0, i=1; p1<6; p1++) for(p2=p1; p2<6; p2++) {
    if(p1 && p1 == p2) continue;
    for(k=0; k<9; k++) {
      int kk = kSquares[k];
      if(kk == aSquares[p1] || kk == aSquares[p2]) continue;
      ASSERT(i < 120, "p-overflow")
      palace[i][A1] = aSquares[p2]; // p2 > p1, so if one ABSENT it must be A2
      palace[i][A2] = aSquares[p1];
      palace[i][K]  = kk;
      pEncode[p2 + 6*p1 + 36*k] = i;
      pEncode[p1 + 6*p2 + 36*k] = i;
      i++;
    }
  }
  ASSERT(i == 120, "p-states")
  // create lookup table for square number to square code
  for(i=1; i<=5; i++) aeCodes[aSquares[i]] = i;
  for(i=1; i<=7; i++) aeCodes[eSquares[i]] = i+8; // Elephant square codes offsetted by 8
  for(i=0; i<=8; i++)  kCodes[kSquares[i]] = i;
  for(i=0; i<BSIZE; i++) sqrNr[Ox88[i]] = i;
}

void SetupPalace(unsigned char *p)
{
  b[p[K]] = 1; b[p[A1]] = 2; b[p[A2]] = 2;
}

void ClearPalace(unsigned char *p)
{
  b[p[K]] = b[p[A1]] = b[p[A2]] = 0;
}

void SetupElephants(unsigned char *p)
{
  b[p[E1]] = 3; b[p[E2]] = 3;
}

void ClearElephants(unsigned char *p)
{
  b[p[E1]] = b[p[E2]] = 0;
}

// index steps due to making move (first 6) or dropping piece (remaining)
int pDelta[119][6+5];
int eDelta[29][6+7];

void InitXQ()
{
  int p1, p2, k, i, j, n;

if(EGT[465832])printf("set to %d at init\n",EGT[465832]),exit(0);
  ProbeInit(); // Initialize tables also used in probing
if(EGT[465832])printf("set to %d after probe init\n",EGT[465832]),exit(0);

  // finish Elphants table
  // elephants[i]: m1 m2 m3 m4 m5 m6 0 E1 E2 b1 b2 b3 b4 b5 b6 u1 u2 u3 u4 u5 u6 u7
  // m = move target as constellation number in arbitrary order, or 0 sentinel
  // b = blocking square for these moves, as square number
  // u = uncapture targets as constellation number, indexed by square code
  for(i=1; i<30; i++) { // all elephant states
    k = 0;
    for(j=1; j<8; j++) {   // all possible codes for Elephant to-squares
      int e = eSquares[j]; // square number of to-square candidate
      int v = elephants[i][E1] - e;         // vector to it from Elephant 1
      // uncaptures (u1-u7)
      if(v && elephants[i][E2] == ABSENT) { // Elephant 2 is lacking, and Elephant 1 does not occupy square e
        elephants[i][14+j] = n = eEncode[j+8*(aeCodes[v+e] & ~8)]; // add code after Elephant uncapture there
        eDelta[i][UNCAPT+j] = (n-i)*STRIDEE;                         // index step for uncaptures
      }
      // moves of Elephant 1
      if(e != elephants[i][E2] &&           // not blocked by Elephant 2
        (v == 4*BWIDTH+2 || v == 4*BWIDTH-2 || v == -4*BWIDTH+2 || v == -4*BWIDTH-2)) { // and one jump away from Elephant 1
        ASSERT(k < 6, "e-moves")
        elephants[i][9+k] = e + v/2;  // blocking square
        elephants[i][k] = n = eEncode[j+8*(aeCodes[elephants[i][E2]] & ~8)]; // add the move
        eDelta[i][k++] = (n-i)*STRIDEE;
      }
      // moves of Elephant 2
      v = elephants[i][E2] - e;
      if(e != elephants[i][E1] && (v == 4*BWIDTH+2 || v == 4*BWIDTH-2 || v == -4*BWIDTH+2 || v == -4*BWIDTH-2)) {
        ASSERT(k < 6, "e-moves")
        elephants[i][9+k] = e + v/2;  // blocking square
        elephants[i][k] = n = eEncode[j+8*(aeCodes[elephants[i][E1]] & ~8)]; // add the move
        eDelta[i][k++] = (n-i)*STRIDEE;
      }
    }
//printf("%3d. ",i);for(j=0;j<22;j++)printf(" %3d",elephants[i][j]);printf("\n");
  }
  // finish Palace table
  // palace[i]: m1 m2 m3 m4 m5 m6 0 K A1 A2 u1 u2 u3 u4 u5
  // m = move target as constellation number in arbitrary order, or 0 sentinel
  // u = uncapture targets as constellation number, indexed by square code
  for(i=1; i<120; i++) {
    k = 0;
    // Advisor moves
    for(j=1; j<6; j++) {
      int a = aSquares[j];
      int v = palace[i][A1] - a;
      // uncaptures (u1-u5)
      if(v && palace[i][A2] == ABSENT && a != palace[i][K]) {
        palace[i][9+j] = n = pEncode[j+6*aeCodes[v+a]+36*kCodes[palace[i][K]]];
        pDelta[i][UNCAPT+j] = (n-i)*STRIDEP;
      }
      // moves of Adviser 1
      if(a != palace[i][A2] && a != palace[i][K] && (v == 2*BWIDTH+1 || v == 2*BWIDTH-1 || v == -2*BWIDTH+1 || v == -2*BWIDTH-1)) {
        ASSERT(k < 6, "a1-moves")
        palace[i][k] = n = pEncode[j+6*aeCodes[palace[i][A2]]+36*kCodes[palace[i][K]]];
        pDelta[i][k++] = (n-i)*STRIDEP;
      }
      // moves of Adviser 2
      v = palace[i][A2] - aSquares[j];
      if(a != palace[i][A1] && a != palace[i][K] && (v == 2*BWIDTH+1 || v == 2*BWIDTH-1 || v == -2*BWIDTH+1 || v == -2*BWIDTH-1)) {
        ASSERT(k < 6, "a2-moves")
        palace[i][k] = n = pEncode[j+6*aeCodes[palace[i][A1]]+36*kCodes[palace[i][K]]];
        pDelta[i][k++] = (n-i)*STRIDEP;
      }
    }
    // King moves
    for(j=0; j<9; j++) {
      int to = kSquares[j];
      int v = palace[i][K] - to;
      if(to != palace[i][A1] && to != palace[i][A2] && (v == 1 || v == -1 || v == 2*BWIDTH || v == -2*BWIDTH)) {
        ASSERT(k < 6, "k-moves")
        palace[i][k] = n = pEncode[aeCodes[palace[i][A1]]+6*aeCodes[palace[i][A2]]+36*j];
        pDelta[i][k++] = (n-i)*STRIDEP;
      }
    }
//printf("%3d. ",i);for(j=0;j<15;j++)printf(" %3d",palace[i][j]);printf("\n");
  }
//getchar();
}

void PBoard()
{
  int r, f;
  int save[2*BSIZE];
  for(r=0; r<2*BSIZE; r++) save[r] = b[r], b[r] = 0;
  SetupPalace(palace[nr[3]]);
  SetupElephants(elephants[nr[2]]);
  b[Ox88[nr[1]]] = 4;
  b[nr[0]+3+8*BWIDTH] = 5;
  for(r=0; r<5; r++) {
    for(f=0; f<BWIDTH; f++) printf(" %c", ".kaeRK"[b[2*BWIDTH*r+f]]);
    printf("\n");
  }
  printf("P=%d E=%d\n",nr[3],nr[2]);
  b[nr[0]+3+8*BWIDTH] = 0;
  b[Ox88[nr[1]]] = 0;
  ClearElephants(elephants[nr[2]]);
  ClearPalace(palace[nr[3]]);
  for(r=0; r<2*BSIZE; r++) b[r] = save[r];
}

// sample piece descriptions: (mode, delta_x, delta_y) triples, where mode 4=leaper, 2=non-capt, 1=capt
int king[]   = {7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,1,0, 7,-1,0, 7,0,1, 7,0,-1, 0};
int knight[] = {7,2,1, 7,2,-1, 7,-2,-1, 7,-2,1, 7,1,2, 7,-1,2, 7,1,-2, 7,-1,-2, 0};
int zebra[]  = {7,2,3, 7,2,-3, 7,-2,-3, 7,-2,3, 7,3,2, 7,-3,2, 7,3,-2, 7,-3,-2, 0};
int camel[]  = {7,3,1, 7,3,-1, 7,-3,-1, 7,-3,1, 7,1,3, 7,-1,3, 7,1,-3, 7,-1,-3, 0};
int bishop[] = {3,1,1, 3,1,-1, 3,-1,-1, 3,-1,1, 0};
int wazir[]  = {7,1,0, 7,-1,0, 7,0,1, 7,0,-1, 0};
int ferz[]   = {7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 0};
int yawn[]   = {7,1,1, 7,1,-1, 7,-1,0, 0};
int silver[] = {7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,0,1, 0};
int copper[] = {7,1,1, 7,-1,1, 7,0,1, 7,0,-1, 0};
int omni[]   = {5,1,1, 5,1,-1, 5,-1,-1, 5,-1,1, 6,1,0, 6,-1,0, 6,0,1, 6,0,-1, 0};
int lang[]   = {7,2,2, 7,2,-2, 7,-2,2, 7,-2,-2, 7,3,3, 7,3,-3, 7,-3,3, 7,-3,-3, 0};
int phoenix[]= {7,1,0, 7,-1,0, 7,0,1, 7,0,-1, 7,2,2, 7,2,-2, 7,-2,2, 7,-2,-2, 0};
int alibaba[]= {7,2,0, 7,-2,0, 7,0,2, 7,0,-2, 7,2,2, 7,2,-2, 7,-2,2, 7,-2,-2, 0};
int unicorn[]= {7,1,0, 7,-1,0, 7,0,1, 7,0,-1, 7,2,1, 7,2,-1, 7,-2,-1, 7,-2,1, 7,1,2, 7,-1,2, 7,1,-2, 7,-1,-2, 0};
int elephant[] = {7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,2,2, 7,2,-2, 7,-2,2, 7,-2,-2, 0};
int fibnif[]   = {7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,1,2, 7,-1,2, 7,1,-2, 7,-1,-2, 0};
int admiral[]= {3,1,1, 3,1,-1, 3,-1,-1, 3,-1,1, 3,2,0, 3,0,2, 3,0,-2, 3,-2,0, 6,1,0, 6,-1,0, 6,0,1, 6,0,-1, 0};
int flamingo[]={7,6,1, 7,6,-1, 7,-6,-1, 7,-6,1, 7,1,6, 7,-1,6, 7,1,-6, 7,-1,-6, 0};
int giraffe[]= {7,4,1, 7,4,-1, 7,-4,-1, 7,-4,1, 7,1,4, 7,-1,4, 7,1,-4, 7,-1,-4, 0};
int hrNF[]   = {7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,2,1, 7,-2,-1, 7,-1,2, 7,1,-2, 0};
int hlNF[]   = {7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,2,-1, 7,-2,1, 7,-1,-2, 7,1,2, 0};
int hrNW[]   = {7,1,0, 7,0,-1, 7,-1,0, 7,0,1, 7,2,1, 7,-2,-1, 7,-1,2, 7,1,-2, 0};
int hlNW[]   = {7,1,0, 7,0,-1, 7,-1,0, 7,0,1, 7,2,-1, 7,-2,1, 7,-1,-2, 7,1,2, 0};
int rook[]   = {3,1,0, 3,-1,0, 3,0,1, 3,0,-1, 0};
int horse[] = {15,1,0,2,1, 15,1,0,2,-1, 15,-2,-1,0,-1, 15,-1,0,-2,1, 15,0,1,1,2, 15,0,1,-1,2, 15,0,-1,1,-2, 15,0,-1,-1,-2, 0};

/*
 *  Initialization stuff
 */

// routines to prepare move-gen tables from the piece descriptors.
// each piece has two tables; one used for retrograde moving (so contains only non-captures),
// one for forward moving. Both the 0x88 board step and EGT index step are tabulated in each.
// To allow for asymmetric pieces, the retro table flips the sign, so it can be used with the same generator.
// The forward table is used for black king escapes, and for determining black-king locations that are
// attacked by the white pieces (by generating captures of the latter on empty squares with black-king stride).

int Fill(int sgn, int mode, int *desc, int stride)
{
  int i, res = ptr;
  for(i=0; desc[i]; i+=3) {
    if(!(desc[i] & mode)) continue; // skip directions we cannot capture in;
    flags[ptr] = desc[i];
    if(desc[i] & 8) blocks[ptr] = 2*BWIDTH*desc[i+1] + desc[i+2], i+=2; // forward w.r.t. from-square
    steps[ptr] = sgn*(2*BWIDTH*desc[i+1] + desc[i+2]);
    isteps[ptr++] = sgn*(BWIDTH*desc[i+1] + desc[i+2])*stride;
  }
  flags[ptr++] = 0;
  return res;
}

int AddPiece(int nr, signed int *desc, int stride)
{
  first[nr]      = Fill(-1, 2, desc, stride); // unmoves, so flip sign, and non-capts only
  firstCapts[nr] = Fill( 1, 1, desc, 1);      // captures only
}

static Init(int *desc1, int *desc2, int *desc3, int *desc4, void *mem)
{
  int i, j;

  // create empty 0x88 board with large guard band
  for(i=0; i<6*BSIZE+BWIDTH; i++) board[i] = 5; // guards
  for(i=0; i<BSIZE; i++) b[Ox88[i] = (i/BWIDTH)*BWIDTH + i] = 0;
  for(i=0; i<256; i++) cnt[i] = 0; // reset stats

  // load move-generator tables
  AddPiece(1, desc2, STRIDER); // only ergodic pieces

  // allocate and cache-align main storage
  EGT = (unsigned char*) mem;
  if(!EGT)
    EGT = (unsigned char*) malloc(3*STRIDEK);
  printf("allocate %d bytes at %lx\n", j, (int_ptr) EGT);
}

/*
 *  routines for retrograde generation through 3-ply tree (2 unmoves followed by 1 move)
 *  Scan:
 *      find DTM=N positions.
 *      does not bother to set up board; broken positions will never have DTM=N
 *  RetroWhite:
 *      makes white unmoves from current DTM=N position
 *      ray scan of sliders aborts on hitting board edge or broken (DTM=2) position
 *      only non-won positions reached this way are treated further (marked as won, and RetroBlack)
 *      no board update, just calculate target index
 *  RetroBlack:
 *      makes black unmoves from newly-won positions, all non-sliding (Palace and Elephants)
 *      don't worry about unleaps to broken positions; they will be taken care of in the next step
 *  Escape:
 *      tries black move and captures, to find one to a non-won position which escapes the loss
 *      if none found, labels the position DTM=N+1
 *      broken positions (DTM=2) and King-stares (DTM=1) are considered escaped to begin with
 *      
 */

int pflag;

static int Escape(int p, int e, int index)
{
  int i, dtm = EGT[index] >> 1;
  if(dtm == 1 || dtm == 2) return 1; // King-stare or broken never become lost
  // King and Adviser moves
  for(i=0; palace[p][i]; i++) {
    if(!(EGT[index + pDelta[p][i]] & 1)) return 1;
}
  // Elephant moves
  for(i=0; elephants[e][i]; i++) {
    if(!b[elephants[e][i+9]] && !(EGT[index + eDelta[e][i]] & 1)) return 1;
}
  return 0;
}

static void RetroBlack(int p, int e, int index)
{
  int i;
  // King and Adviser moves
  b[palace[p][K]] = 0; // temporarily remove King, as Palace transitions could move it away
  for(i=0; palace[p][i]; i++) {
    int nwind = index + pDelta[p][i];
    int k = palace[palace[p][i]][K]; // new King loc
    int save = b[k]; // could be Rook
    b[k] = 1; // place King so it properly blocks Elephants
    if(!Escape(palace[p][i], e, nwind)) {
      EGT[nwind] |= N+2;
      cnt[N+2]++; todo++;
    }
    b[k] = save;
  }
  b[palace[p][K]] = 1;
  // Elephant moves
  for(i=0; elephants[e][i]; i++) {
    int nwind = index + eDelta[e][i];
    if(!b[elephants[e][i+9]] && !Escape(p, elephants[e][i], nwind)) {
      EGT[nwind] |= N+2;
      cnt[N+2]++; todo ++;
    }
  }
}

static void RetroWhite(int p, int index, int pNr)
{
  int r, f, sqrType = aeCodes[pNr];
  FOR_ALL_MOVES(first[p], pos[p], index, 0)
    if(f&8 && b[to+blocks[r]]) break; // lame step is blocked: break from ray scan
    if((EGT[nwind] & ~1) == 4) break;  // unmove to broken position is invalid and terminates ray scan
    if(!(EGT[nwind] & 1)) {    // parent was not yet marked as won (excludes King-stares)
      EGT[nwind] |= 1;         // mark it
      b[to] = 4;               // put Rook on board (so Elephants are properly blocked)
      RetroBlack(nr[3], nr[2], nwind); // check if this closes last escape of parents (making them lost)
      b[to] = 0;
      cnt[N+1]++;
    }
    // also try uncaptures if the square we unmove from is suitable for that
    if(sqrType & 8) {
      if(elephants[nr[2]][E2] == ABSENT) {
        int xind = nwind + eDelta[nr[2]][UNCAPT + sqrType - 8];
        if(!(EGT[xind] & 1) && EGT[xind] != 4) {    // parent was not yet marked as won
          EGT[xind] |= 1;         // mark it
          b[to] = 4;              // put Rook on board (so Elephants are properly blocked)
          RetroBlack(nr[3], elephants[nr[2]][14+sqrType-8], xind); cnt[N+1]++;
          b[to] = 0;
          cnt[N+1]++;
        }
      }
    } else if(sqrType) {
      if(palace[nr[3]][A2] == ABSENT) {
        int xind = nwind + pDelta[nr[3]][UNCAPT + sqrType];
        if(!(EGT[xind] & 1) && EGT[xind] != 4) {    // parent was not yet marked as won
          EGT[xind] |= 1;         // mark it
          b[to] = 4;              // put Rook on board (so Elephants are properly blocked)
          RetroBlack(palace[nr[3]][9+sqrType], nr[2], xind), cnt[N+1]++;
          b[to] = 0;
          cnt[N+1]++;
        }
      }
    }
  NEXT_MOVE
}

static void FindMates()
{
  int i1, i2, i3, k, p, x;
  char cpb[2*BSIZE]; // board copy
  for(nr[0]=0, i1=0; nr[0]<3; nr[0]++, i1+=STRIDEK) { // scan over white King files (by definition cannot colide with anything)
    for(nr[3]=1, i2=i1; nr[3]<120; nr[3]++, i2+=STRIDEP) {  // collisionless scan over unique Palace constellations
      int king = palace[nr[3]][K];
      SetupPalace(palace[nr[3]]);
      for(nr[2]=1, i3=i2; nr[2]<30; nr[2]++, i3+=STRIDEE) { // collisionless scan over unique Elephant constellations
        if(b[EYE] && elephants[nr[2]][E1] == EYE) {                        // King collides with Elephant (112 of 3451 cases)
          for(nr[1]=0, k=i3; nr[1]<BSIZE; nr[1]++, k+=STRIDER) EGT[k] = 5; // mark these broken positions as won with DTM=2
          continue;                                                        // so they cannot be used as escapes or be unmoved to
        }
        SetupElephants(elephants[nr[2]]);
        // at this point the board goes through all black constellations combined with all white King files
        // i3 is the corresponding contribution to the index

        // handle collisions between Rook and black pieces
        for(k=E1; k<=E2; k++) if(elephants[nr[2]][k] != ABSENT) EGT[i3+sqrNr[elephants[nr[2]][k]]*STRIDER] = 4; // non-won with DTM = 2
        for(k=K;  k<=A2; k++) if(   palace[nr[3]][k] != ABSENT) EGT[i3 +  sqrNr[palace[nr[3]][k]]*STRIDER] = 4; // (escape by Rook capture, but no unmoves to them)
        // find checks with major piece
#ifdef HORSE
        FOR_ALL_MOVES(first[1], king, i3+sqrNr[king]*STRIDER, 0)
          if(f & 8 && b[to+blocks[r]]) break; // unmove is blocked (breaks from ray-scan)
          EGT[nwind] = 1;       // checks are won with white to move, undecided with black to move
        NEXT_MOVE
#else
        x = king; k=i3+sqrNr[x]*STRIDER; while(!b[++x]) EGT[k+=STRIDER] = 1; // won, with DTM=0
        x = king; k=i3+sqrNr[x]*STRIDER; while(!b[--x]) EGT[k-=STRIDER] = 1; // (no escape, undecided)
        x = king; k=i3+sqrNr[x]*STRIDER; while(!b[x+=2*BWIDTH]) EGT[k+=BWIDTH*STRIDER] = 1;
        x = king; k=i3+sqrNr[x]*STRIDER; while(!b[x-=2*BWIDTH]) EGT[k-=BWIDTH*STRIDER] = 1;
#endif
        // find King-stares
        x = 10*BWIDTH + 3 + nr[0]; while(!b[x-=2*BWIDTH]) cpb[x] = EGT[i3+sqrNr[x]*STRIDER]; // remember board state on King file
        if(x == king) { // Kings eye to eye without Rook
          for(x=0, k=i3; x<BSIZE; x++, k+=STRIDER) EGT[k] = 3; // won with DTM=1 (no escape, but not lost) for every Rook placement (even captured)
          x = king; k = i3+sqrNr[x]*STRIDER; while(!b[x+=2*BWIDTH]) EGT[k+=BWIDTH*STRIDER] = cpb[x]; // repair unjustly overwritten Rook checks
        }
        ClearElephants(elephants[nr[2]]);
      }
      ClearPalace(palace[nr[3]]);
    }
printf("pass 1\n");
    for(nr[1]=0, i2=i1; nr[1]<BSIZE; nr[1]++, i2+=STRIDER) {
      pos[1] = Ox88[nr[1]];
      b[pos[1]] = 4;
      for(nr[3]=1, i3=i2; nr[3]<120; nr[3]++, i3+=STRIDEP) { // collisionless scan over unique Palace constellations
        SetupPalace(palace[nr[3]]);
        for(nr[2]=1, k=i3; nr[2]<30; nr[2]++, k+=STRIDEE) {  // collisionless scan over unique Elephant constellations
          // label checkmates in the chunk where we just marked all captures
          if(!(EGT[k] & ~1) && !Escape(nr[3], nr[2], k) ) EGT[k] |= 6, cnt[2]++, todo++; //, PBoard(), getchar();
        }
        ClearPalace(palace[nr[3]]);
      }
      b[pos[1]] = 0;
    }
  }
}

void *Build(desc1, desc2, desc3, desc4, verbose, mem)
int *desc1, *desc2, *desc3, *desc4; // piece descriptions
int verbose; // flag to enable printing
void *mem;   // memory area to build EGT in (if NULL the memory is allocated)
// returns start of end-game table (which can be different from mem, because of alignment to cache-line boundaries)
{
  int i1, i2, i3, k, p;
  clock_t t;

  Init(desc1, desc2, desc3, desc4, mem); // initialize auxiliary tables
  if(!EGT) return (void*) EGT;           // allocation failed, abort
printf("init done\n");
  InitXQ();

  N=6;         // double of iteration count
  todo = 0; t = clock();
  FindMates(); // detrmine checkmates, first half (piece-0 moves) of iteration 1

  if(verbose) printf("        mated    mate\nKing captures %d\nmates %7d         (%5.2f sec)\n",
                       cnt[1], cnt[2], (clock()-t)*SEC);
  while(todo) { // plain iteration; cache unfriendly!

    // treat unmoves of white pieces 1 and 2 (plus black unmoves & verification), two iterations
    for(nr[0]=0, i1=0; nr[0]<3; nr[0]++, i1+=STRIDEK) { // scan over white King files
      for(nr[1]=0, i2=i1; nr[1]<BSIZE; nr[1]++, i2+=STRIDER) { // scan over white Rook
        pos[1] = Ox88[nr[1]];
        for(nr[3]=1, i3=i2; nr[3]<120; nr[3]++, i3+=STRIDEP) { // scan over Palace constellations
          SetupPalace(palace[nr[3]]);
          for(nr[2]=1; nr[2]<30; nr[2]++) {             // scan over Elephant constellations
            int nwind = i3+nr[2]-1;
            if((EGT[nwind] & ~1) == N) { /* broken won't ever match! */
              todo--;
              for(p=1; p<2; p++) RetroWhite(p, nwind, pos[1]); // Rook moves
              // do white King file transitions directly from here
              b[pos[1]] = 4;
              if(!(EGT[nwind] & 1)) EGT[nwind] |= 1, RetroBlack(nr[3], nr[2], nwind), cnt[N+1]++; // white King can stay in same file (equivalent to null move)
              if(nr[0] > 0 && !(EGT[nwind-STRIDEK] & 1)) EGT[nwind-STRIDEK] |= 1, RetroBlack(nr[3], nr[2], nwind-STRIDEK), cnt[N+1]++;
              if(nr[0] < 2 && !(EGT[nwind+STRIDEK] & 1)) EGT[nwind+STRIDEK] |= 1, RetroBlack(nr[3], nr[2], nwind+STRIDEK), cnt[N+1]++;
              b[pos[1]] = 0;
            }
          }
          ClearPalace(palace[nr[3]]);
        }
      }
    }

    if(verbose) printf("in-%-2d %7d %7d (%5.2f sec)\n", N/2-2, cnt[N+2], cnt[N+1], (clock()-t)*SEC);
#if DEBUG
for(p=i1=k=0; k<3*STRIDEK; k++)if((EGT[k]&~1)>N+2)printf("Error: EGT[%d]=%d\n", k, EGT[k]),exit(0);
for(k=0; k<3*STRIDEK; k++) {
  p = EGT[k] & ~1;
  nr[0] = k/STRIDEK; nr[1] = (k%STRIDEK)/STRIDER; nr[3] = (k%STRIDER)/STRIDEP + 1; nr[2] = k%STRIDEP+1;
  SetupPalace(palace[nr[3]]); b[Ox88[nr[1]]] = 4;
  i1 = Escape((k%STRIDER)/STRIDEP + 1, k%STRIDEP + 1, k);
  if((p >= 6) == i1) {
    pflag=1; Escape(nr[3], nr[2], k);
    PBoard();
    printf("Wrong value %d at %d\n", p, k);
    exit(0);
  }
  ClearPalace(palace[nr[3]]); b[Ox88[nr[1]]] = 0;
}
#endif
    N += 2;
    if(N>253) break;
  }
  return (void*) EGT;
}

PrintStats()
{
  int i, wtot=0, btot=0, w1, w2; double wsum=0, bsum=0;
  double tot;
  tot = 100./(BSIZE*119*29*3);
  for(i=0; i<254; i+=2) wtot+=cnt[i+1], btot+=cnt[i+2], wsum+=i*cnt[i+1], bsum+=i*cnt[i+2];
  printf("won:  %9d (%5.1f%%)\nlost: %9d (%5.1f%%)\navg:  %9.1f moves\n",
          wtot, wtot*tot, btot, btot*tot, bsum*0.5/btot);

  wtot = btot = w1 = w2 = 0;
  for(i=0; i<N; i+=2) {
    int k, all=0, part=0;
    for(k=0; k<3*STRIDEK; k++) if((EGT[k] & ~1) == i) {
      int ele=k%29, pal=(k%(29*119))/29;
      if(ele > 7 && pal > 48) all++, w1 += EGT[k]&1; else part++, w2 += EGT[k]&1;
    }
    printf("%3d. %6d %6d\n", i, all, part);
    if(i >= 6) wtot += all, btot += part;
  }
  printf("total%6d %6d %6d %6d\n", wtot, btot, w1, w2);

  while(1, 0) {
    i = (2*i) % (3*STRIDEK);
    if(EGT[i]&1) continue;
    nr[0] = i/STRIDEK; nr[1] = (i%STRIDEK)/STRIDER;
    nr[3] = (i%STRIDER)/STRIDEP + 1; nr[2] = i%STRIDEP + 1;
    printf("%d %d %d %d\n", nr[0], nr[1], nr[2], nr[3]);
    PBoard();
    getchar();
  }
}

main()
{
  FILE *f;
  Build(bishop, rook, king, king, 1, NULL); // NBKK
  PrintStats();
  if((f = fopen("KHKd.dat", "wb"))) {
    int i;
    for(i=0; i<3*STRIDEK; i++) fputc(EGT[i]>>1, f);
    fclose(f);
  }
}
User avatar
hgm
Posts: 27896
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Felicity EGTB generators and probers

Post by hgm »

I found the code shown in the previous posting in a file named 4menXQ.c, last modified in 2016. This is all so long ago that I forgot most details of what I was doing. What I do remember was that I took one of the simplistic EGT-generator codes I had for Chess (which does not exploit any form of symmetry, as I used it for chess variants with asymmetric pieces, and had the advantage that it could do boards of arbitrary size), and adapted it to Xiangqi. I never bothered to remove some of the code that was only useful for chess variants.

The generator uses the 'grandfather' algorithm for retrograde propagation from lost-in-N to lost-in-(N+1) posiitons (2 unmoves, one white, one black followed by ferification through normal black moves). With this algorithm it is not needed to store the DTM for won positions, you only need to know whether they are won or not. So the EGT uses one byte per board position, the lowest bit indicating whether it is won with white to move, and the other 7 bits the DTM for black to move (or 0 when it is not a lost position yet).

To adapt it for Xiangqi I treated the entire Palace as a single 'pseudo-piece'. Each Palace constellation had a number (0-118), which could be directly used as contribution to the EGT index. There was a table that for each constellation contained a list of the constellations that could be rached from it through a move. (In general piece moves were generated by getting their move steps from a zero-terminated list, so this was just a small modification from the chess version.) A Palace never has more than 6 moves.

There was a decoding table, which, indexed by the Palace number would provide King and Advisor square numbers. And an encoding table, which for give K and A square numbers would provide the Palace number.

The pair of Elephants is treated in a similar way as a single pseudo-piece. Only the losing player has a Palace and Elephants; for the winning player the King is not represented by a Palace (119 states), but by its file (3 states). The attacking piece was always across the River.
User avatar
hgm
Posts: 27896
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Felicity EGTB generators and probers

Post by hgm »

I found an executable that prints the following table:

Code: Select all

           -       E      EE       A      AE     AEE      AA     AAE    AAEE
  0.    3084  117077  390115   44446 1021918 3045819  107432 1885754 5381442
  2.   15882  105880  301758   62015  411080 1164165   92602  609054 1709682
  4.    2871   37476  163701   20768  227004  920874   51564  512292 1979640
  6.    1270     574    1584     526    2068    5696    1168    5176   13624
  8.    2570     832    1600     884    1124    3076     694    2206    5818
 10.    6480    2354    4142    2702    1648    4256     696    2644    6816
 12.    7264    3649    5600    4893    2224    4778     948    2978    7564
 14.    7906    6250    8296    7250    3370    5668    1770    2936    7472
 16.    4535   10316   11360   10104    4388    6070    3374    2570    6128
 18.    2512   15622   15770   15350    5984    5842    5662    1944    3884
 20.    1040   19808   23422   19642    7564    6722   10134    1560    2688
 22.     354   20650   34984   20442    9184    6728   15095    1382    1392
 24.     116   18406   44894   17426    9362    7994   21706    1694     702
 26.       6   14372   47652   12130    7382    6702   26718    2174     236
 28.       0    9256   43596    6412    6876    6520   27576    2262     524
 30.       0    5460   33528    2558    5972    5728   23125    1270     586
 32.       0    2288   21804     732    5566    5054   16152     768     194
 34.       0     796   12512     120    3460    3024    8950     616      12
 36.       0     164    5596       0    1862    1062    4682     592      26
 38.       0       0    1776       0     520     446    3207     588      50
 40.       0       0       0       0     218     148    2837     644      48
 42.       0       0       0       0      26      28    2804     626      60
 44.       0       0       0       0       0       0    2506     548      56
 46.       0       0       0       0       0       0    1768     352      42
 48.       0       0       0       0       0       0     902     186      12
 50.       0       0       0       0       0       0     384      66       2
 52.       0       0       0       0       0       0     152      14       0
 54.       0       0       0       0       0       0      50       4       0
 56.       0       0       0       0       0       0      34       0       0
 58.       0       0       0       0       0       0       6       0       0
 60.       0       0       0       0       0       0       2       0       0
lost   34053  130797  318116  121171   78798   85542  183102   35800   57936
won    52569  291590  794033  208476  839134 2104190  324652 1124528 3005914
all    54675  382725 1148175  243000 1701000 5103000  425250 2976750 8930250

Draws by Pawn rank:
9       1044   33499  108281   10316  158954  476365   23920  282842  819996
8          0   10750   47324    4550  124016  436144   16676  271930  831751
7          0    5940   39500    2976  110548  384870    9456  248756  762258
6          0    7489   25001       0  142160  516664    2360  320208 1035600
5          0    7809   25394       0  155464  536425    2708  325438 1027597
It is apparently rigged to calculate the KHPKd end-game (where d = any number of defenders). The total size of the EGT it calculates is 3*119*29*45*46 ~ 21MB. This because it confines the attackers to be on the enemy half; it does not use symmetry. The 46th square is probably for when the such a piece is captured; it does calculate the sub-end-games KPKd and KHKd as well.

The 'all' row indicates the total number of positions split out per defender composition, to serve as comparison for the number of won (white to move) and lost (black to move) positions. E.g. for the bare King it is 3*9*45*45, and thus doesn't take account of 'broken positions' where pieces coincide. (Such positions are of course never counted as won or lost.)

Even accounting for the broken positions almost all cases have a lot of draws. This is due to the Pawn becoming almost useless when it reaches last ('9th') rank. I therefore split out the number of draws (with white to move) by Pawn rank.
User avatar
phhnguyen
Posts: 1454
Joined: Wed Apr 21, 2010 4:58 am
Location: Australia
Full name: Nguyen Hong Pham

Re: Felicity EGTB generators and probers

Post by phhnguyen »

Thank Muller for your information!
hgm wrote: Tue May 07, 2024 8:11 pm An impoartnt question that must be asked: what the goal of this endeavor?

All are just for fun! Thus I don’t have a clear goal. Just go and see how far we can go.

As I have written in the first post, this project has been focusing on creating EGTBs for Xiangqi/Jeiqi, answering some curious questions such as how hard to build, what the limitations are, how many Elo they can gain for those chess variants... I guessed EGTBs are useful for Xiangqi but I may be wrong and they all could be useless. We also support chess, not for re-inventing the wheel but for measuring, comparing, verifying and getting ideas. We may add more chess variants later.

The project is an open source. I’m open-minded. Nothing is fixed, no method, scope or tech details are deadly selected. I have just planned to rewrite some of my old code to create a workable generator, generate some data, and measure some parameters as the baseline. Then starting to look around for ideas. We all could work together to try interesting ideas, including your ones.
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
User avatar
hgm
Posts: 27896
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Felicity EGTB generators and probers

Post by hgm »

Sure, it will always be fun, no matter what the design goal is. But without a clear design goal it is hard to come up with a good design.

I am foremost interested in finding algorithms to 'factorize' EGTs into an attacking and defensive part. It seems to me that at least in the case of a slow-moving piece like a Horse this should be possible. E.g. for the end-game Rook + Horse + defenders vs. Horse + defenders a full EGT would have 119*29*119*29*90*90*90 = 8086G positions (for each side to move, but symmetry would again approximately cut that in two). What I would like is to use two partial EGT's that only consider the pieces on one half, plus the distant effect of the Kings on each other. So (liberated) King + Rook + Horse vs King + Horse + defenders (3*119*29*45*45*45 = 900M positions) and King + defenders vs King + Horse (119*29*45 = 152K positions).

The idea is that the Horse on the weak side does not really present any danger (as Horses can at best stalemate a bare King), and its checks can simply be evaded by moving the King back and forth on the same file, until the ban on perpetuals forbids further checking. As long as there is no check the strong player would play by the 'across-the-River' EGT, which presumably would need the defending Horse to be in that area to not result in a quick mate. It could then assume full freedom of the attacking King, or liberating it as a primary goal, as the defending Horse would not restict it.

I guess this is still a bit too simple, because for end-games that are winnable with (liberated)K+R+H vs H+defenders on enemy soil, there is no guarantee that R+H could beat K+defenders without King help, when the H is used to block the King's distant attack. So the winning strategies might have to involve the Rook moving back to its own side of the River in order to chase away or capture an obstructing Horse. But this can be handled by extending the defending Horse's area in the attacking EGT with the 6 squares between Palace and River (from 45 to 51 squares), and the Rook's area with the 9 squares on the same rank as the defending Horse (from 45 to 54). That increases the size of the attacking EGT to 1.22G, which is a significant saving compared to 8086G.
User avatar
phhnguyen
Posts: 1454
Joined: Wed Apr 21, 2010 4:58 am
Location: Australia
Full name: Nguyen Hong Pham

Re: Felicity EGTB generators and probers

Post by phhnguyen »

My program prints out the index size for rn vs n with full defenders (run the program as: fegtb -n rn-n -subinfo)

Code: Select all

...
450) krnaabbknaabb  805'180'500'000
Its index space is about 800 G, or 10 times as small as yours. I think it has one of the most compact index space systems.

However, the size is still so huge even though we have a good compressor too. My friend had used some expensive computers and my code to generate some endgames 2 vs 1, but I did not dare to download them since my old computer has only 1 TB hard disk and I didn’t want to spend months downloading them. I don’t want to receive them via posting hard disks either because that way is too expensive and slow, non-practical for wide publishing and the set is not full enough for me.

I won’t try soon endgames with 3 attackers (ones with Pawns are exceptions since their sizes are much smaller) unless we have some ideas that are proven to work well to reduce significantly their sizes.
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager