Draw scores

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Carey
Posts: 313
Joined: Wed Mar 08, 2006 7:18 pm
Contact:

Draw scores

Post by Carey » Fri Oct 05, 2007 4:15 pm

Let me start off by saying that I'm an idiot. That seems to be the best explanation for why I'm having trouble with this.

I've written a few very minor chess programs over the years. I don't like playing chess, only programming chess, so I never really cared how well they played. I just had fun writing them.

Now I'm trying to make my new one work properly, so I now care about the little details.... like draw scores.

Solving one issue brings up another problem. Solving that one creates ye another, etc. My simple problem has ballooned into several issues and fixing them has become a problem all to itself.

By the time I do all the solutions, it's one heck of a kludge. A wart on a wart.

Obviously I'm doing something wrong. I'm missing something obvious.

When a solution to a simple problem becomes this complicated, something is wrong.


Issue 1)
If you do a draw score of zero, then the program can not tell the difference between a draw in 3 moves from a draw in 33 moves. One draw looks as good as another to the search, so it just picks randomly among them.

In cases where there are multiple draws at the root (and even in the search), the program picks randomly among them. Leading to the possibility of the program playing back & forth between them and never actually getting around to doing the draw. This is similar to why programs give a bonus to mates that are closer to the root than others.

There are a few infamous games where a program couldn't choose between several mates and ended up loosing the game. The draw problem seems to be the same issue.

The solution, of course, is to give a bonus to draws that are closer to the root. Say, 1000-Ply. (That assumes we have a 1000 point window around zero just for draw scores. Don't have to, it just makes this discussion easier.) That leads to issue 2.


Issue 2)
If you give a draw score a non-zero value, then that means a draw can have a negative score, after its been backed up the search and negated by NegaMax.

That seems to be absurd. It shouldn't be negative. A draw is a draw, no matter who plays it. It's not bad or good. It simply 'is'.

You can ignore that, but that leads to issue 3.


Issue 3)
If you allow a draw score to be negative, then that causes problems for the search. You end up with cases where shorter or longer draws appear better because of the sign.

Assume, for example, that we search ply 1 move 1 and discover that it has a draw score of "draw in 2 moves", or 9998 in this scoring system. That score backs up to the first ply and it becomes -9998 because of the NegaMax negation.

That sets Alpha to -9998 and beta is still at +Infinity.

Ply 1 move 2. It has a=-9998 & B=+Inf. It makes the move and recurses.

Ply 2 move 1. It has a=-inf & b=+9998. It makes the move and recurses.

Ply 3... alpha=-9998 & beta=+Inf.
We discover it's a draw. we return the score 1000-Ply = 9997

Back at ply 2 move 1, we negate that return score of 9997 to -9997. That becomes the best move.

There are no more moves at ply 2, so we back up to ply 1.

Back at ply 1, that score of -9997 gets negated by NegaMax and becomes 9997.

So, now at ply 1, we have a case where a draw in two moves has a score of -9998 and a draw in 3 moves has a score of 9997.


Because the draws happened on different plies, they got negated a different number of times and the result is the signs are different.

This causes the search to pick draws at odd plies over draws at even plies. In other words, with this method, it prefers a draw at ply 33 over a draw at ply 2.


That's not right behavior. A draw is a draw. It doesn't matter who does it. (ie: what ply.)

It's not like checkmate, where it's important who gets mated. A draw simply 'is'. It happens equally to both players.

A draw score should never be negative.


Issue 4)
Fixing #3 means not negating draw scores. Leaving draw scores always positive. Solves that. We have to keep a draw score always seperate from a heuristic score, hence the use of the 1000 point window around zero. We could use a flag passed back. That'd work just as well.

However, doing that fix also means we have to *always* be sure and not negate the draw scores. Including where we recurse and swap & negate the alpha & beta scores.




At this point I've got 3 fixes for what seemed to be a simple issue.

It's starting to get complicated and when a solution starts getting this complicated, you know something is wrong with your original thought. It's time to rethink. Or ask for help.


So, if something is wrong with my reasoning, then I must be an idiot because it looks like the reasoning is sound.

I've gone through the search process and looked at the bounds and what the scores can be (including fail-soft), and it sure looks to me like getting the right draw score is not an easy thing to do.


I know most programs don't bother with all this. (I haven't checked all of them, but a few. I don't really like browsing other programs to see how they do things, though.)

And I haven't seen any discussion about these kinds of problems. (I did browse through the CCC archives and didn't see anything there or on other web sites. I did, however, see a comment by Prof. Hyatt about draw scores getting very deep because of the hash table. But artificially limiting draw depth scores to 100 plies should solve that. You end up with issue 1 above, but for draws 100 plies away that's not really a big problem.)


So maybe the other programs just don't bother to fix the initial problem? Figuring that it's such a small problem that it's not worth the complicated fixes to make sure it always picks the best draw move?

Do they figure one draw is as good as the next, or do they not care the program will prefer draws at odd plies over even plies?


Or have I missed something obvious. (That's most likely...)


I looked for articles on dealing with exact vs. inexact scores, but all I found were a few references to some papers by Beal and to one by Slate.

This whole thing just doesn't seem to be discussed much.

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: Draw scores

Post by Chan Rasjid » Fri Oct 05, 2007 4:30 pm

Let me start off by saying that I'm an idiot. That seems to be the best explanation for why I'm having trouble with this.
The Tibetan High Monks over at the inner sanctums of the Potala secretly teach their chosen disciples the recital of the Mantra ... "Omm... Omm Enlightenment is Well Nigh.. Omm... Omm...." I'm afraid the arabic zero may elude you for quite some time yet!

I have heard some reserves a small range [-3, +3] only for "different" draws which means NOT ALL DRAWS ARE THE SAME!!! I don't know why but just have
#define DRAW_SCORE 0
Careful only not to allow eval() to return zero.

Rasjid
Don't believe when you're told "There's no free lunch!" There is Linux.

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: Draw scores

Post by Chan Rasjid » Fri Oct 05, 2007 5:18 pm

Carey wrote:-

It seems most of us are nor troubled with draws.
rep3 draw yes, but the thing is more about path-dependency and hashing the zero.
If you hash, then temporarily:-
1) try to use only zero and see if you can work things out.
2) hash 0 only for stalemate and other recognized material draws; DON'T hash any 0 from rep3 / fifty draws. Hash probing of a 0 from rep3 may no more be a rep3 as the path might be different.
See if this solved your problems.
Issue 1)
If you do a draw score of zero, then the program can not tell the difference between a draw in 3 moves from a draw in 33 moves. One draw looks as good as another to the search, so it just picks randomly among them.
I may not understand this! Say at root my search gives a best move with bestscore = 0 (draw) and assume alpha-beta is correct, this draw PV will be played out and after whatever number of moves, it will be DRAW. Whenever alpha is set to 0, it will not select the next 0 if encounterd, only the next score > 0, thus alpha-beta cannot select draw nodes up the tree, may be the one of 33 moves and not 3 moves. But it IS THE SAME except both sides play for 33 moves more instead of 3!

I don't have a clue how to use -1000 = X, -9988, ..etc for draws. Draws should be solvable even just with
DRAWSCORE = 0.

Rasjid
Don't believe when you're told "There's no free lunch!" There is Linux.

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

Re: Draw scores

Post by bob » Fri Oct 05, 2007 9:05 pm

Carey wrote:Let me start off by saying that I'm an idiot. That seems to be the best explanation for why I'm having trouble with this.

I've written a few very minor chess programs over the years. I don't like playing chess, only programming chess, so I never really cared how well they played. I just had fun writing them.

Now I'm trying to make my new one work properly, so I now care about the little details.... like draw scores.

Solving one issue brings up another problem. Solving that one creates ye another, etc. My simple problem has ballooned into several issues and fixing them has become a problem all to itself.

By the time I do all the solutions, it's one heck of a kludge. A wart on a wart.

Obviously I'm doing something wrong. I'm missing something obvious.

When a solution to a simple problem becomes this complicated, something is wrong.


Issue 1)
If you do a draw score of zero, then the program can not tell the difference between a draw in 3 moves from a draw in 33 moves. One draw looks as good as another to the search, so it just picks randomly among them.
Before you go on, you should read the paper Harry Nelson wrote titled "The draw heuristic in Cray Blitz". We addressed this very issue, but it has its own set of issues as you mentioned. We uses real scores that had a "gap" between 0 and 100 (pawn = 1000 in Cray Blitz), and we squeezed the draw scores into that range based on the ply where they are discovered. The problem is that draw scores (except for insufficient material) are path-dependent, and hashing ignores the path. So we were seeing scores like draw in 90 plies, even though CB had a max depth of 64 plies. We just accepted that, knowing that some draws were getting pushed out to appear that they happened beyond 100 plies, making them move into the real (non-draw score) area.


In cases where there are multiple draws at the root (and even in the search), the program picks randomly among them. Leading to the possibility of the program playing back & forth between them and never actually getting around to doing the draw. This is similar to why programs give a bonus to mates that are closer to the root than others.

There are a few infamous games where a program couldn't choose between several mates and ended up loosing the game. The draw problem seems to be the same issue.

The solution, of course, is to give a bonus to draws that are closer to the root. Say, 1000-Ply. (That assumes we have a 1000 point window around zero just for draw scores. Don't have to, it just makes this discussion easier.) That leads to issue 2.


Issue 2)
If you give a draw score a non-zero value, then that means a draw can have a negative score, after its been backed up the search and negated by NegaMax.

That seems to be absurd. It shouldn't be negative. A draw is a draw, no matter who plays it. It's not bad or good. It simply 'is'.

You can ignore that, but that leads to issue 3.


Issue 3)
If you allow a draw score to be negative, then that causes problems for the search. You end up with cases where shorter or longer draws appear better because of the sign.

Assume, for example, that we search ply 1 move 1 and discover that it has a draw score of "draw in 2 moves", or 9998 in this scoring system. That score backs up to the first ply and it becomes -9998 because of the NegaMax negation.
This is really a non-issue. if you reserve scores between -1000 and +1000 for draws, it will work, in that anything in that range is a draw. Note that more distant draws for white are favorable according to your definition, so for black less distant (more immediate) draws are more favorable, and that is what will happen. But you still have the hash issue to deal with and that is significant.
That sets Alpha to -9998 and beta is still at +Infinity.

Ply 1 move 2. It has a=-9998 & B=+Inf. It makes the move and recurses.

Ply 2 move 1. It has a=-inf & b=+9998. It makes the move and recurses.

Ply 3... alpha=-9998 & beta=+Inf.
We discover it's a draw. we return the score 1000-Ply = 9997

Back at ply 2 move 1, we negate that return score of 9997 to -9997. That becomes the best move.

There are no more moves at ply 2, so we back up to ply 1.

Back at ply 1, that score of -9997 gets negated by NegaMax and becomes 9997.

So, now at ply 1, we have a case where a draw in two moves has a score of -9998 and a draw in 3 moves has a score of 9997.


Because the draws happened on different plies, they got negated a different number of times and the result is the signs are different.

This causes the search to pick draws at odd plies over draws at even plies. In other words, with this method, it prefers a draw at ply 33 over a draw at ply 2.


That's not right behavior. A draw is a draw. It doesn't matter who does it. (ie: what ply.)
Not within the minimax framework. If a draw in 10 is good for me, a draw in less than 10 is better for my opponent, otherwise the min-max approach won't work at all. However, I think it better to ignore the idea with one exception that we use in Crafty explained below.

It's not like checkmate, where it's important who gets mated. A draw simply 'is'. It happens equally to both players.

A draw score should never be negative.


Issue 4)
Fixing #3 means not negating draw scores. Leaving draw scores always positive. Solves that. We have to keep a draw score always seperate from a heuristic score, hence the use of the 1000 point window around zero. We could use a flag passed back. That'd work just as well.

However, doing that fix also means we have to *always* be sure and not negate the draw scores. Including where we recurse and swap & negate the alpha & beta scores.




At this point I've got 3 fixes for what seemed to be a simple issue.

It's starting to get complicated and when a solution starts getting this complicated, you know something is wrong with your original thought. It's time to rethink. Or ask for help.


So, if something is wrong with my reasoning, then I must be an idiot because it looks like the reasoning is sound.

I've gone through the search process and looked at the bounds and what the scores can be (including fail-soft), and it sure looks to me like getting the right draw score is not an easy thing to do.


I know most programs don't bother with all this. (I haven't checked all of them, but a few. I don't really like browsing other programs to see how they do things, though.)

And I haven't seen any discussion about these kinds of problems. (I did browse through the CCC archives and didn't see anything there or on other web sites. I did, however, see a comment by Prof. Hyatt about draw scores getting very deep because of the hash table. But artificially limiting draw depth scores to 100 plies should solve that. You end up with issue 1 above, but for draws 100 plies away that's not really a big problem.)


So maybe the other programs just don't bother to fix the initial problem? Figuring that it's such a small problem that it's not worth the complicated fixes to make sure it always picks the best draw move?

Do they figure one draw is as good as the next, or do they not care the program will prefer draws at odd plies over even plies?


Or have I missed something obvious. (That's most likely...)


I looked for articles on dealing with exact vs. inexact scores, but all I found were a few references to some papers by Beal and to one by Slate.

This whole thing just doesn't seem to be discussed much.
The only exception I have to drawscore = 0 happens for two conditions:

(1) my draw score is dynamic (and the user can adjust it also as in "contempt setting".) But, in general, a draw score should reflect the preferred outcome based on your and your opponent's ratings. For crafty, against a weaker opponent, I have more "contempt" and will work harder to avoid draws because the drawscore goes more negative as crafty's rating goes above the opponent's rating. Ditto for the inverse case where I would prefer to draw a much higher rated opponent.

2. For endgame table draws, I would prefer a drawn KRP vs KR over a drawn KR vs KR ending. And often crafty gets to make that decision. In crafty a drawscore of 0 means drawn, material is even. A drawscore of +1 means draw, program is ahead in material. A score of -1 (-.01 of course) says the program is behind in material. The idea is that given the choice of two draws, I'd like to either take the one where my opponent has the chance to make mistakes and actually lose, or where he has to at least think and perhaps get into a bit of time trouble and then make a more serious mistake.

Carey
Posts: 313
Joined: Wed Mar 08, 2006 7:18 pm
Contact:

Re: Draw scores

Post by Carey » Fri Oct 05, 2007 10:35 pm

Chan Rasjid wrote:Carey wrote:-

It seems most of us are nor troubled with draws.
rep3 draw yes, but the thing is more about path-dependency and hashing the zero.
If you hash, then temporarily:-
1) try to use only zero and see if you can work things out.
2) hash 0 only for stalemate and other recognized material draws; DON'T hash any 0 from rep3 / fifty draws. Hash probing of a 0 from rep3 may no more be a rep3 as the path might be different.
See if this solved your problems.
I don't have hashing in my program yet.

Before I start adding any enhancements or refinements to the quality of the play, I want to get basic playing ability rock solid, along with all the xboard stuff, etc.

Once I get everything working properly and reliably, then I'll start doing the enhancements.

In my older programs I always added lots of features and extras and as a result I never got all the basic stuff nice and solid, or all the xboard stuff, etc. So this time I'm working in the other direction.

Issue 1)
If you do a draw score of zero, then the program can not tell the difference between a draw in 3 moves from a draw in 33 moves. One draw looks as good as another to the search, so it just picks randomly among them.
I may not understand this! Say at root my search gives a best move with bestscore = 0 (draw) and assume alpha-beta is correct, this draw PV will be played out and after whatever number of moves, it will be DRAW. Whenever alpha is set to 0, it will not select the next 0 if encounterd, only the next score > 0, thus alpha-beta cannot select draw nodes up the tree, may be the one of 33 moves and not 3 moves. But it IS THE SAME except both sides play for 33 moves more instead of 3!
[/quote]

Which draw it happens to find and thinks best will depend on the move ordering. Which ever one it stumbles upon first.

Depending on the search time, whether you were pondering (and correctly predicted the other's move), if you don't clear the hash table or the history heuristic tables (if you use it), etc. can influence the move ordering.

I'm sure your program will find a draw. I'm not doubting that at all. Any semi-working program should. (Even mine.) The problem is, you don't know which draw you'll find.

Will it be the shortest? Or just whichever draw it finds first?

Consider this:

You find a drawing line. You save it so when the player responds you can move instantly.

He doesn't make the move you expect, so you have to search again.

Will you find the same drawing line, or another?

If it's some other, will it be the same distance or even longer?

You might not even *find* a draw this time. Because of time limits or hash table effects, you might not even see the draw this time. All because you were switching back and forth among drawing lines.

I don't have a clue how to use -1000 = X, -9988, ..etc for draws. Draws should be solvable even just with
DRAWSCORE = 0.

Rasjid

nczempin

Re: Draw scores

Post by nczempin » Fri Oct 05, 2007 10:47 pm

Carey wrote:
Chan Rasjid wrote:Carey wrote:-

It seems most of us are nor troubled with draws.
rep3 draw yes, but the thing is more about path-dependency and hashing the zero.
If you hash, then temporarily:-
1) try to use only zero and see if you can work things out.
2) hash 0 only for stalemate and other recognized material draws; DON'T hash any 0 from rep3 / fifty draws. Hash probing of a 0 from rep3 may no more be a rep3 as the path might be different.
See if this solved your problems.
I don't have hashing in my program yet.

Before I start adding any enhancements or refinements to the quality of the play, I want to get basic playing ability rock solid, along with all the xboard stuff, etc.

Once I get everything working properly and reliably, then I'll start doing the enhancements.

In my older programs I always added lots of features and extras and as a result I never got all the basic stuff nice and solid, or all the xboard stuff, etc. So this time I'm working in the other direction.
Just a side note from someone who's implemented both: If your goal is to get something rock-solid, why don't you start out with UCI? It's much easier to implement for an engine coder than WB.

Carey
Posts: 313
Joined: Wed Mar 08, 2006 7:18 pm
Contact:

Re: Draw scores

Post by Carey » Fri Oct 05, 2007 11:10 pm

bob wrote:
Carey wrote:Let me start off by saying that I'm an idiot. That seems to be the best explanation for why I'm having trouble with this.

I've written a few very minor chess programs over the years. I don't like playing chess, only programming chess, so I never really cared how well they played. I just had fun writing them.

Now I'm trying to make my new one work properly, so I now care about the little details.... like draw scores.

Solving one issue brings up another problem. Solving that one creates ye another, etc. My simple problem has ballooned into several issues and fixing them has become a problem all to itself.

By the time I do all the solutions, it's one heck of a kludge. A wart on a wart.

Obviously I'm doing something wrong. I'm missing something obvious.

When a solution to a simple problem becomes this complicated, something is wrong.


Issue 1)
If you do a draw score of zero, then the program can not tell the difference between a draw in 3 moves from a draw in 33 moves. One draw looks as good as another to the search, so it just picks randomly among them.
Before you go on, you should read the paper Harry Nelson wrote titled "The draw heuristic in Cray Blitz". We addressed this very issue,
I don't think I happen to have that article. I only have a few from back then. And I don't see it posted on your website.
but it has its own set of issues as you mentioned. We uses real scores that had a "gap" between 0 and 100 (pawn = 1000 in Cray Blitz), and we squeezed the draw scores into that range based on the ply where they are discovered. The problem is that draw scores (except for insufficient material) are path-dependent, and hashing ignores the path. So we were seeing scores like draw in 90 plies, even though CB had a max depth of 64 plies. We just accepted that, knowing that some draws were getting pushed out to appear that they happened beyond 100 plies, making them move into the real (non-draw score) area.
Well, hashing is its own problem. That the failure of the hash and too small of a draw window and not limiting its max draw score.

That's not relevant to the basic search issues I was asking about.

Admittedly I hadn't thought about hashing issues for draw scores. But I haven't added hashing to this program yet, so it's not relevant.

In cases where there are multiple draws at the root (and even in the search), the program picks randomly among them. Leading to the possibility of the program playing back & forth between them and never actually getting around to doing the draw. This is similar to why programs give a bonus to mates that are closer to the root than others.

There are a few infamous games where a program couldn't choose between several mates and ended up loosing the game. The draw problem seems to be the same issue.

The solution, of course, is to give a bonus to draws that are closer to the root. Say, 1000-Ply. (That assumes we have a 1000 point window around zero just for draw scores. Don't have to, it just makes this discussion easier.) That leads to issue 2.


Issue 2)
If you give a draw score a non-zero value, then that means a draw can have a negative score, after its been backed up the search and negated by NegaMax.

That seems to be absurd. It shouldn't be negative. A draw is a draw, no matter who plays it. It's not bad or good. It simply 'is'.

You can ignore that, but that leads to issue 3.


Issue 3)
If you allow a draw score to be negative, then that causes problems for the search. You end up with cases where shorter or longer draws appear better because of the sign.

Assume, for example, that we search ply 1 move 1 and discover that it has a draw score of "draw in 2 moves", or 9998 in this scoring system. That score backs up to the first ply and it becomes -9998 because of the NegaMax negation.
This is really a non-issue. if you reserve scores between -1000 and +1000 for draws, it will work, in that anything in that range is a draw.
Right.
Note that more distant draws for white are favorable according to your definition, so for black less distant (more immediate) draws are more favorable, and that is what will happen. But you still have the hash issue to deal with and that is significant.
Don't worry about the score issue. That was just off my head scores while I was writing the message.

I was more concerned about trying to be clear rather than making sure I had crossed by T's and dotted my I's.

But the issue still exists whether the score is that way or the other way.

But point taken. When I do the draw scoring in my program, I'll make sure they are right.

That sets Alpha to -9998 and beta is still at +Infinity.

Ply 1 move 2. It has a=-9998 & B=+Inf. It makes the move and recurses.

Ply 2 move 1. It has a=-inf & b=+9998. It makes the move and recurses.

Ply 3... alpha=-9998 & beta=+Inf.
We discover it's a draw. we return the score 1000-Ply = 9997

Back at ply 2 move 1, we negate that return score of 9997 to -9997. That becomes the best move.

There are no more moves at ply 2, so we back up to ply 1.

Back at ply 1, that score of -9997 gets negated by NegaMax and becomes 9997.

So, now at ply 1, we have a case where a draw in two moves has a score of -9998 and a draw in 3 moves has a score of 9997.


Because the draws happened on different plies, they got negated a different number of times and the result is the signs are different.

This causes the search to pick draws at odd plies over draws at even plies. In other words, with this method, it prefers a draw at ply 33 over a draw at ply 2.


That's not right behavior. A draw is a draw. It doesn't matter who does it. (ie: what ply.)
Not within the minimax framework. If a draw in 10 is good for me, a draw in less than 10 is better for my opponent, otherwise the min-max approach won't work at all. However, I think it better to ignore the idea with one exception that we use in Crafty explained below.

Draw in 10 moves vs. draw in 20 moves or some such is one thing.

But when you start getting into negative draw scores (because of NegaMax), then something isn't right.

That's the issue... Draws *aren't* bad. They simply are. They are the same to both sides.

Sure, one side may want to postpone it, and pick the furthest. That's to be expected and NegaMax works fine for that.

But when it start negating it, that's when other problems start to show up.

It's not like checkmate, where it's important who gets mated. A draw simply 'is'. It happens equally to both players.

A draw score should never be negative.


Issue 4)
Fixing #3 means not negating draw scores. Leaving draw scores always positive. Solves that. We have to keep a draw score always seperate from a heuristic score, hence the use of the 1000 point window around zero. We could use a flag passed back. That'd work just as well.

However, doing that fix also means we have to *always* be sure and not negate the draw scores. Including where we recurse and swap & negate the alpha & beta scores.




At this point I've got 3 fixes for what seemed to be a simple issue.

It's starting to get complicated and when a solution starts getting this complicated, you know something is wrong with your original thought. It's time to rethink. Or ask for help.


So, if something is wrong with my reasoning, then I must be an idiot because it looks like the reasoning is sound.

I've gone through the search process and looked at the bounds and what the scores can be (including fail-soft), and it sure looks to me like getting the right draw score is not an easy thing to do.


I know most programs don't bother with all this. (I haven't checked all of them, but a few. I don't really like browsing other programs to see how they do things, though.)

And I haven't seen any discussion about these kinds of problems. (I did browse through the CCC archives and didn't see anything there or on other web sites. I did, however, see a comment by Prof. Hyatt about draw scores getting very deep because of the hash table. But artificially limiting draw depth scores to 100 plies should solve that. You end up with issue 1 above, but for draws 100 plies away that's not really a big problem.)


So maybe the other programs just don't bother to fix the initial problem? Figuring that it's such a small problem that it's not worth the complicated fixes to make sure it always picks the best draw move?

Do they figure one draw is as good as the next, or do they not care the program will prefer draws at odd plies over even plies?


Or have I missed something obvious. (That's most likely...)


I looked for articles on dealing with exact vs. inexact scores, but all I found were a few references to some papers by Beal and to one by Slate.

This whole thing just doesn't seem to be discussed much.
The only exception I have to drawscore = 0 happens for two conditions:

(1) my draw score is dynamic (and the user can adjust it also as in "contempt setting".) But, in general, a draw score should reflect the preferred outcome based on your and your opponent's ratings. For crafty, against a weaker opponent, I have more "contempt" and will work harder to avoid draws because the drawscore goes more negative as crafty's rating goes above the opponent's rating. Ditto for the inverse case where I would prefer to draw a much higher rated opponent.

2. For endgame table draws, I would prefer a drawn KRP vs KR over a drawn KR vs KR ending. And often crafty gets to make that decision. In crafty a drawscore of 0 means drawn, material is even. A drawscore of +1 means draw, program is ahead in material. A score of -1 (-.01 of course) says the program is behind in material. The idea is that given the choice of two draws, I'd like to either take the one where my opponent has the chance to make mistakes and actually lose, or where he has to at least think and perhaps get into a bit of time trouble and then make a more serious mistake.

Alright. So if I understand you, because all draws are 0 (with the above exceptions), you are willing to allow a draw in 3 moves to have the same backed up score as a draw in 33 moves?

You don't care whether you find the shortest draw or not?

You accept that in a game that if you play a move with a draw score, that for your next move you may not be able to find the same drawing line? That you might pick a longer drawing line?

To me, that seems almost as dangerous as the mate problem that made CoKo III loose because it had so many choices. It passed up a mate in 1 to try for other mates. And kept going back & forth.

I don't dispute your program's ability. If I'm lucky, my program might play half as well as yours by the time I'm done.

You are the better programmer. You are the better chess player. You have far more chess programming experience than I do.

But it still seems like it's wrong.

Carey
Posts: 313
Joined: Wed Mar 08, 2006 7:18 pm
Contact:

Re: Draw scores

Post by Carey » Fri Oct 05, 2007 11:15 pm

nczempin wrote: Just a side note from someone who's implemented both: If your goal is to get something rock-solid, why don't you start out with UCI? It's much easier to implement for an engine coder than WB.
I never thought about it until you just mentioned it...

My old programs were plain ordinary text programs. Much like GNU Chess. (In fact, mine were based on Stanback's public domain program that became GNU chess.)

So it just seemed natural to keep it like it was and add just enough to make xboard happy.

(And a friend had told me about Arena chess interface, and I was playing with that and a few xboard chess engines.)

When I started my new one, I just automatically did the xboard route.

UCI, huh.... Hmmmm... Maybe I'll go look at the specs.

Thanks.

nczempin

Re: Draw scores

Post by nczempin » Fri Oct 05, 2007 11:44 pm

Carey wrote:
nczempin wrote: Just a side note from someone who's implemented both: If your goal is to get something rock-solid, why don't you start out with UCI? It's much easier to implement for an engine coder than WB.
I never thought about it until you just mentioned it...

My old programs were plain ordinary text programs. Much like GNU Chess. (In fact, mine were based on Stanback's public domain program that became GNU chess.)

So it just seemed natural to keep it like it was and add just enough to make xboard happy.

(And a friend had told me about Arena chess interface, and I was playing with that and a few xboard chess engines.)

When I started my new one, I just automatically did the xboard route.

UCI, huh.... Hmmmm... Maybe I'll go look at the specs.

Thanks.
UCI is "stateless", which means much of the paperwork is taken care of by the GUI. Once your engine gets stronger, you will want to actually keep some state (and UCI doesn't preclude you from doing so, especially with UCI2---WB forces you to keep a lot of state), but for starting out, you will want to concentrate on the engine itself as much as possible.

Another nice thing about UCI is the UCI engines ligue. No matter how weak your engine, they will run a gauntlet against other UCI engines within a day or so of the release of your engine. Once its approximate strength is determined (very inaccurate for weaker engines, because the gauntlet is against the stronger engines), they participate in occasional tournaments. With WB, there is Olivier Deville's ChessWar/OpenWar, which is open to both UCI and WB, but the turnaround is much slower.
Other than that, once your engine reaches a certain strength, more testers will pick it up.

The one thing I wish was in UCI is a mechanism to see who you're playing, to adjust the "contempt factor" Bob mentioned (it's like knighthood if Crafty has you in its contempt list :-)).

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

Re: Draw scores

Post by Uri Blass » Sat Oct 06, 2007 1:40 am

Carey wrote:Let me start off by saying that I'm an idiot. That seems to be the best explanation for why I'm having trouble with this.

I've written a few very minor chess programs over the years. I don't like playing chess, only programming chess, so I never really cared how well they played. I just had fun writing them.

Now I'm trying to make my new one work properly, so I now care about the little details.... like draw scores.

Solving one issue brings up another problem. Solving that one creates ye another, etc. My simple problem has ballooned into several issues and fixing them has become a problem all to itself.

By the time I do all the solutions, it's one heck of a kludge. A wart on a wart.

Obviously I'm doing something wrong. I'm missing something obvious.

When a solution to a simple problem becomes this complicated, something is wrong.


Issue 1)
If you do a draw score of zero, then the program can not tell the difference between a draw in 3 moves from a draw in 33 moves. One draw looks as good as another to the search, so it just picks randomly among them.

In cases where there are multiple draws at the root (and even in the search), the program picks randomly among them. Leading to the possibility of the program playing back & forth between them and never actually getting around to doing the draw. This is similar to why programs give a bonus to mates that are closer to the root than others.
No

This is not similiar.

I see no way that the program lose the game in case of not choosing a losing move.

In case of using hash tables I can see how a program can miss a win because of delaying mate but in your case when you do not have hash tables it is only a cosmetic thing and you practically do not need to have different scores for different distance to mate.

Even if your program delay the mate then it is clear that it will not be able to do it always because of the 50 move rule so it will have to mate(I assume that drawing moves lead to draw and I assume no pruning based on hash).

Uri

Post Reply