EndGame Databases

[Rein Halbersma]

Moving upwards for white is only shifting bits 5 or 6 places (i think everyone is familiar with ghost fields, so moving a man always uses the same number of fields, which is not the case on a normal board!).

So generating a bitboard with all possible moves for white in 1 direction is something like :
( bbEmpty<<5 ) & bbWhiteMan

Bert, I am not familiar with ghost fields and couldn't find anything with Google. Here's what I tried to reconstruct from your message.

The natural mapping of squares to bits would be something like this (so that a piece on square 1 is on the least significant bit)

Code: Select all

{  
  00, 01, 02, 03, 04,
05, 06, 07, 08, 09,
  10, 11, 12, 13, 14,
15, 16, 17, 18, 19,
  20, 21, 22, 23, 24,
25, 26, 27, 28, 29,
  30, 31, 32, 33, 34,
35, 36, 37, 38, 39,
  40, 41, 42, 43, 44,
45, 46, 47, 48, 49
}

Now, a man move = >>4 or >>5 for SW-NE and >>5 or >>6 for SE-NW

Do you use instead the mapping

Code: Select all

{  
  00, 01, 02, 03, 04,
05, 06, 07, 08, 09,
  11, 12, 13, 14, 15,
16, 17, 18, 19, 20,
  22, 23, 24, 25, 26,
27, 28, 29, 30, 31,
  33, 34, 35, 36, 37,
38, 39, 40, 41, 42,
  44, 45, 46, 47, 48,
49, 50, 51, 52, 53
}  

so that the bit fields 10, 21, 32, 43 are "ghost" fields?

Rein

EDIT: the forum killed all the spaces in my layout!

Code: Select all

[ildjarn]

EDIT: the forum killed all the spaces in my layout! [img]images/smilies/icon_redface.gif[/img]

Use the [ code ] ... [ /code ] tags for preformatted text

[BertTuyt]

Rein, you are absolutely right, i do it in the way you described.
This way a move of a man is always +5/+6 for black and -5/-6 for white.

In the Bitfields i set a bit when a board position is empty, or occupied (and then i set the bit in the specific bitboard, like whiteman, whiteking, blackman, blackking).

For the ghost fields (like 10, 21 ,32) i don't set a bit in any of the bitfields, because ghost fields are not empty and don't contain pieces. In this way you can never move a piece to a ghostfield as according to the empty bitfield the position is not empty.

Bert

[BertTuyt]

Gerard, got your point.
I optimize my program for play against computers (not humans), and therefore i always choose the best move (at least according to the eval of Damage).
If i was 100% sure that my program outsearches others , it makes sense to implement it.
But sofar i didn't experiment with this.

I think there are some articles in the Computer Chess world about this approach, if im right it is called "speculative play" and a google search with computer chess speculative play, will bring you further.
I know that it was at least reported in some of the volumes of Advances in Computer Chess, and in the ICCA/ICGA journal it was also mentioned.

Bert

[BertTuyt]

Here a question for the other Computer Draughts Programmers.
Next to the bitboards i use a structure (bitboards are basically included in this structure) with additional position information (like hashvalue, number op whiteman, blackman, whiteking, whiteking, breakthrough possible, number of possible moves for side to move, number op kills, .....).

I use a stack of these structures, so when i do a move i copy the new relevant values to a new stack entry. Advantage doing to a remove is a simple decrement of the pointer to the structure stack.

I don't think this will increase overhead, as i need to update these parameters anyway, which means getting them out of memory to the processer, updating the value, and writing them back.

Do you use a similar approach, or something completely different.

Bert

[Rein Halbersma]

Of course I intensively use AND, OR, XOR and SHIFT functions in order to generate quickly all the possible moves, and I also use ghost fields which help me to know that I move really inside the board !

Gérard

Gérard, what do you precisely mean with your ghost fields? Do you have the same bit layout as Bert (the one I gave earlier)?

Rein

[Rein Halbersma]

Rein, you are absolutely right, i do it in the way you described.
This way a move of a man is always +5/+6 for black and -5/-6 for white.

In the Bitfields i set a bit when a board position is empty, or occupied (and then i set the bit in the specific bitboard, like whiteman, whiteking, blackman, blackking).

For the ghost fields (like 10, 21 ,32) i don't set a bit in any of the bitfields, because ghost fields are not empty and don't contain pieces. In this way you can never move a piece to a ghostfield as according to the empty bitfield the position is not empty.

Bert

It's a clever trick of you, Bert. But you also have to AND with some extra bitmasks to detect moving of the edge of the board, right?

Rein

[BertTuyt]

Rein, as the ghost fields never have a bit set because the related empty bit-position is always zero, i don't need to do any additional things.
I don't have to detect the out of board positions, because i never can move a piece towards them !!!

Its really easy.
My numbering is not 100% the same as you proposed as the first position (which is 1), is not bit 0 in my case, but that basically does not change much. The offsets for moves (+/- 5 and +/- 6 ) are the same.

Bert

[TAILLE]

Of course I intensively use AND, OR, XOR and SHIFT functions in order to generate quickly all the possible moves, and I also use ghost fields which help me to know that I move really inside the board !

Gérard

Gérard, what do you precisely mean with your ghost fields? Do you have the same bit layout as Bert (the one I gave earlier)?

Rein

Yes Rein, obviously I used the same approach as Bert.
The point is the following : in the format representation any white (alternatively black) man (for example a white man on 34) can move forward on a square on the right (30 in this example) and on a square on the left (29 in this example)
Taking now a white man on 36 it can move on a square on the right (31 in this case) and an a square on the left (a ghost square). No harm with that because a ghost square is neither empty nor occupied by a regular piece !
With this approach all manipulations are far easier
Gérard

[TAILLE]

Here a question for the other Computer Draughts Programmers.
Next to the bitboards i use a structure (bitboards are basically included in this structure) with additional position information (like hashvalue, number op whiteman, blackman, whiteking, whiteking, breakthrough possible, number of possible moves for side to move, number op kills, .....).

I use a stack of these structures, so when i do a move i copy the new relevant values to a new stack entry. Advantage doing to a remove is a simple decrement of the pointer to the structure stack.

I don't think this will increase overhead, as i need to update these parameters anyway, which means getting them out of memory to the processer, updating the value, and writing them back.

Do you use a similar approach, or something completely different.

Bert

Bert,
I use only a tree structure and the loacl variables of the recursive search function.
I do not really understand why do you need a special stack. What is your point ? Do you use a sibling approach when evaluate a position ?
Gérard

[steenslag]

Of course I intensively use AND, OR, XOR and SHIFT functions in order to generate quickly all the possible moves, and I also use ghost fields which help me to know that I move really inside the board !

Gérard

Gérard, what do you precisely mean with your ghost fields? Do you have the same bit layout as Bert (the one I gave earlier)?

Rein

Yes Rein, obviously I used the same approach as Bert.
The point is the following : in the format representation any white (alternatively black) man (for example a white man on 34) can move forward on a square on the right (30 in this example) and on a square on the left (29 in this example)
Taking now a white man on 36 it can move on a square on the right (31 in this case) and an a square on the left (a ghost square). No harm with that because a ghost square is neither empty nor occupied by a regular piece !
With this approach all manipulations are far easier
Gérard

I wasn't so smart, so I calculated (in a rather cumbersome way) all adjacent fields, once, on initialize. I even had a NorthNorthEastEast etc. property for every field, for capturing moves. Captures by a king were even more cumbersome.
I have a question about databases. I understand the need for compression, but would it not be possible to add one bit to every record: this bit should say if there is only one way to get the win (or draw). Long series of these unique winning (or drawing) moves are almost always interesting.
Another question: in chess endgames there is the notion of "reciprocal zugzwang". Essentially this means a position in which having the move is bad, for both opponents. (Opposition is the simplest form). These positions are crucial for chess endgame theory. I don't know if the same goes for checkers, but my guess is "yes". Are these positions easy to extract from your databases? You guys are sitting on multiple goldmines.

[Rein Halbersma]

After better reading the contributions of Bert and Gérard, ghost fields are even more clever than I thought. They have a dual purpose: have uniform shifts for left and right moving AND remove the need for edge detection.

The reason: they appear on *both* edges of the board like this:

Code: Select all

{
      00, 01, 02, 03, 04,
    05, 06, 07, 08, 09, [10]
[10]  11, 12, 13, 14, 15,
    16, 17, 18, 19, 20, [21]
[21]  22, 23, 24, 25, 26,
    27, 28, 29, 30, 31, [32]
[32]  33, 34, 35, 36, 37,
    38, 39, 40, 41, 42, [43]
[43]  44, 45, 46, 47, 48,
    49, 50, 51, 52, 53
}  

Just a question for historical reasons: who invented this, and when? Or did you invent this independently? And in which forum was this first discussed? I couldn't find anything with Google.

Rein

[FeikeBoomstra]

Bert, Gerard,

Do you mean: how do you store the progress of the game. I do that in the GUI, not in the engine. The engine is (more or less) memoryless (you don't need to know how you came on a position to calulate the best move).

The other part is tree generation. I first tried to build a real tree in memory, it was really fast, but I got a memory overflow around 8-10 half ply depth.

So I switched to a system where you re-calculate the tree for every pass in the alpha-beta search. It is the algorithm as invented by Aske van der Plaat:

http://home.tiscali.nl/askeplaat/mtdf.html

As you take beta = alpha + 1, it is a kind of binary search through the tree.
The hash-table is essential to prevent recalculation of legs evaluated in a previous run.

But Gerard, did I understand it well that you keep the tree in memory, so with real pointers to the first child and the first brother?

(Now I have to dismantle my computer to start packing, for in the afternoon I will travel to Amsterdam to participate tomorrow in the computer draught tournament.

Feike

[Ed Gilbert]

Bert, I was interested to read your comments about building a breakthrough table. I have a similar table in my 8x8 program, and I plan to port it to 10x10. Like yours, it detects breakthroughs from the 3 rows that are closest to the kingrow, and takes into consideration the placement of both attacking and defending men, and the side to move. I actually use two tables, one to detect breakthroughs from the two rows closest to the kingrow, and then a second table for the third closest row. My tables are smaller because they do not contain the number of moves needed to promote. Each position is represented by one bit in the table. The bit is true if the position contains a breakthrough. I weight the presence of a breakthrough from the two closer rows higher than one from the third row, but this is not as accurate as your method of using a byte for each position.

I do not use separate tables for black and white breakthroughs. I have only tables for black, and then to detect them for white I reverse the board before doing the lookup.

The tables are not compressed, other than the packing of 8 positions in each byte. I form an index from the relevant bitmaps of black and white rows, and use it directly to access the table.

While this has worked well, it has a disadvantage that it cannot detect if there is more than one breakthrough present. I have seen games where there are two breakthroughs on one side and a single one on the other, and Kingsrow misevaluates because it thinks that these values are equal. I may try to enhance it by using two bits per position in the tables and storing the count.

-- Ed

[TAILLE]

Gérard, what do you precisely mean with your ghost fields? Do you have the same bit layout as Bert (the one I gave earlier)?

Rein

Yes Rein, obviously I used the same approach as Bert.
The point is the following : in the format representation any white (alternatively black) man (for example a white man on 34) can move forward on a square on the right (30 in this example) and on a square on the left (29 in this example)
Taking now a white man on 36 it can move on a square on the right (31 in this case) and an a square on the left (a ghost square). No harm with that because a ghost square is neither empty nor occupied by a regular piece !
With this approach all manipulations are far easier
Gérard

I wasn't so smart, so I calculated (in a rather cumbersome way) all adjacent fields, once, on initialize. I even had a NorthNorthEastEast etc. property for every field, for capturing moves. Captures by a king were even more cumbersome.
I have a question about databases. I understand the need for compression, but would it not be possible to add one bit to every record: this bit should say if there is only one way to get the win (or draw). Long series of these unique winning (or drawing) moves are almost always interesting.
Another question: in chess endgames there is the notion of "reciprocal zugzwang". Essentially this means a position in which having the move is bad, for both opponents. (Opposition is the simplest form). These positions are crucial for chess endgame theory. I don't know if the same goes for checkers, but my guess is "yes". Are these positions easy to extract from your databases? You guys are sitting on multiple goldmines.

I do not see the need for keeping in the database the case where there is only one way to get the win because this is precisely the case where there is no difficulty to find the next move. In some difficult situations we need the distance to the next conversion but if there is only one winning move we do not need any extra information.

Depending on the type of final it could be not very easy to find zugswang positions but noting is impossible.

As an example I extract from Damy database this beautiful zugswang position :

White to play : draw
Black to play : white wins

Gérard