TalkChess.com
Hosted by Your Move Chess & Games

 Counting depth as a function of number of legal moves Goto page 1, 2  Next
Author Message
Pio Korinth

Joined: 25 Feb 2012
Posts: 27
Location: Stockholm

 Posted: Tue Feb 28, 2012 10:32 pm    Post subject: Counting depth as a function of number of legal moves 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

Joined: 14 Mar 2006
Posts: 2187
Location: Ethiopia

 Posted: Wed Feb 29, 2012 5:26 am    Post subject: Re: Counting depth as a function of number of legal moves 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._________________https://sites.google.com/site/dshawul/ https://github.com/dshawul
Heiner Marxen

Joined: 08 Mar 2006
Posts: 39
Location: Germany, Berlin

Posted: Wed Feb 29, 2012 7:39 pm    Post subject: Re: Counting depth as a function of number of legal moves

 Pio wrote: 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

 Quote: 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!!!
H.G.Muller

Joined: 10 Mar 2006
Posts: 12777
Location: Amsterdam

 Posted: Wed Feb 29, 2012 8:52 pm    Post subject: Re: Counting depth as a function of number of legal moves 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

Joined: 09 Mar 2006
Posts: 52
Location: Budapest, Hungary

 Posted: Thu Mar 01, 2012 2:26 pm    Post subject: Re: Counting depth as a function of number of legal moves 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!_________________Regards, László
Álvaro Begué

Joined: 09 Mar 2010
Posts: 162
Location: New York

 Posted: Thu Mar 01, 2012 7:16 pm    Post subject: Re: Counting depth as a function of number of legal moves 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 Jr.

Joined: 22 Mar 2006
Posts: 195

Posted: Thu Mar 01, 2012 8:49 pm    Post subject: Re: Counting depth as a function of number of legal moves

 AlvaroBegue wrote: 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.
_________________
Best Regards,
Karlo Bala Jr.
Álvaro Begué

Joined: 09 Mar 2010
Posts: 162
Location: New York

Posted: Thu Mar 01, 2012 9:02 pm    Post subject: Re: Counting depth as a function of number of legal moves

Karlo Bala wrote:
 AlvaroBegue wrote: 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.

 Lazlo Gaspar wrote: 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 Korinth

Joined: 25 Feb 2012
Posts: 27
Location: Stockholm

Joona Kiiski

Joined: 18 Jan 2009
Posts: 546

 Posted: Fri Mar 02, 2012 11:18 am    Post subject: Re: Counting depth as a function of number of legal moves 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 _________________Joona Kiiski
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 All times are GMTGoto page 1, 2  Next Page 1 of 2

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumForum Help and Suggestions
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum