When and how to return a draw evaluation?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
mathmoi
Posts: 265
Joined: Mon Mar 13, 2006 4:23 pm
Location: Québec
Contact:

When and how to return a draw evaluation?

Post by mathmoi » Tue Aug 26, 2008 2:31 am

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?

bob
Posts: 20559
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: When and how to return a draw evaluation?

Post by bob » Tue Aug 26, 2008 4:19 am

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.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: When and how to return a draw evaluation?

Post by sje » Tue Aug 26, 2008 5:37 am

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.

User avatar
hgm
Posts: 23723
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: When and how to return a draw evaluation?

Post by hgm » Tue Aug 26, 2008 6:09 am

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.

PK
Posts: 826
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

50 moves

Post by PK » Tue Aug 26, 2008 7:03 am

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.

mathmoi
Posts: 265
Joined: Mon Mar 13, 2006 4:23 pm
Location: Québec
Contact:

Re: When and how to return a draw evaluation?

Post by mathmoi » Tue Aug 26, 2008 12:24 pm

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.

Uri Blass
Posts: 8591
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: When and how to return a draw evaluation?

Post by Uri Blass » Tue Aug 26, 2008 12:42 pm

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

mathmoi
Posts: 265
Joined: Mon Mar 13, 2006 4:23 pm
Location: Québec
Contact:

Re: When and how to return a draw evaluation?

Post by mathmoi » Tue Aug 26, 2008 2:11 pm

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.

User avatar
hgm
Posts: 23723
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: 50 moves

Post by hgm » Tue Aug 26, 2008 2:59 pm

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.

bob
Posts: 20559
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: When and how to return a draw evaluation?

Post by bob » Tue Aug 26, 2008 3:09 pm

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.

Post Reply