Null move as a function of mobility

[bob]

For the purpose of tree balancing, it would be good to do something like you propse on _any_ search, not just null-move searches. Except I would use the log table that you printed not to define the reduction, but in stead the relative cost of the ply. So if there is only a single move, the cost would be zero, meaning a full ply extension (sigular extension). With 55 moves I would count it as a full ply, i.e. the table gives quarter plies. When you have only two moves, it would count 0.69 quarter plies ~0.17, equivalent to an extension of 0.83 ply.

That way you would reach more depth in critical situations, where you can easily afford it. Such as on conversion to a Pawn ending.

Only one problem. It is difficult to know this information _before_ you start work at a ply. Do you generate all legal moves? Even then, different types of moves have different complexities (giving check as opposed to just hanging a queen).

[zamar]

For the purpose of tree balancing, it would be good to do something like you propse on _any_ search, not just null-move searches. Except I would use the log table that you printed not to define the reduction, but in stead the relative cost of the ply. So if there is only a single move, the cost would be zero, meaning a full ply extension (sigular extension). With 55 moves I would count it as a full ply, i.e. the table gives quarter plies. When you have only two moves, it would count 0.69 quarter plies ~0.17, equivalent to an extension of 0.83 ply.
.

To do something like this was one of my first ideas when I started chess programming. However the more I've thought about it the more impossible it looks like. The problem is that the legal move count is usually quite useless, because most of those moves are garbage anyway. The thing that matters is the number of "candidate moves" (term by Mark Dvoretzky): the number of moves a GM would consider in this position. However getting proper answer for this would enable us to write directly Shannon Type B chess computer.

[zamar]

Only one problem. It is difficult to know this information _before_ you start work at a ply.

I think that transposition table can be used for this (to save necessary info from previous iterations), defining the useful metric is the true problem.

[hgm]

They might be garbage, but the computer is going to search them. So from the computer's perspective, they are not garbage.

I am not sure if it would make any differene how smart the entity that searches is. Compared to a conventional search the formula displaces nodes from sub-trees where they result in very little extra depth to sub-trees where they give much more extra depth. This somehow would have to be balanced, however, by the usefulness to evaluate some moves much more accurate than others.

It would help a lot in these problems where one side has a lot of trapped pieces, and you have to search the branch where you keep them trapped to a very large depth to find the win, while the branches where you let them escape explode.

[bob]

For the purpose of tree balancing, it would be good to do something like you propse on _any_ search, not just null-move searches. Except I would use the log table that you printed not to define the reduction, but in stead the relative cost of the ply. So if there is only a single move, the cost would be zero, meaning a full ply extension (sigular extension). With 55 moves I would count it as a full ply, i.e. the table gives quarter plies. When you have only two moves, it would count 0.69 quarter plies ~0.17, equivalent to an extension of 0.83 ply.
.

To do something like this was one of my first ideas when I started chess programming. However the more I've thought about it the more impossible it looks like. The problem is that the legal move count is usually quite useless, because most of those moves are garbage anyway. The thing that matters is the number of "candidate moves" (term by Mark Dvoretzky): the number of moves a GM would consider in this position. However getting proper answer for this would enable us to write directly Shannon Type B chess computer.

The whole idea behind "depth-first search" is that you don't know anything at all until the search is completed, which makes tests that depend on search results difficult to use at the time they are needed. Hence the static rules that say extend checks even if they are futile, because we don't know they are futile until after we search 'em.

chicken-and-egg sort of problem, overall.

[bob]

Only one problem. It is difficult to know this information _before_ you start work at a ply.

I think that transposition table can be used for this (to save necessary info from previous iterations), defining the useful metric is the true problem.

I'm not sure it is accurate enough. Can you trust a hashed node count that might have come from a hashed position itself???

[hgm]

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

[zamar]

They might be garbage, but the computer is going to search them. So from the computer's perspective, they are not garbage.

That's true very close to leaves, so maybe this technique could work there.

Close to root "candidate moves" take 10x more time than "garbage moves", so using legal move count doesn't sound wise.

[michiguel]

For the purpose of tree balancing, it would be good to do something like you propse on _any_ search, not just null-move searches. Except I would use the log table that you printed not to define the reduction, but in stead the relative cost of the ply. So if there is only a single move, the cost would be zero, meaning a full ply extension (sigular extension). With 55 moves I would count it as a full ply, i.e. the table gives quarter plies. When you have only two moves, it would count 0.69 quarter plies ~0.17, equivalent to an extension of 0.83 ply.
.

To do something like this was one of my first ideas when I started chess programming. However the more I've thought about it the more impossible it looks like. The problem is that the legal move count is usually quite useless, because most of those moves are garbage anyway. The thing that matters is the number of "candidate moves" (term by Mark Dvoretzky): the number of moves a GM would consider in this position. However getting proper answer for this would enable us to write directly Shannon Type B chess computer.

Just for the record, the term was coined by A. Kotov in "Think like a Gran Master". That was an extremely influential book... in the wrong direction. He elaborated a very disciplined way to structure your thinking during the game (he developed a Shannon type B algorithm for humans . Unfortunately, nobody thinks that way. It took decades a lot of guts to say that this is wrong (there are a couple of great books about this from Nunn and Tisdall).

Miguel

[hgm]

Close to root "candidate moves" take 10x more time than "garbage moves", so using legal move count doesn't sound wise.

But that is good, and it should stay that way. You don't want lines without merit to receive equal time as the PV. But this technique would not affect that. By counting the plies as log(nrOfMoves) you balance the unpruned minimax tree. Normal puning will reduce the sub-trees as much as it can, and its task is much easier on trees very far (in score) from the PV.

The point is that two lines that have approximately equal score, because in one you trade Queens and get into a Pawn ending, and the other leaves the Queens on the board, now get an approximately equally sized sub-tree.