Author: Dan Newman
Date: 00:13:19 02/18/00
Go up one level in this thread
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
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.