Engine doesn't search past drawn position with tree reuse

[mooskagh]

Example:

position startpos moves e2e4 e7e6 d2d4 d7d5 f1d3 d5e4 d3e4 c7c5 c2c3 g8f6 e4d3 c5d4 c3d4 g7g6 b1c3 f8g7 g1f3 b8c6 c1g5 e8g8 e1g1 h7h6 g5e3 b7b6 d1d2 g8h7 f3e5 c8b7 e5f7 f8f7 d3g6 h7g8 g6f7 g8f7 e3h6 c6d4 a1d1 g7h6 d2h6 d4f3 g1h1 d8h8 h6h8 a8h8 h2h3 h8g8 g2f3 b7f3 h1h2 g8g2 h2h1 g2g8 h1h2 g8g2 h2h1 g2g8 h1h2
go nodes 1000
bestmove g8g2
position startpos moves e2e4 e7e6 d2d4 d7d5 f1d3 d5e4 d3e4 c7c5 c2c3 g8f6 e4d3 c5d4 c3d4 g7g6 b1c3 f8g7 g1f3 b8c6 c1g5 e8g8 e1g1 h7h6 g5e3 b7b6 d1d2 g8h7 f3e5 c8b7 e5f7 f8f7 d3g6 h7g8 g6f7 g8f7 e3h6 c6d4 a1d1 g7h6 d2h6 d4f3 g1h1 d8h8 h6h8 a8h8 h2h3 h8g8 g2f3 b7f3 h1h2 g8g2 h2h1 g2g8 h1h2 g8g2 h2h1 g2g8 h1h2 g8g2
go nodes 1000
bestmove a1a1

(this game: https://lichess.org/V4XJWHhj)

[RedDenver]

Does it need to search past 3-fold repetition?

[dubslow]

As an analysis tool it should be able to.

I recall working on the Search code that implements this ability, but it bases its check on the identity of root_node_, which obviously won't work during tree reuse. It should eventually be a relatively simple fix.

[dubslow]

Here's the relevant check: https://github.com/LeelaChessZero/lc0/blob/master/src/mcts/search.cc#L666

[RedDenver]

It makes sense if the root node is a draw that it keeps searching, but it shouldn't normally search past a terminal draw that's a leaf on the search tree, should it? Seems like that would mess up training and match play. Or are you suggesting a flag or input that tells search to ignore draws?

[dubslow]

If the position entered is already a draw, we should search indeed. That's different than searching leaves.

But now that I say that, I'm actually not sure now how this bug exists, it should already cover the case crem posted. Plenty of time later though.

[xghostxx]

Somewhat of a long shot, but might have something to do with this:

lc0/src/chess/position.cc

Line 104 in 2321011

if (pos.GetBoard() == last.GetBoard()) {

The parentheses after the word last, ie last.GetBoard() vs history_.Last().GetBoard or Last().GetBoard()

[mooskagh]

This issue is only reproducible when tree is reused.
The node is marked terminal while thinking about previous move, so check node != search_->root_node_ doesn't trigger.
After the move three-fold repetition becomes a root, already marked as terminal and without children.

The fix would be to reset terminal flag for root node in the beginning of the search, and reset N to zero.
And probably Q..
Hm, then we should TrimTreeAtHead() instead in this case in NodeTree::ResetToPosition()

[Videodr0me]

I did this a long time ago for the two-folds in my fork - i just uncertain root before search (if it became certain) . I do not set N to zero, but i recalc N for root (as in my world a node can become certain after it already accumulated a number of visits). In your case resetting Q and N is probably enough.

[mooskagh]

It seems that it's a duplicate of #237