Endgame Database Logic Question

TAILLE · Post by **TAILLE** » Wed Apr 29, 2009 00:33

Hi,

64_bit_checkers_engine wrote:Hello Gérard,
I have what I call the Aggressive Draw Heuristic. I have done something that I think nobody else has done.

I tried in the past a very similar approach but I finally thrown away all that work. Of course Damy was particularly efficient to find a move for which it exists only one correct answer but, most of the time, this answer was very easy to discover. So I concluded that the move chosen was not a valuable trick. For example Damy liked to attack a piece because it is a case where the number of good moves is very low but ... this case corresponds also to the case where it is very often easy to discover the right answer!

This discussion seems very interesting and I will be happy to have other feelings. For me the most interesting positions are really the theoritically draw positions. Assuming that the initial position is a draw position it is obvious that, in order to win, the opponent has to do a mistake.
So, before trying to solve the problem of winning a winning position, we have first to provoque this necessary mistake! A program able to win any winning position is certainly a very strong program but, in order to be even stronger, this program has to have the ability to provoque the mistake needed to win the game.
We reach now a very interesting question : what kind of mistakes do we intend to provoque ?
The answer depends on the opponent. If the opponent is a weak tactical player then a trick based on hidden combinations will be fine. If the opponent is a strong tactical player (like another program) then a trick has to be based on a strategical base. As a consequence you must avoid to choose a move that lead to only one answer due to tactical reason (no trick). The best move may be a move that allows typically 2 or 3 moves which are difficult to analyse for a strategic point of view. That way you may be able to see your opponent chose a weak answer.
I am working hard on the subject and I hope to have a very different version of Damy before the end of the year.
Gérard

64_bit_checkers_engine · Wed Apr 29, 2009 05:57

TAILLE wrote:This discussion seems very interesting and I will be happy to have other feelings. For me the most interesting positions are really the theoritically draw positions. Assuming that the initial position is a draw position it is obvious that, in order to win, the opponent has to do a mistake.

...

We reach now a very interesting question : what kind of mistakes do we intend to provoque ?

The answer depends on the opponent. If the opponent is a weak tactical player then a trick based on hidden combinations will be fine. If the opponent is a strong tactical player (like another program) then a trick has to be based on a strategical base.

Well, it is always easiest to "feed" the program what it can do the best, namely, computation.

What you have described is more the way a human with knowledge of his human opponent would play. It is a very good approach, but computers are better at finding things humans cannot find.

Statistically, the "hardest drawn position" would be a position where there is only 1 move to draw for many, many moves to make in a row.

Consider such a position where 1 move out of 5 draws, and you have to make say 6 of these such moves in a row. The human's chance of getting the draw is 1:(5x5x5x5x5x5) = 1 in 390,625!

To find such a position, no matter what, would be desired. Maybe it has a mix of strategy (to get into it) and tactics (to avoid shots) so there might not be a way to "program" for it.

Let the search find it!

Encourage such a score with a bonus. My technique works for this, and the program would find it every time, with no need to "test" the programming instructions in the evaluation to make sure they work.

Even better, some clever use of the History Heuristic might be able to find the positions where there is only 1 move to make for many in a row.

P.S. In positions where there are jumps, I do not apply the Aggressive Draw routine. I only apply it when the other side is to move, and there are no jumps. That way, a great score does not get truncated by the Alpha_Beta() routine when it finds 1 move that draws with only 1 legal move (the jump).

Rein Halbersma · Post by **Rein Halbersma** » Wed Apr 29, 2009 09:39

ildjarn wrote:
Rein Halbersma wrote: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.

Hi Joost,

Your memory is partially correct: according to TurboDambase, you played against Cerberus in the 1993 Geleen tournament, and against Truus in the 1996 Geleen tournament. Your accounts of the games were spot on, though. Cerberus was indeed in a lost position, and the endgame against Truus didn't show progress: however, the final position was a database draw!

Truus indeed scored a 2+,5= in 1996, and Cerberus surprisingly also scored not too bad in 1993: 3+,1=,4- although she was lucky to win against you and another opponent resigned in a drawn position thinking he was going to lose a piece.

Here are the final results, auto-generated from a few scripts that can read TurboDambase exported to pdn (the scripts also auto-detect whether a list of games is a match, a multi- or single round robin or a swiss tournament)

Note in particular the 3rd position that Truus obtained in 1996, only behind grandmasters Presman and Rybakov, but still before former Dutch champion Heusdens (drawing all encounters with these 3 top players)!

Rein

Code: Select all

Geleen 1993 
-----------
                H  N  P  K  S  D  V  S  D  M  M  V  I  A  H  B  K  G  C  R  L  H  R  V  J  V G + = -  P WP  SB
Heusdens,R.    NA NA  1 NA NA  2  1  2  1 NA NA  2 NA  2  1 NA NA NA NA NA NA NA NA NA NA NA 8 4 4 0 12 74 110
Nartsjoek,G.   NA NA  2  1  1  1  2  1  1 NA NA NA  2 NA NA NA NA NA NA NA NA NA NA NA NA NA 8 3 5 0 11 79 108
Presman,A.      1  0 NA  1  1 NA  2 NA  2 NA NA NA NA NA NA NA NA  2 NA NA NA  2 NA NA NA NA 8 4 3 1 11 76  97
Koning,de,F.   NA  1  1 NA  1  1 NA NA  2 NA NA  1  2 NA NA NA NA NA NA NA NA NA NA NA  2 NA 8 3 5 0 11 71  92
Sjatsov,P.     NA  1  1  1 NA  1  1  1 NA  2 NA NA NA NA NA NA NA NA  2 NA NA NA NA NA NA NA 8 2 6 0 10 79  95
Delmotte,T.     0  1 NA  1  1 NA NA  2 NA NA  2 NA NA NA NA  1 NA NA NA NA NA NA NA  2 NA NA 8 3 4 1 10 74  85
Verdel,O.       1  0  0 NA  1 NA NA NA NA NA  2 NA NA  2 NA NA NA  2 NA NA  2 NA NA NA NA NA 8 4 2 2 10 74  82
Schellekens,P.  0  1 NA NA  1  0 NA NA NA NA NA  2 NA NA NA NA  2 NA NA NA  2  2 NA NA NA NA 8 4 2 2 10 70  75
Dios 93         1  1  0  0 NA NA NA NA NA  2 NA NA NA  1 NA NA  2 NA  2 NA NA NA NA NA NA NA 8 3 3 2  9 76  77
Marini,F.      NA NA NA NA  0 NA NA NA  0 NA NA  1  1  1  2 NA NA  2 NA NA  2 NA NA NA NA NA 8 3 3 2  9 64  66
Meesters,J.    NA NA NA NA NA  0  0 NA NA NA NA  1 NA  1 NA  2 NA NA NA  2  1 NA  2 NA NA NA 8 3 3 2  9 61  60
Voroesjilo,V.   0 NA NA  1 NA NA NA  0 NA  1  1 NA  1 NA NA NA NA NA NA  2 NA  2 NA NA NA NA 8 2 4 2  8 72  63
Iljin,P.       NA  0 NA  0 NA NA NA NA NA  1 NA  1 NA  1 NA  2  1 NA  2 NA NA NA NA NA NA NA 8 2 4 2  8 68  60
Alsvang,A.      0 NA NA NA NA NA  0 NA  1  1  1 NA  1 NA NA NA NA NA NA  2 NA NA NA NA NA  2 8 2 4 2  8 68  57
Heer,de,J.      1 NA NA NA NA NA NA NA NA  0 NA NA NA NA NA NA  1 NA  0 NA  1  2  1  2 NA NA 8 2 4 2  8 56  50
Bosch,H.       NA NA NA NA NA  1 NA NA NA NA  0 NA  0 NA NA NA  1  1  2  0 NA NA  2 NA NA NA 8 2 3 3  7 60  48
Koullen,B.     NA NA NA NA NA NA NA  0  0 NA NA NA  1 NA  1  1 NA  1 NA NA NA  2 NA  1 NA NA 8 1 5 2  7 59  46
Gortel,van,D.  NA NA  0 NA NA NA  0 NA NA  0 NA NA NA NA NA  1  1 NA NA NA  2 NA NA  2 NA  1 8 2 3 3  7 58  38
Cerberus       NA NA NA NA  0 NA NA NA  0 NA NA NA  0 NA  2  0 NA NA NA  1 NA NA NA NA  2  2 8 3 1 4  7 57  39
Rossum,van,P.  NA NA NA NA NA NA NA NA NA NA  0  0 NA  0 NA  2 NA NA  1 NA NA NA  1  2  1 NA 8 2 3 3  7 52  38
Lenselink,S.   NA NA NA NA NA NA  0  0 NA  0  1 NA NA NA  1 NA NA  0 NA NA NA NA NA NA  2  2 8 2 2 4  6 61  33
Hubner,G.      NA NA  0 NA NA NA NA  0 NA NA NA  0 NA NA  0 NA  0 NA NA NA NA NA  2 NA  2  2 8 3 0 5  6 57  26
Rutten,G.      NA NA NA NA NA NA NA NA NA NA  0 NA NA NA  1  0 NA NA NA  1 NA  0 NA  1  1  1 8 0 5 3  5 49  27
Velzen,van,R.  NA NA NA NA NA  0 NA NA NA NA NA NA NA NA  0 NA  1  0 NA  0 NA NA  1 NA  1  1 8 0 4 4  4 52  20
Jannenga,M.    NA NA NA  0 NA NA NA NA NA NA NA NA NA NA NA NA NA NA  0  1  0  0  1  1 NA  1 8 0 4 4  4 50  20
Verjans,N.     NA NA NA NA NA NA NA NA NA NA NA NA NA  0 NA NA NA  1  0 NA  0  0  1  1  1 NA 8 0 4 4  4 47  20

Code: Select all

Geleen 1996 
-----------
                P  R  T  N  H  V  S  S  H  B  V  M  K  L  H  B  M  D  J  G G + = -  P WP SB
Presman,A.     NA  1  1  2 NA  2 NA NA NA  1  2 NA NA NA NA NA  2 NA NA NA 7 4 3 0 11 54 82
Rybakov,Igor    1 NA  1  1 NA  1 NA  2 NA NA  2 NA  2 NA NA NA NA NA NA NA 7 3 4 0 10 58 80
Truus           1  1 NA NA  1 NA  2 NA  1 NA  1 NA NA NA NA NA NA  2 NA NA 7 2 5 0  9 56 68 
Nitsch,P.       0  1 NA NA NA NA NA  1 NA  1  1 NA NA  2 NA NA  2 NA NA NA 7 2 4 1  8 55 56
Heusdens,R.    NA NA  1 NA NA  1  1  2 NA NA  1 NA  1 NA  1 NA NA NA NA NA 7 1 6 0  8 53 61
Verdel,O.       0  1 NA NA  1 NA NA NA NA  1 NA  1 NA NA  2 NA NA NA NA  2 7 2 4 1  8 51 48
Schellekens,P. NA NA  0 NA  1 NA NA NA NA  2 NA  1 NA  2  1  1 NA NA NA NA 7 2 4 1  8 50 55
Sjatsov,P.     NA  0 NA  1  0 NA NA NA NA  1 NA  2 NA NA NA  2 NA  2 NA NA 7 3 2 2  8 50 49
Heer,de,J.     NA NA  1 NA NA NA NA NA NA  1 NA  1  1  1  1 NA NA NA NA  2 7 1 6 0  8 45 47
Bremmer,W.      1 NA NA  1 NA  1  0  1  1 NA NA NA NA NA NA  2 NA NA NA NA 7 1 5 1  7 57 55
Voroesjilo,V.   0  0  1  1  1 NA NA NA NA NA NA NA NA NA NA NA  2 NA  2 NA 7 2 3 2  7 55 43
Michiels,S.    NA NA NA NA NA  1  1  0  1 NA NA NA NA  1  1 NA  2 NA NA NA 7 1 5 1  7 50 47
Kos,Jeroen     NA  0 NA NA  1 NA NA NA  1 NA NA NA NA  1 NA  1 NA  1  2 NA 7 1 5 1  7 47 41
Lewkowicz,J.   NA NA NA  0 NA NA  0 NA  1 NA NA  1  1 NA NA  2 NA NA NA  2 7 2 3 2  7 46 38
Heer,de,M.     NA NA NA NA  1  0  1 NA  1 NA NA  1 NA NA NA NA NA  2  0 NA 7 1 4 2  6 47 39
Bergets,D.     NA NA NA NA NA NA  1  0 NA  0 NA NA  1  0 NA NA NA NA  2  2 7 2 2 3  6 43 27
Mankowski,T.    0 NA NA  0 NA NA NA NA NA NA  0  0 NA NA NA NA NA  2  2  1 7 2 1 4  5 43 18
Dieters,M.     NA NA  0 NA NA NA NA  0 NA NA NA NA  1 NA  0 NA  0 NA  1  2 7 1 2 4  4 41 15
Jannenga,M.    NA NA NA NA NA NA NA NA NA NA  0 NA  0 NA  2  0  0  1 NA  1 7 1 2 4  4 37 18
Gortel,van,D.  NA NA NA NA NA  0 NA NA  0 NA NA NA NA  0 NA  0  1  0  1 NA 7 0 2 5  2 42  9

TAILLE · Post by **TAILLE** » Wed Apr 29, 2009 12:54

64_bit_checkers_engine wrote:Well, it is always easiest to "feed" the program what it can do the best, namely, computation.

What you have described is more the way a human with knowledge of his human opponent would play. It is a very good approach, but computers are better at finding things humans cannot find.

Don't you think that it is better to imitate human manner of playing ?

My feeling is that you cannot really hope to win against a computer due to a tactical mistake. Of course you have to keep a lot of CPU time to search tactical combinations but I think you can afford to spend CPU time to look for strategical tricks.

Let'us take the following example : in a given position your program calculated that the 3 moves A1,B1,C1 seem quite equivalent, giving your program a small advantage of +0,100. How to choose between them ?
Let's suppose that the three best answers to A1,B1 and C1 are :
for A1 :
A2 : +0,100
A2' : +0,200
A2" : +0,200
for B1 :
B2 : +0,100
B2' : +0,200
B2" : +1,000
for C1 :
C2 : +0,100
C2' : +1,000
C2" : +1,000
My analyse is the following : the answers B2", C2' and C2" are probably tactical mistakes so I assume that my opponent will detect easily that these moves are incorrect.
As a consequence it seems to me that the best move is A1 (2/3 of chance for a strategic mistake) then B1 (1/2 of chance for a strategic mistake) and finally C1 (no chance at all for a strategic mistake).

Of course I agree with you when say that you have to try to let your opponent with only one good move. That were the case for the 3 moves A1,B1 and C1 above but I want to go farther, avoiding to take into account tactical mistakes witch are not really relevant against another computer.

As you see this approach need a lot of computation; that means that you have to find a good compromise for using the CPU time, but that means also that a computer may be more efficient than a human to do such strategic trick.

Gérard

Rein Halbersma · Post by **Rein Halbersma** » Wed Apr 29, 2009 13:12

TAILLE wrote:
Don't you think that it is better to imitate human manner of playing ?

My feeling is that you cannot really hope to win against a computer due to a tactical mistake. Of course you have to keep a lot of CPU time to search tactical combinations but I think you can afford to spend CPU time to look for strategical tricks.

As you see this approach need a lot of computation; that means that you have to find a good compromise for using the CPU time, but that means also that a computer may be more efficient than a human to do such strategic trick.

Gérard

I agree completely with your philosophy. It is a very fruitful approach against opponents who are playing for a win as well.

However, do you believe that it is possible to achieve anything against a grand master who is only interested in a draw? E.g., with my limited tactical skills I will usually be slaughtered against Kingsrow or Truus when I play blitz games. However, when I play on purpose to exchange as much as possible and to avoid complicated "bindings" of the position (so I keep things open en simple) then I often can get quite easily a draw (unless I still make a silly tactical mistake). But against such play it is very hard to make strategic progress.

It might simply be a problem of the game itself. At least grand masters have claimed in the past to be able to guarantee a draw through such "anti-play". When I have my program finished, almost certainly I will program it to play in defense mode against Damy/Kingsrow or other programs that I think are superior, to maximize my drawing chances and only try to play to win against all other opposition. This is how humans play tournaments: make a list of who can/should be beaten and conserve energy and minimize risk against others.

What do you think of such issues?

REin

TAILLE · Post by **TAILLE** » Wed Apr 29, 2009 14:50

Rein Halbersma wrote: However, do you believe that it is possible to achieve anything against a grand master who is only interested in a draw? E.g., with my limited tactical skills I will usually be slaughtered against Kingsrow or Truus when I play blitz games. However, when I play on purpose to exchange as much as possible and to avoid complicated "bindings" of the position (so I keep things open en simple) then I often can get quite easily a draw (unless I still make a silly tactical mistake). But against such play it is very hard to make strategic progress.

It might simply be a problem of the game itself. At least grand masters have claimed in the past to be able to guarantee a draw through such "anti-play". When I have my program finished, almost certainly I will program it to play in defense mode against Damy/Kingsrow or other programs that I think are superior, to maximize my drawing chances and only try to play to win against all other opposition. This is how humans play tournaments: make a list of who can/should be beaten and conserve energy and minimize risk against others.

What do you think of such issues?

REin

I cannot avoid to agree with you; It is far more difficult to win against an opponent that is playing only for draw. That's life but as a compensation your opponent recognises by this attitude that its program is not as good as yours.
That is not a reason for not try to do something. If you know that the opponent is a weaker opponent (human or program) may be you can try to have a different evaluation depending of which has to move.
One idea could be the following : instead of building a "normal" or "objective" evaluation you build instead on evaluation taking into account "the chance for a win". Assuming your program is stronger that your opponent let's suppose that the probality to win the game against this opponent if for example 20%. In that case it is logical to add for example 0,150 to your "normal" evaluation in order to keep this estimated difference in strength into account.
Then, at the very beginning of the game your program estimates its advantage to 0,150. Now when the number of pieces on the board decreases then your probablity to win decreases as well and you may decide for example to add only 0,140 after 1 exchange etc.
Note : with this approach your program may well accept an "objective" disadvantage of e.g. 0,040 in order to avoid a vaste exchange. It is not really a problem because your program is stronger than the opponent so you are confident to find a draw even in such situation.
I do not know it is really efficient and I cannot estimate possible collateral damages in the play. At least it is an idea for future tests.

Gérard

64_bit_checkers_engine · Wed Apr 29, 2009 18:45

There are many good points being discussed here. As for programming a computer to play more like a human, in terms of knowledge, this was a goal of the 1970's chess program PARADISE which used a very different approach to the game.

It "created plans" and not only searched. Plans were determined by identifying which squares were attacked/defended, how often, and by what types of pieces, etc.

In the end, search has always defeated knowledge. Even Hans Berliner, author of HiTech, was surprised when he built "LoTech", a HiTech clone with a "dumber" evaluation, and LoTech was winning a majority of the games against his smarter, slower rival.

But, now for a digression.

Originally I started this topic to discuss Distance-To-Win endgames, and the chance of hooking up an "UNMOVE GENERATOR" to solve the endgames faster.

Do any of the programmers here have any more insight into this?

I am still "battling the logic", and it seems no matter what I try, the computation time would take longer than what I already have in place.

It is very frustration to be "so close, yet so far away"!

Ed Gilbert · Post by **Ed Gilbert** » Wed Apr 29, 2009 20:55

64_bit_checkers_engine wrote:Originally I started this topic to discuss Distance-To-Win endgames, and the chance of hooking up an "UNMOVE GENERATOR" to solve the endgames faster.

Do any of the programmers here have any more insight into this?

It is strictly a matter of efficiency, not correctness, as either forward or reverse move non-conversion passes will solve both DTW and WLD. As to whether reverse passes are more efficient, I can say definitely yes for WLD, and I don't know for DTW. Unless someone has already tried it, probably nobody knows. It will only take a short time to try it out, and if I was going to be building DTW databases for many months I would want to test this to see if it saves time.

-- Ed

TAILLE · Post by **TAILLE** » Wed Apr 29, 2009 21:57

Hi,

64_bit_checkers_engine wrote: Originally I started this topic to discuss Distance-To-Win endgames, and the chance of hooking up an "UNMOVE GENERATOR" to solve the endgames faster.

Why do you want to generate the DTW db instead of simply the DTC db?
Do you konw that in very very exceptionnal occasions the DTW give a wrong result when facing a program which has the DTC db ?

Gérard

64_bit_checkers_engine · Thu Apr 30, 2009 06:01

TAILLE wrote:Why do you want to generate the DTW db instead of simply the DTC db?
Do you konw that in very very exceptionnal occasions the DTW give a wrong result when facing a program which has the DTC db ?

That is not correct.

A DTW database knows how many moves until the last move is made on the board.

A DTC database only knows how many moves until the next conversion is made.

A great example of the differences can be seen by Kingsrow's longest conversion distance with 4 kings against 4 kings, and my longest win for 4 kings against 4 kings (in 8x8 checkers.)

Ed's longest conversion takes quite a while for a jump to occur, yet one of the longest wins, 115 plies, is an immediate jump!

Code: Select all

***********************************************************************************
* 8-piece database, 4 white kings 0 white checkers vs. 4 red kings 0 red checkers *
***********************************************************************************

TOTAL POSITIONS: 736281000
TOTAL BYTES:     0 (buffered)


TOTAL WINS   (white to move)........... 355736293
TOTAL DRAWS  (white to move)........... 346875072
TOTAL LOSSES (white to move)........... 33669635

Wins resolved as jumps................. 339573858
Draws resolved as jumps................ 100684741
Losses resolved as jumps............... 18221225

Wins resolved from moving.............. 16162435
Draws resolved from moving............. 11076297
Losses resolved from moving............ 15448410

Wins with NO JUMPS for EITHER SIDE..... 7705209
Draws with NO JUMPS for EITHER SIDE.... 153104694
Losses with NO JUMPS for EITHER SIDE... 197297

Draws resolved from unknowns........... 235114034

Cumulative win length improvements..... 345098
Cumulative loss length changes......... 95483


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

There are 40 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)

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

Where there are NO JUMPS for either side, the longest win requires 115 ply to complete.

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

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

How can there be such a disparity?

The longest win with 4 Kings vs. 4 Kings is actually also the quickest conversion! Why? My resulting 7-piece ending is much longer than the Ed Gilbert conversion with 4 kings vs. 4 kings plus all of his successor positions.

It might be trivial to find the "solution" for the 1st move in my longest win, but it is still the longest win, from move #1 until the last move.

Which is "harder"? Probably the Ed Gilbert position. But is is also shorter.

TAILLE · Post by **TAILLE** » Thu Apr 30, 2009 10:20

Hi,

64_bit_checkers_engine wrote: A DTW database knows how many moves until the last move is made on the board.

A DTC database only knows how many moves until the next conversion is made.

Obviously you miss my point. Remenber my "vicious" question about the "25 moves" rule. How Damy is working with this rule ?
First of all, as any other programmer interested in db, I generated my endgame db without taking into account this rule. I am not sure it is the best solution but it is another subject.
Now how does my engine work when dealing with a position in the db ?
1) I look up in the WLD db
2) Supposing it is "win" position I look up in the DTC db
3) Taking now into account the number of previously moves made without any conversion and adding this number to the DTC found I take into account this "25 rule" to conclude if it is really a "win" or if it is "draw".

If you do not have such mechanism that means that you ignore completly this rule and, in very rare occasions you will not play the good move!
From a practical point of view it is not relevant because the corresponding situations will probably never happen, but from a theoritical point of view, I do not like very much the DTW because I cannot take easily into account one of the game rules.

If you are interested I can give you an example of such situation but only in the 10x10 draughts world.

To summary : if your are a "practical" player ignore completly what I said. But if your are theoritician then you have a problem because you know now that you might not be able to find the good move!

Gérard

64_bit_checkers_engine · Thu Apr 30, 2009 19:56

TAILLE wrote: Remenber my "vicious" question about the "25 moves" rule. How Damy is working with this rule ?
First of all, as any other programmer interested in db, I generated my endgame db without taking into account this rule. I am not sure it is the best solution but it is another subject.

What you are referring to is called "DTZ" in the chess world (distance to "zeroing" of the move count.)

There have been papers published on how to generate databases using a DTZ metric (for chess it is 50, for Draughts it would be set to 25) so that no additional coding (such as how you deal with it) needs to be done.

A position that cannot be won within 25 moves against best defense would be in the database as a draw.

TAILLE · Post by **TAILLE** » Thu Apr 30, 2009 20:13

Hi,

64_bit_checkers_engine wrote: There have been papers published on how to generate databases using a DTZ metric (for chess it is 50, for Draughts it would be set to 25) so that no additional coding (such as how you deal with it) needs to be done.

A position that cannot be won within 25 moves against best defense would be in the database as a draw.

Sorry but I do not understand.
As a pure excercice I proposed one day to a GMI to try and win with white side in the following position :

During about 15 moves Damy confirmed after each white move that white could win but suddenly after a non optimum move from white side, Damy claimed that she had now the draw. This was possible due to the existence of the DTC db and the presence of my special code.
How can you take advantage of such small white mistake with your approach ?

64_bit_checkers_engine · Thu Apr 30, 2009 22:09

TAILLE wrote: As a pure excercice I proposed one day to a GMI to try and win with white side in the following position :

During about 15 moves Damy confirmed after each white move that white could win but suddenly after a non optimum move from white side, Damy claimed that she had now the draw. This was possible due to the existence of the DTC db and the presence of my special code.
How can you take advantage of such small white mistake with your approach ?

It would be easy.

Let's say the position you diagrammed is a win in 29 moves.

GMI moves, Damy moves. Now a win in 28 moves.
GMI moves, Damy moves. Now a win in 27 moves.
GMI moves, Damy moves. Now a win in 26 moves.
GMI moves, Damy moves. Now a win in 25 moves.
GMI moves, Damy moves. Now a win in 24 moves.
GMI moves, makes a mistake. Damy moves. Now a win in 29 moves again.

If you had access to a DTZ database, with Z = 25, here is what would happen.

GMI moves, Damy announces draw! (There is no win in 25 or less, so the position is a draw).

For every GMI move, Damy only needs to stay in the DTZ draw zone, or, when the DTW < 25, it just moves to stay in the longest loss, and after 25 moves, a draw would be declared.

Now, let's say the GMI plays the best move every time. Back to the original position.

GMI moves, Damy moves. Draw announced (really a win in 28 )
GMI moves, Damy moves. Draw announced (really a win in 27 )
GMI moves, Damy moves. Draw announced (really a win in 26 )
GMI moves, Damy moves. Win in 25 announced.
GMI moves, Damy moves. Win in 24 announced.
GMI moves, Damy moves. Win in 23 announced.

-----

GMI moves, Damy moves. Win in 6 announced.
GMI moves, Damy moves. Win in 5 announced.
GMI moves, Damy moves. Win in 4 announced.
GMI moves, Damy moves, draw claimed since 25 moves have passed.

TAILLE · Post by **TAILLE** » Thu Apr 30, 2009 22:41

Hi
It seems I need some more clarification to understand your point.
According to Damy DTC db the initial position is a winning position which needs 47 plies (24 white moves and 23 black moves) before the first conversion.
As you see the "25 moves rule" (or 50 plies rule) is not yet a difficulty at this point of the game : with perfect play White would win.
After eg 10 perfect moves (20 plies) we are then in a situation where white and black have already played 10 moves without any conversion and the DTC db give 27 plies for the number of plies needed before the first conversion.
At this point white make a "small" mistake : instead of choosing a move to reach a position at 26 plies to the first conversion he chooses a move to reach a position at 30 plies to first conversion. From that point Damy knows that she will draw the game because 20 plies have already been played and the DTC db assure that Damy can impose 30 other plies without any conversion. The game becomes a draw.
Could you explain how works exactly your proposal in this scenario ?

World Draughts Forum

Endgame Database Logic Question

Re: tottest