Draw scores

[Uri Blass]

It is *only* guaranteed if you can find the draw on the next move. And assuming you pick the same draw.

If that is true, you have a search bug.

Time control could do it.

On that next move you may not have as much time as you did before. And because of a delaying / wasted move, the drawing line is now longer. Meaning it may be a little harder to find.

I don't score "non-forced draws" as draws. If a draw is not forced, I don't do anything at all in fact. So I am certain that if my search says draw, it is a draw, whether it is on the next move or 30 moves into the future. To believe otherwise would mean my search is worthless.

I certainly wouldn't say it's worthless. Too much evidence to the contrary.

But in spite of what you say, I still believe it to be fundamentally broken.

Not fatally, but still fundamentally broken when it comes to draws.

Situations where you have multiple draws like I've been discussing don't occur too often in a program as strong as Crafty, and only slightly more often in more basic programs.

We obviously have a difference of opinion here. (shrug)

Prof. Kozdrowicki would certainly disagree with you there. And he has the game score & game loss to prove it.

This is not what happened to him. He had two bugs.

(1) he could not differentiate between a mate on the move, and a mate in 2 or 3 or whatever. His search returned "MATE" for any mate found regardless of how deep.

(2) Coko was a selective searcher, and by finding the forced mate, it improperly pruned other parts of the tree. Genie enventually beat him because he kept finding a mate in 2, rather than playing the mate in 1, but the mate in 2 was not correct near the end of the game. If it had been, he would have found the mate rather than losing. But selective search programs in 1970 had severe search errors built in... we all did.

Well, the history books wrote it down as #1.

As for CoKo 3 being a selective search program... I don't think that was the problem.

Don't forget, it did have a specialized mate finding routine, so it didn't have to use its main search.

However, even if it had used it's main search, there is no way it could have declared it to be mate, without actually checking the other branches to decide if it was a mate or not.

Now, assuming it did have a bug and improperly decided that a Mate in 2 existed, then that still goes back to #1.

1)Note that correct selective search should not miss mates.

I also use selective search when the remaining depth is small but only in the right conditions and conditions when mate is a candidate score for one side means that selective search for the opponent moves is not allowed(usually both alpha and beta are not mate scores so selective search when the remaining depth is small is allowed for both sides).


2)If we talk about history
then it is clear that not the bug of having the same score for different mates caused Coko3 to lose.

Coko3 lost because of the following mistake that cannot be explained by that bug

[D]r7/pp6/2p5/8/1P4p1/2Q1P3/k1K2P1P/5B1q w - - 0 44 am Kc1

Even selective search that consider only captures and checks for black could not explain missing Qxf1+(the only possible explanation for missing it by not searching deep enough is if you search only 1 ply forward with no capture search and computers at that time were not so slow not to be able to search 1 ply forward with normal qsearch).

I do not know what was coko3's bug and maybe it did not see that Qxf1 is check in the search and calculated Kc1 Qxf1+ Qb2 mate.

Uri

[jwes]

Isn't it just as likely that the program will find something better than a draw rather than something worse than a draw if it chooses the delayed draw?

[bob]

I think that you care too much about hypotetical case that never happens in practice based on my experience.

You could be right.

If you are in worse position then
In most cases you are going to see the faster draw first.

Considering the fact that you do not even use hash tables then the only way not to see the fastest draw first is because of some extensions or pruning and I cannot see it happens again and again.

I'm not using hash tables *yet*.

It's not because I wont or can't or don't know how.

It's because I made a deliberate design decision to do nothing to improve the play quality or performance until I get the basic code rock solid and all of the xboard stuff implemented.

I haven't even run a profiler on my code yet.

When I get all the basics nice and solid, then I'll start adding a few extras. Like hash tables. And then I'll test stuff to make sure that all of that is done right and solid.

Then I'll probably start on the move ordering. (Right now, I'm just doing captures & history. I haven't even added a GenCaps() routine yet because that would be extra code that isn't needed to get the basic program solid.)

And so on.

I've done it the other way around before. Adding features that are exciting and fun. And I did have fun writing it. Lots of fun. But I ended up with a program I wasn't happy with and was never really complete or reliable.

Cases when you see a draw and miss it later may happen but it should be rare and they may happen also if you prefer faster draws(you can see

They are certainly going to be rare.

But it just seems to me that if you know something isn't right (draw's at zero), then you shouldn't do it, even if you know other programs do it and they work fine.

Basic logic shows pretty clearly that a draw score of zero just isn't the right thing to do, as far as the basic search is concerned, and the way NegaMax / MiniMax work.

Hyatt, and others have made it pretty clear that he feels it's "Good Enough". And it probably is. Still flawed, though.

Let me point out that _everything_ you do is going to be flawed. Your search will always lack a ply or more in critical positions. Your evaluation terms are _all_ going to be flawed, because while a knight on E5 (white) is usually good, there are plenty of positions where it is bad. So we end up with many "flawed" pieces in our chess engines, and there is not a thing that can be done about them.

This is what I call "the classic beginner mistake"... getting hung up on making everything 100% correct, when that is impossible.

draw in 18 plies that is the shortest draw after long ponder on the opponent move and after your opponent move miss draw in 16 plies because you have no time to finish 16 plies)
I see no reason to care about something that may happen in 1 out of 1000 games.

You have better ways to try to improve your program and I suggest that you simply return 0 for draws.

Uri

I probably will. Not because it's the right thing to do, but because doing it the right way, the proper way, the correct way, causes too many side effects that make the basic search code ugly.

I can't think of any clean way to do it right. It always adds code & complexity that distracts from the basic search algorithm.

[bob]

Isn't it just as likely that the program will find something better than a draw rather than something worse than a draw if it chooses the delayed draw?

An important concept. If you are wrong in some random way, the result can be just as good as it is bad. And for cases where you really can't control how right or wrong you are, it is better to go as simple as possible for other reasons.

[GothicChessInventor]

This might sound strange, but I had a problem of a similar nature when working on my checkers program. Tablebases in checkers (we call them "databases") are responsible for giving programs a tremendous amount of strength, since you can hit them from a search in the initial position.

The problem I had was: since I have over 8 trillion positions, and maybe 3 trillion of them are draws, when heading for a drawn tablebase position, what differentiates an "easy draw" from a "hard draw"?

The solution was what I called The Aggressive Draw Heuristic.

I created a tablebase composed entirely of draws, using values 0-255 to greatly stratify the values. The algorithm was basicaly:

score = (# of legal moves that lose)/(# of moves that draw) x some constant, where # of moves that draw >= 1.

For each drawn node, I could count the number of legal moves leading to it that did not draw (by definition, there was no "win") and the number of moves that would lose. For the computer's side, we want to put the human into a position where he has the most ways to "mess up", so we want positions with large scores (say 100 * number of moves that lose/number of moves that save the draw.)

For each possible enumeration, I used an idex. For example, 2 legal moves with 1 move that loses and 1 move that draws = 0, 2 legal moves with 2 move that draw = 1, 3 legal moves with 1 move that loses and 2 moves that draw = 2, etc., until I fill up all 256 entries for one byte.

So, I would pass the counts into a 2D matrix, like draw_score_array[][], and out comes the index, 0...255. I then pass the index to another array, such as aggressive_draw_score[], and then I give that to the search engine.

So, say your program has the choice of for the human into the tablebase where there are 12 legal moves and only 1 leads to a draw, or a position where there are 8 legal moves and 7 of them draw.

This algorithm will return a high score for the computer for the 12/1 scenario (yet all scores are less than the value of one checker, which was worth 3000 in my scheme.)

The idea being, in the vast sea of draws that are hit during the search, the program will be able to lead the human down a path where it is harder and harder to maintain a draw.

In your case though, you might want to do something completely different.

But say you did want to stratify your scores in some way. Here is what you can do:


1. Have your evaluation function only return odd numbers for scores.
2. That means you can use the domain of "all even numbers" to represent your draws. Code them as you see fit, and see what happens.

[Carey]

Isn't it just as likely that the program will find something better than a draw rather than something worse than a draw if it chooses the delayed draw?

Quite possibly.

It's just the horizion problem.

You can't search forever, so you have to decide when to stop. That's basically decided by how much time you have left, how far down in material you are, and whatever heuristics you've programmed in.

There's never a guarantee, of course. But if you are down a queen or so, tthen a draw looks pretty darn good. And it's probably in your best interest to take the quickest one you can find.

Delaying it, hoping for your oponent to make a mistake (Hyatt's "Meat makes mistakes") is a little foolish unless your program is really strong and your opponent is under time pressure.

[Carey]

Let me point out that _everything_ you do is going to be flawed. Your search will always lack a ply or more in critical positions. Your evaluation terms are _all_ going to be flawed, because while a knight on E5 (white) is usually good, there are plenty of positions where it is bad. So we end up with many "flawed" pieces in our chess engines, and there is not a thing that can be done about them.

This is what I call "the classic beginner mistake"... getting hung up on making everything 100% correct, when that is impossible.

Correct as far as you go.

1) During the search itself, the program sees *everything*. That's why classic selective search (Mac Hack VI) went out of fashion. Later selective search programs even do at least a few plies of full width.

Enhancements such as null moves, hash tables, etc. interfere with that, but that's a seperate issue.

2) Talking about the evaluation terms being flawed is mostly definetly correct! I am very VERY aware of that. That's one of the reasons why I want to keep the draw scores.

The search is having to deal with both inexact & exact scores. The basic minimax / negamax isn't designed for that. That's why Beal, Slate, and others have tried to develop algorithms that do know about how reliable a score is.

3) When you do have exact information (draw or mate), then that is precious information. It's rather foolish to throw away information that you might be able to use.

Think about it, you have exact knowlege how a move can to end... Why would you want to throw away that information? You may choose to ignore it and search deeper (possibly changing that draw into a win or loss or unknown), but at least at that point, you know something for sure.


I'm not fixated on making everything 100%. I know null moves & hash tables will introduce inaccuracies and even errors. I'm not stupid.

But for the basic search, when you do have some hard earned knowledge, why would you want to throw it away? You can make a decision (to take the draw or mate or not take it) knowing 100% what the outcome will be.

For mate, the choice is pretty simple. It's "obvious".

But for a draw, you still have the option. Whether you choose to or not is up to you.

If you choose to take the shortest draw or delay it and hope the opponent makes a mistake, or whatever, is up to you. But at least you know what the outcome will be and can make an informed choice.

Instead of making random moves. Really.... RANDOM moves? That's basically what you are advocating. Then why do you even bother doing a search in the first place? Crafty doesn't randomly pick between the first two moves. It picks the first move. The one it decides is 'best'.

How is chosing to pick a closer draw any different from that?

I'm advocating knowing which draw is best so you can choose to take it.

Unless the search later says otherwise (mate etc. found at deeper searches), the closer draws are better than deeper draws because it reduces the possibily of errors made by the horizon effect in the current search and time control limited searches later.


As I've said before... we obviously have differences of opinion on this.

I do respect your experience in computer chess and am well aware that you know a lot.

But I also know that the field of computer chess has lots of different ideas and implementations. Often new ideas are wrong, but sometimes old ideas are wrong. And sometimes both work but are simply different.

I happen to believe something you disagree with. (shrug.) I can live with that.

As I've already said, I probably wont implement this because it clutters up the code too much.

[Carey]

Even selective search that consider only captures and checks for black could not explain missing Qxf1+(the only possible explanation for missing it by not searching deep enough is if you search only 1 ply forward with no capture search and computers at that time were not so slow not to be able to search 1 ply forward with normal qsearch).

I do not know what was coko3's bug and maybe it did not see that Qxf1 is check in the search and calculated Kc1 Qxf1+ Qb2 mate.

Uri

Well, all I can really say is that it has always been blamed on the mate bonus issue.

Supposedly even Kozdrowicki himself said that was the issue.

I don't have the source to CoKo 3 or 4 (he never wrote back), so I can't examine the source to make any definite statements.

All I can say is that's what the books say, and that supposedly even Kozdrowicki himself blamed it. (shrug)

[bob]

Let me point out that _everything_ you do is going to be flawed. Your search will always lack a ply or more in critical positions. Your evaluation terms are _all_ going to be flawed, because while a knight on E5 (white) is usually good, there are plenty of positions where it is bad. So we end up with many "flawed" pieces in our chess engines, and there is not a thing that can be done about them.

This is what I call "the classic beginner mistake"... getting hung up on making everything 100% correct, when that is impossible.

Correct as far as you go.

1) During the search itself, the program sees *everything*. That's why classic selective search (Mac Hack VI) went out of fashion. Later selective search programs even do at least a few plies of full width.

There are two dimensions to a search space. Full width certainly sees everything in the "breadth" dimension, but it lacks a _lot_ seeing everything in the "depth" dimension. Selectivity helps with depth, hurts with breadth. We are all doing trade-offs today as a result.

Enhancements such as null moves, hash tables, etc. interfere with that, but that's a seperate issue.

2) Talking about the evaluation terms being flawed is mostly definetly correct! I am very VERY aware of that. That's one of the reasons why I want to keep the draw scores.

99.99999% of the positions you search have nothing to do with draws, and they all have errors associated with both the search space and the evaluation terms. The draw score issue is such a tiny fraction it is not worth the effort. And once you add hashing, which you have to do eventually to even approach reasonable skill levels, draw scores won't work correctly anyway...

The search is having to deal with both inexact & exact scores. The basic minimax / negamax isn't designed for that. That's why Beal, Slate, and others have tried to develop algorithms that do know about how reliable a score is.

3) When you do have exact information (draw or mate), then that is precious information. It's rather foolish to throw away information that you might be able to use.

Think about this question for a minute before I go on:

"what causes your program to accept a draw?"

After thinking about that, the only thing that can possibly convince it to take a draw is your positional evaluation, which has to convince the search that the draw is better. But the evaluation is full of holes. It really is a waste of time to worry about this issue...

Think about it, you have exact knowlege how a move can to end... Why would you want to throw away that information? You may choose to ignore it and search deeper (possibly changing that draw into a win or loss or unknown), but at least at that point, you know something for sure.

Problem is, your draw score is _not_ exact. You just think it is best, and that one side of the other will force it to happen. But it is a _long_ way from "exact knowledge". And I do mean a _long_ way...

I'm not fixated on making everything 100%. I know null moves & hash tables will introduce inaccuracies and even errors. I'm not stupid.

But for the basic search, when you do have some hard earned knowledge, why would you want to throw it away? You can make a decision (to take the draw or mate or not take it) knowing 100% what the outcome will

The problem is your basic premise is wrong... Your evaluation has great influence on the program actually accepting a draw score. And that is so inaccurate, the draw score is no better.

For mate, the choice is pretty simple. It's "obvious".

But for a draw, you still have the option. Whether you choose to or not is up to you.

You are slowly working yourself into the classic corner, and you are about to "see the light". Why do you _choose_ to take a draw? Because otherwise your evaluation says "this is worse than equality for my side" and minmax chooses the best score for the side on move? But what makes the draw score best? The evaluation of all the non-drawn positions...

If you choose to take the shortest draw or delay it and hope the opponent makes a mistake, or whatever, is up to you. But at least you know what the outcome will be and can make an informed choice.

Instead of making random moves. Really.... RANDOM moves? That's basically what you are advocating. Then why do you even bother doing a search in the first place? Crafty doesn't randomly pick between the first two moves. It picks the first move. The one it decides is 'best'.

Choosing between a long draw and a short draw is not the same as randomly choosing moves. If the draw is real, and the opponents are equal, there is absolutely no advantage to take either the shortest or longest draw. If you believe your opponent can make mistakes, then the longer draw is better, so long as it is the draw that offers the most significant chance for him to make mistakes. Otherwise it makes no difference at all, since a draw counts 1/2 point no matter how many moves it takes to reach...

How is chosing to pick a closer draw any different from that?

I'm advocating knowing which draw is best so you can choose to take it.

\

You have two moves that evaluate as 0.0. How can one be better than the other, since by definition both evaluate to dead equality?

Shorter mates are preferred, only to prevent repetitions from turning a mate into a draw. But the shortest draw is certainly not the best plan if your opponent is a human, or if it is a computer of significantly lower skill than yours.

Unless the search later says otherwise (mate etc. found at deeper searches), the closer draws are better than deeper draws because it reduces the possibily of errors made by the horizon effect in the current search and time control limited searches later.


As I've said before... we obviously have differences of opinion on this.

I do respect your experience in computer chess and am well aware that you know a lot.

But I also know that the field of computer chess has lots of different ideas and implementations. Often new ideas are wrong, but sometimes old ideas are wrong. And sometimes both work but are simply different.

I happen to believe something you disagree with. (shrug.) I can live with that.

As I've already said, I probably wont implement this because it clutters up the code too much.

[bob]

Even selective search that consider only captures and checks for black could not explain missing Qxf1+(the only possible explanation for missing it by not searching deep enough is if you search only 1 ply forward with no capture search and computers at that time were not so slow not to be able to search 1 ply forward with normal qsearch).

I do not know what was coko3's bug and maybe it did not see that Qxf1 is check in the search and calculated Kc1 Qxf1+ Qb2 mate.

Uri

Well, all I can really say is that it has always been blamed on the mate bonus issue.

Supposedly even Kozdrowicki himself said that was the issue.

I don't have the source to CoKo 3 or 4 (he never wrote back), so I can't examine the source to make any definite statements.

All I can say is that's what the books say, and that supposedly even Kozdrowicki himself blamed it. (shrug)

All you have to do is try it. Modify crafty (or your program) to always return mate in 3, no matter what. And see what happens. You won't play a real mate in 3 if your opponent mates you the next move, you will find any move to prevent that, which would be the mate in 1 move.

They really did have two bugs. The search bug would never have been seen had it not been for the all mates are equal primary bug.