我怎样才能从TicTacToe的Min Max中获取最佳动作？(How can i extract my best move from Min Max in TicTacToe?)

我怎样才能从TicTacToe的Min Max中获取最佳动作？(How can i extract my best move from Min Max in TicTacToe?) 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; }

问题在于，这个小功能告诉我游戏是赢，输还是平局，但我怎么能得到让我获胜的举动呢？ 我的Point类是一个简单的Class有2个坐标X，Y和我希望得到答案作为一个点，所以后来我可以说像game.Do_Move(myPoint) 。

如果某些功能不明显：

game.IsFinished() - 如果赢/输/否则返回true

game.Score(turn) - 返回-1/0/1，以防下一次移动的玩家失败/平局/获胜

game.Generate_Moves() - 返回一个包含可用移动的List

game.Do_Move() - 将移动应用于游戏的void

game.Undo_Move() - 为自己说话

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

最满意答案

如果在游戏树的根节点上调用的minimax函数返回两者，选择的移动和分数就足够了。 对于游戏树的所有其他节点，该功能仅需要返回分数。 因此，通常的方法是实现两个稍微不同的minimax函数 - 请参阅此NegaMax框架描述中的注释＃2 。 应用于您的minimax界面，您将拥有以下附加功能：

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; }

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

It would be enough if the minimax function which gets called on the root node of the game tree returns both, the choosen move and the score. For all other nodes of the game tree, the function needs only to return the score. Thus the usual way is to implement two slightly different minimax functions – Look at Note #2 in the description to this NegaMax Framework. Applied to your minimax interface you would have following additional function:

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; }

Note that I have removed the call to Undo_Move as it is not needed because you make a copy of game in each iteration.