阿尔法贝塔象棋引擎搜索算法没有做出正确的举动

Alpha-Beta chess engine search algorithm not making proper moves

本文关键字：贝塔 引擎 搜索算法 阿尔法      更新时间：2023-09-26

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

目前，这两种算法在3+的搜索深度下都需要相当长的时间，但minimax有效，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);

我的逻辑出了什么问题？我是否在正确的位置进行移动/撤销？还有，为什么这么慢？

代码中的calculatePositionStrength()非常琐碎，对于任何用于机器人游戏的AI算法来说，它都是代码的核心和灵魂。如果你的称重是错误的，你甚至无法想象你的代码会产生（甚至接近）最佳的移动。现在，在游戏中棋子相等的每一步，你们的计算都会说，位置是相等的，但事实并非如此。

现在，国际象棋中有大量的攻击空位，其中一方为了位置而放弃材料（称为Gambits）。在这种情况下，你的发动机会说那一侧的位置较弱，但事实并非如此。

你可以在你的重量计算功能中包括的一些东西可以是：

  • 是的，当然，物质力量是最重要的东西之一
  • 任何一边的碎片可能占据的正方形数量。f3上的骑士可能会占据空的8个方块（h2、h4、d2、d4、g1、g5、e1、e5）中的任何一个
  • 几乎所有的棋子都有可能在中心比在棋盘两侧更强。所以，你也可以在正方形上分配一些权重
  • 此外，如果你正在制作一个国际象棋引擎，我建议你有一个最常见的开局、位置牺牲和结束游戏的数据库
  • 此外，你的体重必须考虑战术，如发现的攻击，大头针，串，叉，这一切只有考虑到第2点才有可能

最后，祝你好运，开发出一个伟大的国际象棋引擎

编辑：我没看到你问题的第二部分。我想说，阿尔法-贝塔修剪可能无法修剪掉它应该修剪的边，因为权重没有明显分布。如果您实现了更好的权重计算功能，这也应该会有所改进。此外，当游戏树的深度较大时，alpha-beta修剪效果良好。在小深度树中，几乎看不到alpha-beta和min-max之间的性能差异。所以，若将树的深度增加到6，即使使用基本的实现，性能差异也应该是可见的。

编辑2：几个链接：

如何实现高效的Alpha Beta修剪游戏搜索树？

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

Minimax 的阿尔法-贝塔修剪

第三版：深度3意味着，你做出一个动作，你的对手做出一个，然后你再做出一个。让我们举一个例子。你的主教在c1，骑士在d2，敌方兵在d5，敌方骑士在h6。你要行动，Ne6。对方移动棋子带走骑士。你移动主教带走骑士。现在，在下一步中，如果h6上的敌方骑士得到任何棋子（典当/主教等）的支持，你的主教就不见了，但那是第4步，你的位置计算功能无法理解。根据它的说法，这是一种平等的贸易。比方说，在接下来的3次移动中，没有移动顺序会让你在材料上有任何优势，所以，这个移动顺序很可能会被选中，你说这是一个愚蠢的移动（没错），但你的阿尔法-贝塔修剪并不是罪魁祸首。现在，如果这个Nf6被选中，你的骑士就死了，下一步，它又是一个新的棋盘和新的局面。所以，如果你试着去理解，你会的。我把我的案子放在这里。

相关文章：