typo What is/are the exact criterion/criteria that different engines use for a “cutnode” flag? (setting aside for a moment my perennial qualms about terminology) seer When applying reduction, always expect a cut node: https://github.com/Ciekce/Stormphrax/blob/main/src%2Fsearch.cpp#L1013 When re-searching, set the child expected cutnode to !parent expected cutnode: https://github.com/Ciekce/Stormphrax/blob/main/src%2Fsearch.cpp#L1022 (referencing SP as this seems to be the most common implementation) typo > When applying reduction, always expect a cut node. Wouldn’t this be the other way around? You are more willing to more aggressively reduce the children if the current node has the “cutnode” flag marked, and the children are expected-All? seer The assumption is most moves you're reducing are going to be bad to very bad and will result in child cut nodes (as in actually cut nodes). I actually think this is all bogus regardless and the key that makes this work is the error type observation though which enables soundly applying extra reductions without changing the search result. potential what exactly the difference between cut node and all node? seer I think @typo has a good write up on the terminology. Notably, here we're talking about a heuristic that tries to predict whether a node is a cutnode in advance ("expected cutnode"). In Seer, I formulate this differently and track which player reduced last: https://github.com/connormcmonigle/seer-nnue/blob/ 8f7c794c47d24121f76ef1994093ddb8614a3e10/src/search/search_worker.cc#L429 It's equivalent though. typo > The assumption is most moves you're reducing are going to be... ah — reduce more aggressively in expected-All nodes (when !cutnode) (and then be sure to mark the successors as cutnode=true) seer Unfortunately no: https://github.com/official-stockfish/Stockfish/blob/ master/src%2Fsearch.cpp#L1200 ^ Reduce more aggressively on expected cut nodes typo ah so I had it the right way ’round typo > When applying reduction, always expect a cut node. so by expect a cut node you were not referring to the successor but to the current node seer I was referring to the successor typo surely you never expect the successor of an expected-Cut node to be expected-Cut? seer I think you do in practice and the logic sets all the reduced searches from the successor to true for expected cut node again. Again, most moves are really bad so the successor of an expected cut node will only have one all node child usually seer Here's my thinking on why this heuristic actually works though: | [kirill] | Why do we reduce more in cut-nodes in lmr? | | [seer] | This is a great question and I think the answer generally isn't well | understood / accepted. I think it's helpful to think in terms of error | types. | | If you reduce more on the child of a node where the depth was already | reduced, the worst error that will result in is making a node that would | have been a cut node into an all node -> extra reduction means some good | move was missed and never re-searched at full depth by the child. | | In this worst case, the fail low induced on the child due to the extra | child reduction means the parent will just re-search at full depth and | nothing will be missed. Therefore, reducing more on cut nodes is "safe" | / at worst just means the position will be searched again at even higher | depth. This reasoning can be extended recursively and effectively | recovers "cut node" | | [tsoj] | Is the parent node of a cut node always searched at reduced depth? | (Maybe that question is senseless, I am not 100% understanding the | cutnode allnode classification that most engines use.) | | [seer] | I mean when the parent node reduces and then the child is searched at | that reduced depth. If the child reduces more, then in the worst case, | the child will be searched again at full depth by the parent | | [seer] | > is there no LMR cut node reduction in Seer? | | Seer has some code to propagate which side has reduced recursively | through the tree. I did this independently, but it worked out to be | equivalent to cutnode. | | [seer] | > Is the parent node of a cut node... | | To make this concrete, let's say we have: A -> B -> C | | A is at depth 10 and reduces by 3 when searching B. B is then marked | as a cut node in this case (we expect a fail high). B is searched at | depth 7. When B searches C, B reduces the depth by 1 more than it | normally would: instead of searching C at reduced depth 5, B searches | C at reduced depth 4. Reducing more than you normally would might result | in missing a move that beats beta: you can get a wrong fail low, but | critically never a wrong fail high. | | In the case of a wrong fail low at B, A will re-search B at full depth | as A was reducing when searching B. | | @tsoj it wouldn't go by unnoticed by A because the wrong fail low at B | would look like a move that beats beta at A and trigger a full depth | search. | | [tsoj] | Aren't there cases where A isn't going to do a full depth re-search | since it already is a full depth? Probably only a full window re-search? | | [seer] | Right, but B will not be marked as an expected cutnode on the re-search. | | [tsoj] | You mean the full window re-search? | | [seer] | Let's just ignore PV nodes for this discussion (99% of nodes are not | PV nodes). I mean the full depth re-search | | [tsoj] | Oh right, I forgot that a full window is a zero window in non PV nodes | | [seer] | > it wouldn’t go unnoticed | | Did this make sense? | | [tsoj] | Yeah, I am only unsure about the case "A is at depth 10 and doesn't | reduce (apart from the depth-1) when searching B". Is it guaranteed that | in such cases B is not marked as cutnode? | Or is there a re-search happening anyway if the node type was not the | expected one? | | [seer] | The re-search is only happening if the node type wasn't the expected one. | If it was the expected one (cutnode), you wouldn't have re-searched at | full depth. | There is some trickiness with the propagation of the status of A on the | re-search that falls out of applying this rule recursively | | [tsoj] | Ah okay. I don't have the expected-node concept in my engine at all, | so I thought that if the search depth is the unreduced search depth, | no re search is needed. typo > I think you do in practice... i suppose i’m surprised by this let’s see, with rubbish move ordering nodes that are actually-All nodes will only have only actually-Cut nodes as successors and nodes that are actually-Cut nodes will have several actually-Cut node successors and finally one actually-All node successor so yeah i suppose if move ordering is not very accurate it might be reasonable to just treat everything as expected-Cut by default i wonder what the distribution of nodes in zero-window trees is seer I think it's more like, we had a node we thought was a cutnode. After the first move didn't yield a cut, now we're probably on an all node and all the remaining children will be cut nodes. Which is true for chess / chess like game trees (where most moves are bad) typo i should reread my own notes https://expositor.dev/notes/pvs-notes-4 > you guess the second sucessor is expected-Cut even if the first successor > failed low! > which means you have very strong belief in your move ordering and are sorta > doing this: > If you strongly believe your move ordering is perfect and the first > successor fails to raise alpha (meaning it was a Cut node), then you > should consider yourself an expected-All node instead of an expected-PV > node. although i suppose this situation is slightly different because here we’re talking about revising belief about nodes that were expected-Cut rather than were expected-PV