我有时会编写程序来玩棋盘游戏.基本策略是标准的alpha-beta修剪或类似的搜索,有时通过终结游戏或开放的常用方法来增强.我主要使用国际象棋变体,所以当需要选择我的评估功能时,我会使用基本的国际象棋评估功能.

但是,现在我正在编写一个程序来玩一个全新的棋盘游戏.我如何选择一个好的甚至是体面的评估函数？

主要的挑战是相同的棋子总是在棋盘上,因此通常的材料功能不会根据位置而改变,并且游戏的播放次数不到一千次左右,所以人类不一定玩得太多还没有给出见解.(PS.我考虑过MoGo方法,但随机游戏不太可能终止.)

游戏细节:游戏在10×10的棋盘上进行,每侧固定6个棋盘.这些作品具有一定的运动规则,并以某种方式相互作用,但没有任何一块被捕获.游戏的目标是在棋盘上的某些特殊方块中放置足够的棋子.计算机程序的目标是提供与当前人类玩家竞争或更好的玩家.

我正在尝试使用alpha-beta修剪为Java中的跳棋游戏实现minimax.我的minimax算法运行得很好.我的代码运行时使用了alpha-beta代码.不幸的是,当我使用标准的极小极大算法玩1000场比赛时,alpha-beta算法总是落后50场左右.

由于alpha-beta修剪不应该降低移动的质量,只需要实现它们所需的时间,因此必定是错误的.但是,我已经拿出笔和纸并绘制了假设的叶节点值,并使用我的算法来预测它是否会计算出正确的最佳移动,并且似乎没有任何逻辑错误.我使用了这个视频中的树:Alpha-Beta Pruning来跟踪我的算法.它在逻辑上应该做出所有相同的选择,因此是一个有效的实现.

我还将print语句放入代码中(它们已被删除以减少混乱),并且正确返回值,并且修剪确实发生.尽管我付出了最大的努力,但我一直无法找到逻辑错误所在.这是我实现这一点的第三次尝试,所有这些尝试都有同样的问题.

我不能在这里发布完整的代码,它太长了,所以我已经包含了与错误相关的方法.我不确定,但我怀疑这个问题可能出现在非递归的move()方法中,虽然我无法在其中找到逻辑错误,所以我只是在其中进行更多的讨论,可能是在制作东西没有押韵或理由,更糟糕而不是更好.

有没有从for循环中的递归调用中恢复多个整数值的技巧？它适用于我的minimax和negamax实现,但alpha-beta修剪似乎产生了一些奇怪的结果.

@Override
public GameState move(GameState state) 
{
    int alpha = -INFINITY;
    int beta = INFINITY;
    int bestScore = -Integer.MAX_VALUE;
    GameTreeNode gameTreeRoot = new GameTreeNode(state);
    GameState bestMove = null;
    for(GameTreeNode child: gameTreeRoot.getChildren())
    {
        if(bestMove == null)
        {
            bestMove = child.getState();
        }
        alpha = Math.max(alpha, miniMax(child, plyDepth - 1, alpha, beta));
        if(alpha > bestScore)
        {
            bestMove = child.getState();
            bestScore = alpha;
        }
    }
    return bestMove;
}

private int miniMax(GameTreeNode currentNode, int depth, int alpha, …

我花了一整天的时间试图在没有真正了解它的情况下实现minimax.现在,我想我理解minimax是如何工作的,但不是alpha-beta修剪.

这是我对极小极大的理解:

1. 生成所有可能移动的列表,直到深度限制.

2. 评估游戏区域对底部每个节点的有利程度.

3. 对于每个节点(从底部开始),如果图层为最大,则该节点的得分是其子节点的最高得分.如果图层是min,则该节点的得分是其子项的最低得分.

4. 如果您尝试最大分数,则执行分数最高的移动;如果您想要最小分数,则执行最低分数.

我对alpha-beta修剪的理解是,如果父层是min并且你的节点得分高于最低得分,那么你可以修剪它,因为它不会影响结果.

但是,我不明白的是,如果你能计算出一个节点的得分,你需要知道一个低于节点的层上所有节点的得分(根据我对minimax的理解).这意味着您将继续使用相同数量的CPU功率.

任何人都可以指出我错了什么？这个答案(Minimax为一个白痴解释)帮助我理解minimax,但我不知道alpha beta修剪会有多大帮助.

谢谢.

我有一个alpha-beta修剪的基本实现,但我不知道如何改进移动顺序.我已经读过它可以通过浅搜索,迭代加深或将bestMoves存储到转换表来完成.

有关如何在此算法中实现这些改进之一的任何建议？

 public double alphaBetaPruning(Board board, int depth, double alpha, double beta, int player) {
    if (depth == 0) {
        return board.evaluateBoard();
    }

    Collection<Move> children = board.generatePossibleMoves(player);
    if (player == 0) {
        for (Move move : children) {
            Board tempBoard = new Board(board);
            tempBoard.makeMove(move);
            int nextPlayer = next(player);
            double result = alphaBetaPruning(tempBoard, depth - 1, alpha,beta,nextPlayer);
            if ((result > alpha)) {
                alpha = result;
                if (depth == this.origDepth) {
                    this.bestMove = move;
                }
            }
            if (alpha >= beta) {
                break; …

我正在实现一个国际象棋引擎,我已经编写了一个相当复杂的alpha-beta搜索例程,具有静止搜索和转置表.但是,我正在观察一个奇怪的错误.

评估函数使用了方块表,就像这个用于典当的:

static int ptable_pawn[64] = {  
   0,  0,  0,  0,  0,  0,  0,  0,
  30, 35, 35, 40, 40, 35, 35, 30,
  20, 25, 25, 30, 30, 25, 25, 20,
  10, 20, 20, 20, 20, 20, 20, 10,
   3,  0, 14, 15, 15, 14,  0,  3,
   0,  5,  3, 10, 10,  3,  5,  0,
   5,  5,  5,  5,  5,  5,  5,  5,
   0,  0,  0,  0,  0,  0,  0,  0
};

当它转过黑色时,表格会在x轴上反射出来.具体来说,如果你很好奇,查找会发生这样的情况,其中AH列映射到0-7,而行的颜色是白色的0-7:

int ptable_index_for_white(int col, int row) {
    return …

我正在尝试使用转置表来实现alpha-beta min-max prunning增强功能.我用这个伪代码作为参考:

http://people.csail.mit.edu/plaat/mtdf.html#abmem

function AlphaBetaWithMemory(n : node_type; alpha , beta , d : integer) : integer;
    if retrieve(n) == OK then /* Transposition table lookup */
        if n.lowerbound >= beta then return n.lowerbound;
        if n.upperbound <= alpha then return n.upperbound;
        alpha := max(alpha, n.lowerbound);
        beta := min(beta, n.upperbound);
    if d == 0 then g := evaluate(n); /* leaf node */
    else if n == MAXNODE then
        g := -INFINITY; a := alpha; /* save original alpha value */
        c …

我在C中实现了一个国际象棋游戏,具有以下结构:

移动 - 代表在char板上从(a,b)到(c,d)的移动[8] [8](棋盘)

移动 - 这是一个有头部和尾部的移动链表.

变量: playing_color是'W'或'B'.minimax_depth是之前设置的极小极大深度.

这是我使用alpha-beta修剪和getMoveScore函数的Minimax函数的代码,该函数应返回之前设置的某个minimax_depth的Minimax树中的移动得分.

我也在使用getBestMoves函数,我将在这里列出它,它基本上找到Minimax算法中的最佳移动并将它们保存到全局变量中,以便我以后能够使用它们.

我必须补充说,我将​​在这里添加的三个函数中列出的所有函数都正常工作并进行了测试,因此问题是alphabetaMax算法的逻辑问题或getBestMoves/getMoveScore的实现.

问题主要在于,当我在深度N处获得最佳动作时(为什么还没有计算出来),然后使用getMoveScore函数在相同深度上检查他们的分数,我得到的分数与得分不匹配那些实际的最佳动作.我花了几个小时来调试这个并且看不到错误,我希望也许有人可以给我一个关于找到问题的小费.

这是代码:

/*
* Getting best possible moves for the playing color with the minimax algorithm
*/
moves* getBestMoves(char playing_color){
    //Allocate memory for the best_moves which is a global variable to fill it in   a minimax algorithm//
    best_moves = calloc(1, sizeof(moves));
    //Call an alpha-beta pruned minimax to compute the best moves//
    alphabeta(playing_color, board, minimax_depth, INT_MIN, INT_MAX, 1);
    return best_moves;
}

/*
* Getting the score …

更新

更新1

我试过这个(第2行):我添加了更改节点颜色作为alphabeta函数中的第一条指令.我得到了这个结果:

绿色节点是访问节点.看起来,算法正确地投掷节点,对吗？但是如何在节点中输出正确的值 - 我还需要这样做？最小子值,最大子值(不包括已修剪的分支).

更新2

我试图输出alpha和beta到树节点,但没有得到正确的结果.这是代码(添加了第18行和第31行).这是代码的结果:

在这张图片上我展示了奇怪的地方:

第一个箭头:为什么7和6的最小值是5？第二个箭头:为什么最多4,3和2是5？奇怪.这就是为什么我认为它现在正常工作.

老问题

曾几何时我在这里创建了类似的问题.这就像:"为什么我会收到这个错误？".让我们回滚并创建一个新的.这个问题将是:"如何显示Alpha Beta修剪算法结果？"

我在维基上找到了这个算法的伪代码.它可以在这里找到.

我的实现如下(它是在JavaScript上,但我不认为回答这个问题你必须知道JS或Java或C++等).问题是如何在图形(树形结构)上输出该算法的结果？一开始我有这个树结构:

注意:我有树结构(一定数量的链接nodes),我将使用alpha beta修剪算法,我有另一个树结构(为了显示结果,我们称之为"图").我用来显示图形的树节点与节点连接,我用它来查找算法的结果.

因此,alpha beta修剪algroithm的代码如下.你能说清楚我必须输出的内容和位置,以正确显示算法的过程/结果吗？

我的假设是输出alpha和beta,但我认为,这是错误的.我尝试过,但它不起作用.

我想显示修剪并用正确的值填充树中的所有节点.

这是我用alpha beta修剪实现的minimax:

function alphabeta(node, depth, alpha, beta, isMax, g) {
    if((depth == 0) || (node.isTerminal == true)) {
        return node.value;
    }
    if(isMax) {
        console.log('maximizing');
        for (var i in node.children) {
            var child = node.children[i];
            console.log(child);
            alpha = Math.max(alpha, alphabeta(child, depth-1, alpha, beta, false, g)); …

我在上个月用c#创建了一个简单的国际象棋引擎,并取得了一些不错的进展.它使用简单的Alpha-Beta算法.

为了纠正Horizo​​n-Effect,我试图实现静态搜索(并在它工作之前多次失败).发动机的强度似乎有点改善了安静,但速度非常慢!

在此之前,我可以在大约160秒(在游戏中期的某个地方)搜索6层深度,通过静态搜索,计算机需要大约80秒才能在搜索深度3上移动!

蛮力节点计数器在深度3处大约20000个节点,而静态节点计数器高达2000万!

由于这是我的第一个国际象棋引擎,我真的不知道这些数字是否正常,或者我是否在我的静止算法中犯了错误.如果有经验的人能告诉我BF节点/静态节点的通常比例是多少,我将不胜感激.

顺便说一句,看看:(每当searchdepth为0时,此方法由BF树调用)

public static int QuiescentValue(chessBoard Board, int Alpha, int Beta)
    {
        QuiescentNodes++;

        int MinMax = Board.WhoseMove; // 1 = maximierend, -1 = minimierend
        int Counter = 0;
        int maxCount;


        int tempValue = 0;
        int currentAlpha = Alpha;
        int currentBeta = Beta;
        int QuietWorth = chEvaluation.Evaluate(Board);

        if(MinMax == 1) //Max
        {
            if (QuietWorth >= currentBeta)
                return currentBeta;
            if (QuietWorth > currentAlpha)
                currentAlpha = QuietWorth;
        }

        else            //Min
        {
            if (QuietWorth <= currentAlpha)
                return currentAlpha;
            if (QuietWorth …

我对 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 有点让我相信他们是从单人视角来执行它的。