Author: Andrei Fortuna
Date: 17:06:10 03/21/00
In my chess program Freyr I've used simple alpha beta from the start, each time
I tried to change it to pvs/negascout it didn't work as expected because it just
generated too many nodes. Does anyone else experienced this behavior ? Is there
a logical explanation for this ?
First I thought I needed better move ordering, so I used SEE for ordering
captures and history scores for non-captures, but the efect was the same.
Then I rewrote the search function, making it as simple as possible, generate
all moves from the start, score captures based on SEE and non captures based on
history scores (making sure that the SEE scores are a few orders of magnitude
higher than history scores so winning captures get first), then sort the move
list and process moves, no hashtable or any other trick. To my disapointment the
simple AB was again generating much more less nodes than my PVS.
Here's an approximation of the simplified code I used :
Search(alpha, beta, depth, ply)
if (depth <= 0)
return Quiescence(...)
[generate all moves]
[score moves based on SEE and history]
[sort moves based on score]
moves_searched = 0;
for each move m {
make move(m)
#if USE_AB
score = -Search(-beta, -alpha, ...)
#else // pvs
if (moves_searched == 1)
score = -Search(-beta, -alpha, ...)
else {
score = -Search(-alpha-1, -alpha, ...)
if (score > alpha && score < beta)
score = -Search(-beta, -alpha, ...)
}
#endif
unmake move(m)
if (score > alpha){
if (score >= beta)
return score;
alpha = score;
}
moves_searched++;
}
return alpha
This page took 0.01 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.