ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Counting depth as a function of number of legal moves
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Heiner Marxen



Joined: 08 Mar 2006
Posts: 39
Location: Germany, Berlin
PostPost subject: Re: Counting depth as a function of number of legal moves    Posted: Wed Feb 29, 2012 7:39 pm Reply to topic Reply with quote
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 Shocked

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!!!
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
Counting depth as a function of number of legal moves Pio Korinth Tue Feb 28, 2012 10:32 pm
      Re: Counting depth as a function of number of legal moves 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
      Re: Counting depth as a function of number of legal moves H.G.Muller Wed Feb 29, 2012 8:52 pm
            Re: Counting depth as a function of number of legal moves Stefano Gemma Sun Aug 12, 2012 8:01 am
                  Re: Counting depth as a function of number of legal moves H.G.Muller Sun Aug 12, 2012 8:53 am
                        Re: Counting depth as a function of number of legal moves Pio Korinth Tue Aug 14, 2012 7:28 pm
      Re: Counting depth as a function of number of legal moves Laszlo Gaspar Thu Mar 01, 2012 2:26 pm
            Re: Counting depth as a function of number of legal moves Álvaro Begué Thu Mar 01, 2012 7:16 pm
                  Re: Counting depth as a function of number of legal moves Karlo Bala Jr. Thu Mar 01, 2012 8:49 pm
                        Re: Counting depth as a function of number of legal moves Álvaro Begué Thu Mar 01, 2012 9:02 pm
                              Re: Counting depth as a function of number of legal moves Pio Korinth Thu Mar 01, 2012 10:48 pm
                                    Re: Counting depth as a function of number of legal moves Pio Korinth Thu Aug 09, 2012 9:52 pm
      Re: Counting depth as a function of number of legal moves Joona Kiiski Fri Mar 02, 2012 11:18 am
            Re: Counting depth as a function of number of legal moves Uri Blass Fri Mar 02, 2012 8:40 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
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




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads