Author: Uri Blass
Date: 15:31:33 03/14/04
Go up one level in this thread
On March 14, 2004 at 16:54:02, Vincent Diepeveen wrote: >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. The average number of moves that are added in iteration n to a position of iteration n-1 is connected with the branching factor of iteration n. This is not the average number of moves that are searched from a position even if you ignore qsearch nodes. Suppose for example that it is easy to see by evaluation that there is a long sequence of moves when all of them except one are losing and after making the moves it is easy to find it by evaluation. You have something like: Iteration 1: 1.all legal moves Iteration 2: 1.e4 all legal moves(not e4 was evaluated in iteration 1 as losing so they are not searched) iteration 3: 1.e4 e5 all legal moves(not e5 was evaluated in iteration 2 as losing so they are not searched) iteration 4: 1.e4 e5 2.Nf3 all legal moves(not Nf3 pruned for similiar reasons) ... iteration 11: 1.e4 e5 2.Nf3 Nf6 3.Nxe5 d6 4.Nf3 Nxe4 5.d4 d5 all legal moves Every iteration of the first 11 iterations searches the number of legal moves so you have very small branching factor but all the legal moves are searched in every node that is not qsearch node so if you do not include qsearch nodes you get big average of moves that were searched. 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.