C ++极小功能

问题描述

我已经搜索谷歌和＃1的这个问题，但我还是不明白，怎么一个极小功能的工作。

I have searched Google and Stackoverflow for this question, but I still don't understand how a minimax function works.

我发现维基百科条目的功能的伪code版：

I found the wikipedia entry has a pseudocode version of the function:

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 α

其他几个极小的功能，我发现与谷歌基本上是相同的事情;我想用C ++来实现这一点，这就是我来了这么远：

Several other minimax functions I found with Google are basically the same thing; I'm trying to implement this in C++, and this is what I have come up with so far:

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?*/
}

正如你所看到的，我是pretty的困惑，这个极小的功能。请最起码给我一些提示，以帮助我。

As you can see, I'm pretty confused about this minimax function. Please at the very least give me some hints to help me with this.

谢谢！ ：）

推荐答案

从维基百科这样做NegaMax 与α/β剪枝。

That sample from Wikipedia is doing NegaMax .

您可以通过获取命名笔直帮助：

You may be helped by getting the naming straight:

• 的基础是极小，文字的实施将涉及2的方法轮流（相互递归），1每边。

• The basis is MiniMax, a literal implementation would involve 2 methods that take turns (mutually recursive), 1 for each side.

懒惰的程序员变成NegaMax这一点，方法与战略地位 - 运营商。

Lazy programmers turn this into NegaMax, one method with a strategically placed - operator.

α/β修剪跟踪最佳动作一个窗口（在多个深度）来检测枯枝。

Alpha/Beta pruning is keeping track of a Window of best moves (over multiple depths) to detect dead branches.

您 playerTurn 用于确定该轮到谁。在NegaMax可以从深度（重复）获得这是奇数还是偶数。但是这将是更容易使用2个参数（myColor，otherColor）并且在每个级别切换它们。

Your playerTurn is used to determine whose turn it is . In NegaMax you can derive this from the depth (iterations) being odd or even. But it would be easier to use 2 parameters (myColor, otherColor) and switch them at each level.

这篇关于C ++极小功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！