javascript - Alpha-Beta 国际象棋引擎搜索算法没有做出正确的 Action

Question

我成功地实现了 minimax 算法，并且正在寻找 Alpha-Beta 的改进。

目前，这两种算法在 3+ 的搜索深度下都需要非常长的时间，但是 minimax 有效，而且 Alpa-Beta 正在做出非常可怕的举动。下面的算法基于在 chess programming wiki 中找到的伪代码。 .

当前位置强度

calculatePositionStrength()    //currently very simple
    return (My piece material - opponent's piece material)

算法:chessjs.move(m) 走棋。 chessjs.undo() 撤消它。

var score = 0, bestMove;

function alphaBetaMax(alpha, beta, depthleft) {
    if(depthleft==0) {
        return calculatePositionStrength();
    }
    chessjs.moves().forEach(function(move) {
        chessjs.move(move);
        score = alphaBetaMin(alpha, beta, depthleft-1);
        chessjs.undo();
        if(score>=beta) {
            return beta;   // fail hard beta-cutoff
        }
        if(score>alpha) {
            bestMove = move;
            alpha = score; // alpha acts like max in MiniMax
        }
    });
    return alpha;
}

function alphaBetaMin(alpha, beta, depthleft) {
    if(depthleft==0) {
        return -calculatePositionStrength();
    }
    chessjs.moves().forEach(function(move) {
        chessjs.move(move);
        score = alphaBetaMax(alpha, beta, depthleft-1);
        chessjs.undo();
        if(score<=alpha ) {
            return alpha; // fail hard alpha-cutoff
        }
        if(score<beta ) {
            beta = score; // beta acts like min in MiniMax
        }
    });
    return beta;
}
alphaBetaMax(-Infinity, Infinity, 3);

我的逻辑有什么问题？我是否在正确的位置放置了移动/撤消？另外，为什么这么慢？

Answer 1

代码中的 calculatePositionStrength() 非常简单，对于任何用于机器人游戏的 AI 算法，它是代码的核心和灵魂。如果您的权衡是错误的，您甚至无法认为您的代码会产生(甚至接近)最佳移动。现在，在游戏中棋子相等的每一步，您的计算都会说位置相等，但实际上情况并非如此。

现在，例如。国际象棋中有大量的进攻空缺，其中一方放弃 Material 以获得位置(称为开局)。在这种情况下，您的引擎会说那一侧的位置较弱，但实际上并非如此。

您可以在权重计算函数中包含一些内容:

• 是的，当然，物质实力是最重要的事情之一。
• 可能被任一侧的棋子占据的方格数。例如。 f3 上的马可能会占据 8 个空方格中的任何一个(h2、h4、d2、d4、g1、g5、e1、e5)。
• 几乎所有棋子在棋盘中央的强度都比在棋盘两侧的强度大。因此，您也可以在正方形上分配一些重量。
• 此外，如果您正在制作国际象棋引擎，我建议您拥有一个包含最常见开局、位置牺牲和残局的数据库。
• 此外，您的权重必须考虑策略，例如发现的攻击、销、串、叉，而这一切只有在考虑第 2 点时才有可能。

最后，祝您在开发出色的国际象棋引擎时好运。 :)

编辑:我没有看到你问题的第二部分。我会说，可能 alpha-beta 剪枝无法剪掉它应该剪掉的边缘，因为权重分布不明显。如果您实现更好的权重计算功能，这也应该会有所改善。此外，当博弈树的深度很大时，alpha-beta 剪枝效果很好。在小深度树中，alpha-beta 和 min-max 之间的性能差异几乎不可见。因此，如果将树的深度增加到 6，即使是基本实现，性能差异也应该是可见的。

EDIT2:几个链接:

How to implement efficient Alpha-Beta pruning Game Search Tree?

https://chessprogramming.wikispaces.com/Alpha-Beta

Alpha-beta pruning for Minimax

EDIT3:深度 3 意味着，你下棋，你的对手下棋，然后你下棋。让我们举个例子。你的主教在 c1，骑士在 d2，敌人的棋子在 d5，敌人的骑士在 h6。你行动吧，Ne6。对手使走卒取马。你移动主教带骑士。现在，在下一步中，如果 h6 上的敌方骑士受到任何棋子(兵/主教等)的支持，您的主教就消失了，但那是第 4 步，您的位置计算功能无法理解。根据它，这是一个平等的交易。比如说，接下来的 3 步没有任何移动顺序给你带来任何 Material 优势，所以，这个移动顺序很可能被选中，你说这是一个愚蠢的移动(obvs 是)，但你的 alpha-beta trim 不是罪魁祸首这里。现在，如果选择了这个 Nf6，您的骑士就完蛋了，下一步又是一个新的棋盘和一个新的局面。所以，如果你试着去理解，你会的。我在这里休息。