Author: Vincent Diepeveen
Date: 03:53:18 03/15/04
Go up one level in this thread
On March 14, 2004 at 18:31:33, Uri Blass wrote: >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) You failed your exam. Additionally you show zero proof of anything. > >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.