Below is the basic structure of my alpha-beta search. My question is a sanity check: Does the use of the transposition table look correct? (Notes: zobrist is updated incrementally in make/undoMove, and addTransposition takes the zobrist, depth, eval, and type.).
Thanks,
-Erin
Code: Select all
function absearch(int a, int b, int depth, bool quiesce)
{
entry = getTransposition(zobrist);
if (entry && entry.depth >= (quiesce ? 0 : depth))
{
if (entry.type == Type.Exact && entry.eval > a && entry.eval < b)
{
return entry.eval;
}
else if (entry.type == Type.Beta && entry.eval >= b)
{
return b;
}
else if (entry.eval <= a)
{
return a;
}
}
if (quiesce)
{
eval = evaluate();
if (eval > a)
{
if (eval >= b)
{
addTransposition(zobrist, 0, b, Type.Beta);
return b;
}
a = eval;
}
}
if (null_move_allowed)
{
makeMove(null);
eval = -absearch(-b, -b + 1, depth - R - 1);
undoMove(null);
if (eval >= b)
{
addTransposition(zobrist, max(0, depth - R), b, Type.Beta);
return b;
}
}
localBest = -inf;
movelist = getMoves(quiesce);
foreach move in movelist
{
makeMove(move);
eval = -absearch(-b, -a, depth - 1);
undoMove(move);
if (eval > a)
{
if (eval >= b)
{
addTransposition(zobrist, quiesce ? 0 : depth, b, Type.Beta, move);
return b;
}
addTransposition(zobrist, quiesce ? 0 : depth, eval, Type.Exact, move);
localBest = eval;
a = eval;
}
}
if (localBest < a)
{
addTransposition(zobrist, quiesce ? 0 : depth, a, Type.Alpha);
}
return a;
}
If your logic was that a type beta can't reach that point - note that type beta that aren't sufficient to fail high DO reach that point.