2 
        int minmax(Board game, int depth)
        {
            if (game.IsFinished() || depth < 0)
                return game.Score(game.Turn);

            int alpha = int.MinValue + 1;
            foreach (Point move in game.Generate_Moves())
            {
                Board currentBoard = game;
                currentBoard.Do_Move(move); 

                alpha = max(alpha, -minmax(currentBoard, depth-1));
                currentBoard.Undo_Move(move);
            }

            return alpha;
        }

The thing is that this little function tells me if the game is a win, a lose or a draw, but how can i get the move that will led me to a win? My Point class is a simple Class With 2 coordinates X, Y and i want to get the answer as a point so i can latter say something like game.Do_Move(myPoint).

In case some functions aren't obvious:

game.IsFinished() - returns true if win/lose/draw else otherwise

game.Score(turn) - returns -1/0/1 in case is a lose/draw/win for the player with the next move

game.Generate_Moves() - returns a List with available moves

game.Do_Move() - void that applies the move to game

game.Undo_Move() - talks for itself

4

2 回答 2

1

如果在博弈树的根节点上调用的 minimax 函数同时返回选择的移动和得分就足够了。对于博弈树的所有其他节点，该函数只需要返回分数。因此，通常的方法是实现两个略有不同的极小极大函数——请看 NegaMax 框架描述中的注释 #2。
应用于您的极小极大接口，您将拥有以下附加功能：

int minimaxWithMove(Board game, int depth, Point& choosen)
{
    assert (!game.IsFinished() && depth > 0); // not possible at root node
    int alpha = int.MinValue + 1;
    foreach (Point move in game.Generate_Moves())
    {
        Board currentBoard = game;
        currentBoard.Do_Move(move);
        int score = -minmax(currentBoard, depth-1);
        if (score > alpha)
        {
            alpha = score;
            choosen = move;
        }
    }
    return alpha;
}

请注意，我已经删除了对的调用，Undo_Move因为它不需要，因为您game在每次迭代中都制作了副本。

于 2012-02-13T21:22:52.380 回答
0

您需要应用极小极大定理。

您基本上必须制作一个游戏树，其中树中的每个节点都是棋盘位置，每个子节点都是合法移动的结果。叶节点（游戏结束的地方）将根据 game.score() 获得分数，一个玩家试图沿着导致高分的路径选择移动，而另一个玩家试图选择迫使低分的移动分数。该定理将帮助您了解如何严格应用该想法。

于 2012-02-10T15:04:11.027 回答