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.
Felicity EGTB generators and probers
Moderators: hgm, Rebel, chrisw
-
phhnguyen
- Posts: 1447
- Joined: Wed Apr 21, 2010 4:58 am
- Location: Australia
- Full name: Nguyen Hong Pham
Re: Felicity EGTB generators and probers
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
The most features chess GUI, based on opensource Banksia - the chess tournament manager
-
phhnguyen
- Posts: 1447
- Joined: Wed Apr 21, 2010 4:58 am
- Location: Australia
- Full name: Nguyen Hong Pham
Re: Felicity EGTB - Attempt 10: index space for Xiangqi
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.
More details at https://banksiagui.com/forums/viewtopic.php?p=642#p642
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
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
The most features chess GUI, based on opensource Banksia - the chess tournament manager
-
phhnguyen
- Posts: 1447
- 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
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.
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
The most features chess GUI, based on opensource Banksia - the chess tournament manager
-
hgm
- Posts: 27859
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Felicity EGTB generators and probers
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).
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).
-
hgm
- Posts: 27859
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Felicity EGTB generators and probers
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);
}
}
-
hgm
- Posts: 27859
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Felicity EGTB generators and probers
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.
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.
-
hgm
- Posts: 27859
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Felicity EGTB generators and probers
I found an executable that prints the following table:
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.
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
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.
-
phhnguyen
- Posts: 1447
- Joined: Wed Apr 21, 2010 4:58 am
- Location: Australia
- Full name: Nguyen Hong Pham
Re: Felicity EGTB generators and probers
Thank Muller for your information!
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.
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
The most features chess GUI, based on opensource Banksia - the chess tournament manager
-
hgm
- Posts: 27859
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Felicity EGTB generators and probers
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.
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.
-
phhnguyen
- Posts: 1447
- Joined: Wed Apr 21, 2010 4:58 am
- Location: Australia
- Full name: Nguyen Hong Pham
Re: Felicity EGTB generators and probers
My program prints out the index size for rn vs n with full defenders (run the program as: fegtb -n rn-n -subinfo)
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.
Code: Select all
...
450) krnaabbknaabb 805'180'500'000
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
The most features chess GUI, based on opensource Banksia - the chess tournament manager