Banksia GUI forums

Posted: **Tue Apr 16, 2024 12:40 pm**

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.

Posted: **Wed Apr 17, 2024 1:42 pm**

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.

Posted: **Fri Apr 19, 2024 12:59 am**

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".

Posted: **Sat Apr 20, 2024 8:03 am**

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!

Posted: **Sun Apr 21, 2024 10:20 am**

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"

Posted: **Thu May 02, 2024 1:59 pm**

Attempt 9:

Position indexes work for both Chess and Xiangqi/Jeiqi

Posted: **Sun May 05, 2024 2:43 am**

Attempt 10: index space for Xiangqi

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

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

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

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

Code: Select all

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

Total files: 729, total size: 167'077'730'106

Posted: **Mon May 06, 2024 12:21 pm**

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.

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

Posted: **Sun May 26, 2024 12:48 pm**

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!

Posted: **Mon May 27, 2024 10:40 pm**

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.

Posted: **Thu May 30, 2024 9:01 am**

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.

Posted: **Sat Jun 01, 2024 7:58 am**

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:

Code: Select all

fegtb -n 4 -subinfo

The generator prints out:

Code: 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

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

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

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

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

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

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

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.

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

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.

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

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.

Posted: **Fri Jun 28, 2024 9:41 am**

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".

Posted: **Sat Jun 29, 2024 10:29 am**

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".

Posted: **Sun Jun 30, 2024 2:05 pm**

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.

Posted: **Mon Jul 08, 2024 12:24 pm**

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.

Posted: **Wed Jul 10, 2024 2:14 am**

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.:

Code: Select all

fegtbxq.exe -d c:\xqegtb -n 2-0 -g -core 10

Here are some stats for all endgames with only one attacker (with all configurations of defenders):

Code: 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.1

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???

Posted: **Sun Jul 14, 2024 11:51 am**

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.

Banksia GUI forums

Progress reports

Progress reports

Attempt 4

Re: Progress reports

Re: Progress reports

Re: Progress reports

Re: Progress reports

Re: Progress reports

Attempt 11: calculate 5-men Index space for chess

Attempt 12: generate all 5-men endgames for chess

Attempt 13: generate all 5-men endgames for chess using the backward method

Attempt 14: Improve the speed of generating all 5-men endgames for chess with the backward method

Attempt 15: calculate index spaces for more men for chess

Attempt 16: Store whole board data in Hist record

Attempt 17: Use table move generator

Attempt 18: create a test EPD file from all existent endgames

Attempt 19: more compact for chess index space

Attempt 20: Xiangqi generator

Attempt 21: integrate Felicity EGTB with some chess GUIs