Author: Sanjiv Karnataki
Date: 08:37:34 02/18/00
Go up one level in this thread
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. b) is move ordering at the root based on the scores returned for each move at the previous iteration? c) what are the other techniques of move ordering and is there a site that discusses these ? Thank you in advance. Sanjiv.
This page took 0.04 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.