标签: alpha-beta-pruning

我无法理解我在维基百科上发现的alpha beta修剪的伪代码:

function alphabeta(node, depth, ?, ?, Player)         
    if  depth = 0 or node is a terminal node
        return the heuristic value of node
    if  Player = MaxPlayer
        for each child of node
            ? := max(?, alphabeta(child, depth-1, ?, ?, not(Player)))     
            if ? ? ?
                break (* Beta cut-off *)
        return ?
    else
        for each child of node
            ? := min(?, alphabeta(child, depth-1, ?, ?, not(Player)))     
            if ? ? ?
                break (* Alpha cut-off *)
        return ?

令我困惑的是if Player = …

我已经为我的国际象棋游戏实现了 alpha beta 算法，但是最终做出一个相当愚蠢的举动需要很多时间（4 层需要几分钟）。

我一直在努力寻找错误（我假设我犯了一个）2 天了，我非常感谢我的代码中的一些外部输入。

getMove 函数：为根节点调用，它为其所有子节点（可能的移动）调用 alphaBeta 函数，然后选择得分最高的移动。

Move AIPlayer::getMove(Board b, MoveGenerator& gen)
{
    // defined constants: ALPHA=-20000 and BETA= 20000
    int alpha = ALPHA; 
    Board bTemp(false); // test Board
    Move BestMov;
    int i = -1; int temp;
    int len = gen.moves.getLength();  // moves is a linked list holding all legal moves
    BoardCounter++; // private attribute of AIPlayer object, counts analyzed boards
    Move mTemp;     // mTemp is used to apply the nextmove in the list to the …

我使用 Minimax 和 Alpha Beta Pruning 制作了一个 Tic Tac Toe 游戏。我想为 Tic Tac Toe (10x10) 游戏制作计算机 AI，但它的游戏树大小大得离谱。

我的代码是这样的，我只需要更改两个变量即可更改连续所需的棋盘大小 + 单元格数。例子：

boardSize = 3 // This is for 3x3 tic tac toe

boardSize = 4 // This is for 4x4 tic tac toe

boardSize = 10 // This is for 10x10 tic tac toe

和

winStreak = 3 // Need to make 3 cells in a row to win

winStreak = 4 // Need to make 4 cells in a row …

我正在尝试使用 alpha-beta 剪枝和转置表来实现极小极大算法。这是针对可能循环的 pacman 代理，因此必须特别注意这一点。如果一个状态（游戏和回合的状态（pacman 或 Ghost））在换位表中，并且之前看到的状态是该节点的父节点（祖父节点，...），则可以将其丢弃。这适用于没有 ab 剪枝的极小极大。从之前的搜索来看，tt（转置表）与ab的实现似乎要困难得多。我试图使代码尽可能清晰，它基于伪代码Artificial Intelligence: A Modern Approach。我希望使用第一种方法使最终结果尽可能接近。

我发现的每个伪代码都以非常不同的方式定义：

第一个伪代码； 第二个伪代码；第三个伪代码

大多数差异看起来只是表面上的。但这些代码都没有完全符合我正在寻找的结构：用 ab 剪枝除以 minValue 和 maxValue 的 minimax

提前致谢，

请询问任何进一步的解释

我必须为Android实施一个Reversi游戏.我已经设法实现了所有游戏,功能齐全,但问题是我没有AI.实际上,在每次移动时,计算机都会移动到能够获得最多件数的位置.

我决定实现alpha-beta修剪算法.我在互联网上做了很多关于它的研究,但我无法得出最终结论如何去做.我试图实现一些功能,但我无法实现所需的行为.

我的电路板存储在类Board中(在这个类中,每个播放器占用的部分存储在一个二维int数组中).我附上了一张小图(抱歉看起来很像).

图:https://docs.google.com/file/d/0Bzv8B0L32Z8lSUhKNjdXaWsza0E/edit

我需要帮助来弄清楚如何在我的实现中使用minimax算法.

到目前为止我所理解的是,我必须对董事会的价值进行评估.

为了计算董事会的价值,我必须考虑以下因素: - 免费角落(我的问题是我必须只关注自由角落,或者我现在可以采取的角落？!这里的困境) . - 董事会的动力:检查当前移动后可移动的件数. - 板的稳定性......我知道这意味着无法在板上翻转的件数. - 此举将为我提供的件数

我计划实现一个新的类BoardAI,它将把我的Board对象和部门作为参数.

你能否告诉我一个合理的思路如何实现这个AI？我在dept中计算时需要一些关于递归的帮助,我不明白它是如何计算最佳选择的.

谢谢!

在实现alpha-beta修剪算法和接受的答案时,我正在查看函数中的Strange行为,其中声明:"您rootAlphaBeta不更新alpha值".我想知道代码的必要添加内容是什么.

我怎么知道何时可以通过negamax alpha beta修剪和转置表来停止增加迭代加深算法的深度？以下从wiki页面获取的伪代码:

function negamax(node, depth, ?, ?, color)
 alphaOrig := ?

 // Transposition Table Lookup; node is the lookup key for ttEntry
 ttEntry := TranspositionTableLookup( node )
 if ttEntry is valid and ttEntry.depth ? depth
     if ttEntry.Flag = EXACT
         return ttEntry.Value
     else if ttEntry.Flag = LOWERBOUND
         ? := max( ?, ttEntry.Value)
     else if ttEntry.Flag = UPPERBOUND
         ? := min( ?, ttEntry.Value)
     endif
     if ? ? ?
         return ttEntry.Value
 endif

 if depth = 0 or node is a terminal …

我正在努力学习人工智能以及如何在程序中实现它.最简单的起点可能是简单的游戏(在这种情况下是Tic-Tac-Toe)和游戏搜索树(递归调用;不是实际的数据结构).我在关于该主题的讲座上发现了这个非常有用的视频.

我遇到的问题是第一次调用算法需要花费很长的时间(大约15秒)来执行.我已经在整个代码中放置了调试日志输出,似乎它调用了算法的一部分过多次.

这是为计算机选择最佳移动的方法:

    public Best chooseMove(boolean side, int prevScore, int alpha, int beta){
    Best myBest = new Best(); 
    Best reply;

    if (prevScore == COMPUTER_WIN || prevScore == HUMAN_WIN || prevScore == DRAW){
        myBest.score = prevScore;
        return myBest;
    }

    if (side == COMPUTER){
        myBest.score = alpha;
    }else{
        myBest.score = beta;
    }
    Log.d(TAG, "Alpha: " + alpha + " Beta: " + beta + " prevScore: " + prevScore);
    Move[] moveList = myBest.move.getAllLegalMoves(board);
    for (Move m : moveList){ …