Null move as a function of mobility

[bob]

It is not the node count (of a sub-tree), but the legal moves count of the current position that was needed for this.

Legal move count is not very relevant. It is the node count for each resulting tree that tells you something.

[hgm]

Yes, but not what you want to know. The search-tree size is score related. The number of moves tells you the size of the unpruned tree. The log(nrOfMoves) prescription amounts to awarding equal numbers of nodes to all un-pruned sub-trees.

[metax]

I don't think the legal move count is a good indicator for such an extension/reduction method. There might be positions where there are 60 moves which are all rubbish and others where there is only one legal move, e.g. capturing the opponent's queen which checks your king that don't deserve an extension.

Implementing such a method would be extremely costly anyway because in every position you have to generate all pseudolegal moves, then check them for legality - and all this for a questionable method? I don't know...

[Uri Blass]

I don't think the legal move count is a good indicator for such an extension/reduction method. There might be positions where there are 60 moves which are all rubbish and others where there is only one legal move, e.g. capturing the opponent's queen which checks your king that don't deserve an extension.

Implementing such a method would be extremely costly anyway because in every position you have to generate all pseudolegal moves, then check them for legality - and all this for a questionable method? I don't know...

You do not have to do it in every position.

If you have some extension it does not mean that you do it in every node and you can extend based on number of legal moves only when the remaining depth is at least 3.

I also do not think that extending based on number of moves is something that work for most programs but I think that the main reason that extensions does not work is the odd-even effect.

The main problem is that if you extend move X and do not extend move Y then you may need to compare between 1.X X1 as a leaf node and 1.Y as a leaf node.

The probability that the computer get correct conclusion when it compare between positions with the same side to move is simply higher.

I can imagine that a chess program may play even weaker at the same depth with more extensions.

Maybe people can try to have random extension that mean that you extend every node with probability p so out of N nodes that you need to search to depth 1 pN nodes are going to be searched to depth 2 and (1-p) nodes are going tp e search to depth 1.

It may be interesting to know the rating as function of p.

I suspect that when p=0.5 you are not going to get half of the improvement relative to the case p=1(that means searching to depth 2)

You can also do the same experiment for depth 2-3 or depth 3-4.

Uri

[bob]

Yes, but not what you want to know. The search-tree size is score related. The number of moves tells you the size of the unpruned tree. The log(nrOfMoves) prescription amounts to awarding equal numbers of nodes to all un-pruned sub-trees.

The problem is that number of moves in a position has little information. I am in check and have few choices. Beyond this point the tree can be huge or tiny. I don't know until after I search it. The information is only revealed after the fact, which is a huge problem quite unlike what is found in best-first type searches. I might have 25 legal moves, and 24 of them lose instantly, in one case, while in another I might have only 10 and any one of them wins.

[hgm]

If the branching ratio goes up again later in the tree, it means that plies there get more expensive again, so you run out of depth early anyway.

Counting a ply as log(nrOfMoves) depth units, is equivalent to defining a node budget in the root, and dividing it up evenly over every move (searched or unsearched). Because subtracting log(nrOfMoves) from the remaining depth is equivalent to dividing something by the nrOfMoves. The remaining depth (in depth units) is simply the log of the node budget. the lower the branching ratio, the longer you can continue dividing up the budget until you run out, i.e. the more ply you can search.

[bob]

If the branching ratio goes up again later in the tree, it means that plies there get more expensive again, so you run out of depth early anyway.

Counting a ply as log(nrOfMoves) depth units, is equivalent to defining a node budget in the root, and dividing it up evenly over every move (searched or unsearched). Because subtracting log(nrOfMoves) from the remaining depth is equivalent to dividing something by the nrOfMoves. The remaining depth (in depth units) is simply the log of the node budget. the lower the branching ratio, the longer you can continue dividing up the budget until you run out, i.e. the more ply you can search.

My goal is to search the important moves as deeply as possible. At the present, I do this by extending all "interesting" moves, leaving the generic moves alone, reducing the "trashy-looking" moves, and outright pruning the moves that look lousy. I am not sure about applying some sort of selective search algorithm (whether it is forward pruning, backward pruning, or reductions) based on the number of moves I have. I can have a small number of possibilities where almost all are good, or a large number of possibilities where almost all are bad. Most selective ideas work best when used with dynamic information obtained by doing searches. Singular Extensions comes to mind. Static extensions like giving check and such are more problematic because it is difficult to tell, before-the-fact, whether a check leads somewhere, is a delaying move (either of which is important to know) or if it is just a spite check or even just a legal move.

I'm not saying the idea is hopeless or worthless, just that static characteristics can completely miss dynamic issues.

[hgm]

Information and knowledge can always be applied to selectively prune any tree further. The balancing algorithm tries to optimize the tree shape in absence of any information on the quality of the moves, by re-allocating nodes from a sub-tree where statistically they would contribute little to the result, to a sub-tree where they have a higher probability to make a difference. So it would describe the difference in search depth you could best apply to moves that to the best of your knowledge are of equal quality.

I have no idea wheater it would work to increase general quality of play. I never tried it, and in most games the branching ratio is pretty homogeneous throughout the tree anyway, so it would hardly make any difference. Except in the case where you convert to a Pawn ending, for which many engines already apply an extension technique that has a similar effect.

It seems, however, that in extreme cases, such as these problems with trapped pieces, this technique would facilitate finding the solution enormously.

[bob]

Information and knowledge can always be applied to selectively prune any tree further. The balancing algorithm tries to optimize the tree shape in absence of any information on the quality of the moves, by re-allocating nodes from a sub-tree where statistically they would contribute little to the result, to a sub-tree where they have a higher probability to make a difference. So it would describe the difference in search depth you could best apply to moves that to the best of your knowledge are of equal quality.

I have no idea wheater it would work to increase general quality of play. I never tried it, and in most games the branching ratio is pretty homogeneous throughout the tree anyway, so it would hardly make any difference. Except in the case where you convert to a Pawn ending, for which many engines already apply an extension technique that has a similar effect.

It seems, however, that in extreme cases, such as these problems with trapped pieces, this technique would facilitate finding the solution enormously.

I'm sure you are right. But that is the basic problem with chess in general, it is hard to recognize these positions before searching them. After searching them it is too late..