draughts EGTs: 9-men possible?

[H.G.Muller]

EGT generation is one of my hobbies, especially designing efficient algorithms for it. Until now it never occurred to me that EGTs coulkd be very important in draughts , perhaps more so than in Chess, where they really are not much help to improve playing strength of engines.

I wondered what the state of the art is in draughts EGT generation. A back-of-the-envelope calculation tells me a 5+4 men EGT with all kings (the worst 9-men case) would contain 50^9/(4*5!*4!) = 10^18/(2^9*4*120*24) = 10^18/(2048*2880) ~ 1e18/(5.9e6) = 1.7e11 = 170G positions. That is not too big for current hard disks. With 1 bit per position it could even be considered smallish (~20GB) even before compression. So this does sound rather feasible.

Once you have the king-only EGT, working your way back through the slices with at least 1 unpromoted disk is effectively only solving a 6-men, which is 10 times smaller. A high-end gaming PC might be able to hold such a slice in RAM, speeding up the generation process a factor 100 or so. I can add that to fully characterize most of the slices with many unpromoted disks the 7-king EGT might not even be needed. (And for game play these might be the most interesting ones...) A further advantage of draughts EGTs is that when you have seen one, you have basically seen them all, as there is no variation of (reversible) piece types.

So I wondered if 9-men EGTs have already been built, and if not, if there is any interest in doing this.

[Ed Gilbert]

Hi HG,

Nice to see you at the draughts forum. I am an occasional reader of the talk chess forum and I'm somewhat familiar with your work on winboard and various chess engines.

Egdbs are very important in draughts. They start having an effect when there are ~18 pieces on the board, and with 16 or less they can have a big effect. In 8x8 English checkers, the effect is even more powerful. The state of the art in that game is that engines with a large opening book and a 10-piece egdb are basically unbeatable. In 10x10 international draughts there is still a region between dropping out of opening book and hitting the egdbs where the engines have to rely primarily on heuristic evals. In that game there is still a lot of room for improvement of the programs.

A few of us have built the 8-piece egdb for 10x10 draughts. I have also built some 9-piece subsets, but not using the traditional method that you mentioned, ie. starting with 9 kings. In international draughts a very high percentage of moves are captures due to the forced capture rule, the rule allowing men to capture in both forward and back directions, and the flying kings. Because of all these captures, it is possible to build for example the 5 men vs. 4 men subset of 9 pieces without building any of the other 9-piece subsets. Of course some of the positions depend on other 9-piece positions with some kings and their win/loss/draw values can not be resolved, but a large percentage can be exactly resolved. Some positions can also be partially resolved to values that are 'win or draw', or 'draw or loss'. I built the 5 men vs. 4 men subset twice. The first time I had no other 9-piece subsets available. I was able to resolve 51% of the positions to win, loss, or draw, and another 37% were partially resolved. I later built the 5 men vs. 3 men 1 king, and 4 men 1 king vs. 4 men subsets, and then rebuilt the 5 men vs. 4 men subset, making use of the subsets with 1 king. This time I was able to resolve 74% of positions to an exact WLD value, and only 2% were totally unknown. The positions that are partially resolved are used during an engine search to clip the heuristic values within the known range.

I have the most useful subsets of the 9-piece db, and right now I have no plans to build any more. The size of the 2 - 8 pieces db is approximately 400gb compressed, and the 5 men vs. 4 men subset is another 18GB. A full 9-piece db might not be practical to use on a typical home PC with e.g. 8 or 16gb of RAM, and it might consume ~5TB of disk space.

-- Ed

[Rein Halbersma]

Hi HG,

You probably know about the Chinook project that solved 8x8 checkers in 2007. There are 2 very good research papers on the state of the art for checkers database building.

Building the Checkers 10-piece Endgame Databases (this algorithm has been used to build the 8 piece db for 10x10 draughts):
http://www.ru.is/faculty/yngvi/pdf/SchaefferBBLLS03.pdf

Partial Information Endgame Databases (this algorithm is what Ed used for his 5 vs 4 men db for 10x10 draughts):
http://www.ru.is/faculty/yngvi/pdf/BjornssonSS06.pdf

Ed also has his own summaries of building the 10-piece db for 8x8 checkers and the 8-piece db for 10x10 draughts:
http://edgilbert.org/EnglishCheckers/10-pieceBuild.htm
http://edgilbert.org/InternationalDraug ... hts_db.htm

Efficiently accessing (i.e. avoiding too much disk I/O) the databases during a live search requires quite a bit of infrastructure (LRU caching, index files etc.), for a brief summary see this forum:
viewtopic.php?t=1925&start=236

Martin Fierz has published the source code for his own 8x8 checkers database generator and access code:
http://www.fierz.ch/download.php

There are some tricks from the CCRL/talkchess forums that have not been applied to draughts (out-counting, leap-frog). So perhaps you might surprise us with some new breakthroughs!

Rein

[H.G.Muller]

'On-the-fly' building of EGT slices with many irreversible pieces is a possibility that is very attractive for Chess. The problem is always that the slices required for the game at hand can eventually convert to the far greater end-games with promoted pieces. The situation in Draughts seems a bitless favorable in this respect. When solving relevant slices of KPPPKPP in Chess, a lasting conversion to KQPPKPP (i.e. the Q is not taken the next move) can usually be proven a win under the (too pessimistic) assumption that every position from KQQPKPP and KQPPKQP is lost). This means you can avoid generation of end-games with ridiculously large numbers of Queens. KQPPKPP will be contaminated with wrong DTx values and perhaps even wrong WDL assignment for some positions with highly advanced Pawns, but if in the position of interest the Pawns are not likewise advanced this does not affect the WDL value of the relevant promotion. And the latter is all that is needed to get the relevas slices of KPPPKPP correct.

In draughts a King is not as all-powerful as a Queen in Chess, so proving a win after the first promotion under restrictive assumptions can quickly become too difficult. So the assumption that your first King will be able to finish the job might have to be dropped, meaning that you would also have to generate end-games with multiple Kings for the winning side. The assumption that an opponent promotion will spoil the win actually seems less overly pessimistic than in Chess, as you typically need multiple Kings to defeat a single one, where in Chess the advantage of a single Queen is usually decisive. What is bad for on-the-fly generation is that unpromoted checkers have two moves, where FIDE Pawns only have one, and can thus usually reach a much larger number of squares from a given position. This means you have to solve more slices for a given location of the checker in the game.

The P-slices in Chess that you won't be able to solve without solving the 'all-promoted' end-game (KQQQKQQ in the example) are usually the P-slices that, although formally reachable through legal moves, are not reachable by sensible play. E.g. with 3 white Pawns on 7th rank, and 2 Black Pawns on 2nd. There you usually won't be able to prevent opponent promotion with your first Queen. But of course no one would ever advance a third Pawn to 7th rank if he had already 2 Pawns there, which he could promote immediately (in the mean time allowing the opponent to advance his to 2nd rank). I assume this is similar in Draughts.

I am currently thinking about how a many-King end-game could best be pseudo-sliced in order to implement leap-frog. The high exchage-symmetry, which I am not used to in Chess, and can often be ignored even if it is there at the expense of a modest amount of extra work, is essential to reduce the EGT size to a manageable value in Draughts, but greatly complicates the slicing. The only way I have come up so far exploits that Kings in Draughts are basically Rooks, which allow factorization into horizontal and vertical moves (i.e. parallel to the long diagonal, or to the short ones). What is horizontal and vertical is not affected by permuting the Kings (while attempts to split the moves into moves of the first half and second half are thwarted by this). The problem, however, is that the diagonals are not equally long, so that the various working sets will differ greatly in size, making it harder to accomodate the worst case.

E.g. with 4 Kings (of the same color), the worst case for vertical moves is two diagonal of length 9, two of 7. That makes 63^2, while moving two of the four Kings over the entire board would only have been 50^2. So in the 4+5 EGT, where a chunk of 5 fully symmetried black King constellations would take 50^5/(4*5!) = 1e10/(128*120) = 651k positions, the assembled pseudo-slice for all white vertical moves would measure 2.58G positions. With only 1 bit per position this would amount to 308 MB.

This is still doable, of course, but it leaves little room for reducing the number of seek operations. When the entire EGT would have to be stored as 50^4/4! = 1e8/(16*24) = 260k chunks of 261k/8 = 80kB, you would need 260k seeks to assemble the pseudo-slices for one iteration when traversing the matrix in the unnatural order (and an equal number to write them back). IIRC you had to store the 'won' bitmap in duplicate (accumulated wins as well as new wins, before packing the latter to write it to disk), so that makes 616MB, soon a 4GB machine you might be able to afford storing four times as much. That means you could make the chunks 4 times larger in both dimensions, though, reducing the number of seek operations 16-fold (to 16k). That doesn't sound too bad, though: modern hard disks have sub-10ms seek times, so it would be 160sec (x2) worth of seek time per iteration. (That can't be right, can it? I would not have expected this to be easy... Of course I don't really have 4GB in my machine. )

[H.G.Muller]

OK, it seems I have a workable scheme for factorization for the case of 4 Kings (of one color):

The board can be divided into 5 diagonal zones of 10 squares, by combing pairs of diagonals (1+9, 3+7 an 5+5 in one direction, 2+8, 4+6 and 10 in the other). If every zone contains 1 King (worst case), there are 10,000 constellations of the Kings for each set of zones, but there are only 5 such sets. More often a zone contains multiple Kings, reducing the number of constellations by exchange symmetry within that zone. E.g. with occupation numbers of the zones 21100 (possible in 30 ways) there are 4500 constellations, 22000 (10 ways) has 2025, 31000 (20 ways) has 1200, and 40000 (5 ways) only 210.

By combining cases until they are nearly as large as the worst case, we can reduce the number of occupation groups to 25:
*) 11110 each form a group (of 10,000 constellations) of their own. (5 groups: 11110, 11101, 11011, 10111, 01111)
*) 21100 patterns are combined in pairs of 9000 constellations when the 2 is not between the 0 (10 groups: 21100+01102, 11200+11002, etc.)
*) The remaining 21100 patterns are combined with one 22000 and two 31000 patters (8925 constellations), for 10 groups (e.g. 01120+02200+03100+01300).
*) The five negligibly numerous 40000 occupation patterns are also absorbed in some of the latter

This achieves subdivision of the total number of 4-King constellations into 25 slices, each invariant under moves in one direction, as well as in 25 slices invariant under moves in the orthogonal direction. The total set of constellations can then be subdivided over a 25x25 matrix, each row and column of the matrix containing 9000-10,000 constellations. Each of the 230,300 white constallation maps into a cell of this matrix, (some 400 per cell), and represents 650k complete constellations after adding the 5 opponent kings in all possible ways (taking care of spacial symmetry there by allowing only one of the 4 equivalent orientation). That maps about 260M complete constellations into one cell. These are packed to bitmaps of ~33MB, and stored on the hard disk as contiguous data, (one 'chunk'), so they can be read or written as streaming I/O with only a single seek operation.

To assemble one slice, 25 such chunks have to be read in memory, filling 800MB (for the won-with-white-to-move bitmap). This allows processing of all intra-slice white unmoves, followed by all necessary black unmoves and moves, for two subsequent iterations, with the data currently loaded in memory, before writing it back, and going on to the next slice. After treating the entire matrix that way, (25 slices) we would do the same thing for slices in the other direction (leapfrog).

So per iteration we would have to do 625 seek operations, read and write 20GB of bitmap data, and perhaps some 5GB of lost positions (packed, because it is a sparse bitmap), stored contiguous with the bitmap chunks (so no extra seeks). The iteration that steps through the matrix in natural order would only need 25 seek operations, before it could stream in an entire.

Unless I made a major mis-calculation here, 9 Kings (or at least 4 vs 5) does not really seem a tough job at all. How long would it take to read 20GB? Can modern hard disks do 100MB/sec? Even with 10MB/sec it would only take about an hour per iteration. That makes it sound like a single-day job...

[Rein Halbersma]

Hi HG,

That are some really intricate slicing techniques that you describe there. I'm not sure about the 1-day job though: if you include adapting (and debugging!) the single-db generator to your scheme as well, it might take many days of work.

OTOH, the whole 5K vs 4K database fits within choose(50,4)*choose(46,5)/ (4*8) = 9.86 Gb of RAM, which at $10 per Gb costs about $120. Then you can simply run it as a single slice. Depending on your current motherboard, and the distance to the hardware store, it might take a few hours to compute it that way. I'm just saying, for people without experience with your advanced slicing, this might be the easiest solution.

One reason this has not been done yet, is that the really interesting dbs are those with only 1 or 2 kings for each side. Computing these is best done by the incomplete information db techniques mentioned by Ed, because then you save on a few Tb of disk space that all the uninteresting king-heavy 9-piece dbs would fill up.

If you really want to stretch the limits, you could shoot for the 5K vs 5K db, which requires 80 Gb of raw RAM for a single slice run. So unless you have large server access, you really need your subdivisions for that 10-piece db. Assuming that would take 8 times as long as the 5K vs 4K, you would need 200 Gb of fast disk space, and about 1-2 weeks of computing time.

Anyway, I guess what you really show is that memory is not the bottleneck for building very large endgame databases. Given enough disk space (100 Tb anyone?), today's high-end desktops (>16Gb RAM, >8cores) could compute the full 9 piece dbs within 2 years probably, and a good chunk of the incomplete 10 piece databases as well.

Rein

[H.G.Muller]

I'm not sure about the 1-day job though: if you include adapting (and debugging!) the single-db generator to your scheme as well, it might take many days of work.

Ah, yes, it is good of you to point this out. Indeed programming it would be a job of many days, if not weeks. I am just to set in my way of thinking for Chess, where you program one generator, and then can use it to solve hundreds of different end-games, so that the investment of writing the generator is negligible. But here it is basically a one-time effort. This is definitely an area where the "seen one, seen them all" character of Draughts works against you.

But estimating the run-time is a worthwile endeavor, because when it seems neligibly short compared to the programming effort (suggesting youwould gain by using aless advanced algorithm to reduce programming time at the expense of multiplying run time), it of course means I get more ambitious. Due to the high exchange symmetry adding another King only drives up the size a factor 10, and 200GB is still very modest. A program that could do 9 kings would probably be able to handle 10 kings as well,with only minor modifications, and if I get the 9-men run time around 1 day, two weeks for 10 kings would have a more reasonable ratio between program development and run time.

OTOH, the whole 5K vs 4K database fits within choose(50,4)*choose(46,5)/ (4*8) = 9.86 Gb of RAM, which at $10 per Gb costs about $120. Then you can simply run it as a single slice. Depending on your current motherboard, and the distance to the hardware store, it might take a few hours to compute it that way. I'm just saying, for people without experience with your advanced slicing, this might be the easiest solution

Sure. All my computers are pretty old and 32 bit, so I tend to forget how much you can stretch things with modern hardware. So 9 kings is a piece of cake, but that simply means we should set out aim higher, e.g. to do 11 men. Using the large amount of RAM you mention you can hold 10 times larger slices, and thus generate 100 times larger EGTs with an optimally sliced disk-based algorithm. To wire up two 1TB disks also doesn't cost you a king's ransom, these days.

One reason this has not been done yet, is that the really interesting dbs are those with only 1 or 2 kings for each side. Computing these is best done by the incomplete information db techniques mentioned by Ed, because then you save on a few Tb of disk space that all the uninteresting king-heavy 9-piece dbs would fill up.

Well, there is no need to actually store what is not interesting. My idea was to start with the all-King EGT to get exact values for all promotionpositions, and then work your way back through the slices until you reach material compositions of interest. Until then you can delete anything as soon as you are done with it. I was counting on being able to build the slices purely in RAM, although for 8 kings + 1 checker this might not be feasible yet. It is only an 8-men EGT, but you don't save that much per king in Draughts, and you lose the spatial symmetry factor of 4. But of course an 8GB machine would come in handy here. The results could be saved on disk as WDL bitbases to save space, or perhaps even only the promotion positions in them (I am not sure if this saves significantly), to be used for seeding the 7 kings + 2 checkers slices, after which they can be deleted.

If you really want to stretch the limits, you could shoot for the 5K vs 5K db, which requires 80 Gb of raw RAM for a single slice run. So unless you have large server access, you really need your subdivisions for that 10-piece db. Assuming that would take 8 times as long as the 5K vs 4K, you would need 200 Gb of fast disk space, and about 1-2 weeks of computing time.

Anyway, I guess what you really show is that memory is not the bottleneck for building very large endgame databases. Given enough disk space (100 Tb anyone?), today's high-end desktops (>16Gb RAM, >8cores) could compute the full 9 piece dbs within 2 years probably, and a good chunk of the incomplete 10 piece databases as well.

Well, cores do in general not help. This is hardly a CPU intensive problem. Dann Corbit once tried to make a fast PGO compile of my in-RAM EGT generator, and complaint afterwards that 95% of the execution time was spent in a single statement: x = tb[index]; Of course that was the statement that produced the cache miss, and had to wait for the memory access. By optimizing the code to make it run 5 times faster, he could drive up the cost of this statement to 99%, for a total speed gain of 0%...

What would help is multiple disk and raid controllers. At least for the king-heavy end-games that are too big to fit in RAM. As soon the slices fit in RAM the disks also become irrelevant. (Unless you want to store everything you calculate, and even then the speed is not very important, as there is a big difference between having to shuttleback and forth the data to disk for every iteration, or just storing the result after a memory-based calculation.) RAM is really the decisive factor, and the motherboard/chipset could be of help here by supporting multiple memory banks that can be accessed in parallel.

[TAILLE]

Hi,

I am sure that generating the 5K4K EGT is feasible with the current technology but my knowledge of draugths tells me that this EGT is absolutely unuseful.
Let's assume that the most interesting slices are those with a maximum of 1 king on the board.
Depending of your goal you can have several approach for that:
1) You can generate the complete 5x4 EGT from 5Kx4K to 5Mx4M which is perfect but very time consumming
2) As Ed. did you can also made partial generation by avoiding genrating a lot of slices assuming the corresponding positions are unknown
3) I see a third option: generating the EGT with acceptable errors in it by just setting a default value for a number of quite obvious slices.
For example it is quite obvious that considering by default that a 5Kx4K is a draw will not impact the interesting slices (with at most one king on the board) and you can go quite further assuming e.g. that 1K4Mx2K2M is draw etc. etc.
The point is the following : in very rare occasions the result given for the interesting slices will be incorrect but in the great majority of the cases it will be correct and thus it is a big improvment comparing to heuristic evaluation.
I see basically two difficulties with Ed. approach:
1) firstly it is quite a big programmation investment to handle a partial generation
2) secondly in a real game between two programs with quite similar strenghs I imagine it often happens that the side with only 4 men (against 5 men) will have some positionnal compensation for that, and then will be able to promote one of its men more or less at the same time its opponent will promote a man. In that case the result given by the EGT will always be unknown.

What is your feeling?

[H.G.Muller]

Well, I don't play Draugts myself, so my intuition on this is limited. I have designed a number of slicing techniques for Chess EGTs, though, and I wanted to investigate if these would be of any use in Draughts. Building selected slices of end-games with only few Kings without first generating all end-games into which they could in theory convert is usually possible. In Chess the analogous case exists in Pawn endings, where the ultimate all-Queens EGT is totally irrelevant for any sensible Pawns-only slice. The strategy is to start with successor P-slices that are easily won because of a promotion, while the opponent Pawns are still far from promotion. These P-slices can then usually be won even under the pessimistic assumption that no second promotion of your own is needed, and no promotion of the opponent has to be allowed. So you won't need any successors of that, but simply assume that they are all draw (so not good enough when computing wins). If the P-slice is already generally won under those pessimistic assumptions, it will certainly be won in real life, and there is no need to solve any of the promotion successors.

So basically it becomes a forward tree-search over P-slices from the slices you are interested in (e.g. with 0 or 1 King), where you are searching under pessimistic assumptions for slices that are generally won. If you can't find any, you have to relax the assumptions (meaning you have to expand the node, as without the assumptions you need to solve successors first). You can lift the restrictions in steps (partially expanding the node), e.g. first allow no (viable) Pawn pushes at all, then also allow opponent Pawn pushes, then also allow your own, then allow also promotions of your own, and as a final resort also allow (viable) promotions of the opponent. In the end you should find a path through generally won P-slices to one that is generally won without the need to compute successors, which avoids visiting end-game with more Queens than you need.

I assume this same technique is applicable to Draughts. A qualitative difference is that winning with 1 vs 0 King in Draughts seems more difficult than wining with 1 vs 0 Queen in Chess (in the presence of irreversible pieces), and that the tree of successor P-slices in Draughts is branched, while in Chess it is linear. This makes the searches over P-slices larger, and makes it less certain you won't need 2 vs 0 King end-games to prove a win for a Kingless position.

[Ed Gilbert]

2) secondly in a real game between two programs with quite similar strenghs I imagine it often happens that the side with only 4 men (against 5 men) will have some positionnal compensation for that, and then will be able to promote one of its men more or less at the same time its opponent will promote a man. In that case the result given by the EGT will always be unknown.

What is your feeling?

I think this is true if you don't have any 9pc slices with kings. If you have the 9pc slices with 1 king then the all men slice becomes more useful. In my 5 vs 4 men slice only 2% of positions are unknown, and 74% have exact values. I don't have any test data to show how often it is useful in a game.

-- Ed

[TAILLE]

Hi Ed.

2) secondly in a real game between two programs with quite similar strenghs I imagine it often happens that the side with only 4 men (against 5 men) will have some positionnal compensation for that, and then will be able to promote one of its men more or less at the same time its opponent will promote a man. In that case the result given by the EGT will always be unknown.

What is your feeling?

I think this is true if you don't have any 9pc slices with kings. If you have the 9pc slices with 1 king then the all men slice becomes more useful. In my 5 vs 4 men slice only 2% of positions are unknown, and 74% have exact values. I don't have any test data to show how often it is useful in a game.

-- Ed

Oops my wording was not correct I should have written
2) secondly in a real game between two programs with quite similar strenghs I imagine it often happens that the side with only 4 men (against 5 men) will have some positionnal compensation for that, and then will be able to promote one of its men more or less at the same time its opponent will promote a man. In that case the result given by the EGT will always be non exact.

Clarification of my view:
1) My feeling is that your 74% of exact values are very useful but the remaining 26% are quite completely unuseful comparing to a heuristic value
2) In a real game, the side with only 4 pieces (against 5) will often have some positional compensation for the piece down. As a consequence for a real game the proportion 74% vs 26% looks a little optimistic.

Do you have statistics showing on real game the figures for reaching on exact value or not for the 5Mx4M egdb?
value.

[Ed Gilbert]

Do you have statistics showing on real game the figures for reaching on exact value or not for the 5Mx4M egdb?

The only stats I took were to see how often a partial value was used to limit a heuristic score. It was a small effect but enough to make me think that keeping these was at least not totally useless.

-- Ed

[BertTuyt]

I tend to believe that 9P DB's are (more or less) possible, especially when you have access to an exotic server (or even a PC with a dual octa-core Xeon will do, with an insane amount of RAM).
These DB's are great for analyzing games.
What I'm not sure off, if the programs with a 9P DB plays better.

I often see a reduction of search speed as the cache needs to load all these (mostly Draw) positions, where as a result the average search-depth reduces.
Next to that, in case the other party does (normally) not have a 9P Db, so most likely no clue how to handle this, the risk is that (as the program does not differentiate between narrow-escape draws, and ultra simple draws) the program choses a move sequence which for the waker party is easy to defend.

So to benefit really from these dB's you need to add some additional code and/or develop specific algorithms. Think this is was Gerard (with Damy) is doing.

Bert