C++minimax的功能

Question

我已经Google搜索和计算器，为这个问题，但我还是不明白，如何一个极小的功能起作用。

我找到了维基百科条目有一个代码版本的功能：

function integer minimax(node, depth)
    if node is a terminal node or depth <= 0:
        return the heuristic value of node
    α = -∞
    for child in node:                       # evaluation is identical for both players 
        α = max(α, -minimax(child, depth-1))
    return α

其他几个minimax的功能我找到了与谷歌基本上是相同的事情；我试图实施这C++，这是我们想出了迄今为止:

double miniMax(Board eval, int iterations)
{
    //I evaluate the board from both players' point of view and subtract the difference
    if(iterations == 0)
        return boardEval(eval, playerNumber) - boardEval(eval, opponentSide());

    /*Here, playerTurn tells the findPossibleMoves function whose turn it is;
    I mean, how do you generate a list of possible moves if you don't even know
    whose turn it's supposed to be? But the problem is, I don't see where I can
    get playerTurn from, as there are only 2 parameters in all the examples of
    minimax I've seen*/
    vector<int> moves = eval.findPossibleMoves(playerTurn);

    //I'm assuming -∞ in the wikipedia article means a very low number?
    int result = -999999999;

    //Now I run this loop to evaluate each possible move
    /*Also, the Lua example in the wiki article has
      alpha = node.player==1 and math.max(alpha,score) or math.min(alpha,score)
      Is alpha a boolean there?!*/
    for(int i = 0; i * 2 < moves.size(); i++)
    {
        //I make a copy of the board...
        Board temp = eval;

        /*and make the next possible move... once again playerTurn crops up, and I
        don't know where I can get that variable from*/
        temp.putPiece(moves[i * 2], moves[i * 2 + 1], playerTurn);

        /*So do I create a function max that returns the bigger of two doubles?*/
        result = max(result, -miniMax(temp, iterations - 1));
    }

    return result;
    /*So now I've returned the maximum score from all possible moves within a certain
    # of moves; so how do I know which move to make? I have the score; how do I know
    which sequence of moves that score belongs to?*/
}

正如你可以看到，我很感到困惑这minimax的功能。请至少给我一些提示，以帮助我这个。

谢谢！:)

Answer 1

这样从维基百科的做负极大值 有阿尔法/贝他修剪.

你可以帮助通过获取的命名直:

• 基础是MiniMax,文字的执行将涉及2的方法，把实证明(相互递归)，1个为每个侧面。

• 懒把这变成负极大值，方法之一与一个战略位置 - 操作员。

• 阿尔法/贝他修剪是跟踪的一个窗口的最好的动作(在多个深度)检测死了分支机构。

你的 playerTurn 用于确定其打开它。在负极大值可以得出这从深度(迭代)之中。但它会更容易使用2参数(myColor,otherColor)和关它们在每个级别。

Answer 2

您极小（）函数应该记住它迄今发现的最好的举措。因此，而不是这个代码：

  /*So do I create a function max that returns the bigger of two doubles?*/
  result = max(result, -miniMax(temp, iterations - 1));

您应该做这样的事情：

  /*So do I create a function max that returns the bigger of two doubles?*/
  double score = -miniMax(temp, iterations - 1);
  if (score > result)
  {
     result = score;
     bestMove = i;
  }

当然，你需要一个变量“bestMove”等方式来回报最好的移动发现给调用者。

Answer 3

添加playerTurn变量作为自变量，以miniMax，和呼叫miniMax其当前玩家的举动最初和递归。

另外，opponentSide需要是playerTurn的函数。

Answer 4

一个良好开始游戏树搜寻是的 国际象棋程wiki.对于你的问题有关的移动:我认为这是最常见有两个最大的功能。两者之间的差别最大的功能是，一个只返回，这是你和其他返回的分和最佳的移动。递归叫顺序将如下:

maxWithBestMoveReturn(...) --> min(...) --> max(...) --> min(...)

有一些很好的论文，与伪Alpha Beta算法：

• TA Marsland-国际象棋计算机和搜索
• J Schaeffer-游戏计算机(人)发挥

你的问题的评论： 和数学。max(阿尔法分)或数学。min(阿尔法分)是阿尔布尔有？！

没有阿尔法是一个窗口开在alpha beta算法。阿尔法的价值得到更新与新的价值。因为α和β交换用递归的呼吁负极大值功能的阿尔法的变量是指测变量在未来的递归的呼吁。

一个注意到的playerTurn变量：Minimax或alpha beta算法不需要这个信息。所以我会得到的信息--谁是下一个--，进入董事会的结构。该职能findPossibleMoves和boardEval获得的所有信息，他们需要从董事会的结构。

一个注意到的递归休息的条件：如果我理解你的代码,然后你只有一个 iterations == o.我认为这意味着算法已经达到所期望的深度。但是，如果没有可能的行动左前算法达到这个深度。也许你应该写如下：

vector<int> moves = findPossibleMoves(...);
if (!moves.size())
    return boardEval(...);

Answer 5

在你的伪代码，该节点变量具有包含所有有关当前板位置（或其他）的信息。该信息将包括轮到谁移动。