I'm trying to put Transposition tables into my alpha beta scout. I do see an incremental speed boost I think toward mid or late game, however, even with a table size of 1-2GB, its may or may not be slower than just not reading from the Transpose table at all. I'm also noticing some less than efficient moves if I were to play the exact same game without the tables.
I tested my Zobrist key hashing, and they come out properly even after making and undoing moves. I don't believe they are the issue. I tried to follow the advice of these articles in designing the alpha/beta pruning. http://web.archive.org/web/20070809015843/http://www.seanet.com/~brucemo/topics/hashing.htm http://mediocrechess.blogspot.com/2007/01/guide-transposition-tables.html
Can anyone help me identify a mistake? Perhaps I'm not understanding the evaluation of checking alpha vs beta from the hash. Or is 1-2GB too small to make a difference? I can post more of the Transposition table code if need be.
public int alphaBetaScout(Board board, int depth, int alpha, int beta, bool color, bool
quiscence)
{
// !!!! With or without this specific section, and any other Transpose.Insert, doesn't make the game play or evaluate any faster.
HashType type = HashType.AlphaPrune;
HashEntry h = Transpose.GetInstance().Get(board.zobristKey);
if (h != null)
{
if (h.depth >= depth)
{
if (h.flag == HashType.ExactPrune)
{
return h.scored;
}
if (h.flag == HashType.AlphaPrune)
{
if(h.scoredState > alpha)
{
alpha = h.scored;
}
}
if (h.flag == HashType.BetaPrune)
{
if(h.scoredState < beta)
{
beta = h.scored;
}
}
if (alpha >= beta)
{
return alpha;
}
}
}
if (board.terminal)
{
int scoredState = board.Evaluate(color);
Table.GetInstance().Add(board.zobristKey, depth, Entry.EXACT, scoredState);
return scoredState;
}
//May do Quescience search here if necessary && depth = 0
Stack movesGenerated = GeneratePossibleMoves();
while(!movesGenerated.isEmpty())
{
int scoredState = MAXNEGASCOUT;
board.MakeMove(movesGenerated.pop());
int newAlpha = -(alpha +1)
scoredState = -alphaBetaScout(board, depth - 1, newAlpha, -alpha, !color, quiscence);
if (scoredState < beta && alpha < scoredState)
{
scoredState = -alphaBetaScout(board, depth - 1, -beta, -scoredState, !color, quiscence);
}
board.UndoMove();
if (scoredState >= beta)
{
Table.GetInstance().Add(key, depth, Entry.BETA, beta);
return scoredState;
}
if (scoredState > alpha)
{
type = HashType.ExactPrune;
alpha = scoredState;
}
}
Table.GetInstance().Add(key, depth, type, alpha);
return alpha;
}