标签: alpha-beta-pruning

我正在尝试开发一个简单的国际象棋引擎,但我正在努力实现其性能.我已经使用alpha-beta修剪和迭代加深实现了Negamax(没有任何额外的启发式),但是我无法获得超过3-4层的合理搜索时间.以下是从游戏开始我的程序日志的摘录:

2013-05-11 18:22:06,835 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 1
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 28
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 28
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A4->A6 
2013-05-11 18:22:06,835 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 2
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 90
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 118
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - …

我对 MCTS“树策略”的实施方式有些困惑。我读过的每一篇论文或文章都谈到了从当前游戏状态（在 MCTS 术语中：玩家即将采取行动的根）的树。我的问题是，即使我处于 MIN 玩家级别（假设我是 MAX 玩家），我如何选择最好的孩子。即使我选择了 MIN 可能采取的某些特定动作，并且我的搜索树通过该节点变得更深，MIN 玩家在轮到它时也可能会选择一些不同的节点。（如果 min 玩家是业余人类，它可能就像选择一些不一定是最好的节点）。由于 MIN 选择了一个不同的节点，这种类型使得 MAX 在通过该节点传播的整个工作都变得徒劳。对于我所指的步骤： https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/ 其中树政策：https : //jeffbradberry.com/images/mcts_selection.png 有点让我相信他们是从单人视角来执行它的。

我理解minimax和alpha-beta修剪的基础知识.在所有文献中,他们谈论最佳情况的时间复杂度是O(b ^(d/2)),其中b =分支因子,d =树的深度,基本情况是所有首选节点都是首先扩大.

在我的"最佳案例"的例子中,我有一个4级的二叉树,所以在16个终端节点中,我需要扩展最多7个节点.这与O(b ^(d/2))有何关系？

我不明白他们是怎么来到O(b ^(d/2)).

拜托,有人可以向我解释一下吗？吃了很多!

我正在为国际象棋比赛做AI.

到目前为止,我已经成功实现了Alpha-Beta Pruning Minimax算法,它看起来像这样(来自维基百科):

(* Initial call *)
alphabeta(origin, depth, -?, +?, TRUE)

function alphabeta(node, depth, ?, ?, maximizingPlayer)
    if depth = 0 or node is a terminal node
        return the heuristic value of node
    if maximizingPlayer
        for each child of node
            ? := max(?, alphabeta(child, depth - 1, ?, ?, FALSE))
            if ? ? ?
                break (* ? cut-off *)
        return ?
    else
        for each child of node
            ? := min(?, alphabeta(child, depth - 1, ?, ?, TRUE))
            if …

我正在为游戏开发AI,我想使用MinMax算法和Alpha-Beta修剪.

我对它是如何工作有一个粗略的想法,但我仍然无法从头开始编写代码,所以我花了最近两天在网上寻找某种伪代码.

我的问题是,我在网上发现的每个伪代码似乎都是基于找到最佳移动的价值,而我需要返回最佳移动而不是数字.

我当前的代码基于这个伪代码(源代码)

minimax(level, player, alpha, beta){  // player may be "computer" or "opponent"
    if (gameover || level == 0)
       return score
    children = all valid moves for this "player"
    if (player is computer, i.e., max's turn){
       // Find max and store in alpha
       for each child {
          score = minimax(level - 1, opponent, alpha, beta)
          if (score > alpha) alpha = score
          if (alpha >= beta) break;  // beta cut-off
       }
       return …

在我的方法newminimax499我有一个minimax算法,利用memoization和alpha beta修剪.该方法适用于3x3游戏,但是当我玩4x4游戏时,我会为计算机选择奇怪的意外位置.他仍然没有输球,但他似乎没有赢得胜利.为了说明这里的问题,从3x3和4x4的2场比赛开始.首先是一个3x3游戏的场景,其中玩家是X并进行第一步:

这不错,实际上这是人们期望计算机做的事情.现在来看看4x4游戏中的场景.O再次是计算机而X开始:

正如你所看到的,计算机只是一个接一个地将Os放入一个系统的顺序中,只有当它有潜在的胜利时才打破该命令以阻止X. 这是非常防守的比赛,不像在3x3比赛中看到的那样.那么为什么3x3和4x4的方法表现不同？

这是代码:

//This method returns a 2 element int array containing the position of the best possible 
//next move and the score it yields. Utilizes memoization and  alpha beta 
//pruning to achieve better performance. 
public int[] newminimax499(int a, int b){
    //int bestScore = (turn == 'O') ? +9 : -9;  //X is minimizer, O is maximizer
    int bestPos=-1;
    int alpha= a;
    int beta= b;
    int currentScore;
    //boardShow();
    String stateString = "";                                                
    for (int i=0; i<state.length; i++) …

我正在尝试使用换位表实现 alpha beta 剪枝，我在维基百科中找到了该算法的伪代码：https: //en.wikipedia.org/wiki/Negamax#cite_note-Breuker-1 \n但是我相信这psudocode 是错误的，我认为 alphaOrig 是无用的，而不是：

if bestValue \xe2\x89\xa4 alphaOrig\n        ttEntry.Flag := UPPERBOUND\n

它应该是：

if bestValue \xe2\x89\xa4 \xce\xb1\n        ttEntry.Flag := UPPERBOUND\n

谁能确认我是否正确或向我解释为什么我错了，谢谢！

这里是伪代码：

function negamax(node, depth, \xce\xb1, \xce\xb2, color)\n\nalphaOrig := \xce\xb1\n\n// Transposition Table Lookup; node is the lookup key for ttEntry\nttEntry := TranspositionTableLookup( node )\nif ttEntry is valid and ttEntry.depth \xe2\x89\xa5 depth\n    if ttEntry.Flag = EXACT\n        return ttEntry.Value\n    else if ttEntry.Flag = LOWERBOUND\n        \xce\xb1 := max( \xce\xb1, ttEntry.Value)\n    else if ttEntry.Flag …

这是我上一篇文章的后续内容。该代码运行时没有任何错误，并且可以计算下一个最佳移动。我一直在研究如何将换位表和移动排序合并到我的 negamax 函数中，以使其运行得更快、更准确，但对于像我这样的初学者来说，这似乎有些困难和先进。

你可以在这里找到我的代码。

在研究国际象棋编程维基时，我发现了一些换位表的示例代码：

def negamax(node, depth, alpha, beta, color):
alphaOrig = alpha

## Transposition Table Lookup; node is the lookup key for ttEntry
ttEntry = transpositionTableLookup(node)
if ttEntry.is_valid is True and ttEntry.depth >= depth:
    if ttEntry.flag == EXACT :
        return ttEntry.value
    if ttEntry.flag == LOWERBOUND:
        alpha = max(alpha, ttEntry.value)
    if ttEntry.flag == UPPERBOUND:
        beta = min(beta, ttEntry.value)

    if alpha >= beta:
        return ttEntry.value

if depth == 0 or node is terminal_node:
    return color* heuristic_value_of_node

childNodes = …

我已经使用换位表实现了 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-beta 剪枝算法的硬失败和软失败版本，我找不到其行为的差异：

努力失败

function alphabeta(node, depth, \xce\xb1, \xce\xb2, maximizingPlayer) is\n    if depth = 0 or node is a terminal node then\n        return the heuristic value of node\n    if maximizingPlayer then\n        value := \xe2\x88\x92\xe2\x88\x9e\n        for each child of node do\n            value := max(value, alphabeta(child, depth \xe2\x88\x92 1, \xce\xb1, \xce\xb2, FALSE))\n            if value \xe2\x89\xa5 \xce\xb2 then\n                break (* \xce\xb2 cutoff *)\n            \xce\xb1 := max(\xce\xb1, value)\n        return value\n    else\n        value := +\xe2\x88\x9e\n        for each child of node do\n            value := …