α-Beta国际象棋引擎搜索算法没有正确的移动

Question

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

目前，这两种算法在3+的搜索深度上花费了相当长的时间，尽管极小极大有效，而Alpa-Beta正在做出非常可怕的举动。下面的算法是基于在国际象棋编程维基中找到的伪码。

当前位置强度

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算法来说，它都是代码的核心和灵魂。如果您的称重是错误的，您甚至不能认为您的代码会产生(甚至接近)最佳移动。现在，在游戏中棋子相等的每一步，你的计算都会说，位置是相等的，但实际上并非如此。

现在，例如。国际象棋中有大量的攻击开口，在棋盘中，一方为了位置而放弃材料(称为棋盘)。在这种情况下，你的引擎会说，那一侧的位置会变弱，但实际上并非如此。

在权重计算函数中可以包括以下几点：

• 是的，当然，物质力量是最重要的事情之一。
• 有可能被任何一边的碎片占据的方格数。例如：f3上的骑士可能会占据空旷的8个广场中的任何一个(h2，h4，d2，d4，g1，g5，e1，e5)。
• 几乎所有的碎片都有可能更强的在中间，在板的两侧。所以，你也可以在正方形上分配一些重量。
• 此外，如果你正在制作一个国际象棋引擎，我建议你有一个数据库，最常见的空缺，位置牺牲和结束游戏。
• 此外，你的体重必须考虑战术，如发现的攻击，针，串，叉，这一切都是可能的，只有考虑到第2点。

最后，祝你在开发一个伟大的国际象棋引擎方面好运。:)

编辑:我没看到你问题的第二部分。我想说的是，可能α-β剪枝不能修剪它应该修剪的边缘，因为重量没有明显的分布。如果您实现了更好的权重计算功能，这也应该会得到改善。此外，当游戏树的深度很大时，α-beta剪枝效果很好。在小深度树中，α-β和min-max之间的性能差异几乎不可见.因此，如果将树的深度提高到6，即使使用基本实现，性能差异也应该是可见的。

EDIT2:几个链接：

如何实现高效的α-Beta剪枝游戏搜索树？

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

Minimax的α-β剪枝

EDIT3:深度3意味着，你移动，你的对手做一个，然后你做一个。让我们举个例子。你的主教在c1，骑士在d2，敌人当兵在d5，敌人骑士在h6。你行动吧，Ne6。对手移动，当兵，骑士。你移动主教拿骑士。现在，在下一个动作中，如果h6上的敌人骑士被任何一个棋子(典当/主教等)所支持，你的主教就消失了，但那就是移动4，你的位置计算功能无法理解。根据它的说法，这是一种平等的交易。比如说，在接下来的3次移动中，没有移动顺序给了你任何材料上的优势，所以，这个移动顺序很可能被选择，你说这是一个愚蠢的移动(obvs是)，但是你的α-β剪枝并不是罪魁祸首。现在，如果选择了这个Nf6，那么您的骑士就死了，在接下来的移动中，它又是一个新的董事会和一个新的情况。所以，如果你试着去理解，你会的。我把我的案子放这儿。