NegaScout与国际象棋中的Zobrist换位表
本文关键字:Zobrist 换位 国际象棋 NegaScout | 更新日期: 2023-09-27 18:34:21
我正在尝试将转置表放入我的alpha beta侦察机中。我确实看到了我认为在游戏中期或后期的增量速度提升,但是,即使表格大小为 1-2GB,它也可能比根本不从 Transpose 表中读取要慢,也可能不会慢。我还注意到,如果我在没有桌子的情况下玩完全相同的游戏,一些效率较低的动作。
我测试了我的 Zobrist 密钥哈希,即使在进行和撤消移动后,它们也能正常工作。我不认为他们是问题所在。我试图在设计 alpha/beta 修剪时遵循这些文章的建议。http://web.archive.org/web/20070809015843/http://www.seanet.com/~brucemo/topics/hashing.htm http://mediocrechess.blogspot.com/2007/01/guide-transposition-tables.html
谁能帮我识别错误?也许我不理解从哈希中检查 alpha 与 beta 的评估。还是 1-2GB 太小而无法发挥作用?如果需要,我可以发布更多的转置表代码。
// !!!! 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.BetaPrune)
{
if(h.scoredState < beta)
{
beta = h.scored;
}
}
if (h.flag == HashType.AlphaPrune)
{
if(h.scoredState > alpha)
{
alpha = 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;
我相信
在一开始搜索表格之前,您需要复制您的 alpha 和 beta 边界。当您更新边界(使用表格或通过搜索(时,这些副本不会更改。
然后,当您将新条目添加到转置表中时,您应该将 scoredState 与表中保存的边界(即您在开始时创建的边界的副本(进行比较,而不是将其与更新的边界进行比较,因为更新的边界不是存储在表中的边界,而是备份!