TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Heiner Marxen

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

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

 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!!!
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
Pio Korinth Tue Feb 28, 2012 10:32 pm
Daniel Shawul Wed Feb 29, 2012 5:26 am
Re: Counting depth as a function of number of legal moves Heiner Marxen Wed Feb 29, 2012 7:39 pm
H.G.Muller Wed Feb 29, 2012 8:52 pm
Stefano Gemma Sun Aug 12, 2012 8:01 am
H.G.Muller Sun Aug 12, 2012 8:53 am
Pio Korinth Tue Aug 14, 2012 7:28 pm
Laszlo Gaspar Thu Mar 01, 2012 2:26 pm
Álvaro Begué Thu Mar 01, 2012 7:16 pm
Karlo Bala Jr. Thu Mar 01, 2012 8:49 pm
Álvaro Begué Thu Mar 01, 2012 9:02 pm
Pio Korinth Thu Mar 01, 2012 10:48 pm
Pio Korinth Thu Aug 09, 2012 9:52 pm
Joona Kiiski Fri Mar 02, 2012 11:18 am
Uri Blass Fri Mar 02, 2012 8:40 pm

 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