Draw scores

[Carey]

Your fear that the program is going to see draw and miss it later has no rational basis because usually if it can see a draw in move X then you can expect it also to see the draw in move X+1 because you need less search depth at move X+1.

Not when you start throwing in time control issues.

If you can guarantee you'll always have enough time or are searching to a fixed depth this it wont be an issue.

We do not know what was Coko's problem to find the mate but I suspect that it was simply a bug that caused Coko to believe that there is mate when there was no mate or caused Coko to play too fast.

Nope, we do know why. It was admitted & discussed. That became a classic in computer chess because of that. There have been lots of games lost due to bugs that aren't even remembered.

He simply did not have bonsuses for closer mates. So it picked at random.

Then with the shallow search depths they were using way back then, it didn't take much to push the mate over the horizion.

That's not to say the program was bug free.

But even Kozdrowicki was saying it was the mate bonus issue that caused the loss.

Funnily enough, it was just a few hours before that when he entered in the famous Levy bet. After the loss, he was supposedly heard muttering about making a bad bet....

finding mate at move X and missing it at move X+1 to lose the game is not something that you can normally expect.

Uri

I think it doesn't effect most programs because most programs don't get into draws. They simply aren't in positions where there are multiple draws for them to randomly pick among.

There's usually one drawing move at the root, and that's considered best.

[Uri Blass]

Your fear that the program is going to see draw and miss it later has no rational basis because usually if it can see a draw in move X then you can expect it also to see the draw in move X+1 because you need less search depth at move X+1.

Not when you start throwing in time control issues.

If you can guarantee you'll always have enough time or are searching to a fixed depth this it wont be an issue.

We do not know what was Coko's problem to find the mate but I suspect that it was simply a bug that caused Coko to believe that there is mate when there was no mate or caused Coko to play too fast.

Nope, we do know why. It was admitted & discussed. That became a classic in computer chess because of that. There have been lots of games lost due to bugs that aren't even remembered.

He simply did not have bonsuses for closer mates. So it picked at random.

Then with the shallow search depths they were using way back then, it didn't take much to push the mate over the horizion.

That's not to say the program was bug free.

But even Kozdrowicki was saying it was the mate bonus issue that caused the loss.

Funnily enough, it was just a few hours before that when he entered in the famous Levy bet. After the loss, he was supposedly heard muttering about making a bad bet....

finding mate at move X and missing it at move X+1 to lose the game is not something that you can normally expect.

Uri

I think it doesn't effect most programs because most programs don't get into draws. They simply aren't in positions where there are multiple draws for them to randomly pick among.

There's usually one drawing move at the root, and that's considered best.

Again you may not be able to reach fixed depth but usually even reaching depth that is 2 plies less than the previous move is enough if the first 2 moves of the pv are not extended.

I agree that Kozdrowicki did not have bonus for shorter mate but I am unsure if it was the only reason for the loss(it is possible that he simply had another bug).

Movei that use hash does not have correct mate scores and may claim mate in 8 when the position is only mate in 10 but practically I still did not see movei miss a mate from a winning position(the problem of wrong mate scores is only with hash and I did not see movei has wrong mate score without hash).

Same is correct also for glaurung so I think that from practical point of view if you do not have strong program you should not care about the problem of correct mate score or of draws that you can miss because all draws are the same.

Uri

[hgm]

Well, the delayed-loss bonus exactly addresses the problem of path length to the final score, which minimax completely ignores.

To give a short summary:

If the search tells you that you are going to win material or position (score is higher than the current evaluation, so this applies also for reaching a stalemate from an inferior position) you want to take a short path to it. If you are going to experience a score drop (current evaluation, or QS score if the position is non-quiet, is better than the score from a deeper search), you want to delay the point where this actually happens as long as possible.

This can be reached by ameliorating scores that are below eval (or QS), by adding a small bonus to them. In a very long path to the point where the actual gain takes place, the losing side would add this bonus on every ply, but the gaining side would add nothing. So the score gets devaluated in the direction of the losing side.

By tuning the magnitude of the bonus you can affect how much positional advantage the engine is willing to sacrifice for less risky play. (Based on the idea that the side who is going to lose material usually has more options to sarifice his material he is going to lose anyway, than that the side playing to the win can find alternative targets, and that delaying the gain thus involves a certain risk.) If you make in infinitesimally small, it only acts as a tie breaker between exactly equal scores. But if you make it sizable, it really starts to balance the urgency against possible extra advantages it might achieve by delaying the gain.

[bob]

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. 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.

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.

[bob]

this is not exactly right. His lack of a score to differentiate between mate in N and mate in N+1 was a problem. But at the end of the game, his selective search still "thought" it had a mate in 2, but it pruned away the move by the opponent that mated him instead...

Had he had the mate bonus based on the ply, he would probably have won. But by not having it, he prolonged the game until a different bug caused him to lose.

He was in no time trouble or anything else..

[Chan Rasjid]

Hello Carey,

I now know what you mean,that the side forcing a draw picking draw-in-33 over draw-in-3 may miss it for various reasons, like time failure,etc..valid and accepted. I'll still rather not worry about it too much and still insist on DRAWSCORE = 0. Just make sure your program has a 300ELO advantage over the others!

Rasjid

[Carey]

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.

[Carey]

Hello Carey,

I now know what you mean,that the side forcing a draw picking draw-in-33 over draw-in-3 may miss it for various reasons, like time failure,etc..valid and accepted. I'll still rather not worry about it too much and still insist on DRAWSCORE = 0. Just make sure your program has a 300ELO advantage over the others!

Rasjid

I was meaning that if the search keeps going on (as it often does when it discovers a possible drawing line, in case it may find it can be a mating line), that if it does discover a couple of lines that draw, to the program there is no difference between a quick draw or a very delayed draw.

The more you delay, the more chances that the program may get into time trouble or decide on some other even more delaying move line and then get into time trouble.

And then because of that time trouble, have to do a shallower search and possibly miss that drawing line it had been following. And then making some other non-drawing move.

Will it happen.... the odds are against it, especially if your program is strong. The stronger it is, the less like it would happen. Strong programs usually don't draw, and the condition is somewhat rare to begin with, so the odds are very much against it.

But it can still happen. The possibility is still there, lurking in the basement of the program.


I'm not actually *worrying* about it. I came in here and asked because I was doing a simple change that I believed (and still believe) to be correct, and the complications kept building. So I asked for help.


As for me making sure my program is 300elo stronger... (laugh) I'm such a terrible chess player that the odds are good my program will on the wrong end of that 300 elo difference! (grin)

[Carey]

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.

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]

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.

Possible, but _very_ unlikely. We are now two plies closer to the draw...

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.

Right. But the "books" are not always right. I was there. I talked to Ed many times over the next 10 years. Just always finding a forced mate in 2 would either win or draw. But coko was highly selective, and that was its undoing. The mate score bug kept it from winning, but pruning away the opponent's promotion to miss the loss was the real problem that caused them to lose rather than just check over and over until they repeated.

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.

Yes, but _everything_ in Coko was selective. I used to have the source for Coko IV, and ran it on our computer at USM to test my early versions of blitz against. Its selective search was _really_ problematic. It played brilliant moves, and then horrible moves...

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.

Of course there was. Forced mates were selectively analyzed. You just try the opponent moves that appear to have something to do with the forced mate or its prevention. But it totally overlooked their advancing that pawn square by square until they were actually losing. It just pruned that pawn push away completely. Coko IV had the same problem, except that the mate scores were dependent on the ply. But the selective part of the search was, as all selective programs were, a tad light on doing this part of the search properly.

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

No argument there. But playing a mate in 2 over and over will, at worst, draw. Unless one selectively prunes away opponent moves that can actually cause you to lose...