Counting depth as a function of number of legal moves

[Uri Blass]

Hi Pio,

As others have pointed out the idea is already well known.

However personally I think that the total number of moves in a position is not a good metric, because it stays pretty constant during the middle-game.

The more interesting metric IMO would be "the number of reasonable moves" / position. By a reasonable move I mean a move where evaluation doesn't drop more than say 30cp compared to the best move.
But the obvious problem with this approach is the huge additional computing cost, so... likely we are just better off by extending checks, singular moves and pawn endgames

I do not think that it is a good metric and the problem is that a move that is 0.4 pawn weaker than the best move or even more than it may be the best move with deeper search so I cannot decide to prune it and I need to search it.

If you need to search a move then it makes the search more complex and I do not see the logic of ignoring it completely in calculating complexity.

Maybe you can consider it with smaller weight because you expect to waste less time on the search on it but you should count all moves(maybe not with the same weight).

[Pio]

Hi all of you!

I am comming back with a faster but a less accurate simplification extension idea. Of course my idea might not work but I think and hope it can make a difference since the additional computational cost is a constant and the gain in search tree exponential. I guess therfore if you want to see any gains of my idea you would have to test the idea on different time controls and then extrapolate the result to longer time controls to see if it might be a gain.

If you think it is to expensive counting the number of opponents moves you could do an approximation by counting the opponents average mobility based on the opponents pieces instead.

For example you could count the average mobility for the pieces maybe as averagePawnMobility = 1, averageKnightMobility = 6, averageBishopMobility = 7, averageRookMobility = 9, averageQueenMobility = averageBishopMobility + averageRookMobility = 16 and averageKingMobility = 4 and finally take the logarithm of the sum of the opponents averageMobilities multiplied with some constant multiplied with the depth you usually would consider your move as. You could precalculate the logarithms and put them in an array and the averageMobility could easily be incrementally updated when moving or undoing a move.

The benifit of this type of reduction/extension it is that you will look deeper into lines where you simplify the game by removing pieces and thus more easily could see if a move is good or not.

If you want to improve the idea even more you could use two types of averageMobilityValues depending on the game stage and then interpolating between opening (give bonus to knights) and endgame (give bonus to bishops, rooks, queens and king) and then round the value to use the precalculated logarithms.

Good luck with your engines!!!

[stegemma]

Maybe a variation could be to analyze any moves from the first ply (or from a chosen depth) up to a fixed values of nodes/moves. This will analyze deeper the variants where there are nodes with less moves but could be not so good for more complex continuations.

[hgm]

The problem there is that alpha-beta and hash hits hides the true number of nodes in the sub-tree. And there is no reason why you would want to search the same sub-tree much deeper if you encounter it a second time (after transposition of the moves leading to it) and have many hash hits in it.

[Pio]

Hi H.G.Muller!

You are probably right, but if it is a problem, why is this not a problem with check extensions too? (maybe it is???). I am sorry if my question is a little bit stupid, but I have not finished writing my engine so I have an excellent excuse .

Even if you research the same sub-tree you may still get information because you might detect a three-fold repition and the research of the same tree should also be quite cheap/fast since there would be lots of hash hits in it.

The way I see it is that the depth to an arbitrary node/position should correspond to the probability that you actually will end up in the node/position, even if that means that you will revisit some nodes again in the path to the final node.

I think why you look twice as deep on checks is because you reduce the branching factor by roughly the square (from maybe 36 to 6 on average I guess) on checks and that is also why you do it recursively. Why should you look deeper on checks recursively otherwise? I have problem seeing why you should look deeper into a check than for example a move that traps the queen and also reduce the branching factor by the same. What is the logic?

I do however understand that it will be expensive to count all the oppponents moves and that is why I proposed a much cheaper way of counting the moves based on the logarithm of the sum of the opponents pieces average mobility. Of course the method will not be so accurate and it will not look deeper if you trap the opponent but you will be able to incorporate the method in your engine without having to rewrite/remove check extensions.

Thank you all for your responses!!!