Endgame Database Logic Question

[64_bit_checkers_engine]

I have a question about computing Distance-To-Win databases for checkers (or Draughts) using an "Unmove Generator".

Just so everyone knows, I've already done it using a forward move generator. And a quick reminder, DTW is different than "Distance To Conversion", just so we all are "on the same page" to start.

My question centers on an elementary position, such as this one...



Black to move wins easily, as any human can spot 18-23 in an instant. A DTC database will prefer 25-30 (or 25-29) which "converts" instantly. This is because 18-23 "wins in 3 plies", and the "loss in 2 plies" has not been computed yet on the first non-jump pass over the database.

Code: Select all

The question is, what is the order in which things need to be resolved with an UNMOVE GENERATOR in order to solve Distance-To-Win databases?

Of course, all jumps are solved first. But, as this diagram shows, conversions for DTW cannot be solved right away. Why? The win length would be incorrect!

My thinking is that, perhaps all of the LOSSES where jumps are unavoidable must be solved before promotions. That way, the "loss in 2 plies" with the Black king on 23 would be known, so the position in the diagram could be "unmoved into" from that, and scored as a proper win in 3.

But such logic could potentially miss many positions with "instant wins" where the promotion leads to the end of the game even sooner.

This leads to the situation I am in now with the forward mover: I seem to have to visit EVERY position and see if the most recently computed win is the quickest win, if so, change the DTW for the position, and iterate over the other side to see what loss lengths are affected, etc.

The only thing I can think of is this:

Before scoring any position a win once completing the jump pass, on the very next pass over the database, only score wins where EVERY move for the other side to move has a known result. That way, the win length for 25-29 and 25-20 would be known, but since the win length for 18-23 isn't, the DTW would not be written yet.

This has many drawbacks also. Namely, 18-14 and 18-15 both move further away from the win, and these would also be unknown, so 18-23 would not be scored as a win in 3.

There must be some simple logic I am overlooking! I need to somehow deal with the jump DTW and the promotion DTW simultaneously, and this is frustrating me at the moment.

[TAILLE]

Hi,

I do not see your problem.
Of course you described very clearly why DTC if far quicker to calculate than DTW but in any case the database is quite easy to generate.
When generating a new DTW database you have to search first all wins in one ply, then 2 plies etc. and, at each pass, you have to generate all possible moves (catpure if needeed and otherwise promotions and man moves and king moves).
When generatind a new DTC it is far quicker (but not that easier) : you look first to conversion moves and, for the following passes, you take into account only king moves.

Gérard

[64_bit_checkers_engine]

I do not see your problem.

Hi Gérard.

The problem is, I must first do some forward move passes with "different logic" before I can switch to doing the "unmove" logic. But, as the example position shows, my "forward move logic" no longer applies.

In my forward move generator, I would "solve" 25-30 as the best move and report the parent position as a win in 21 plies. Then I do a pass over the reflection slice for the other side to move, and it would resolve the loss in 2 plies as being inescapable.

The next pass over, the move generator finds that 18-23 wins in 3 plies, so the position has its win length updated from 21 to 3. The cycle then repeats until no more wins/losses are found, and no more DTW values change.

This is very long for 2 reasons: 1) I have to look at EVERY position on every pass over the database 2) Even when WLD has been completed, sometimes DTW is still being improved.

When generating a new DTW database you have to search first all wins in one ply, then 2 plies etc. and, at each pass, you have to generate all possible moves (catpure if needeed and otherwise promotions and man moves and king moves).

Because DTW has the distance of the subdatabases added to it, this would mean making more passes than in necessary. Right now, except for the 2-piece database, I can always resolve DTW in fewer passes than the longest distance.

Here is some of my data (be warned, this next link could take a long time to load if you have a slow internet connection)

http://www.gothicchess.com/checkers_data.txt

So take this for example:

Code: Select all

***********************************************************************************
* 2-piece database, 1 white king 0 white checkers vs. 1 red king 0 red checkers   *
***********************************************************************************

TOTAL POSITIONS: 992
TOTAL BYTES:     992


TOTAL WINS   (white to move)........... 230
TOTAL DRAWS  (white to move)........... 654
TOTAL LOSSES (white to move)........... 108

Wins resolved as jumps................. 72
Draws resolved as jumps................ 0
Losses resolved as jumps............... 0

Wins resolved from moving.............. 158
Draws resolved from moving............. 0
Losses resolved from moving............ 108

Wins with NO JUMPS for EITHER SIDE..... 140
Draws with NO JUMPS for EITHER SIDE.... 650
Losses with NO JUMPS for EITHER SIDE... 108

Draws resolved from unknowns........... 654

Cumulative win length improvements..... 0
Cumulative loss length changes......... 0


Database resolved after 11 iterations (includes the JUMP pass).
The longest win requires 11 ply to complete.

There are 34 wins of the same length in this database slice.
One of the longest white to move and win positions: (white pieces start at top of board)

***************************************************************************************************************
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
***************************************************************************************************************
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*### 32 ###*          *### 31 ###*          *### 30 ###*          *### 29 ###*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
***************************************************************************************************************
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *### 28 ###*          *### 27 ###*          *### 26 ###*          *### 25 ###*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
***************************************************************************************************************
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*### 24 ###*          *### 23 ###*          *### 22 ###*          *### 21 ###*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
***************************************************************************************************************
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *### 20 ###*          *### 19 ###*          *### 18 ###*          *### 17 ###*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
***************************************************************************************************************
*----------*##########*          *##########*          *##########*          *##########* -------- *----------*
*----------*##########*          *##########*          *##########*          *##########* |RRRRRR| *----------*
*----------*### 16 ###*          *### 15 ###*          *### 14 ###*          *### 13 ###* -------- *----------*
*----------*##########*          *##########*          *##########*          *##########* |RRRRRR| *----------*
*----------*##########*          *##########*          *##########*          *##########* -------- *----------*
***************************************************************************************************************
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *### 12 ###*          *### 11 ###*          *### 10 ###*          *### 09 ###*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
***************************************************************************************************************
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*### 08 ###*          *### 07 ###*          *### 06 ###*          *### 05 ###*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
***************************************************************************************************************
*----------*          *##########*          *##########*          *##########* -------- *##########*----------*
*----------*          *##########*          *##########*          *##########* |WWWWWW| *##########*----------*
*----------*          *### 04 ###*          *### 03 ###*          *### 02 ###* -------- *### 01 ###*----------*
*----------*          *##########*          *##########*          *##########* |WWWWWW| *##########*----------*
*----------*          *##########*          *##########*          *##########* -------- *##########*----------*
***************************************************************************************************************
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*

The 1 King vs. 1 King database takes 11 passes, and the longest win is 11 plies. Easy enough to understand, and it makes sense.

Now let's look at 2 kings vs. 1 king

Code: Select all

***********************************************************************************
* 3-piece database, 2 white kings 0 white checkers vs. 1 red king 0 red checkers  *
***********************************************************************************

TOTAL POSITIONS: 14880
TOTAL BYTES:     14880


TOTAL WINS   (white to move)........... 14846
TOTAL DRAWS  (white to move)........... 34
TOTAL LOSSES (white to move)........... 0

Wins resolved as jumps................. 2016
Draws resolved as jumps................ 0
Losses resolved as jumps............... 0

Wins resolved from moving.............. 12830
Draws resolved from moving............. 26
Losses resolved from moving............ 0

Wins with NO JUMPS for EITHER SIDE..... 12190
Draws with NO JUMPS for EITHER SIDE.... 10
Losses with NO JUMPS for EITHER SIDE... 0

Draws resolved from unknowns........... 8

Cumulative win length improvements..... 454
Cumulative loss length changes......... 0


Database resolved after 21 iterations (includes the JUMP pass).
The longest win requires 33 ply to complete.

There are 220 wins of the same length in this database slice.
One of the longest white to move and win positions: (white pieces start at top of board)

***************************************************************************************************************
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
***************************************************************************************************************
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*### 32 ###*          *### 31 ###*          *### 30 ###*          *### 29 ###*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
***************************************************************************************************************
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *### 28 ###*          *### 27 ###*          *### 26 ###*          *### 25 ###*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
***************************************************************************************************************
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*### 24 ###*          *### 23 ###*          *### 22 ###*          *### 21 ###*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
***************************************************************************************************************
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *### 20 ###*          *### 19 ###*          *### 18 ###*          *### 17 ###*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
***************************************************************************************************************
*----------*##########*          *##########*          *##########* -------- *##########*          *----------*
*----------*##########*          *##########*          *##########* |RRRRRR| *##########*          *----------*
*----------*### 16 ###*          *### 15 ###*          *### 14 ###* -------- *### 13 ###*          *----------*
*----------*##########*          *##########*          *##########* |RRRRRR| *##########*          *----------*
*----------*##########*          *##########*          *##########* -------- *##########*          *----------*
***************************************************************************************************************
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *### 12 ###*          *### 11 ###*          *### 10 ###*          *### 09 ###*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
*----------*          *##########*          *##########*          *##########*          *##########*----------*
***************************************************************************************************************
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*### 08 ###*          *### 07 ###*          *### 06 ###*          *### 05 ###*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
*----------*##########*          *##########*          *##########*          *##########*          *----------*
***************************************************************************************************************
*----------*          *##########*          *##########* -------- *##########* -------- *##########*----------*
*----------*          *##########*          *##########* |WWWWWW| *##########* |WWWWWW| *##########*----------*
*----------*          *### 04 ###*          *### 03 ###* -------- *### 02 ###* -------- *### 01 ###*----------*
*----------*          *##########*          *##########* |WWWWWW| *##########* |WWWWWW| *##########*----------*
*----------*          *##########*          *##########* -------- *##########* -------- *##########*----------*
***************************************************************************************************************
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------

The longest win is 33 plies, but only 21 iterations were needed. Why?

The iteration count matches the "longest conversion", and the longest win is the combination of the position that took the longest to convert + landed in the longest subdatabase position as well.

That means iterating and looking for wins in 1 ply, losses in 2 plies, wins in 3 plies, etc. would require more passes than the forward move generator.

This is not correct, I think.

The "unmover" should resolve the databases in fewer passes than the forward mover. The reason is, for each loss, you determine ALL POSSIBLE WINS in "ply + 1" on the same pass. The forward move generator cannot do this.

The problem is, what do you do in the INITIAL forward passes, so that when you switch to the UNMOVING, your DTW will always remain correct?

[TAILLE]

Hi,
Thank you for this explanation. Though I am not able to understand your examples because I do not know chekers rules, I believe I understand now your problem. It seems that that you look for some efficient algorithm to generate DTW databases in the same manner that we can generate DTC database.
As far as I am concerned I only generated DTC database and I do not see how I can help you to generate efficiently DTW databases.
Just a question : in 10x10 international draughts game it exists a rule called the "25 moves" rule. This rule says that a game is a draw if 25 moves are played without any conversion. As a consequence it may exist some positions where only the DTC database (not the DTW database!) may give the good moves in order to win or to draw. Does it existe similar rule in cherckers ?

Gérard

[64_bit_checkers_engine]

Hi,
Thank you for this explanation. Though I am not able to understand your examples because I do not know chekers rules, I believe I understand now your problem. It seems that that you look for some efficient algorithm to generate DTW databases in the same manner that we can generate DTC database.
As far as I am concerned I only generated DTC database and I do not see how I can help you to generate efficiently DTW databases.
Just a question : in 10x10 international draughts game it exists a rule called the "25 moves" rule. This rule says that a game is a draw if 25 moves are played without any conversion. As a consequence it may exist some positions where only the DTC database (not the DTW database!) may give the good moves in order to win or to draw. Does it existe similar rule in cherckers ?

Gérard

Hi Gérard,

There is a "40 move rule" in checkers, but it is vaguely stated, and highly subjective. A player must "show progress" in order for a draw claim to be denied.

Software in checkers exceeds the strength of every player and every possible referee, so, as the rule is worded, any program that announces "win in 253" would always be able to "show progress" as long as the move count decreases.

This will always be the case with my program.

[TAILLE]

Software in checkers exceeds the strength of every player

Does the checkers (or 10x10 international draugths) software strength exceed every player strength?
Is this question really resolved ?
I understand what you mean. In a match in e.g. 40 games, because the software cannot lose, it probably will win the match because the human will face difficulties to avoid a fatal mistake. Anyboby agrees on that.
But what about a tournament with a software, a top player and a lot of weaker players ? Assuming that the game between the software and the top player will result in a draw, the winner on the tournament will (as usual) depends on the ability to win against weaker players. A big part of the strength of a top players is in this ability; he manages to build difficult positions/tricks in order to provoque a mistake from the opponent. In some occasions the top player will lose a game (this is an important point as I explain below) due to the risks he took but he will win a lot of games and that is the really the point.
As far as I know a software as not such ability. In addition the opponent of a sofware know perfectly that he cannot win (see above that a top player may lose a game). As a consequence the opponent of a software will try, as far as possible, to keep a solid position and to simplify the game as far as possible.
Of course the software will win some games but will it win the tournament ?

Gérard

[wellnesswrotter]

The only way to test this is to host a tournament where computerprogram(s) are participants. But the Draughts world is a little reluctant.

[TAILLE]

The only way to test this is to host a tournament where computerprogram(s) are participants. But the Draughts world is a little reluctant.

Yes of course.
Did you make something in your program to try to complicate the game ?
I made something in Damy : as soon as the real position reaches a 7 pieces position (Damy has the 7 pieces endgame db) Damy calculate some tricks in order to try and win against a program which do not have this db. I do not know if it is efficient but, at least, I tried something.
Gérard

[Rein Halbersma]

The only way to test this is to host a tournament where computerprogram(s) are participants. But the Draughts world is a little reluctant.

Truus played in the 1997 Minsk open, an 8 round Swiss tournament, scoring 5+, 3=. There are not other results from that tournament in TurboDambase, so it's unclear what score she got, but it can't have been too far away from the top.

In 8x8 checkers, Chinook finished near or at the top of almost every human tournament it played in.

[Rein Halbersma]

The only way to test this is to host a tournament where computerprogram(s) are participants. But the Draughts world is a little reluctant.

Yes of course.
Did you make something in your program to try to complicate the game ?
I made something in Damy : as soon as the real position reaches a 7 pieces position (Damy has the 7 pieces endgame db) Damy calculate some tricks in order to try and win against a program which do not have this db. I do not know if it is efficient but, at least, I tried something.
Gérard

Gérard,

I like your approach very much but I think it could be applied much earlier in the game. E.g., many programs do not seem to care to offer the opponent a big exchange in the opening, often given the humans slightly inferior but much simplified positions. Do you also take into consideration the complexity (measured by e.g. the number of positions, number of free moves)? It would seem that it might be worth the risk for a computer program to bias the search towards complicated positions with many pieces and few moves rather than to simplified positions with few pieces and many moves.

Rein

[TAILLE]

Gérard,

I like your approach very much but I think it could be applied much earlier in the game. E.g., many programs do not seem to care to offer the opponent a big exchange in the opening, often given the humans slightly inferior but much simplified positions. Do you also take into consideration the complexity (measured by e.g. the number of positions, number of free moves)? It would seem that it might be worth the risk for a computer program to bias the search towards complicated positions with many pieces and few moves rather than to simplified positions with few pieces and many moves.

Rein

For the moment I did not find a good tuning for taking into account complexity. I tried to change the evaluation of a leaf position depending of who has to move (Damy of the opponent) but I did not conclude it was efficient (I took into account only the number of pieces on the board).

I do not think that the number of choices for a move is relevant, except perhaps if you can detect that your opponent will have very few possibilities during a lot of moves but it seems difficult to detect.

On the contrary I do not like to play a move which forces the answer because the opponent will not be incitated to do a weak move.

I have in mind the following algorithm but I never tried to program it :

Suppose that after a search at depth N your program hesitate between move A1 and move B1 which are then considered equivalent. Suppose that you calculated that the best answer to the move A1 is the move A2 and the best answer to move the B1 is the move B2.
If now you remember that at depth N-1 you considered that the best answer to move A1 was already A2, but the best answer to move B1 was B2' then it could be better to play the move B1 because it seems more difficult for the opponent (especially if it is a human opponent) to find the good answer.
It is only an idea but if I had to play against human I think I will explore seriously such new algorithm.

Gérard

[64_bit_checkers_engine]

Software in checkers exceeds the strength of every player

Does the checkers (or 10x10 international draugths) software strength exceed every player strength?
Is this question really resolved ?

Alex Moiseyev visited my house right before Christmas in 2004. For me, the timing was very unfortunate. I was still recovering from re-injuring my broken back, and I could not even stand up straight.

Alex and I played a few game of checkers, and he wanted to see my 7-piece "Perfect Play Database (distance to win) for 8x8 checkers. I had already saved a few of the longest wins possible.

The longest is 253 plies, and the win requires very precise play. Alex took the winning side. He gave away the draw at least 3 times during the play, after which time we took the move back, and he tried to play a better move.

Alex had the side with 4 pieces, so the first time he gave away the draw, it was not the least bit obvious. He wanted to play on in that position, and play continued for quite some time. Draw, Draw, Draw... the program announced move after move. Finally, a very distant form of what is known as "Fourth Position" appeared on the board, and Alex recognized this. He was amazed that the program "knew this" from such a distance, but, in reality, even a program with the win-loss-draw databases would have been able to play the line the same way once we entered the position.

Chinook was the strongest checkers program that played in tournaments in the USA. But even it had mistakes in its 8-piece databases. My friend Gil and I found out the errors, and Dr. Schaeffer even mentions this in his new book:



Programs today have the benefit of better hardware, computer-generated opening books that are flawless, and larger and "proven correct" endgame databases.

Players today are not as strong as Marion Tinsley was.

Therefore, with certainty, checker programs are stronger than the top players.

The program I am building will probe the "perfect play" endgame databases in RAM. That way, it will be able to announce the distance to win with even 16- or 14-pieces on the board. There will be no way for humans to deal with such strength.

[TAILLE]

The program I am building will probe the "perfect play" endgame databases in RAM. That way, it will be able to announce the distance to win with even 16- or 14-pieces on the board. There will be no way for humans to deal with such strength.

I believe I perfectly understand what you say but it seems that you miss my point.
Let's take a position with only 10 pieces and I assume that you have build the DTW corresponding database.
No doubt at all that your software is far better than a human for dealing with a winning position, but what about dealing with a draw (or losing) position ?
How will your program choose between several draw moves ? A top human player is often very strong in finding a move suite which can lead to very difficult tricks and some chances for the opponent to make a mistake.

Damy having the 7 pieces endgame database I programmed an algorithm based on the following idea. Suppose we reach a 7 pieces endgame position and it is Damy to play in a draw (result of the db) position.
1) Damy lists all correct (draw) moves : A1,B1,C1...
2) Damy inhibits the 7 pieces endgame database and search the corresponding answers using only the 6 pieces endgame database : A2,B2,C2 ...
3) If one of the A2,B2,C2... move is a losing move (according to the 7 pieces endgame database) then Damy will choose the corresponding move hoping to have found a good trick.
Damy goes a little farther but you have the basic idea.

Did you program something similar ?

Gérard

[ildjarn]

Truus played in the 1997 Minsk open, an 8 round Swiss tournament, scoring 5+, 3=. There are not other results from that tournament in TurboDambase, so it's unclear what score she got, but it can't have been too far away from the top.

Truus also played in Geleen open somewhere halfway the '90s. I think she scored +2 or +3, I managed to get a draw (well, a draw offer in a difficult endgame, because Stef didn't see Truus make any progress after approx. 15 moves with an unchanged evaluation, perhaps with larger endgame databases it would've been a win for Truus).

In the same tournament, Cerberus was a participant, but it ended in the back of the list. I managed to lose against it though, after crushing it totally positionally and winning a piece, my concentration dropped and I allowed a trivial 3x3 to king.

[64_bit_checkers_engine]

I believe I perfectly understand what you say but it seems that you miss my point.
Let's take a position with only 10 pieces and I assume that you have build the DTW corresponding database.
No doubt at all that your software is far better than a human for dealing with a winning position, but what about dealing with a draw (or losing) position ?
How will your program choose between several draw moves ? A top human player is often very strong in finding a move suite which can lead to very difficult tricks and some chances for the opponent to make a mistake.

Damy having the 7 pieces endgame database I programmed an algorithm based on the following idea. Suppose we reach a 7 pieces endgame position and it is Damy to play in a draw (result of the db) position.
1) Damy lists all correct (draw) moves : A1,B1,C1...
2) Damy inhibits the 7 pieces endgame database and search the corresponding answers using only the 6 pieces endgame database : A2,B2,C2 ...
3) If one of the A2,B2,C2... move is a losing move (according to the 7 pieces endgame database) then Damy will choose the corresponding move hoping to have found a good trick.
Damy goes a little farther but you have the basic idea.

Did you program something similar ?

Gérard

Hello Gérard,

I have what I call the Aggressive Draw Heuristic. I have done something that I think nobody else has done.

For every position that is a draw, I have precomputed the drawing difficulty for the position, and I have a special database of scores for all of these positions.

The score is basically:

Code: Select all

if((# of moves that can lose) > (# of moves that preserve the draw))
{
   (10 *(# of moves that can lose))/(# of moves that preserve the draw) + (# of moves that can lose)
}
else
{
   (-10 *(# of moves that preserve the draw))/(1+abs(# of moves that can lose) - (# of moves that preserve the draw))
}

For any position that is a draw, there is a guarantee of at least 1 move to draw, 0 moves that win, and 0 or more moves that can lose.

My program never scores the position for its own turn to move, only the opponent. So the move generator probes the special database in RAM, and evaluates "how hard" a draw it can force the opponent into.

Some positions have all moves that lead to a draw. Say the opponent has 4 moves, and all 4 draw. My program would return a score of

(-10 * 4)/(4-4+1) = -40

For 5 moves that all lead to a draw

(-10 * 5)/(5-5+1) = -50

I use 1 checker = 1000, so this score is small, -5% of a piece, but you can see the program avoids giving players an easy draw.

Suppose 4 out of 7 moves lead to a draw?

(-10 * 4)/(abs(3-4) + 1) = -20

And if 3 out of 7 lead to a draw, this will be a positive score

(10 * 4)/(3) + (4) = 40/3 + 4 = 17.333~

If 3 out of 8 lead to a draw

(10 * 5)/(3) + (5) = 50/3 + 5 = 21.666~

If 6 out of 16 lead to a draw, you will see the "tiebrake" prefers this to the 3 out of 8

(10 * 10)/(6) + (6) = 22.666~

But the program will eventually search and find a series of moves where the person might have only 1 legal move to draw each time. Suppose only 1 out of 7 leads to a draw

(10 * 6)/(1) + (6) = 66

You can see that a database of these precomputed values can very useful. Since you don't have to query the database to get the counts of loosing and drawing moves, the scores are retrieved very quickly.