Author: José Carlos
Date: 09:02:59 02/18/00
Go up one level in this thread
On February 18, 2000 at 11:37:34, Sanjiv Karnataki wrote: >On February 18, 2000 at 03:13:19, Dan Newman wrote: > >>On February 17, 2000 at 15:30:10, Jeff Anderson wrote: >> >>>Hi, right now I am trying to learn about the Alpha-Beta algorithm, I have a few >>>questions that maybe someone can help me with: >>> >>> >>>With sophisticated move ordering, like that found in Crafty, how much time is >>>saved (like in actual numbers or %'s) over having no alpha-beta alogirithm at >>>all? >>> >>>With random move ordering how much time is saved over having no alpha-beta >>>algorithm at all? >>> >> >>This will vary with depth searched: the deeper you search the greater the >>savings alpha-beta gives. Let's imagine we search to ten plies deep and >>that the mini-max branching factor is 36 (about like chess). With mini-max >>we will visit 36^10 == 3.7x10^15 nodes. The last time I tried alpha-beta >>without any attempt at move ordering I got an average branching factor of >>about 11 or so (IIRC). So 11^10 == 2.6 x10^10 nodes would be visited in >>this case. Thus alpha-beta, even with "random" move ordering, can give an >>enormous speedup--in this case 142,000 times. >> >>Now, if you put in good move ordering you can get the branching factor down >>to about 6, and if you also do the null-move heuristic, down to about 3. >>So you might then visit 3^10 == 59,000 nodes to get 10 plies deep, which >>is about 60 billon times as fast as pure mini-max... >> >>-Dan. >> >>> >>>Are there any top programs which do not use the alpha-beta algorithm in their >>>search? >>> >>>If one has a program that creates a tree with no evaluations and no effort to >>>find the best move, simply creating a brute force tree, how much faster will >>>this be than when it creating a tree with evaluations attached (assume no >>>pruning or anything to the tree)? >>> >>> >>> >>>Thanks in advance, >>>Jeff > > >That is very impressive, but I am new here so a few questions: > >a) by move ordering, does that mean move ordering at the root only. No, move ordering is important at every ply, but usually managed in a different way at the root. >b) is move ordering at the root based on the scores returned for each move at >the previous iteration? Yes, the PV move must always be the first searched, but not only at the root, but at every ply. >c) what are the other techniques of move ordering and is there a site that >discusses these ? Now I'm at work and can't point you any web sites, but there are a lot. If no one else tell you, I'll look for them later at home. >Thank you in advance. > >Sanjiv. José C.
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.