EndGame Databases

TAILLE · Post by **TAILLE** » Thu Jun 21, 2007 14:27

Ed Gilbert wrote:Hi Gerard,

I can use my workstation at work to run this slice over the weekend and give you an exact answer next week. It has been a while since I ran this so I don't remember how long it took. But my prediction is that if I start this on Friday evening when I leave the office, it will be finished on Monday.

What is the clock speed your processor? I will run this on a single thread of a 2.67GHz core 2 duo running 32-bit XP.

-- Ed

Hi,
Thank you it will be a very interesting information.
To answer your question I use 2.00GHz core 2 duo running also 32it XP.
For your information I am improving my algorithm to gain in time by reducing lookups and also to go further in my partial information approach. This was not essential for generating the 6 pieces db but with the 7 pieces it is different.
Gérard

Rein Halbersma · Post by **Rein Halbersma** » Thu Jun 21, 2007 14:56

TAILLE wrote: What is your approach of your calculation ?
Gérard

When you count correctly you have choose(50,5) * choose(45,2) = 2,097,572,400 possibilities per side to move. A naive symmetry reduction by 1/4 gives 524,393,100 positions with per side to move.

But you need to take into account positions that are symmetric in flips along the long diagonal. These are positions in which black and white both have an even number of kings on opposite squares of the long diagonal. There are 6 possibilities (white can have 1,3,5 kings on the diagonal, black 0 or 2) for in total 206,160 positions.

So the total number of inequivalent 5vs2 positions is (2,097,572,400 + 206,160)/4 = 524,444,640 per side to move, or 1,048,889,280 for both sides to move.

This number is easy to calculate, but I think having an index function that takes into account the exact symmetry is very difficult.

BertTuyt · Post by **BertTuyt** » Thu Jun 21, 2007 19:38

I try to understand the number of a 5Kx2K database positions with white to move.

I always thought that the number of possible positions (without taking symmetry into consideration) is :
comb(50,5) * comb(45,2) = 2118760 * 990,
which totals 2.076.596.676.000

Bert

BertTuyt · Post by **BertTuyt** » Thu Jun 21, 2007 19:42

Forget my last post I made an error it is indeed 2097572400, but then i don't understand the choose(52,5) * choose(47,2) from Rein ?

Bert

Rein Halbersma · Post by **Rein Halbersma** » Thu Jun 21, 2007 22:33

BertTuyt wrote:Forget my last post I made an error it is indeed 2097572400, but then i don't understand the choose(52,5) * choose(47,2) from Rein ?

Bert

sorry, I made a Freudian typo while thinking of 5vs2 I typed 52. It was in my Excel sheet like this: choose(50,5) * choose(45,2) = 2,097,572,400.

Rein Halbersma · Post by **Rein Halbersma** » Thu Jun 21, 2007 23:01

Who of you has implemented an indexing function that takes into account all symmetries?

When both sides have an even number of kings, the symmetries are rather messy. Take 2 kings vs 2 kings e.g.

There are choose(50,2)*choose(48,2) = 1,381,800 positions per side to move when not taking symmetries into account. Naive symmetry reduction of 1/4 would give 345,450 positions per side to move.

But, there are also choose(25,1)*choose(24,1)=600 positions that are symmetric under flipping in the trictrac lines 1-45 and 6-50. There are a further 600 positions that are symmetric under 180 degree rotation of the board (with 2 kings of the same color in squares that sum to 51).

Then there are the 3,440 positions that are symmetric under flipping in the main diagonal 5-46, where both sides have an even number of kings on this diagonal (choose(10,2)*(choose(8,2)+choose(20,1)) + choose(20,1)*(choose(10,2)+choose(19,1))=45*(28+20)+20*(45+19)=3,440).

All in all there are (1,381,800 + 2 * 600 + 3,440)/4 = 346,610 inequivalent positions per side to move, or 693,220 in total.

Indexing such positions seems particularly hard since you also need to take care of the choose(5,1)*choose(4,1)=20 positions that are symmetric under all three symmetry operations simultaneously and that are double counted in the 2*600 and 3,440 positions that are symmetric under only one of the three symmetries...

Ed Gilbert · Post by **Ed Gilbert** » Fri Jun 22, 2007 15:00

Rein, I used the symmetry about the double corner diagonal when I wrote the indexing functions for 5k vs 5k in English checkers. If there are more black kings in the triangle {5,29,32} than in {1,4,28} then I flip the board bitmaps around the diagonal. You are right that this complicates the design of the indexing functions. This particular slice took 2 days to compute using the symmetry. It would have taken a lot longer without it because my computer only had 2gb ram and I needed nearly all of it to buffer the slice in memory using the symmetry. If I was doing it today I would not bother using the symmetry because it takes longer to write and debug the indexing code than the time saved building the all-kings slices.

-- Ed

steenslag · Post by **steenslag** » Fri Jun 22, 2007 17:14

Michel Grimminck seems to use yet a different form of reducing calculation time: he doesn't bother to calculate the fastest win in some trivial cases. For instance:
(from http://www.xs4all.nl/~mdgsoft/draughts/ ... -1221.html )

<APPLET CODEBASE = "http://www.damweb.nl/" CODE = "webdam.Viewer.class" NAME = "webdam" ARCHIVE ="webdam/Viewer.jar" WIDTH = 360 HEIGHT = 240 HSPACE = 0
VSPACE = 0 ALIGN = middle><PARAM NAME="options" VALUE="bgcolor: b0c0a0; notation:right"><PARAM NAME="position" VALUE="WMWP46WK0106BP0405BK50]0112504406500510120710150701152001072025070125300107303507013540014504104540101540341520342920252923253023183035181235401245[/damweb_position]

The obvious 3. 12-3 wins much faster.

Or could there be another explanation for this?

steenslag · Post by **steenslag** » Fri Jun 22, 2007 17:22

I am in way above my head, but have you considered using rotated (or diagonal) bitmaps? Explained here: http://www.cis.uab.edu/hyatt/bitmaps.html .

Rein Halbersma · Post by **Rein Halbersma** » Fri Jun 22, 2007 18:01

steenslag wrote:I am in way above my head, but have you considered using rotated (or diagonal) bitmaps? Explained here: http://www.cis.uab.edu/hyatt/bitmaps.html .

yes, these are quite useful when generating moves for sliding pieces. but for database generation of kings only endgames you wouldn't need them.

Rein Halbersma · Post by **Rein Halbersma** » Fri Jun 22, 2007 18:04

steenslag wrote:Michel Grimminck seems to use yet a different form of reducing calculation time: he doesn't bother to calculate the fastest win in some trivial cases. For instance:
(from http://www.xs4all.nl/~mdgsoft/draughts/ ... -1221.html )

<APPLET CODEBASE = "http://www.damweb.nl/" CODE = "webdam.Viewer.class" NAME = "webdam" ARCHIVE ="webdam/Viewer.jar" WIDTH = 360 HEIGHT = 240 HSPACE = 0
VSPACE = 0 ALIGN = middle><PARAM NAME="options" VALUE="bgcolor: b0c0a0; notation:right"><PARAM NAME="position" VALUE="WMWP46WK0106BP0405BK50]0112504406500510120710150701152001072025070125300107303507013540014504104540101540341520342920252923253023183035181235401245[/damweb_position]

The obvious 3. 12-3 wins much faster.

Or could there be another explanation for this?

I think he calculates the longest possible win, where white doesn't try to win as quickly as he can, ie. the longest possible win when white tries to avoid winning

what would be interesting is the longest possible win where white tries to win as quickly as he can.

ildjarn · Post by **ildjarn** » Fri Jun 22, 2007 20:22

steenslag wrote:Or could there be another explanation for this?

There are some errors in the maximum pages. I have the full databases at work, will generate the maximum positions on tuesday (I have a day off on monday). From what I remember, the maximum length is OK, but the positions given aren't.

BertTuyt · Post by **BertTuyt** » Fri Jun 22, 2007 21:14

Rein, i don't make use of the symmetry concept so far.
Based on profiling I found out that the index function is consuming quite some time during the database generation, so i try to keep it as simple as possible.
So far I didn't generate databases beyond the capabilities of 32bit Windows, and as my current system has 1.5 GigaByte i did not bother that much.

When we want to generate 7piece to 8piece databases , im not sure what the right approach is.
The mirror approach does not yield much gain in positions where kings are not dominant.

Based on the replies so far i think we have huge opportunities in reducing storage space for calculated databases based on the work/suggestions/ideas of Gerard, also we should study in more details the concept of partial information databases as applied by Ed.

So far i miss breaktroughs in overall database generation time.
I have some weird ideas never tested, but i hope we can break the exponentional barrier here some time.

Bert

Rein Halbersma · Post by **Rein Halbersma** » Fri Jun 22, 2007 22:08

BertTuyt wrote:Rein, i don't make use of the symmetry concept so far.
Based on profiling I found out that the index function is consuming quite some time during the database generation, so i try to keep it as simple as possible.
So far I didn't generate databases beyond the capabilities of 32bit Windows, and as my current system has 1.5 GigaByte i did not bother that much.

When we want to generate 7piece to 8piece databases , im not sure what the right approach is.
The mirror approach does not yield much gain in positions where kings are not dominant.

Based on the replies so far i think we have huge opportunities in reducing storage space for calculated databases based on the work/suggestions/ideas of Gerard, also we should study in more details the concept of partial information databases as applied by Ed.

So far i miss breaktroughs in overall database generation time.
I have some weird ideas never tested, but i hope we can break the exponentional barrier here some time.

Bert

Could you share some of your weird, but undoubtedly interesting, ideas on database generation with the rest of us, Bert?

steenslag · Post by **steenslag** » Sat Jun 23, 2007 00:42

ildjarn wrote:
steenslag wrote:Or could there be another explanation for this?
There are some errors in the maximum pages. I have the full databases at work, will generate the maximum positions on tuesday (I have a day off on monday). From what I remember, the maximum length is OK, but the positions given aren't.

Ildjarn, these maximum-pages contain some very interesting positions and I've played trough most of them. However, many of them start with a (multiple) capture into a set of standard positions. That's understandable from a database-point of view, but it doesn't result in new interesting material. When you generate the maximum length positions, could you exclude initial captures?