当前位置: 首页 > 知识库问答 >
问题:

使用内存的alpha-beta搜索何时返回截止值?

宫子晋
2023-03-14

我已经使用换位表实现了 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;
}

共有1个答案

颜楚青
2023-03-14

我的实现似乎与此相冲突

换位表查找的代码对我来说似乎是对的。它大致相当于维基百科上的那个。

// 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页面: 这是迭代深化调用: 当然,当我知道游戏中的总移动次数时,我可以使用深度