标签: minimax

我正在尝试使用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算法来制作无与伦比的tictactoe AI.我一路上都错过了一些东西(大脑炒).

我不是在这里寻找代码,只是更好地解释我出错的地方.

这是我当前的代码(minimax方法由于某种原因总是返回0):

from copy import deepcopy


class Square(object):
    def __init__(self, player=None):
        self.player = player

    @property
    def empty(self):
        return self.player is None


class Board(object):
    winning_combos = (
        [0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8],
        [0, 4, 8], [2, 4, 6],
    )

    def __init__(self, squares={}):
        self.squares = squares
        for i in range(9):
            if self.squares.get(i) is None:
                self.squares[i] = Square()

    @property
    def available_moves(self):
        return [k for k, v in self.squares.iteritems() …

我花了一整天的时间试图在没有真正了解它的情况下实现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 …

我正在为Chomp游戏编写一个程序.你可以在维基百科上阅读游戏的描述,但无论如何我都会简要描述一下.

我们在尺寸为nxm的巧克力棒上玩,即酒吧分为nxm正方形.在每个回合中,当前玩家选择一个正方形并吃掉所选正方形下方和右侧的所有内容.因此,例如,以下是有效的第一步:

目的是迫使你的对手吃掉最后一块巧克力(它被中毒).

关于AI部分,我使用了具有深度截断的minimax算法.但是我无法想出合适的位置评估功能.结果是,通过我的评估功能,人类玩家很容易赢得我的计划.

谁能:

• 建议一个好的位置评估功能或
• 提供一些有用的参考或
• 建议一个替代算法？

我在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 …

我在微控制器上创建了一个Tic-Tac-Toe游戏,包括一个完美的AI(完美意味着它不会丢失).我没有使用minimax算法,只是一个具有所有可能和最佳移动的小状态机.我现在的问题是我想实现不同的困难(简单,中等和困难).到目前为止,人工智能将是艰难的.所以我已经考虑过如何以最好的方式做到这一点,最终想要使用minimax算法,但它计算所有游戏位置的所有分数,这样我有时也可以选择第二个最佳分数而不是最佳分数.由于我不能总是在微控制器本身上进行所有这些计算,我想创建一个可以在我的计算机上运行的小程序,它给出了所有可能的板状态的数组(关于对称性等,以最小化存储使用)和他们的相应分数.为此,我首先尝试实现minimax算法本身,depth以便正确计算scores每个状态.然后它应该让我回到阵列中的所有最佳动作(现在).但是,它似乎没有那么好用.我试图用一些printf线调试它.这是迄今为止的两个代码minimax 功能以及我的主要功能:

    static int minimax(int *board, int depth)
{
    int score;
    int move = -1;
    int scores[9];
    int nextDepth;

    printf("\n----- Called Minimax, Depth: %i -----\n\n", depth);

    if(depth%2 ==1){
        player = -1;
    } else {
        player = 1;
    }

    printf("Player: %i\n---\n", player);

    if(isWin(board) != 0){
        score = (10-depth)*winningPlayer;

        printf("Player %i won on depth %i\n", winningPlayer, depth);
        printf("Resulting score: (10-%i)*%i = %i\nScore returned to depth %i\n---\n", depth, winningPlayer, score, depth-1);

        return score;
    } …

我在这里问一个特定的话题 - 我在网上找到了很少有关于此的信息.我正在实现一个F#版本的Minimax算法.我现在遇到的问题是我要比较我的树叶(下面的数据结构).搜索VS给我的错误,我得到了这样的东西:

我曾经拥有的树类型:

type TreeOfPosition =
    | LeafP   of Position
    | BranchP of Position * TreeOfPosition list

和实施IComparable的流行

type staticValue = int
[<CustomEquality;CustomComparison>]
type TreeOfPosition =
    | LeafP   of Position * staticValue
    | BranchP of Position * TreeOfPosition list

    override x.Equals(yobj) = 
        match yobj with
        | :? TreeOfPosition as y -> (x = y)
        | _ -> false

    override x.GetHashCode() = hash (x)
    interface System.IComparable with
        member x.CompareTo yobj =
            match yobj with
            | :? TreeOfPosition as y -> …

我想使用minimax搜索(使用alpha-beta修剪),或者更确切地说是使用negamax搜索来使计算机程序玩纸牌游戏.

纸牌游戏实际上由4名玩家组成.因此,为了能够使用minimax等,我将游戏简化为"我"以对抗"其他人".在每次"移动"之后,您可以客观地从游戏本身读取当前状态的评估.当所有4名玩家都已经放置了这张牌时,最高赢得了所有牌 - 并且牌的价值计算在内.

由于你不知道其他3个玩家之间的牌分布是如何确切的,我认为你必须使用不属于你的牌来模拟所有可能的分布("世界").你有12张卡,其他3个玩家共有36张牌.

所以我的方法是这个算法,其中player1到3之间的数字表示程序可能需要找到移动的三个计算机玩家.并-player代表对手,即所有其他三名球员在一起.

private Card computerPickCard(GameState state, ArrayList<Card> cards) {
    int bestScore = Integer.MIN_VALUE;
    Card bestMove = null;
    int nCards = cards.size();
    for (int i = 0; i < nCards; i++) {
        if (state.moveIsLegal(cards.get(i))) { // if you are allowed to place this card
            int score;
            GameState futureState = state.testMove(cards.get(i)); // a move is the placing of a card (which returns a new game state)
            score = negamaxSearch(-state.getPlayersTurn(), futureState, 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
            if …