Page 1 of 4

When and how to return a draw evaluation?

Posted: Tue Aug 26, 2008 4:31 am
by mathmoi
Hi,

I have a (relatively) simple problem with my search. At the begining of NegaMax, before I start to recursively call NegaMax again, I check if the game is a draw :

Code: Select all

if (IsRepetition() || FiftyMovesCounter > 100)
   return DrawEval; // Zero (0)
If my opponent does not call the repetition or the 50 moves rules i have two problems :

1) every search returns 0, even if the games continue, so my moves are not the bests.
2) Every iteration of my Iterative deepening returns zero very quickly without searching because every positions now is a draw.

How do you deals with that in your programs, or how do you think I shoulf handle that?

Re: When and how to return a draw evaluation?

Posted: Tue Aug 26, 2008 6:19 am
by bob
mathmoi wrote:Hi,

I have a (relatively) simple problem with my search. At the begining of NegaMax, before I start to recursively call NegaMax again, I check if the game is a draw :

Code: Select all

if (IsRepetition() || FiftyMovesCounter > 100)
   return DrawEval; // Zero (0)
If my opponent does not call the repetition or the 50 moves rules i have two problems :

1) every search returns 0, even if the games continue, so my moves are not the bests.
2) Every iteration of my Iterative deepening returns zero very quickly without searching because every positions now is a draw.

How do you deals with that in your programs, or how do you think I shoulf handle that?
at the root, if you repeat 3 times, you can claim the draw and you don't have to continue. Otherwise, and in the case of Crafty, I will continue to play, but it will continue to go for repetitions.

Re: When and how to return a draw evaluation?

Posted: Tue Aug 26, 2008 7:37 am
by sje
Symbolic claims a draw immediately. The idea is that it's better to spend time on a new game than to continue the old one.

However, some authors have incorporated a "contempt factor" into their programs. A program that thinks it's stronger than the opponent or the opponent is short on time might keep on playing in a drawn position. Alternatively, a program that fears its opponent or is itself short on time, will accept a draw and may even play for a draw.

Re: When and how to return a draw evaluation?

Posted: Tue Aug 26, 2008 8:09 am
by hgm
Never make the program aware in its search of 50-move draws. That is just asking for trouble. If programs cannot make progress in a won situation without negative re-inforcement, there is something fundamentally wrong in their evaluation. Better solve the problem where it lies, in stead of using the 50-move rule as a work-around.

50 moves

Posted: Tue Aug 26, 2008 9:03 am
by PK
HG,

I noticed that in just about all Your posts about 50-move rule You look at it from the perspective of the winning side. But what about the loser? The weaker player may actually need the negative reinforcement not to move its wretched last pawn, despite it being a passer. In the long run, assuming the oposition of similar strength, this effect might cancel out with the problems You wrote about. And to catch the opponent on a desperate sacrifice for the purpose of avoiding the draw, You need actually to come close to that draw.

Re: When and how to return a draw evaluation?

Posted: Tue Aug 26, 2008 2:24 pm
by mathmoi
bob wrote:
mathmoi wrote:Hi,

I have a (relatively) simple problem with my search. At the begining of NegaMax, before I start to recursively call NegaMax again, I check if the game is a draw :

Code: Select all

if (IsRepetition() || FiftyMovesCounter > 100)
   return DrawEval; // Zero (0)
If my opponent does not call the repetition or the 50 moves rules i have two problems :

1) every search returns 0, even if the games continue, so my moves are not the bests.
2) Every iteration of my Iterative deepening returns zero very quickly without searching because every positions now is a draw.

How do you deals with that in your programs, or how do you think I shoulf handle that?
at the root, if you repeat 3 times, you can claim the draw and you don't have to continue. Otherwise, and in the case of Crafty, I will continue to play, but it will continue to go for repetitions.
HI,

Do you mean that you don't check for repetitions or 50 moves draw in the search? I don't think.

My main problem is with Iterative Deepening. When I'm close to the 50 moves repetitions, every iterations abort after a small depth (say depth=3) . Because the search hit the 50 moves rules after 3 plys. Then because the search returned very quickly, The iterative deepening goes crazy and call iterations after iterations up to some really large hard limit (2000).

My first idea was to stop to iterate after the search return a draw score, but this would be obviously wrong since I can't know if a score of zero means 1) the position is balanced or 2) The position is a draw because of a rule (50 Move or 3 repetitions).

Thanks for your post.

Re: When and how to return a draw evaluation?

Posted: Tue Aug 26, 2008 2:42 pm
by Uri Blass
mathmoi wrote:
bob wrote:
mathmoi wrote:Hi,

I have a (relatively) simple problem with my search. At the begining of NegaMax, before I start to recursively call NegaMax again, I check if the game is a draw :

Code: Select all

if (IsRepetition() || FiftyMovesCounter > 100)
   return DrawEval; // Zero (0)
If my opponent does not call the repetition or the 50 moves rules i have two problems :

1) every search returns 0, even if the games continue, so my moves are not the bests.
2) Every iteration of my Iterative deepening returns zero very quickly without searching because every positions now is a draw.

How do you deals with that in your programs, or how do you think I shoulf handle that?
at the root, if you repeat 3 times, you can claim the draw and you don't have to continue. Otherwise, and in the case of Crafty, I will continue to play, but it will continue to go for repetitions.
HI,

Do you mean that you don't check for repetitions or 50 moves draw in the search? I don't think.

My main problem is with Iterative Deepening. When I'm close to the 50 moves repetitions, every iterations abort after a small depth (say depth=3) . Because the search hit the 50 moves rules after 3 plys. Then because the search returned very quickly, The iterative deepening goes crazy and call iterations after iterations up to some really large hard limit (2000).

My first idea was to stop to iterate after the search return a draw score, but this would be obviously wrong since I can't know if a score of zero means 1) the position is balanced or 2) The position is a draw because of a rule (50 Move or 3 repetitions).

Thanks for your post.
1)No reason for hard limit of 2000.
Most porgrams use hard limit of 50 or 60 or something like that.

2)I do not see what is the problem with the fact that you get the maximal depth in positions when there is a forced draw by the 50 move rules in the next move.

The move that you play is unimportant because you are going to play it with a draw claim and finish the game.

Uri

Re: When and how to return a draw evaluation?

Posted: Tue Aug 26, 2008 4:11 pm
by mathmoi
Uri Blass wrote:
mathmoi wrote:
bob wrote:
mathmoi wrote:Hi,

I have a (relatively) simple problem with my search. At the begining of NegaMax, before I start to recursively call NegaMax again, I check if the game is a draw :

Code: Select all

if (IsRepetition() || FiftyMovesCounter > 100)
   return DrawEval; // Zero (0)
If my opponent does not call the repetition or the 50 moves rules i have two problems :

1) every search returns 0, even if the games continue, so my moves are not the bests.
2) Every iteration of my Iterative deepening returns zero very quickly without searching because every positions now is a draw.

How do you deals with that in your programs, or how do you think I shoulf handle that?
at the root, if you repeat 3 times, you can claim the draw and you don't have to continue. Otherwise, and in the case of Crafty, I will continue to play, but it will continue to go for repetitions.
HI,

Do you mean that you don't check for repetitions or 50 moves draw in the search? I don't think.

My main problem is with Iterative Deepening. When I'm close to the 50 moves repetitions, every iterations abort after a small depth (say depth=3) . Because the search hit the 50 moves rules after 3 plys. Then because the search returned very quickly, The iterative deepening goes crazy and call iterations after iterations up to some really large hard limit (2000).

My first idea was to stop to iterate after the search return a draw score, but this would be obviously wrong since I can't know if a score of zero means 1) the position is balanced or 2) The position is a draw because of a rule (50 Move or 3 repetitions).

Thanks for your post.
1)No reason for hard limit of 2000.
Most porgrams use hard limit of 50 or 60 or something like that.

2)I do not see what is the problem with the fact that you get the maximal depth in positions when there is a forced draw by the 50 move rules in the next move.

The move that you play is unimportant because you are going to play it with a draw claim and finish the game.

Uri
Hi Uri,

Thanks for your post.
1)No reason for hard limit of 2000.
Most porgrams use hard limit of 50 or 60 or something like that.
You're probably right. When I implemented the limit I did not tough about it and used something big enough it would not ever be hit. I'll drop it to 50 for now.
2)I do not see what is the problem with the fact that you get the maximal depth in positions when there is a forced draw by the 50 move rules in the next move.
Well, maybe it's not a problem... but it felt wrong. Since all the iterations returns immediately they provide no new informations. But even with my hard limit of 2000 they are done so fast that it does not really waste much time.

Re: 50 moves

Posted: Tue Aug 26, 2008 4:59 pm
by hgm
PK wrote:HG,

I noticed that in just about all Your posts about 50-move rule You look at it from the perspective of the winning side. But what about the loser? The weaker player may actually need the negative reinforcement not to move its wretched last pawn, despite it being a passer. In the long run, assuming the oposition of similar strength, this effect might cancel out with the problems You wrote about. And to catch the opponent on a desperate sacrifice for the purpose of avoiding the draw, You need actually to come close to that draw.
Good point. Of course ignoring one, does not mean you have to ignore the other.

In fact I do react to the 50-move counter in Joker, but in a more emotional way: If the count gets above 50 ply, Pawn pushes are awarded more for the side that is ahead. I guess I should really penalize them foo\r the side that is behind, in that case. The main reason I have not done that is that I never perceived the problem. If Joker did refrain from moving a Pawn for 45 moves, it is very unlikely that it would suddenly do it in the last 5 moves.

Re: When and how to return a draw evaluation?

Posted: Tue Aug 26, 2008 5:09 pm
by bob
mathmoi wrote:
bob wrote:
mathmoi wrote:Hi,

I have a (relatively) simple problem with my search. At the begining of NegaMax, before I start to recursively call NegaMax again, I check if the game is a draw :

Code: Select all

if (IsRepetition() || FiftyMovesCounter > 100)
   return DrawEval; // Zero (0)
If my opponent does not call the repetition or the 50 moves rules i have two problems :

1) every search returns 0, even if the games continue, so my moves are not the bests.
2) Every iteration of my Iterative deepening returns zero very quickly without searching because every positions now is a draw.

How do you deals with that in your programs, or how do you think I shoulf handle that?
at the root, if you repeat 3 times, you can claim the draw and you don't have to continue. Otherwise, and in the case of Crafty, I will continue to play, but it will continue to go for repetitions.
HI,

Do you mean that you don't check for repetitions or 50 moves draw in the search? I don't think.

My main problem is with Iterative Deepening. When I'm close to the 50 moves repetitions, every iterations abort after a small depth (say depth=3) . Because the search hit the 50 moves rules after 3 plys. Then because the search returned very quickly, The iterative deepening goes crazy and call iterations after iterations up to some really large hard limit (2000).

My first idea was to stop to iterate after the search return a draw score, but this would be obviously wrong since I can't know if a score of zero means 1) the position is balanced or 2) The position is a draw because of a rule (50 Move or 3 repetitions).

Thanks for your post.
There are two issues:

(1) in the search, I treat a 2-fold as an absolute draw and when I find a two-fold repetition I always instantly return draw score.

(2) when you actually make a move on the board by sending it to the GUI or whatever, you can check to see if it repeats for a third time (rather than just twice) and if so, tell the GUI that you are claiming a draw. Then you could elect to not play further although I continue as long as the opponent wants. But the GUI should end the game at that point. On ICC for example, if you make a valid repetition draw claim, the game ends as it should.