TT bug? or something else

[amanjpro]

So, I tried going back a few moves and couldn't reproduce the issue.

What I thought was happening was:

- In root node, first move is hashmove, and it finds the bestmove
- Other nodes are tried, and one of them is causing beta-cutoff (in this case, Qe5). And since the code above updates PV when the score is higher than bestscore, and before betacutoff is tried, it updates PV to that move...

Not sure if this is the scenario, but I don't have a better explanation than that, gotta think about it harder

Well, this 'scenario' is how alpha-beta with iterative deepening works in general. You start with the move that was best in the previous iteration, and when you find a better one you switch to that. Of course in the root you cannot have a beta cutoff, as beta is +infinite there. Unless you would use aspiration, and then you would re-search after enlarging the window.

Qe5 had a poor score. It can only have superceded Qxg8 if that had an even lower score. And this is obviously wrong, as this line is about a Queen better.

I understand what you are saying, and I agree with you.

But imagine, when Qe5 was searched, beta cutoff happened (I have aspiration window), given the below code:

Code: Select all

	if score > bestscore {
			// Potential PV move, lets copy it to the current pv-line
			e.innerLines[searchHeight].AddFirst(move)
			e.innerLines[searchHeight].ReplaceLine(e.innerLines[searchHeight+1])
			if score >= beta {
				e.TranspositionTable.Set(hash, move, score, depthLeft, LowerBound, e.Ply)
				// e.AddKillerMove(move, searchHeight)
				e.AddHistory(move, move.MovingPiece(), move.Destination(), depthLeft)
				return score
			}
			bestscore = score
			hashmove = move
		}

first thing is done, is update PV, then check if score has beaten beta! and viola it has! so our PV is wrongly updated (wrong bestmove is returned).
Or maybe I am missing something?

[hgm]

If you 'return' anything from the root after a beta cutoff this is a bug. You are supposed to re-search with enlarged window, and keep doing that until beta is so large that the score of the move is no longer above it.

Note that you cannot have a PV after a beta cutoff in the first place. That is, you have only the cut move. There is no reply, as the child after that move failed low. So if you did see a longer PV you can be sure that it has not been causin a beta cutoff. Or that you have a bug that creates fake PVs out of nothing.

None of this should have the slightest relevance for the issue at hand, though. Qe5 should not score above alpha, if Qxg8 was searched before it. So it should not lead to updating the PV. And the gain of a Queen after Qxg8 is immediate; it should have been noticed even at d=0, and should thus have been PV move from the very first iteration, always setting alpha to around +500.

[Henk]

I remember also having aspiration search causing blunders some time ago. Also had to do with time is up event and returning the wrong move.

Maybe If it searched a move in a reduced window, can't complete a research because time was up but still returning that move as best move.


Most stupid way to be sure is just disable aspiration search. Play many games and see if it still blunders. If not you can be sure it was aspiration search.

You can only return a partial searched move if it was the iterative deepening move. Also watch out not to store incomplete results in TTable when time is up.

[Henk]

Edit should be:

Maybe If it searched moves in a reduced window, can't complete a research because time was up but still returning a best move of that search.

[amanjpro]

Also watch out not to store incomplete results in TTable when time is up.

Wow this is a very likely reason, I have no check for this prior to inserting data in tt... Worth adding it. Thank you

[mvanthoor]

Wow this is a very likely reason, I have no check for this prior to inserting data in tt... Worth adding it. Thank you

Don't you have a check at the beginning of the alpha/beta function, which cuts the search short if the time is up? (Even before the move loop.) That should be enough... You shouldn't be breaking IN the move loop, because then your move may not be finished.

[amanjpro]

Wow this is a very likely reason, I have no check for this prior to inserting data in tt... Worth adding it. Thank you

Don't you have a check at the beginning of the alpha/beta function, which cuts the search short if the time is up? (Even before the move loop.) That should be enough... You shouldn't be breaking IN the move loop, because then your move may not be finished.

Let's say:

- I am in the node 1, call node 2 (child node),
- Time is up, return early (set signal that the search was abrupt)
- In node 1, I see that node2 returned value A, and this is beta cutoff, I have a choice to make, do I trust it, or not, if I do then I insert it in TT, if not then I skip. And, since node2 was stopped abruptly, I should actually skip it, as the returned value doesn't mean much

[mvanthoor]

Let's say:

- I am in the node 1, call node 2 (child node),
- Time is up, return early (set signal that the search was abrupt)
- In node 1, I see that node2 returned value A, and this is beta cutoff, I have a choice to make, do I trust it, or not, if I do then I insert it in TT, if not then I skip. And, since node2 was stopped abruptly, I should actually skip it, as the returned value doesn't mean much

I have no provisions for this... I have a break at the beginning of Alpha/Beta where it returns when time was up. The position might end up in the TT (don't know; I'll have to think about that, as this happens within the move loop), but the move that will be played is the one from the previous iteration. The iterative deepening function saves the first PV-move (best_move) from the last completed iteration, and returns this when the time is up.

Even though I've seen Rustic throw away games because of not knowing anything positionally, and having it seen being outplayed by an engine that can just think deeper, I've never seen it make obvious blunders like the one in this thread. (But I have to state that I did not play through every game the engine ever played.)

[amanjpro]

Let's say:

- I am in the node 1, call node 2 (child node),
- Time is up, return early (set signal that the search was abrupt)
- In node 1, I see that node2 returned value A, and this is beta cutoff, I have a choice to make, do I trust it, or not, if I do then I insert it in TT, if not then I skip. And, since node2 was stopped abruptly, I should actually skip it, as the returned value doesn't mean much

I have no provisions for this... I have a break at the beginning of Alpha/Beta where it returns when time was up. The position might end up in the TT (don't know; I'll have to think about that, as this happens within the move loop), but the move that will be played is the one from the previous iteration. The iterative deepening function saves the first PV-move (best_move) from the last completed iteration, and returns this when the time is up.

Even though I've seen Rustic throw away games because of not knowing anything positionally, and having it seen being outplayed by an engine that can just think deeper, I've never seen it make obvious blunders like the one in this thread. (But I have to state that I did not play through every game the engine ever played.)

Well, I wouldn't have seen it in Zahak if I weren't programming for King-Safety. I was looking in the many thousands of games, to see if there is a short win that the "dev" version has over "master" version, and found the issue. Then was lucky to notice it against Rustic too...

I believe this is a rarity, and happens very rarely, but it can happen. We basically fool ourselves, by storing eval in TT attach it a depth, but in reality it might not have been searched at all...

I added a guard, and running a match, the version with guard is some 10 elo points ahead, but not sure if it is there to stay, the match is still early:

Code: Select all

Score of zahak_next vs zahak_master: 169 - 152 - 223  [0.516] 544
...      zahak_next playing White: 93 - 67 - 113  [0.548] 273
...      zahak_next playing Black: 76 - 85 - 110  [0.483] 271
...      White vs Black: 178 - 143 - 223  [0.532] 544
Elo difference: 10.9 +/- 22.4, LOS: 82.9 %, DrawRatio: 41.0 %
Started game 547 of 2000 (zahak_next vs zahak_master)

[hgm]

What I always do for cold-turkey timeout is return immediately after UnMake(). Then an interrupted node does not get to the code for storing anything in the TT.

If you abort at the start of a node, nodes that are already busy while the timeout occurs do store their result in the hash, but because some of their daughters (those called after the timeout occurred) will return nonsense, their result will be nonsense nevertheless. And it will get stored in the TT. Now this is not very harmful, as the number of nodes that are busy at any time is just the search depth. So you perhaps get 20 corrupted TT entries, and the chances this has any effect on a future search is very small.