我已经使用换位表实现了 alpha beta 搜索。
关于在表中存储截止值,我有正确的想法吗?
具体来说,我在表命中时返回截止值的方案是否正确?(同样,存储它们。)我的实现似乎与这个冲突,但直觉上它似乎是正确的。
此外,我的算法从不存储带有 at_most 标志的条目。我应该何时存储这些条目?
下面是我演示主要思想的(简化)代码:
int ab(board *b, int alpha, int beta, int ply) {
evaluation *stored = tt_get(b);
if (entryExists(stored) && stored->depth >= ply) {
if (stored->type == at_least) { // lower-bound
if (stored->score >= beta) return beta;
} else if (stored->type == at_most) { // upper bound
if (stored->score <= alpha) return alpha;
} else { // exact
if (stored->score >= beta) return beta; // respect fail-hard cutoff
if (stored->score < alpha) return alpha; // alpha cutoff
return stored->score;
}
}
if (ply == 0) return quiesce(b, alpha, beta, ply);
int num_children = 0;
move chosen_move = no_move;
move *moves = board_moves(b, &num_children);
int localbest = NEG_INFINITY;
for (int i = 0; i < num_children; i++) {
apply(b, moves[i]);
int score = -ab(b, -beta, -alpha, ply - 1);
unapply(b, moves[i]);
if (score >= beta) {
tt_put(b, (evaluation){moves[i], score, at_least, ply});
return beta; // fail-hard
}
if (score >= localbest) {
localbest = score;
chosen_move = moves[i];
if (score > alpha) alpha = score;
}
}
tt_put(b, (evaluation){chosen_move, alpha, exact, ply});
return alpha;
}
我的实现似乎与此相冲突
换位表查找的代码对我来说似乎是对的。它大致相当于维基百科上的那个。
// Code on Wikipedia rewritten using your notation / variable names
if (entryExists(stored) && stored->depth >= ply)
{
if (stored->type == at_least)
alpha = max(alpha, stored->score);
else if (stored->type == at_most)
beta = min(beta, stored->score);
else if (stored->type == exact)
return stored->score;
if (alpha >= beta)
return stored->score;
}
这相当于(检查<代码> if(α
if (entryExists(stored) && stored->depth >= ply)
{
if (stored->type == at_least)
{
alpha = max(alpha, stored->score);
if (alpha >= beta) return stored->score;
}
else if (stored->type == at_most)
{
beta = min(beta, stored->score);
if (alpha >= beta) return stored->score;
}
else if (stored->type == exact)
return stored->score;
}
这可以更改为:
if (entryExists(stored) && stored->depth >= ply)
{
if (stored->type == at_least)
{
// if (max(alpha, stored->score) >= beta) ...
if (stored->score >= beta) return stored->score;
}
else if (stored->type == at_most)
{
// if (min(beta, stored->score) <= alpha) ...
if (stored->score <= alpha) return stored->score;
}
else if (stored->type == exact)
return stored->score;
}
剩下的区别是,维基百科使用故障软优化,而你的代码是经典的阿尔法-贝塔修剪(故障硬)。Fail-soft是一个小的改进,但并没有改变算法的关键点。
我的算法从不存储带有atmost标志的条目。我应该什么时候存储这些条目?
在如何存储确切的
/at_most
节点类型时存在一个错误。这里假设节点的类型始终为exact
:
tt_put(b, (evaluation){chosen_move, alpha, exact, ply});
实际上它可以是一个at_most
节点:
if (alpha <= initial_alpha)
{
// Here we haven't a best move.
tt_put(b, (evaluation){no_move, initial_alpha, at_most, ply});
}
else
tt_put(b, (evaluation){chosen_move, alpha, exact, ply});
好的,我的问题对于任何玩过棋盘游戏编程的人来说都应该很熟悉,所以这里是: 我实现了MiniMax算法的一种变体(返回移动而不是最小/最大值) 我还尝试将其设置为alpha beta版,尽管最终完全失败 这是我的极大极小码: 有什么想法吗?如何调整上述内容,使其成为Alpha Beta搜索? 下面是我尝试的Alpha-Beta转换(失败得很惨): 提示(以避免任何误解): > 此- 和分别被定义为一
本篇将简要介绍α-β剪枝,这是一种基于剪枝( α-βcut-off)的深度优先搜索(depth-first search)。 一、什么是α剪枝? (1)将走棋方定为MAX方,因为它选择着法时总是对其子节点的评估值取极大值,即选择对自己最为有利的着法; (2)将应对方定为MIN方,因为它走棋时需要对其子节点的评估值取极小值,即选择对走棋方最为不利的、最有钳制作用的着法。 (3)在对博弈树(博弈树是指
我在我的象棋引擎中添加了静止搜索,使用了alpha-beta prunning和称为内部MTD(f)算法的转置表。在我的主搜索中,在到达深度=0(叶节点)后,我调用了Quiescence search,它被实现为简单的alpha beta prunning,而没有转置表(因为测试表明,搜索仅捕获在没有TT的情况下工作得更快) 我注意到有关此主题的伪代码中未涵盖的内容:当我在主搜索中处于 depth
我在写国际象棋的最小化算法。 对于不带alpha-beta修剪的minimax和带alpha-beta修剪的minimax,我得到了不同的最终结果值。 下面是我的伪代码。有人能帮我吗? 极小极大() αβ() 董事会代表董事会。对于每一次移动,我都在传递的董事会对象的副本上移动,然后将这个临时董事会传递给进一步的调用。 evaluateBoard(董事会b)接收董事会并根据给定董事会情景计算分数。
我用alpha-beta修剪创建了一个极大极小函数,我用迭代深化调用它。问题是,当计时器完成时,该函数会一直运行,直到在计时器用完之前,它在开始的深度上完成为止。 我想要的是:当计时器运行完时,minimax函数应该退出并返回none(我将best move保留在minimax之外,请参阅下面的minimax调用代码),或者返回之前计算的best move。我似乎不知道如何在minimax函数中实
如何知道何时可以停止增加使用negamax alpha beta修剪和换位表的迭代深化算法的深度?以下伪代码取自wiki页面: 这是迭代深化调用: 当然,当我知道游戏中的总移动次数时,我可以使用深度