Author: Uri Blass
Date: 12:59:46 03/14/04
Go up one level in this thread
On March 14, 2004 at 15:50:30, Uri Blass wrote: >On March 14, 2004 at 15:00:44, Christophe Theron wrote: > >>On March 13, 2004 at 11:52:07, Steven Edwards wrote: >> >>>Consider the position BWTC.0025: >>> >>>[D] r1bq1r1k/ppp1N1p1/7p/2bp1pN1/2Bn1B1Q/8/PP3PP1/R3R1K1 w - - 0 1 >>> >>>It's a mate in three starting with 1. Qxh6+; however, I picked it for an example >>>as it also has a number of possible knight forks for White. >>> >>>A traditional chess programs can discover knight forks only by search. A goal >>>for Symbolic is to recognize tactical motifs via pattern matching, use these >>>ideas for plan formation, and then use the plan to guide a very narrow search to >>>produce a verification of the plan. >> >> >> >>I do not want to criticize your efforts to conduct a narrower, smarter search, >>because I believe that there is something to be gained from this. >> >>However I would like to point out that using a classical alpha-beta approach >>improved by state-of-the-art selective search techniques, current top chess >>programs have a branching factor that is clearly below 3. >> >>That means that at any point in the search tree, the average number of moves >>searched is somewhere between 2 and 3. > > >No > >The branching factor is not the average number of moves search somewhere. > >1)By this logic even if you use minimax then majority of the positions are >leaves when you search 0 moves so the average number of moves is small. > >average number of moves is >(400*0+20*20+1*20)/421=420/421 if we take the opening position and search all >lines to depth 2. > >2)If you mean to average number of moves that you search not in the leaves then >it can be clearly bigger than the branching factor >suppose that you use selective search when you always choose only one move(the >move with the best evaluation). To make it clear you need to make all moves to calculate evaluation and compare but you choose to prune all moves after you make them except the move with the best evaluation. I will give an example for the way that the dubious search I thought about can be done You may get a tree 1.a3 0.00 1.a4 -0.01 1.b3 0.01 ... 1.d4 0.06 1.e4 0.07(maximal) 1.f3 and other legal moves 1.e4 a6(0.12) 1.e4 a5(0.13) ... 1.e4 e5(0.04 maximal) Later you may decide on your move based on the tree and you may decide 1.d4 based on search to depth 2 because 1.d4 gets a score of 0.06 when 1.e4 e5 only a score of 0.04. >You can search to the end of the game(the search is dubious but my point is that >you get a very small branching factor). > >Now what is the average number of nodes that you search in no leaf positions. >The average is very big because in every no leaf position you search all moves. > >Uri
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.