Counting depth as a function of number of legal moves

[Pio]

Hi all of you!

This is my first post here even though I have read and enjoyed most of the threads in this forum for at least half a year. First of all I apologize that I do not know the computer chess terminology very well.

I hope my idea is not too stupid. It has to do with how to count the depth of a move. I do not know if it is original but so far I have not read anything similar. I know that it will performance wise will cost a little bit, but I think and hope it can scale the search tree better, which I think is the important issue.

The idea is when creating a move, you immediately create all the opponent's counter moves. The depth of your move should be counted as some constant c times the logarithm of the number of legal opponent moves. The idea is that if the opponent has fewer legal moves it will be easier to prove that none of them are good. Why taking the logarithm? Taking the logarithm has to do with probabilities. Going through a sub tree of depth two with a branching factor of 6 creates 36 leaf nodes which is the same as the number of leaf nodes of a sub tree of depth one with branching factor of 36. That is, we will roughly spend the same time in both the sub trees. I think it is the right thing to do since then the probability of ending up in a leaf node will be the same for both trees (if you consider all the moves as equally probable).

Hopefully the extra cost of generating all the counter moves can be offset by the fact that, if I am not wrong, you can do ETC (Enhanced Transposition Cutoff).

I hope this can make check extensions superflous as well as single reply extensions. Of course it might be good to do some extra extension on multiple checks after each other (for the weaker side) since the likelihood of repetition is usually quite large then.

Good luck with your chess computers!!!

[Daniel Shawul]

Hello and welcome to CC
If I understand you correctly, D = K * log (no_of_opponent_moves) which sort of means we extend more towards positions where the opponent has more moves. I am not sure if that is what you want. Infact we usually extend towards positions where opponent has less moves so that we can nail him by tactics. Checks,single reply,threats, and forced moves in general fall under this category. So the lesser number of moves opponent has the bigger should our search depth be. Maybe D = K /log(no_of_opponent_moves) is what you meant? Also I think taking log of number of opponent moves at one node is not appropriate. That is true only for all the leaf nodes at a level not for one particular node. The number of opponent moves should be taken as it is IMO.
Anyway it is a pleasure to read about your efforts. Hope you enjoy cc.

[hMx]

Hi all of you!

This is my first post here even though I have read and enjoyed most of the threads in this forum for at least half a year. First of all I apologize that I do not know the computer chess terminology very well.

I hope my idea is not too stupid. It has to do with how to count the depth of a move. I do not know if it is original but so far I have not read anything similar. I know that it will performance wise will cost a little bit, but I think and hope it can scale the search tree better, which I think is the important issue.

The idea is when creating a move, you immediately create all the opponent's counter moves. The depth of your move should be counted as some constant c times the logarithm of the number of legal opponent moves. The idea is that if the opponent has fewer legal moves it will be easier to prove that none of them are good. Why taking the logarithm? Taking the logarithm has to do with probabilities. Going through a sub tree of depth two with a branching factor of 6 creates 36 leaf nodes which is the same as the number of leaf nodes of a sub tree of depth one with branching factor of 36. That is, we will roughly spend the same time in both the sub trees. I think it is the right thing to do since then the probability of ending up in a leaf node will be the same for both trees (if you consider all the moves as equally probable).

That is not stupid at all. As I understand it, you try to shape the tree not by depth but rather by an estimation of the size.

I have experimented with such an idea a long time ago, although not for chess, but rather for Reversi/Othello. Unfortunately, the results were not as good as I had hoped, and I conjectured, that it just does not work.

Maybe I was wrong, who knows... most probably you will have to try it

Hopefully the extra cost of generating all the counter moves can be offset by the fact that, if I am not wrong, you can do ETC (Enhanced Transposition Cutoff).

I hope this can make check extensions superflous as well as single reply extensions. Of course it might be good to do some extra extension on multiple checks after each other (for the weaker side) since the likelihood of repetition is usually quite large then.

Good luck with your chess computers!!!

[hgm]

I once proposed this too, except that I did not want to count depth as log of the number of opponent moves, but as your own moves. I don't think that makes much difference, and it is cheaper to implement.

The idea was that this would mainly help to solve those kind of problems that are impossible to solve for engines now (and easy for humans), where one side has overwhelmingly strong material, which is somehow trapped, and the key to beating him is preventing the material to escape. This means you have to search very deep along a tree with very low branching factor, in the face of parallel branches where the branching factor explodes. Balancing sub-tree sizes would be a big help.

It would also solve the problem encountered in real games, where you convert to a Pawn ending, in a natural way. Most programs use an ad-hoc method now (like extending 2 ply where you enter the Pawn ending) to solve that.

I never tried it out, though.

[Laszlo Gaspar]

Hello guys,

The theory behind this idea is well worked out. It is called: Alpha-Beta Conspiracy Search by David A. McAllester and Deniz Yuret. They measured the stability of the evaluation as the number of leaf evaluations which are necessary to change in order to change the outcome of the search. They introduced two depth parameters for both sides which mean the number of moves below a certain node in the tree which already reached the established alpha - delta (usually a half pawn value) value for the side to move. When both sides reach their 'depth' the search is aborted.

I implemented it and it did something just it was very resource hungry. When you generate the moves you also have to evaluate them with at least a quiescent search knowing instantly it is good or bad. And the good moves are counted in the tree. It was a very interesting experiment but I realized that it is simpler just extending check by one ply...

Good luck!:-)

[AlvaroBegue]

No, this is not Conspiracy Number Search at all. What this thread proposes is a particular case of "Realization Probability Search". Look it up.

[Karlo Bala]

No, this is not Conspiracy Number Search at all. What this thread proposes is a particular case of "Realization Probability Search". Look it up.

Laszlo mentioned the alpha-beta conspiracy (ABC) search, and that's not a classical conspiracy number search. ABC is however very close to Pio's proposal.

[AlvaroBegue]

No, this is not Conspiracy Number Search at all. What this thread proposes is a particular case of "Realization Probability Search". Look it up.

Laszlo mentioned the alpha-beta conspiracy (ABC) search, and that's not a classical conspiracy number search. ABC is however very close to Pio's proposal.

They measured the stability of the evaluation as the number of leaf evaluations which are necessary to change in order to change the outcome of the search.

That sounds exactly like CNS to me...

[Pio]

Hi to all of you!

Daniel Shawul, I thank you so much for wellcomming me to CC and I can assure you I very much enjoy this forum.

Heiner Marxen, you are completely right that I "try to shape the tree not by depth but rather by an estimation of the size" and I am happy you do not think the idea is stupid.

H.G Muller you are one of my biggest idols and I admire your micro-max engine even though I cannot understand most of the code. How you could squeeze in so much features with so few characters is a mystery to me. I think you are a genius!

H.G, I think you are right that the method (if it works???) will solve lots of ad-hoc solutions like extending by two plys when entering a pawn ending.

H.G, first I thought of doing the same as you once proposed by looking at the number of own moves, but I then realised that would lead to some problems (not that I say that I am right). The problems I see with looking deeper ahead on your own moves is that it will lead you to look far ahead on positions with low mobility for yourself that usually would not favour your cause.

The advantage I see with my proposal is that you search those moves where the opponent does not have many options, hence controlling the game.

My thought experiment is completly unrealistic but goes like this. Let us say that you have two sub tress, each of them depth 2, in the search tree but unfortunately you do not have so much time left. The first sub tree has two moves connected to its root and 44 moves connected to each of the two nodes/moves (in total 90 nodes), The other sub tree has 30 moves connected to the root and each of the 30 nodes has two moves connected (in total 90 nodes). I would prefer searching the second sub tree because then, if I have almost perfect move ordering, I would only have to show that two of the opponents moves are bad if I was lucky to choose the best move for me. In the second tree I would have to show that all 30 of the opponents moves are bad before I could be sure my move was good. So in some way I think my Idea will work quite well with alpha beta. I agree that if we would do plain min-max the ideas would not be so much different. I know that my thought experiment has some flaws but I am so tired now and have to sleep. Sorry!

Laszlo, Álvaro and Karlo, I think all of you are right after a quick lookup of all the different types of searches you mentioned on the internet. My idea has similarities to all of them and I am really glad you discuss ways to improve general ways of searching not limited only to chess.

Good luck and thank you all for this really interesting discussion!!!

[zamar]

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