Perft speed
=====
The speed when generating EGTB depends much on the speed of some so basic functions:
- Move generator
- Check InCheck
- Make move, takeback
Perft is a perfect one to check the correctness and speed of those functions. In this task, we attempt to make those functions be fast enough.
Board representation
--------------------
The board of Felicity EGTB uses the mailbox technique. We start by taking the board from our OCGDB code project (another of our open-source projects), add Perft code. To know how fast our perft is, we compare it with Stockfish 16.1. Stockfish is compiled for standard x86-64 (make -j profile-build ARCH=x86-64) without using any special struct such as BMI, or AVX). All run on my old computer iMac 3.6 GHz Quad-Core Intel Core i7 (7-year-old)
Stockish run for pertf 5 with starting position and took 24 ms
Bellow attempts are elapsed time for perft 5 too. All node counts are correct.
Attempt 1
--------
Origin board took from OCGDB project: 734 ms
The board of Felicity EGTB is 734/24 = 31 times as slow as Stockfish.
All code is updated on the GitHub.
Attempt 2
--------
We removed all "redundant" functions/features such as move comments, hash key, mutex locks... It took 579 ms = 579/24 = 21 times slower than Stockfish
Attempt 3
--------
We used the piece list technique to speed up. It took 374 ms = 374/24 = 16 times slower than Stockfish
It is amazing Stockfish is so fast even though it is much more complicated than our current code. The speed of our code is so disappointing.
All code is updated on GitHub.
Progress reports
Attempt 4
Attempt 4
We run perft with Xiangqi (Chinese chess) board with the same techniques (mailbox representation + piece list). We used Pikafish (a Xiangqi chess engine developed from Stockfish) to compare. Pikafish was compiled for standard x86-64. All perft depths are 5 and for the start position.
Pikafish took 1498 ms. Our code took 6260 ms = 6260/1498 = 4 times slower than Pikafish.
The gap between the two programs for Xiangqi is much smaller than the ones for Chess but it is still so large.
We run perft with Xiangqi (Chinese chess) board with the same techniques (mailbox representation + piece list). We used Pikafish (a Xiangqi chess engine developed from Stockfish) to compare. Pikafish was compiled for standard x86-64. All perft depths are 5 and for the start position.
Pikafish took 1498 ms. Our code took 6260 ms = 6260/1498 = 4 times slower than Pikafish.
The gap between the two programs for Xiangqi is much smaller than the ones for Chess but it is still so large.
Re: Progress reports
Attempt 5
---------
We tried to reduce the number of calling the function incheck for the Xiangqi board. Typically that function is called whenever making a move to check if that move is valid or invalid. The new code calls that function considering if it may affect the status of being incheck: the positions of the move are the same rank or column with the king or on checkable, blockable positions of the horse. It used some simple tables to check the status.
The number of calling the incheck function is reduced significantly to about half.
The new code took 6536 ms, a bit larger than Attempt 5. It is a surprising and upsetting result.
All code has been pushed into a new branch "incheck".
---------
We tried to reduce the number of calling the function incheck for the Xiangqi board. Typically that function is called whenever making a move to check if that move is valid or invalid. The new code calls that function considering if it may affect the status of being incheck: the positions of the move are the same rank or column with the king or on checkable, blockable positions of the horse. It used some simple tables to check the status.
The number of calling the incheck function is reduced significantly to about half.
The new code took 6536 ms, a bit larger than Attempt 5. It is a surprising and upsetting result.
All code has been pushed into a new branch "incheck".
Re: Progress reports
Attempt 6
---------
Just clean the code, rewrite some parts, and cut some redundant variants and functions.
- Chess perft 5 took 324 ms
- Xiangqi perft 5 took 5453 ms
The code looks better and becomes a bit faster
Attempt 7
---------
Our code for basic functions such as board representations, move generators, move makes, take back, check in-check… is simple and straightforward. Logically, it should be fast, their speed should be comparable with the fastest chess engines such as Stockfish, not the big gaps as in previous attempts. Thus we doubt the way to calculate perfts. Stockfish and Pikafish use a method named "Bulk-counting", to ignore making/taking back leaf nodes, and save a lot of time. In contrast, our code uses a different method and has to make/take back all nodes, including leaf nodes, which cannot save as much time as Stockfish. Since we need to compare the speed of basic functions it’s better to use the same method for perfts.
We have modified code of Stockfish/Pikafish to calculate perfts similar to our code and got new statistics:
- Stockfish perft 5 took 187 ms
- Pikafish perft 5 took 8023 ms
Stockfish is still faster than our program (187 ms vs 324 ms = 1.7 times faster) but the gap is now acceptable. We guess Stockfish becomes faster due to having a lot of pre-calculation data and the chess board of 64 squares is optimized for model computers of 64 bits.
On the other hand, our program is surprisingly faster than Pikafish on the Xiangqi variant (5453 ms vs 8023 ms = 1.5 times faster). We guess the huge board of 90 squares is not fit for integers of 64 bits, making it not optimised for running on model computers. For those kinds of huge boards, mailbox board representation has some advantages.
We list some advantages of mailbox board representation:
- simple: all code is short, clear, easy to understand and maintenance
- easy to support different chess variants, from small to huge boards
- fast (for basic functions such as in/out, move generators, make, takeback, incheck...) enough for chess, be faster than ones with bitboards for huge board
It is good that our work targets mainly Xiangqi but not chess. Thus we are satisfied with the results, finish that task, and move on to others.
All code on GitHub is updated!
---------
Just clean the code, rewrite some parts, and cut some redundant variants and functions.
- Chess perft 5 took 324 ms
- Xiangqi perft 5 took 5453 ms
The code looks better and becomes a bit faster
Attempt 7
---------
Our code for basic functions such as board representations, move generators, move makes, take back, check in-check… is simple and straightforward. Logically, it should be fast, their speed should be comparable with the fastest chess engines such as Stockfish, not the big gaps as in previous attempts. Thus we doubt the way to calculate perfts. Stockfish and Pikafish use a method named "Bulk-counting", to ignore making/taking back leaf nodes, and save a lot of time. In contrast, our code uses a different method and has to make/take back all nodes, including leaf nodes, which cannot save as much time as Stockfish. Since we need to compare the speed of basic functions it’s better to use the same method for perfts.
We have modified code of Stockfish/Pikafish to calculate perfts similar to our code and got new statistics:
- Stockfish perft 5 took 187 ms
- Pikafish perft 5 took 8023 ms
Stockfish is still faster than our program (187 ms vs 324 ms = 1.7 times faster) but the gap is now acceptable. We guess Stockfish becomes faster due to having a lot of pre-calculation data and the chess board of 64 squares is optimized for model computers of 64 bits.
On the other hand, our program is surprisingly faster than Pikafish on the Xiangqi variant (5453 ms vs 8023 ms = 1.5 times faster). We guess the huge board of 90 squares is not fit for integers of 64 bits, making it not optimised for running on model computers. For those kinds of huge boards, mailbox board representation has some advantages.
We list some advantages of mailbox board representation:
- simple: all code is short, clear, easy to understand and maintenance
- easy to support different chess variants, from small to huge boards
- fast (for basic functions such as in/out, move generators, make, takeback, incheck...) enough for chess, be faster than ones with bitboards for huge board
It is good that our work targets mainly Xiangqi but not chess. Thus we are satisfied with the results, finish that task, and move on to others.
All code on GitHub is updated!
Re: Progress reports
Attempt 8:
We compare the access speeds of some arrays in memory:
- created some huge arrays in memory (about 7 GB) using 3 ways: malloc, std::vector and std::array
- create random values and set them to random locations in those arrays
- measure time
Conclusion: their speeds are quite similar. We can use any of them.
The code for this attempt has been pushed already in the branch "array"
We compare the access speeds of some arrays in memory:
- created some huge arrays in memory (about 7 GB) using 3 ways: malloc, std::vector and std::array
- create random values and set them to random locations in those arrays
- measure time
Conclusion: their speeds are quite similar. We can use any of them.
The code for this attempt has been pushed already in the branch "array"
Re: Progress reports
Attempt 9:
Position indexes work for both Chess and Xiangqi/Jeiqi
Position indexes work for both Chess and Xiangqi/Jeiqi
Re: Progress reports
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.
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
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 rank to be compared with Syzygy 5 men (0.9 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 rank to be compared with Syzygy 5 men (0.9 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
Attempt 12: generate all 5-men endgames for chess
Attempt 12: generate all 5-men endgames for chess
We generated all endgames 5-men (3 attackers + 2 Kings) for chess. The estimated size was about 10 GB, very small relatively compared with Xiangqi 2 attackers thus it is a much easier and quicker task. By doing that we could fix, and verify the new generator, trying some ideas. Furthermore, we could measure some stats as a baseline and compare our work with some existing EGTBs.
In this attempt, the generator uses the forwarding method for the move generator. The compress library is LZMA from the 7zip library, compressed by blocks of 4 KB. It ran an old computer AMD Ryzen 7 1700 8-Core 16 threads, 16 GB RAM, ran with 12 threads and took about 85% of the computer's power.
The generator took about 3 days and 15 hours to generate. If we add the time for verification, compressing and saving down it took almost 4 days to generate all 5-men endgames.
The size of all endgames is 8.8 GB, better than the estimation of 10 GB. However, it is noticeably larger than the Gaviota one (about 7.03 GB or 25% larger) and the Nalimov one (about 7.1 GB or 24% larger).
The bad thing is that our EGTB is larger/worse in size than all popular ones.
The good thing is that our code works fully!
We generated all endgames 5-men (3 attackers + 2 Kings) for chess. The estimated size was about 10 GB, very small relatively compared with Xiangqi 2 attackers thus it is a much easier and quicker task. By doing that we could fix, and verify the new generator, trying some ideas. Furthermore, we could measure some stats as a baseline and compare our work with some existing EGTBs.
In this attempt, the generator uses the forwarding method for the move generator. The compress library is LZMA from the 7zip library, compressed by blocks of 4 KB. It ran an old computer AMD Ryzen 7 1700 8-Core 16 threads, 16 GB RAM, ran with 12 threads and took about 85% of the computer's power.
The generator took about 3 days and 15 hours to generate. If we add the time for verification, compressing and saving down it took almost 4 days to generate all 5-men endgames.
The size of all endgames is 8.8 GB, better than the estimation of 10 GB. However, it is noticeably larger than the Gaviota one (about 7.03 GB or 25% larger) and the Nalimov one (about 7.1 GB or 24% larger).
The bad thing is that our EGTB is larger/worse in size than all popular ones.
The good thing is that our code works fully!
Attempt 13: generate all 5-men endgames for chess using the backward method
Attempt 13: generate all 5-men endgames for chess using the backward method
We use a retro move generator to detect and work with only necessary positions, avoiding checking and updating all as the forwarding method. That caused a significant speed improvement.
The total generating time for 5-man chess is almost 21 hours (not including time for verifying, compressing and saving into hard drivers). Compared to 3 days and 15 hours (87) of using the forwarding method in the previous attempt, that is 4 times as fast.
We use a retro move generator to detect and work with only necessary positions, avoiding checking and updating all as the forwarding method. That caused a significant speed improvement.
The total generating time for 5-man chess is almost 21 hours (not including time for verifying, compressing and saving into hard drivers). Compared to 3 days and 15 hours (87) of using the forwarding method in the previous attempt, that is 4 times as fast.
Attempt 14: Improve the speed of generating all 5-men endgames for chess with the backward method
Attempt 14: Improve the speed of generating all 5-men endgames for chess with the backward method
We made some improvements to speed up the generator with the backward method.
The generating time for 5-men chess is nearly 17 hours or 5 times as fast as the forwarding method.
We made some improvements to speed up the generator with the backward method.
The generating time for 5-men chess is nearly 17 hours or 5 times as fast as the forwarding method.
Attempt 15: calculate index spaces for more men for chess
Attempt 15: calculate index spaces for more men for chess
From a question (@Dann Corbit) about the limit of the generator, we have checked and added all necessary code/modifications to make sure the generator can work with more men for chess endgames.
When indexing, the generator combines similar chess pieces to save their index space. For example, two different chess pieces (say, a Rook and a Knight “rn”) have index space of 64 x 64 = 4,096, but the combination of two Rooks “rr” takes only 2016, saving more than half of the space. More similar pieces, much more savings. The previous code missed combinations for more than 3 pieces thus they can’t work with more than 3 attackers (5 men). Theoretically, a chess position can have a maximum of 10 similar pieces (say, 10 white Rooks). After adding the necessary code we could run the generator for more pieces of endgames.
That doesn’t mean we can build EGTBs easily for higher numbers of men since we are hardly limited by hardware and time to generate those endgames. For example, to build a 7-man EGTB, the Lomonosov team had to use supercomputers running multiple months to build it. We should use similar computing power to build our 7-man EGTB too which is too expensive and out of reach for almost all of us. Instead, we will get some interesting information with those EGTBs (higher numbers of pieces).
The generator can receive the name of endgames from command line arguments (e.g., “-n krkp”). If we give it the number of attackers, say -n 5, it will add all valid configurations of 5 attackers, plus all valid configurations of defenders (in the case of chess, it’s two Kings only, the total is 5+2 = 7 men).
With the argument “-subinfo” the generator will list all sub-endgames with their index size.
6 men
Command line:
The generator prints out:
The largest endgames have an index size of about 22 G, we need at least 22 x 2 = 44 GB RAM (to allocate two arrays for two sides, 1 byte per item). We may (highly likely) need to double that size (88 GB) if each item needs to be 2 bytes. The computers with that size of RAM are not cheap but still reachable for many of us.
In Attempt 12 we generated a 5-man EGTB, the index size is 21 G, the EGTB after compressing is 8.8 GB, and we have a compress ratio of 8.8 / 21 = 0.42. This 6-man has an index size of 3421 G. If we have a similar compression ratio, the size should be 3421 G x 0.42 = 1,436.82 GB = 1.44 TB. That size is larger than 1.2 TB of Nalimov 6-man but they all are still on the same level.
That size is about 163 times larger than a 5-man one. We have built 5-man in 17 hours. If we use the same computer, the new one may take 17 hours x 163 = 2,771 hours = 115.5 days.
Building 6-men EGTB is difficult, long time and not cheap. But it’s clearly feasible.
7 men
We need a computer with 1.5x2x2 = 6 TB RAM (2 sides x 2 bytes) to fit the largest endgames. The EGTB index size is about 440 T, equal to 440 T x 0.42 = 185 TB. That is significantly larger than 140 TB of Lomonosov 7-man EGTB, but the number looks reasonable and on the same level too.
Look like we cannot build 7-men without having very expensive computers.
8 men
EGTB size should be around 48 P x 0.42 = 20 PB.
We can’t build this EGTB with current hardware as well as bigger ones anyway.
9 men
EGTB size should be around 4'272 P x 0.42 = 1794 PB
10 men
Some integer variants of 64-bit became overflow. We have to change them into unsigned 64-bit.
The index size is about 4203 P, smaller than 9 men. We guest the variant for the total number (it is an unsigned 64-bit integer) is overflowed. However, the number of endgames and their sizes are still valid and good for reference.
11 men
We have to wait a very long time (over 1 hour) when the program is computing for 11 men. Since this computing is very rare to run, we didn’t try to speed up the code.
A gain, the total size (6501 P) is incorrect because of being overflowed. The number of endgames and their sizes are still valid.
Fixing issues of being overflowed requires some good effort. Thus we stopped here.
From a question (@Dann Corbit) about the limit of the generator, we have checked and added all necessary code/modifications to make sure the generator can work with more men for chess endgames.
When indexing, the generator combines similar chess pieces to save their index space. For example, two different chess pieces (say, a Rook and a Knight “rn”) have index space of 64 x 64 = 4,096, but the combination of two Rooks “rr” takes only 2016, saving more than half of the space. More similar pieces, much more savings. The previous code missed combinations for more than 3 pieces thus they can’t work with more than 3 attackers (5 men). Theoretically, a chess position can have a maximum of 10 similar pieces (say, 10 white Rooks). After adding the necessary code we could run the generator for more pieces of endgames.
That doesn’t mean we can build EGTBs easily for higher numbers of men since we are hardly limited by hardware and time to generate those endgames. For example, to build a 7-man EGTB, the Lomonosov team had to use supercomputers running multiple months to build it. We should use similar computing power to build our 7-man EGTB too which is too expensive and out of reach for almost all of us. Instead, we will get some interesting information with those EGTBs (higher numbers of pieces).
The generator can receive the name of endgames from command line arguments (e.g., “-n krkp”). If we give it the number of attackers, say -n 5, it will add all valid configurations of 5 attackers, plus all valid configurations of defenders (in the case of chess, it’s two Kings only, the total is 5+2 = 7 men).
With the argument “-subinfo” the generator will list all sub-endgames with their index size.
6 men
Command line:
Code: Select all
fegtb -n 4 -subinfoCode: Select all
1) knk 36'096
2) kbk 36'096
3) krk 36'096
4) kqk 36'096
…
175) krbkrb 9'462'349'824
176) krrknn 2'292'240'384
177) krrkbn 4'657'250'304
…
509) kpppkp 1'499'355'648
510) kppppk 351'411'480
Total endgames: 510, total size: 3'421'720'926'408
One of the largest endgames: krkbnp, size: 22'724'739'072
In Attempt 12 we generated a 5-man EGTB, the index size is 21 G, the EGTB after compressing is 8.8 GB, and we have a compress ratio of 8.8 / 21 = 0.42. This 6-man has an index size of 3421 G. If we have a similar compression ratio, the size should be 3421 G x 0.42 = 1,436.82 GB = 1.44 TB. That size is larger than 1.2 TB of Nalimov 6-man but they all are still on the same level.
That size is about 163 times larger than a 5-man one. We have built 5-man in 17 hours. If we use the same computer, the new one may take 17 hours x 163 = 2,771 hours = 115.5 days.
Building 6-men EGTB is difficult, long time and not cheap. But it’s clearly feasible.
7 men
Code: Select all
1379) kqbppkq 534'031'368'192
1380) kqbnpkp 1'090'787'475'456
...
1467) krpppkr 127'945'015'296
1468) krnppkp 400'523'526'144
...
1510) kppppkp 16'867'751'040
1511) kpppppk 3'092'421'024
Total endgames: 1511, total size: 439'858'437'385'704
One of the largest endgames: kqkrbnp, size: 1'454'383'300'608
Look like we cannot build 7-men without having very expensive computers.
8 men
Code: Select all
581) kqrkrrr 96'249'839'616
582) kqrkqnn 298'064'019'456
583) kqrkqbn 605'590'388'736
...
1568) kqnkrnnn 6'159'989'735'424
1569) kqnkrbnn 19'076'097'245'184
...
1657) krbnkrnn 19'076'097'245'184
1658) krbnkrbn 38'757'784'879'104
1659) krbbknnn 3'031'869'947'904
...
4030) kpppppkp 148'436'209'152
4031) kppppppk 22'162'350'672
Total endgames: 4031, total size: 47'556'659'223'031'800
One of the largest endgames: kqnkrbnp, size: 93'080'531'238'912
We can’t build this EGTB with current hardware as well as bigger ones anyway.
9 men
Code: Select all
7192) kqbnnnpkq 946'803'528'695'808
7193) kqbnnnnkp 225'605'528'322'048
7194) kqbbnnpkn 1'443'111'830'028'288
…
9750) kppppppkp 1'063'792'832'256
9751) kpppppppk 132'974'104'032
Total endgames: 9751, total size: 4'272'270'680'220'272'472
One of the largest endgames: kqbnkrbnp, size: 5'957'153'999'290'368
10 men
Some integer variants of 64-bit became overflow. We have to change them into unsigned 64-bit.
Code: Select all
19861) kqrpppkbnn 16'507'977'653'551'104
19862) kqrpppkbbn 16'507'977'653'551'104
19863) kqrpppkbbb 5'330'701'117'292'544
19864) kqrpppkrnn 16'507'977'653'551'104
19865) kqrpppkrbn 33'540'018'089'754'624
…
21940) kpppppppkp 6'382'756'993'536
21941) kppppppppk 681'492'283'164
Total endgames: 21941, total size: 4'202'946'837'452'060'244
One of the largest endgames: kqrbnkrbnp, size: 381'257'855'954'583'552
11 men
We have to wait a very long time (over 1 hour) when the program is computing for 11 men. Since this computing is very rare to run, we didn’t try to speed up the code.
Code: Select all
28952) kqrrbkqbbbp 1'908'755'913'850'748'928
28953) kqrrbkqrnnp 5'910'986'055'795'867'648
28954) kqrrbkqrbnp 12'009'622'462'569'381'888
28955) kqrrbkqrbbp 5'910'986'055'795'867'648
...
46240) kbpppppppkp 408'496'447'586'304
46241) krpppppppkp 408'496'447'586'304
46242) kqpppppppkp 408'496'447'586'304
46243) knppppppppk 43'615'506'122'496
46244) kbppppppppk 43'615'506'122'496
46245) krppppppppk 43'615'506'122'496
46246) kqppppppppk 43'615'506'122'496
46247) kpppppkpppp 601'723'282'849'920
46248) kppppppkppp 383'320'017'222'912
46249) kpppppppkpp 149'994'789'348'096
46250) kppppppppkp 32'711'629'591'872
Total endgames: 46250, total size: 6'501'485'980'035'256'340
One of the largest endgames: kqrbnpkrbnp, size: 18'300'377'085'820'010'496
Fixing issues of being overflowed requires some good effort. Thus we stopped here.
Attempt 16: Store whole board data in Hist record
Attempt 16: Store whole board data in Hist record
When making a move, whole board data is copied into Hist record, thus the takeback function could be simplified by copying back stored board.
- Chess perft 5 took 523 ms, 161% longer (slower) than Attempt 7
The code is in the branch "wholeboardinhist".
When making a move, whole board data is copied into Hist record, thus the takeback function could be simplified by copying back stored board.
- Chess perft 5 took 523 ms, 161% longer (slower) than Attempt 7
The code is in the branch "wholeboardinhist".
Attempt 17: Use table move generator
Attempt 17: Use table move generator
Use table move generator. It could speed up Perft to 10%. If using table move data for isInCheck function, the speed up is about 5% (slower).
The code is in the branch "tablemovegen".
Use table move generator. It could speed up Perft to 10%. If using table move data for isInCheck function, the speed up is about 5% (slower).
The code is in the branch "tablemovegen".
Attempt 18: create a test EPD file from all existent endgames
Attempt 18: create a test EPD file from all existent endgames
The test file will be used to verify the correctness of an EGTB later.
The test file will be used to verify the correctness of an EGTB later.
Attempt 19: more compact for chess index space
Attempt 19: more compact for chess index space
We reduced index space for chess. For 5 men chess EGTB, the index space sank about 13%. The size becomes 7.5 GB, a 15.5% reduction (compared with the previous size of 8.88 GB). However, the time to generate is about 29% longer (22 hours vs 17 hours). We are still not clear yet why/where the speed was lost.
We reduced index space for chess. For 5 men chess EGTB, the index space sank about 13%. The size becomes 7.5 GB, a 15.5% reduction (compared with the previous size of 8.88 GB). However, the time to generate is about 29% longer (22 hours vs 17 hours). We are still not clear yet why/where the speed was lost.
Attempt 20: Xiangqi generator
Attempt 20: Xiangqi generator
The code for the Xiangqi generator has been added. It can generate endgames with a side with up to 2 attackers and one side with no attacker (armless). E.g., kraabkaabb, kcnaabbkaabb, kcpakaab. It could work with more attackers but I haven't checked them yet. Both sides with attackers will be later work.
To generate those endgames, set the parameter name as 1, 2-0, cn-0. E.g.:
Here are some stats for all endgames with only one attacker (with all configurations of defenders):
The compression ratio of 0.1 (or 10 times smaller) is much better than that of chess (0.42). The data size is reasonably small.
However, compared with the data size of the first release one 6 years ago (2018), when the size of 1 attacker EGTB is only 14 MB, the current one is 28 times bigger (392 MB vs 14 MB).
Did we make an improvement or a serious disimprovements???
The code for the Xiangqi generator has been added. It can generate endgames with a side with up to 2 attackers and one side with no attacker (armless). E.g., kraabkaabb, kcnaabbkaabb, kcpakaab. It could work with more attackers but I haven't checked them yet. Both sides with attackers will be later work.
To generate those endgames, set the parameter name as 1, 2-0, cn-0. E.g.:
Code: Select all
fegtbxq.exe -d c:\xqegtb -n 2-0 -g -core 10Code: Select all
Total endgames: 324
Index space: 2'017'954'701 (2 G)
Data size: 392 MB
Compression ratio: 0.392 / (2 G x 2) = 0.1However, compared with the data size of the first release one 6 years ago (2018), when the size of 1 attacker EGTB is only 14 MB, the current one is 28 times bigger (392 MB vs 14 MB).
Did we make an improvement or a serious disimprovements???
Attempt 21: integrate Felicity EGTB with some chess GUIs
Attempt 21: integrate Felicity EGTB with some chess GUIs
The work is outside this project. It tests the abilities of integrating and displaying. It is useful for checking EGTBs in visual ways.
The work is outside this project. It tests the abilities of integrating and displaying. It is useful for checking EGTBs in visual ways.