When setting out to build a DTZ database, for whatever your "Z" value is, you need:
A. (2 * Z) - 1 values for won and lost positions.
B. 1 value for a theoretical DRAWN result
C. 1 value for an UNKNOWN position
D. 1 value for a "TOO LONG TO LOSE" DRAW.
E. 1 value for a "TOO LONG TO WIN" DRAW.
The reason for D and E will become clear in a moment.
In Draughts, you must win in 25 moves (or is it just force a conversion? It sounds like you only look for a conversion in 25 rather than a full win with no pieces remaining.)
So, your DTZ database would need to store the numbers 0 (immediate loss for the side to move) to 49 (a win in 25 moves, since the losing side can only make 24) for the wins and losses, the number "50" could be for the DRAW that is "easy", the number 51 could be for UNKNOWN positions as you try and solve the database, the number 52 could be for ANY loss in more than 25 moves that is declared a draw, and the number 53 would be for any WIN that is longer than 25 moves that would be declared a draw.
So your database would look like this if you looked at some positions:
{13,22,0,7,9,11,50,50,50,3,21,53,47,45,52,53,17,...}
Your initial position that you descrived would have the value 49 in its database.
GMI moves, damy position would have a value of 48.
Damy looks for mistakes first, to check and see if it could win, of course. If not, it looks for a theoretical draw. If not...
Damy looks in the database and tries to find any value of 52, which would be a loss that would take too long, so a draw by the 25-move rule. If it would not find any, it would look for a move that forces the GMI into the longest win. It finds it can play for a 47, so it does that move.
The GMI has a win in 47 plies, plays the correct move, damy's position has a value of 46. Damy moves into a position where the GMI has a win in 45 plies, etc.
At one point, the GMI has a win in 37 plies, but he makes a "small mistake."
Now what happens?
From the position created by the GMI, damy can see values of 52, which means the win for the GMI > 49 plies. Or, if this is not the case, damy should ALWAYS SEARCH FOR THE LONGEST WIN for the GMI.
Say the GMI has just made his 11th move, (21 plies into the ending). damy is about to make a move for ply #22. Therefore if the GMI can be forced into any position where the value is > (50 - 21) then the game will be a draw.
There is never a need for damy to compute this value.
Damy looks for either the #52 (too long to lose), the #50 (a regular draw), or the longest loss possible (largest even number.)
The reason is, the bigger the number, the more moves the opponent must make.
But suppose there are still 20 pieces on the board, and you are searching ahead into this database?
This is why you need D and E. If you are winning, YOU MUST AVOID E positions in order to still win. So, you hunt for ODD numbers (1-49) and always want the smallest of these.
Suppose you are losing and searching?
You want to find a way to trade into D! The opponent might allow this, since they do not know the position can be drawn by damy in this case.
Or, even better, search for 50, and that is the easy draw.
Endgame Database Logic Question
-
64_bit_checkers_engine
- Posts: 62
- Joined: Mon Apr 20, 2009 01:10
- Contact:
The rules are:64_bit_checkers_engine wrote:In Draughts, you must win in 25 moves (or is it just force a conversion? It sounds like you only look for a conversion in 25 rather than a full win with no pieces remaining.)
- If 50 halfmoves were played without a non-king move or capture, a draw can be claimed.
- In an endgame of 3 pieces (including at least one king) against a king, if 32 halfmoves are played a draw can be claimed (so no capture/non-king move subclause here).
- In an endgame of 2 pieces (including at least one king) against a king, and the endgame of one king against one king, if 10 halfmoves are played a draw can be claimed (no capture/non-king move subclause here too).
For the official text: http://www.fmjd.org/docs/Annex%201%20of ... aughts.doc (6.2-6.4).
Also note that the 25-move rule isn't a hard rule: The draw has to be claimed!
How many chess databases take into account the 50-move rule by the way? AFAIK both the Nalimov and the Bourzutschky/Konoval tablebases ignore this rule. As it should, IMO, since the 25-move rule (draughts)/50-move rule (chess) is a human-vs-human rule, and databases should be independent of these rules. The reason for this rule (useless prolongation of a game) is absent if you have a perfect-play database.
Lasst die Maschinen verhungern, Ihr Narren...
Lasst sie verrecken!
Schlagt sie tot -- die Maschinen!
Lasst sie verrecken!
Schlagt sie tot -- die Maschinen!
Hi,
If you take the above example, after the small mistake at the 11th white move how a program with only the DTW can win ? With a DTC (or DTZ) we saw it is possible but it might not be possible with only a DTW db.
The "perfect" program must have both DTW ant DTC db. Let's take my example with a GMI as white side and a "perfect" program as black side.
Take the position after the 10th white move (the last "correct" move) :
1) 19 plies have been played (10 white moves ans 9 black moves)
2) The DTC db tell us that black as a losing position and black can impose 28 plies before the first conversion, for a total of 47 plies
3) because black cannot impose a draw by using the DTC table, black will then use the DTW db in order to choose the best defense
Now take the position after the 11th weak white move :
1) 21 plies have been played (11 white moves ans 10 black moves)
2) The DTC db tell us that black as a losing position and black can impose 29 plies (instead of 26 plies if white had not made a mistake) before the first conversion.
3) By using my special code, you can then detect that you can impose a total of 50 plies to impose a draw. From that point you will continue the game by using only the DTC db.
You can see here clearly why it could be very poor to continue using only DTW db : black has not to find the best resistance and lose the game, it has to take the opportunity to draw be imposing 50 plies witout any conversion.
Let's take another example. Imagine a position in which it seems to exist 2 winning moves. But imagine now the following DTW and DTC :
move 1 : DTW = 65 plies, DTC = 51 plies
move 2 : DTW = 70 plies, DTC = 48 plies
If you play according to DTW db you will choose move 1 and you will be very disappointed by seeing your opponent impose the draw after 50 plies without any conversion.
The good move is move 2 isn't it ?
To summary my view.
1) I would have prefered that this "25 moves rule" does not exist at all
2) The perfect program must have both DTW and DTC db
3) If I had to choose between generating DTW or DTC db I prefer generating DTC db; it is almost always less efficient but I am able to avoid wrong moves in some specific situations
OK, now I understand out it works and we can come back to to initial question : why to build a DTW db instead of DTC (or DTZ) db ?64_bit_checkers_engine wrote:Say the GMI has just made his 11th move, (21 plies into the ending). damy is about to make a move for ply #22. Therefore if the GMI can be forced into any position where the value is > (50 - 21) then the game will be a draw.
There is never a need for damy to compute this value.
Damy looks for either the #52 (too long to lose), the #50 (a regular draw), or the longest loss possible (largest even number.)
The reason is, the bigger the number, the more moves the opponent must make.
If you take the above example, after the small mistake at the 11th white move how a program with only the DTW can win ? With a DTC (or DTZ) we saw it is possible but it might not be possible with only a DTW db.
The "perfect" program must have both DTW ant DTC db. Let's take my example with a GMI as white side and a "perfect" program as black side.
Take the position after the 10th white move (the last "correct" move) :
1) 19 plies have been played (10 white moves ans 9 black moves)
2) The DTC db tell us that black as a losing position and black can impose 28 plies before the first conversion, for a total of 47 plies
3) because black cannot impose a draw by using the DTC table, black will then use the DTW db in order to choose the best defense
Now take the position after the 11th weak white move :
1) 21 plies have been played (11 white moves ans 10 black moves)
2) The DTC db tell us that black as a losing position and black can impose 29 plies (instead of 26 plies if white had not made a mistake) before the first conversion.
3) By using my special code, you can then detect that you can impose a total of 50 plies to impose a draw. From that point you will continue the game by using only the DTC db.
You can see here clearly why it could be very poor to continue using only DTW db : black has not to find the best resistance and lose the game, it has to take the opportunity to draw be imposing 50 plies witout any conversion.
Let's take another example. Imagine a position in which it seems to exist 2 winning moves. But imagine now the following DTW and DTC :
move 1 : DTW = 65 plies, DTC = 51 plies
move 2 : DTW = 70 plies, DTC = 48 plies
If you play according to DTW db you will choose move 1 and you will be very disappointed by seeing your opponent impose the draw after 50 plies without any conversion.
The good move is move 2 isn't it ?
To summary my view.
1) I would have prefered that this "25 moves rule" does not exist at all
2) The perfect program must have both DTW and DTC db
3) If I had to choose between generating DTW or DTC db I prefer generating DTC db; it is almost always less efficient but I am able to avoid wrong moves in some specific situations
Gérard
Hi,
Take the position I gave which leads to 47 plies without any conversion
47 plies are necessary before the first conversion (according to Damy DTC db)
And suppose that neither of the programs have this 7 pieces db. When will you stop the game ? 50 plies? 60 plies? ...
What about a position with 12 pieces (nobody as built it). When will you stop the game if only non conversion moves are made ?
By the way how can a referee takes its decision ? It does not exist a reference db does it ?
This position is well know and can be found on the Dragon's site in the endgame statistics.
Dragon claims here for a win in 65 plies. But there is a problem : after the forced moves 1.13-36 35-40 2.33-28 40-45 we reach the following position
White to play
and now, according to Damy DTC db, black can impose 50 plies without any conversion and it will then be able to claim for a draw.
I imagine that the referee would be in a great trouble with 2 db giving different results !
I do not really like this "25 moves" but, in a sense, it is quite avoidable even between computers.ildjarn wrote: How many chess databases take into account the 50-move rule by the way? AFAIK both the Nalimov and the Bourzutschky/Konoval tablebases ignore this rule. As it should, IMO, since the 25-move rule (draughts)/50-move rule (chess) is a human-vs-human rule, and databases should be independent of these rules. The reason for this rule (useless prolongation of a game) is absent if you have a perfect-play database.
Take the position I gave which leads to 47 plies without any conversion
47 plies are necessary before the first conversion (according to Damy DTC db)
And suppose that neither of the programs have this 7 pieces db. When will you stop the game ? 50 plies? 60 plies? ...
What about a position with 12 pieces (nobody as built it). When will you stop the game if only non conversion moves are made ?
By the way how can a referee takes its decision ? It does not exist a reference db does it ?
This position is well know and can be found on the Dragon's site in the endgame statistics.
Dragon claims here for a win in 65 plies. But there is a problem : after the forced moves 1.13-36 35-40 2.33-28 40-45 we reach the following position
White to play
and now, according to Damy DTC db, black can impose 50 plies without any conversion and it will then be able to claim for a draw.
I imagine that the referee would be in a great trouble with 2 db giving different results !
Gérard
For computer tourneys, perhaps an amended 25-move rule could be used: "Draw after 25 moves, unless one of the parties has the relevant database and this database indicates a win" (the precise wording should be somewhat more exact of course). Or even better: "The game ends when a position appears that has a known database result for one of the participants, unless this result is a draw/loss and the opponent doesn't have the database."
Lasst die Maschinen verhungern, Ihr Narren...
Lasst sie verrecken!
Schlagt sie tot -- die Maschinen!
Lasst sie verrecken!
Schlagt sie tot -- die Maschinen!
Hi,
1) If a program has the WLD db but not the corresponding DTC db. Like a human who knows that 5 kings wins against 2 kings a program can know that a position is a win but it may be a too difficult task to win. The indication "database win" seems not sufficient to claim that the program is able to find effectively the win.
2) Suppose that 20 plies have been played in eg. the 5 kings vs 2 kings final and we reach the 75th move (the game is now over) . If, seeing the 20 last plies, it is clear that the program having the advantage has not the corresoponding DTC db. If nevertheless some progress have been made, on which basis would the referee take his decision ?
Why not but it remains at least two problemsildjarn wrote:For computer tourneys, perhaps an amended 25-move rule could be used: "Draw after 25 moves, unless one of the parties has the relevant database and this database indicates a win" (the precise wording should be somewhat more exact of course). Or even better: "The game ends when a position appears that has a known database result for one of the participants, unless this result is a draw/loss and the opponent doesn't have the database."
1) If a program has the WLD db but not the corresponding DTC db. Like a human who knows that 5 kings wins against 2 kings a program can know that a position is a win but it may be a too difficult task to win. The indication "database win" seems not sufficient to claim that the program is able to find effectively the win.
2) Suppose that 20 plies have been played in eg. the 5 kings vs 2 kings final and we reach the 75th move (the game is now over) . If, seeing the 20 last plies, it is clear that the program having the advantage has not the corresoponding DTC db. If nevertheless some progress have been made, on which basis would the referee take his decision ?
Gérard
25 moves rule
Hi,
The goal of the "25 moves rule" is to be able to stop a game when the result is a draw or when the player having the winning position is unable to find the way to effectively reach the win.
My view is the following :
If we keep the computer rule "the game is over after the 75th move" then I think we would be better to delete the "25 moves rule" because it appears rather a redondant rule.
I consider that we should decide between keeping "25 moves rule" or keeping the "75th move rule".
As far as computers are concerned it seems not realistic to delete the "75th move rule" because a lot of computers will not be able to propose or accept a draw, and a game may easily last several hundreds of moves even if the "25 moves rule" is active.
I would then be happy to say that the "75th move rule" replace the "25 moves rule".
What is your feeling ?
The only big problem remaining for computer tournament is the tools at referee disposal in order to decide what is the result of these games reaching the 75th move.
Do you have some suggestions ?
The goal of the "25 moves rule" is to be able to stop a game when the result is a draw or when the player having the winning position is unable to find the way to effectively reach the win.
My view is the following :
If we keep the computer rule "the game is over after the 75th move" then I think we would be better to delete the "25 moves rule" because it appears rather a redondant rule.
I consider that we should decide between keeping "25 moves rule" or keeping the "75th move rule".
As far as computers are concerned it seems not realistic to delete the "75th move rule" because a lot of computers will not be able to propose or accept a draw, and a game may easily last several hundreds of moves even if the "25 moves rule" is active.
I would then be happy to say that the "75th move rule" replace the "25 moves rule".
What is your feeling ?
The only big problem remaining for computer tournament is the tools at referee disposal in order to decide what is the result of these games reaching the 75th move.
Do you have some suggestions ?
Gérard
-
64_bit_checkers_engine
- Posts: 62
- Joined: Mon Apr 20, 2009 01:10
- Contact:
The DTW is the proven best possible move, period.TAILLE wrote: If you take the above example, after the small mistake at the 11th white move how a program with only the DTW can win ? With a DTC (or DTZ) we saw it is possible but it might not be possible with only a DTW db.
You should read the paper I published on it.
http://www.GothicChess.com/7_piece.pdf
I had two other programs play the winning side in 8x8 checkers. It was a position with 4 vs. 3 and each program on the winning side had the WLD databases for 7 pieces also. Even knowing it was a win, and knowing every move during the search that was a win, NEITHER PROGRAM COULD WIN against the perfect play database.
The longer the win, the "greater the fall" if a person makes a mistake against a perfect play database.
If you believe a person that makes a bad move against a conversion database can miss a win, how you can possibly say the same bad move would allow them to draw against a database with perfect information? Your statement is ridiculous.
World Champion Alex Moiseyev could not win the won position in 2004, neither could Kingsrow in 2002. I think this experiment is what made Ed Gilbert build his databases with conversion information as well. You'll have to ask him to be sure.
Purely hypothetical and very, very unlikely.TAILLE wrote:You can see here clearly why it could be very poor to continue using only DTW db : black has not to find the best resistance and lose the game, it has to take the opportunity to draw be imposing 50 plies witout any conversion.
The numbers are rarely like that. The longest win for 4 Kings vs. 4 Kings is 115 plies, but it converts in just 1 ply since there is a jump ! I have already shown that ending. So, in that case, your DTC would think it is in a very bad situation, when, the truth is, the resulting 4x3 ending with 7 pieces would be very difficult, and the program should try and enter the 8-piece position that plays into such a hard subdatabase.TAILLE wrote: Let's take another example. Imagine a position in which it seems to exist 2 winning moves. But imagine now the following DTW and DTC :
move 1 : DTW = 65 plies, DTC = 51 plies
move 2 : DTW = 70 plies, DTC = 48 plies
But let's say such a position as you propose does exist. Are you saying a person will make all 50 moves correctly and avoid the conversion horizon? How convenient!
I have played my DTW databases in checkers against DTC databases. My databases have ALWAYS won faster than the originally reported DTW, because the DTC datasbases play differently, and only try to avoid conversions. I have also seen a conversion database misplay very badly, because in order to "live longer" it had to convert more quickly than its conversion count. I can show an example of this also.
There are also positions with 2 types of conversions equally distant: a checker promotion or a capture. In some cases, a DTC database on the winning side can cycle forever, getting closer to one conversion, then making a reversible move, then getting closer to the other conversion. This takes a "kludge" to fix, and more than one programmer has fallen into this trap. Such a scenario never occurs with DTW databases.
Hi,
For the 10x10 international draugths game it is true only if we accept to not take into account the "25 moves rule".
If your are familiar with the 10x10 international draughts I can show you, form the following position
why the sequence calculated by Dragon with the DTW db is wrong. At some moment black plays the best move according to the DTW db (trying to lose with the maximum number of moves) but black had really a draw move due to the DTC db and the existence of the "25 move rule".
By the way I am against this rule for games between computers but it is another subject.
DTW is perfect without the "25 moves rule" but this rule creates a lot of difficulties. Of course I agree with you that the corresponding positions are certainly very very unprobable. It is then only a theorical discussion.
Maybe Ed. could help us in order to clarify the problem.
Of course I trust you when you are saying that DTW is always the best possible move in checkers.64_bit_checkers_engine wrote: The DTW is the proven best possible move, period.
For the 10x10 international draugths game it is true only if we accept to not take into account the "25 moves rule".
If your are familiar with the 10x10 international draughts I can show you, form the following position
why the sequence calculated by Dragon with the DTW db is wrong. At some moment black plays the best move according to the DTW db (trying to lose with the maximum number of moves) but black had really a draw move due to the DTC db and the existence of the "25 move rule".
By the way I am against this rule for games between computers but it is another subject.
DTW is perfect without the "25 moves rule" but this rule creates a lot of difficulties. Of course I agree with you that the corresponding positions are certainly very very unprobable. It is then only a theorical discussion.
Maybe Ed. could help us in order to clarify the problem.
Gérard
-
64_bit_checkers_engine
- Posts: 62
- Joined: Mon Apr 20, 2009 01:10
- Contact:
This is the type of position that can confuse a DTC checkers program
It is white to move and win. white has 2 kings. red has 2 checkers and 1 king.
The side that is down material wins. The side with the extra piece loses.
White plays 1-6 threatening the red checker on square 9, so red plays 9-14. It looks like white wins easily after that with 6-10, since the red piece is "held" and can't advance without capture.
But, in order to win, white must play 6-2!, retreating away from winning the piece!
So, the winning side, down material, must AVOID winning material (a conversion) in order to win.
Red, the losing side, up material, must now CONVERT immediately with 14-17! in order to "stay in the game." By throwing away this checker, it frees the red king trapped on square 30.
You can see how this is the complete opposite of all other logic.
1. The side down material wins by NOT winning a piece when it can.
2. The side up material is losing, and must not postpone a conversion, it MUST convert in order to survive the game longer.
This is a good example, with an actual position, that proves my post. Avoiding conversion when losing, or trying to convert when winning, is NOT always the best.
Code: Select all
***************************************************************************************************************
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
***************************************************************************************************************
*----------*##########* *##########* *##########* -------- *##########* *----------*
*----------*##########* *##########* *##########* |RRRRRR| *##########* *----------*
*----------*### 32 ###* *### 31 ###* *### 30 ###* -------- *### 29 ###* *----------*
*----------*##########* *##########* *##########* |RRRRRR| *##########* *----------*
*----------*##########* *##########* *##########* -------- *##########* *----------*
***************************************************************************************************************
*----------* *##########* *##########* *##########* *##########*----------*
*----------* *##########* *##########* *##########* *##########*----------*
*----------* *### 28 ###* *### 27 ###* *### 26 ###* *### 25 ###*----------*
*----------* *##########* *##########* *##########* *##########*----------*
*----------* *##########* *##########* *##########* *##########*----------*
***************************************************************************************************************
*----------*##########* *##########* *##########* -------- *##########* *----------*
*----------*##########* *##########* *##########* |WWWWWW| *##########* *----------*
*----------*### 24 ###* *### 23 ###* *### 22 ###* -------- *### 21 ###* *----------*
*----------*##########* *##########* *##########* |WWWWWW| *##########* *----------*
*----------*##########* *##########* *##########* -------- *##########* *----------*
***************************************************************************************************************
*----------* *##########* *##########* *##########* *##########*----------*
*----------* *##########* *##########* *##########* *##########*----------*
*----------* *### 20 ###* *### 19 ###* *### 18 ###* *### 17 ###*----------*
*----------* *##########* *##########* *##########* *##########*----------*
*----------* *##########* *##########* *##########* *##########*----------*
***************************************************************************************************************
*----------*##########* *##########* *##########* *##########* *----------*
*----------*##########* *##########* *##########* *##########* *----------*
*----------*### 16 ###* *### 15 ###* *### 14 ###* *### 13 ###* *----------*
*----------*##########* *##########* *##########* *##########* *----------*
*----------*##########* *##########* *##########* *##########* *----------*
***************************************************************************************************************
*----------* *##########* *##########* *##########* *##########*----------*
*----------* *##########* *##########* *##########* *##########*----------*
*----------* *### 12 ###* *### 11 ###* *### 10 ###* -------- *### 09 ###*----------*
*----------* *##########* *##########* *##########* |rrrrrr| *##########*----------*
*----------* *##########* *##########* *##########* -------- *##########*----------*
***************************************************************************************************************
*----------*##########* *##########* *##########* *##########* *----------*
*----------*##########* *##########* *##########* *##########* *----------*
*----------*### 08 ###* *### 07 ###* *### 06 ###* *### 05 ###* *----------*
*----------*##########* *##########* *##########* *##########* *----------*
*----------*##########* *##########* *##########* *##########* *----------*
***************************************************************************************************************
*----------* *##########* *##########* *##########* -------- *##########*----------*
*----------* *##########* *##########* *##########* |WWWWWW| *##########*----------*
*----------* *### 04 ###* -------- *### 03 ###* *### 02 ###* -------- *### 01 ###*----------*
*----------* *##########* |rrrrrr| *##########* *##########* |WWWWWW| *##########*----------*
*----------* *##########* -------- *##########* *##########* -------- *##########*----------*
***************************************************************************************************************
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
*----------*----------*----------*----------*----------*----------*----------*----------*----------*----------*
The side that is down material wins. The side with the extra piece loses.
White plays 1-6 threatening the red checker on square 9, so red plays 9-14. It looks like white wins easily after that with 6-10, since the red piece is "held" and can't advance without capture.
But, in order to win, white must play 6-2!, retreating away from winning the piece!
So, the winning side, down material, must AVOID winning material (a conversion) in order to win.
Red, the losing side, up material, must now CONVERT immediately with 14-17! in order to "stay in the game." By throwing away this checker, it frees the red king trapped on square 30.
You can see how this is the complete opposite of all other logic.
1. The side down material wins by NOT winning a piece when it can.
2. The side up material is losing, and must not postpone a conversion, it MUST convert in order to survive the game longer.
This is a good example, with an actual position, that proves my post. Avoiding conversion when losing, or trying to convert when winning, is NOT always the best.
Though I am not a all familiar with checkers I did my best in order to understand your point.64_bit_checkers_engine wrote:This is the type of position that can confuse a DTC checkers program
But, in order to win, white must play 6-2!, retreating away from winning the piece!
So, the winning side, down material, must AVOID winning material (a conversion) in order to win.
Red, the losing side, up material, must now CONVERT immediately with 14-17! in order to "stay in the game." By throwing away this checker, it frees the red king trapped on square 30.
You can see how this is the complete opposite of all other logic.
1. The side down material wins by NOT winning a piece when it can.
2. The side up material is losing, and must not postpone a conversion, it MUST convert in order to survive the game longer.
This is a good example, with an actual position, that proves my post. Avoiding conversion when losing, or trying to convert when winning, is NOT always the best.
I believe that the misunderstanding concernes the "DTC" definition.
1) How I use the term of "conversion" : for me a conversion is, either a capture or a man move. A non-conversion move is a king move without capture.
2) For the winning side the DTC if the maximum number of moves necessary before reaching a "winning conversion"
3) For the losing side the DTC if the minimum number of moves that can be imposed before the next (losing) "conversion"
Let'us forget about "25 move rule".
If the winning side follow the DTC db it is sure to win. It will be less efficient (no doubt at all about that!) than following a DTW db but the win is 100% sure.
In your example if 6-2 is the only winning move then the DTC db will tell you to choose this move because the position after 6-10 is not marked as a losing position for red.
My point is the following :
Until you take into account the "25 move" (or the equivalent in checkers) the DTW approach is definitely better that the DTC approach.
For the winning side, using a DTW db is a far better optimisation but keep in mind that you cannot miss the win by only using a DTC db.
For the losing side using the DTW db is certainly the best choice when playing against a human. Against another computer it may not be best approach in order to provoque a mistake.
Let's suppose that you have plenty of different kind of db up to 7 pieces and your opponent has only the DTW bd up to 6 pieces. Suppose that your are in a 7 pieces losing position (according to your powerful 7 pieces db). What will be your best move ? If you know that your opponent has the 6 pieces DTW db then, your very first priority (to try and provoque a mistake) is to avoid reaching to quickly this 6 pieces db. As a consequence the best move may be a move that would use a kind of "Distance To 6 pieces db".
As you see using DTW is definitly a perfect approach for the winning side but it may not be the best approach for the losing side.
If now you try to take into account the "25 moves rule" then the situation, in some exceptionnal positions, may become dramatic because, when using only the DTW db, you might miss a possible draw after a "small mistake" of your opponent.
Gérard
-
64_bit_checkers_engine
- Posts: 62
- Joined: Mon Apr 20, 2009 01:10
- Contact:
My definition of conversion is the promotion of a checker to a king, or the capture of any piece. Just moving a checker is not a conversion, for my part of the following discussion.TAILLE wrote:If the winning side follow the DTC db it is sure to win. It will be less efficient (no doubt at all about that!) than following a DTW db but the win is 100% sure.
I have concrete proof that a conversion database in checkers, sometimes, can "count down" but at a certain point, the count will increase after a move is made. The reason is because a conversion database only "counts down" when it plays against its own logic. When a conversion database plays against a DTW database, the DTW db can get it into trouble.
Look how many "exceptions" must be made to play the position that I showed previously in the 2 checkers + 1 king vs. 2 kings example. The DTC database must check to see if its conversion move really is the best move by querying subdatabases constantly.
The DTW database has no faulty logic. It's move is correct, always. It never needs to "consult", and it never need to check conversion boundaries into other databases.
Which database is most likely to play correctly 100% of the time? The DTW database.
Since the wording of the "25 move" rule uses the word conversion, then the ruling supports making any non-optimal move as long as pieces are traded or the checkers pieces are moved. That doesn't mean the DTW is worse. If the words of the rules are changed, then does that mean the DTC best play becomes worse? Changing rules should have no bearing on the "true play".TAILLE wrote: My point is the following :
Until you take into account the "25 move" (or the equivalent in checkers) the DTW approach is definitely better that the DTC approach.
The play of the DTC is either the same as the DTW, or not as good, and never better. The rules are there for the sake of human exhaustion, and should not be used to objectively evaluate the true play of a database.
You are also assuming that the move produced by the DTW and DTC will be different. This is not always true. Many of the DTW moves are the same, or lead to the same DTC decremented counts. It is only near a node leading to a conversion boundary that DTC databases tend to misplay.
I provided a definite example, with a position, and you reply with something hypothetical that cannot be tested.TAILLE wrote: Let's suppose that you have plenty of different kind of db up to 7 pieces and your opponent has only the DTW bd up to 6 pieces. Suppose that your are in a 7 pieces losing position (according to your powerful 7 pieces db). What will be your best move ? If you know that your opponent has the 6 pieces DTW db then, your very first priority (to try and provoque a mistake) is to avoid reaching to quickly this 6 pieces db. As a consequence the best move may be a move that would use a kind of "Distance To 6 pieces db".
Your premise is faulty. You haven't had the opportunity to play a DTW so you do not realize what the result of this will be. I think you will be surprised.
Hi Ed.
I hope to see you in the future in a 10x10 draughts tournament.
You are right, I have no experience of one could bring a DTW db and no experience on checkers. Sorry to not be able to help you.64_bit_checkers_engine wrote: Your premise is faulty. You haven't had the opportunity to play a DTW so you do not realize what the result of this will be. I think you will be surprised.
I hope to see you in the future in a 10x10 draughts tournament.
Gérard
-
Rein Halbersma
- Posts: 1722
- Joined: Wed Apr 14, 2004 16:04
- Contact:
Re:
Some new thoughts on this old post.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.
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
It is indeed tempting to play A1 rather than B1 as you say. But consider the opponent also. Suppose after A1 the opponent is about to make the mistake A2', but after some search then suddenly finds the other mistake A2'' to be slightly better. As a consequence, it is likely that this will trigger time extensions because of an unstable PV. After an even deeper search it might then find the correct play A2. After B1 on the other hand, once the mistake is about to be made, there is no chance that alternative mistakes will be considered. The "wrong" PV is therefore more likely to be stable.
So there are 2 factors to be considered: number of mistake to be made, and likelihood that the mistake is not discovered.
One approach might be to balance these by *randomly* playing either A1 or B1, e.g. with probabilities 3/7 and 4/7! If randomize consistently in situations where your opponent is aware that you are speculating (e.g. playing a 7-pc endgame against a program that doesn't have the 7 pc db and knows that you do), then your opponent will never know for sure whether he is in a quiet position with only 1 mistake to make or in a tricky position with many possible mistakes. This makes it harder for your opponent to allocate most of the search time to the difficult positions.
Rein
