hash move and move ordering

[Aleks Peshkov]

Suppose during tree search we reach a position, found a hash hit and searching hash move failed. So we need to generate and search all other possible moves from this position.

What if failed hash move was a non-capture move? It means that some time ago no "good" captures was good enough because we reach non-capture phase. IMHO it is little point to try captures first again. They proved to fail and chances that these captures will occasionally become good are low. Especially SEE ordering is futile because we have really refuted SEE ordering earlier by real search.

I think it is make sense to firstly search moves that have obvious similarity to the hash move: moves of the same piece or moves that target the same target square.

Better chess understanding can help to found more similarities. For example if the hash move was a checking move, it is a solid reason to search another checking moves. If we can understand tactical reasons for the hash move, we can generate moves that attack that threatened tactical victim with other pieces or attacking defenders of that discovered earlier victim.

There are many other sourches of dynamic chess knowledge that is worse to test: mate killer suggests to search checks and other king-related moves. Killer move that pushes a passed pawn suggests move that related to that particular pawn...

[Gerd Isenberg]

Suppose during tree search we reach a position, found a hash hit and searching hash move failed. So we need to generate and search all other possible moves from this position.

What if failed hash move was a non-capture move? It means that some time ago no "good" captures was good enough because we reach non-capture phase. IMHO it is little point to try captures first again. They proved to fail and chances that these captures will occasionally become good are low. Especially SEE ordering is futile because we have really refuted SEE ordering earlier by real search.

I think it is make sense to firstly search moves that have obvious similarity to the hash move: moves of the same piece or moves that target the same target square.

Better chess understanding can help to found more similarities. For example if the hash move was a checking move, it is a solid reason to search another checking moves. If we can understand tactical reasons for the hash move, we can generate moves that attack that threatened tactical victim with other pieces or attacking defenders of that discovered earlier victim.

There are many other sourches of dynamic chess knowledge that is worse to test: mate killer suggests to search checks and other king-related moves. Killer move that pushes a passed pawn suggests move that related to that particular pawn...

Interesting. If that node is an expected cut-node - but a hash-move (and nullmove) don't cuts as expected, further move sorting seems crucial. May be we have some killers? Or a tactical as well positional threat from nullmove to refute? How was the former best move refuted? Since it occurs rarely in cut nodes, one may investigate some time to find good candidate moves early. Additionally one may consider maintained minimal tree node-types combined with static score >= beta or < alpha or other measures on strong and weak node-types, for instance +63 strong cut- .... +1 weak cut-node and -63 strong all ... -1 weak all-node, 0 PV-node.

[Aleks Peshkov]

Additionally one may consider maintained minimal tree node-types combined with static score >= beta or < alpha or other measures on strong and weak node-types, for instance +63 strong cut- .... +1 weak cut-node and -63 strong all ... -1 weak all-node, 0 PV-node.

Do not understand what do you mention at all. What is strong/weak node types? Where does this information could be maintained?

[Harald Johnsen]

Do not understand what do you mention at all. What is strong/weak node types? Where does this information could be maintained?

In the has table since you are concerned about hash moves that are refuted. Btw how many of them are refuted ? And what about even/odd depth search ? Isn't the opponent supposed to have a better positional score if he plays the last move ?
So in the hash table you could store the fact that the hash move is better than the others only by a few centipawns (random positional adavantage) - and perhaps you don't care if it's not the best move in a later search,
or the move was very good (singular move) and then you really need to do a full search of it's sibling if later this move gives a bad score.

HJ.

[Gerd Isenberg]

Additionally one may consider maintained minimal tree node-types combined with static score >= beta or < alpha or other measures on strong and weak node-types, for instance +63 strong cut- .... +1 weak cut-node and -63 strong all ... -1 weak all-node, 0 PV-node.

Do not understand what do you mention at all. What is strong/weak node types? Where does this information could be maintained?

From Yngvi Björnsson' and Tony Marsland's MultiCut Paper:
http://www.ru.is/kennarar/yngvi/pdf/BjornssonM01a.pdf

Defnition 2 (Minimal tree). Every child of a pv-node or an all-node is a part of the minimal tree, but only one child of a cut-node. Given any game-tree, we can derive a minimal tree by identifying its nodes as follows:

• 1. The root of the game-tree is a pv-node.
  2. At a pv-node, n, at least one child must have a minimax value -vmm(n)
  (when there are several such children pick one arbitrarily). That child is a
  pv-node, but the remaining children are cut-nodes.
  3. At a cut-node, a child node n with a minimax value vmm(n) < vmm(npv) is an all-node, where npv is the most immediate pv-node predecessor of n. At least one child must have such a value; when there are several, pick one arbitrarily.
  4. Every child node of an all-node is a cut-node.

Some programs pass expected node-type, e.g. {pv = 0, all = -1, cut = 1} as additional parameter to the search routine. Starting at the root with pv. In Null-Window searches we only have to deal with alternating cut- and all-nodes as expected node-types. The idea of using expected minimal-tree node-types, is for instance to enable multiCut-Pruning only at expected cut-nodes.

Code: Select all

int NWS(int depth, int beta, int nt)
{
   ...
   if ( depth > D && nt == cut )
   {
      if ( MultipleCuts(depth-R, .. )
         return beta;
   }
   ...
   for each move
   {
     ...
     score = -search(depth-1, 1-beta, -nt);
     if ( score >= beta )
        return score; // fail soft
     ...
   }
   ...
}

The idea of strong or weak cut- and all nodes - is to use a wider range of values to somehow arbitrary adapt minimal tree node-types to a real search-tree, where expected all nodes fail high and expected cut-nodes fail to cut at least on the first childs. Each time an expected cut-node fails to cutoff, it's node-type is for instance decremented. The less the absolute value, the "weaker" the node-type.

Code: Select all

{pv = 0, all = -63, cut = 63}

int NWS(int depth, int beta, int nt)
{
   ...
   if ( depth > D && nt >= NPERCENT*cut/100 )
   {
      if ( MultipleCuts(depth-R, .. )
         return beta;
   }
   ...
   for each move
   {
     ...
     score = -search(depth-1, 1-beta, -nt);
     if ( score >= beta )
        return score;
     nt -= ( nt > 1 ); // makes cut nodes "weaker"
     ...
   }
   ...
}