LMR & TT interaction

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

LMR & TT interaction

Post by xmas79 » Tue Apr 29, 2014 10:34 pm

After observing my engine playing against "its" favorite opponent (FairyMax 4.8S), I did notice a strange thing: it often reaches a position where it is actually up, and then suddenly makes a bad move. An example is the following position (my engine is black):
[d]r4r1k/2p3bp/6p1/8/1PQP2P1/2P5/1q2P1K1/r1BR3R b - - 1 36
(Yes there are three rooks, a pawn has just underpromoted to ROOK instead of QUEEN.... this is another issue I've seen many times, I'm still investigating...). Here my engine played Qc2 after a bunch of centiseconds at ply 11, and let the opponent play Rxh7+!. Every move except Qc2 seems to keep the advantage....... So I tried to understand why it played such move. If I let the engine analyze this position it discovers pretty quickly (depth 3) all the tactics behind:

Code: Select all

  3	+4.14	1198	0:00.00	b2c2 h1h7 h8h7 d1h1 g7h6 c4c7 h7g8 c1h6 c2e2 g2g3 a1h1 h6f8 g8f8
The problem here seems to be that in the very last plies some imprecision occurs, since h6f8 is a wrong move: Qg7# is a little bit preferable... But this sequence is all QS, which produces all the captures and not the checks, so this actually is a "right" thing. So if this is OK, what can be wrong?

I was playing a bit with LMR and then realized that once you have chosen an arbitrary reduction R value (say R=10 just to take a very big value) for LMR, your engine will be weaker because it will be blind to tactics (never reduce a capture btw...). This has a direct implication on the TT: every entry stored within R plies from horizon could be a weak entry if "properly" reduced. Since LMR is recursive, this is more relevant where the bad move lies in the rightmost part of the search tree.

So I'm supposing that Qc2 has been reduced so much in earlier searches that it entered directly qsearch, and when my engine hit this position it trusted a score from a "blind" TT. Is this possible?

What I really cannot explain is why when the engine hit this position at root, it still preferred to play such move instead of playing another move. Qc2 has a flaw (but it is behind the horizon and engine of course cannot see that), other moves have a better score (within the horizon), why the engine did not see that?


Thanks,
Natale.

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: LMR & TT interaction

Post by kbhearn » Tue Apr 29, 2014 11:07 pm

If in a previous search Qc2 had been reduced 'so much', the TT entry should have insufficient depth to be copied out to a higher depth line (i.e. if depth remaining for Qc2 in our fictitious other line is 2, and the search reaches it looking for depth 10, it should just try the hash pv move and not take the cutoff), it sounds like you have some buggy behavior happening once your engine reaches clearly won positions, perhaps some sort of overflow that is masked off causing a lower score to be preferable to a higher one?

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

Re: LMR & TT interaction

Post by bob » Wed Apr 30, 2014 4:13 am

kbhearn wrote:If in a previous search Qc2 had been reduced 'so much', the TT entry should have insufficient depth to be copied out to a higher depth line (i.e. if depth remaining for Qc2 in our fictitious other line is 2, and the search reaches it looking for depth 10, it should just try the hash pv move and not take the cutoff), it sounds like you have some buggy behavior happening once your engine reaches clearly won positions, perhaps some sort of overflow that is masked off causing a lower score to be preferable to a higher one?
One thing is certain, when you start reducing with LMR or null-move, if you reduce so that you cause the search to drop into the q-search, you overlook all sorts of serious threats. Simplest solution most use is to include checking moves in the first ply of q-search. Or else make certain you never reduce so far that you don't leave one full-width ply left (and you STILL need to escape checks in the first ply of q-search to avoid overlooking the mate "stinger" he has at the end of his PV.

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: LMR & TT interaction

Post by xmas79 » Wed Apr 30, 2014 9:07 am

kbhearn wrote:If in a previous search Qc2 had been reduced 'so much', the TT entry should have insufficient depth to be copied out to a higher depth line (i.e. if depth remaining for Qc2 in our fictitious other line is 2, and the search reaches it looking for depth 10, it should just try the hash pv move and not take the cutoff), it sounds like you have some buggy behavior happening once your engine reaches clearly won positions, perhaps some sort of overflow that is masked off causing a lower score to be preferable to a higher one?
Hi,
it would be a very strange bug, this happens in won positions where score is far less than mate scores (my checkmate score is +/-32000). And I use ints to store scores during search in order to avoid such things. The only place where I use a short is the TT entry where I have 16-bit. So I don't know if it's a TT bug or an excessive reduction problem that make my TT entries pretty bad. As you say, TT will not have enough draft to cause cut-off, but it will place the wrong move on top of the list, so the wrong move will be searched first, and the good one will be reduced (too much..)

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: LMR & TT interaction

Post by hgm » Wed Apr 30, 2014 10:08 am

I think you are just expecting too much here. The Rxh7 sac only refutes Qc2 because it ends in checkmate. As long as the search does not go deep enough to prove mate, there is not much reason to shy away from Qc2, and the line shown seems to win a full Rook. I am a bit surprised that it thinks this is the best white can do, though. The given line doesn't seem to achieve anything for white, and leaves him down 1 Rook for 2 Pawns. In stead of going for a Pawn with Qxc7, it could have at least captured Rxh6+, and stand pat after the evasion, to do a full Bishop better. You are already in QS there, where any hash hit should be deep enough, so it seems to me that this has nothing to do with hashing.

The way I always debug this kind of thing is to print the searched moves and their scores in any node along a given path. If you would do that in the node after Bh6 you would see why the engine prefers Qxc7 over Rxh6, and by their scores whether this is because it over-values Qxc7 or undervalues Rxh6. You could then follow the branch that gave the wrong score, to see how it obtained that score.

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: LMR & TT interaction

Post by xmas79 » Wed Apr 30, 2014 10:13 am

bob wrote:One thing is certain, when you start reducing with LMR or null-move, if you reduce so that you cause the search to drop into the q-search, you overlook all sorts of serious threats. Simplest solution most use is to include checking moves in the first ply of q-search. Or else make certain you never reduce so far that you don't leave one full-width ply left (and you STILL need to escape checks in the first ply of q-search to avoid overlooking the mate "stinger" he has at the end of his PV.
With null-moves I see it less problematic. You usually save nodes because you are confident that a fail-high on a null move is an indication a winnning position. When you get this wrong you are usually in a zugzwang position, or in a position where the tactics involved are so deep that the normal search wouldn't catch it either. No?

LMR is a different beast: when you get it right, you save nodes on CUT node, and that means you already searched the best move on the node and the rest can be reduced (I see them as "lost positions"), but if you get it wrong, you are saving on nodes that could potentially make your position looks better.

That was my observation playing with nulls and LMR. Correct?


As for Qsearch, I already do full-width check escapes in qsearch (I generate all moves when in check and do not prune/reduce a single move). And I generate checks on the first ply of QS, but with this technique the mate is impossible to catch at lower depths: search should drop in QS just in the position "before" the mate, in order to generate captures and then checks.

To be more precise, I have to say that I don't really like the "to include checking moves in the first ply of q-search" method. Check generation is done to avoid some tactics. Since at some point qsearch must stand-pat, and this is not allowed when side to move is in check, I prefer to generate checks in QS indipendently of the QS ply number, but when the opponent at previous ply could not stand-pat.

The idea is simple: if at first ply of QS (with white to move) white is not in check, it can generate checks to make the position quieter or generate some tactical shot, so at ply 2 of QS black cannot stand-pat, and at ply 3 white can stand-pat if (say) wins some material. If at first ply of QS white is in check, it cannot stand pat, so it's black's turn to generate checks at 2nd ply of QS (if white's escape doesn't give check). And so on.... So at the end of a long (and rare) sequence of checks, the last checked side-to-move will be put again in check on the next QS ply. This is probabily not going to change a single thing on an engine, but I think is a more precise Qcheck generation.

tpetzke
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

Re: LMR & TT interaction

Post by tpetzke » Fri May 02, 2014 6:13 am

LMR is a different beast: when you get it right, you save nodes on CUT node, and that means you already searched the best move on the node and the rest can be reduced (I see them as "lost positions"), but if you get it wrong, you are saving on nodes that could potentially make your position looks better.
Hmm, you probably mean LMR saves nodes in ALL nodes. If you have searched the best move in a CUT node, you are done.

Thomas...
Thomas...

=======
http://macechess.blogspot.com - iCE Chess Engine

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: LMR & TT interaction

Post by xmas79 » Fri May 02, 2014 7:04 am

tpetzke wrote:Hmm, you probably mean LMR saves nodes in ALL nodes. If you have searched the best move in a CUT node, you are done.

Thomas...
Absolutely! Biggest typo in the world.... :D

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: LMR & TT interaction

Post by xmas79 » Fri May 02, 2014 7:20 am

hgm wrote:I think you are just expecting too much here. The Rxh7 sac only refutes Qc2 because it ends in checkmate. As long as the search does not go deep enough to prove mate, there is not much reason to shy away from Qc2, and the line shown seems to win a full Rook. I am a bit surprised that it thinks this is the best white can do, though. The given line doesn't seem to achieve anything for white, and leaves him down 1 Rook for 2 Pawns. In stead of going for a Pawn with Qxc7, it could have at least captured Rxh6+, and stand pat after the evasion, to do a full Bishop better. You are already in QS there, where any hash hit should be deep enough, so it seems to me that this has nothing to do with hashing.

The way I always debug this kind of thing is to print the searched moves and their scores in any node along a given path. If you would do that in the node after Bh6 you would see why the engine prefers Qxc7 over Rxh6, and by their scores whether this is because it over-values Qxc7 or undervalues Rxh6. You could then follow the branch that gave the wrong score, to see how it obtained that score.
It's clear to me that if search can't get deep enough there's no way to not play Qc2, but the problem is that if I put the engine in analysis mode in this position if prefers another move (Qa2) since depth 6. If I let the engine analyze two or three moves before this position and then manually make moves to force the engine to analyze this position, the engine wrecks things up, and then it will end up with preferring Qc2 instead of the Qa2. That's what I experienced observing the engine. In a position where the score drops significantly (I don't usually trust my engine score, I trust my opponent score) I see my engine playing bad moves. When starting a fresh analysis on the same position, my engine clearly prefers other moves. Now I'm in hurry, maybe later I will post some other examples and outputs to bette explain it.

op12no2
Posts: 349
Joined: Tue Feb 04, 2014 11:25 am
Location: Mumbles, Wales, UK.
Full name: Colin Jenkins
Contact:

Re: LMR & TT interaction

Post by op12no2 » Fri May 02, 2014 7:50 am

Similarly, my in-development Javascript engine will get an advantage over Fairy-Max then start to commit Seppuku.

Image

:)

I mention it because I discovered that if I reset the TT on the uci position message rather than just at the start of the game, it stops doing it; but I have no idea why...

Post Reply