Author: Vincent Diepeveen
Date: 13:54:02 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. You are wrong and Christophe is right in general. Please consider a search depth of 10 ply. Now we move to 11 ply. Assuming no extensions that cripple the search and that qsearch is a constant overhead then: The increase in branching factor is caused by the average number of moves we search extra when going from 10 ply lines to 11 ply lines. You are focussing upon 1 ply which is an all node, so you search all moves there. But your logics should try to understand that branching factor is a moving thing. When we move from 10 to 11 we have a branching factor. When we just study a 1 ply search we do not have a branching factor yet as we started with nothing and went to 1 ply. That's a very bad example to use. Dividing by 0 is very hard. In openings position branching factor moving from 0 to 1 ply: 20 / 0 = ???? What's the result of 20 / 0 ? So let's not discuss about 1 or 2 nodes more or extra nor discuss 1 ply searches. That is for academics who like to discuss the difference between 1 and 2 nodes. Let's look at the big picture. The big picture is simple. The average number of moves searched extra compared to previous iteration is the branching factor. Leafs in qsearch have nothing to do with that. >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 nodes 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). >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.