Author: Robert Hyatt
Date: 06:42:37 10/20/98
Go up one level in this thread
On October 20, 1998 at 09:03:46, Jari Huikari wrote: >On October 20, 1998 at 08:11:21, Robert Hyatt wrote: > >>>On October 20, 1998 at 00:34:41, Komputer Korner wrote: >>> >>>>Bob why can't programs present the move list either in a log file or on screen >>>>in the alpha beta order? CSTAL does a 1 ply search to get the score evals for >>>>each legal move but unfortunately it doesn't list the moves in the alpha beta >>>>order of the engine search. Why couldn't a program do this? > >>..the tree, assuming there are 38 moves to be made, would require 19X as long >>to produce as just finding the best move and going on to the next iteration. >> >>With a branching factor of 3x this costs almost 3 plies. With a branching >>factor of 2.5X, this is more than 3 plies. Either is *hugely* expensive and >>makes such analysis useless... > >What about only having higher value for beta cutoffs in Ply=2. Won't it find >then exact values of the best replies for opponent and so with quite a low >cost values for legal moves? Two plies minimax, the rest alpha-beta. Can it >cost many plies? > > Jari no real change. REmember that with PVS 99.9999% of the nodes are searched with a null window (X,X+1). if you want to minimax at the first two plies, rather than just at the first ply, the math would look like this: normal alpha/beta nodes= W^ceil(D/2)+W^floor(D/2) where ceil=round up, and floor = round down. For D even, we shorten this to N=2*W^(D/2) to minimax at ply=2 also, you get N=W*(W^ceil((D-1)/2)+W^floor((D-1)/2)) which is about W times slower where W = the number of nodes at each ply. Very ugly exponential explosion. Several of us used to do this for a couple of iterations to get good scores to sort the ply=1 move list, but we only did this for a 3-4 ply search, then reverted to normal for the 5-9 ply searches...
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.