如何从TicTacToe中的Min Max中提取最佳移动？

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

事情是，这个小函数告诉我，如果游戏是赢，输或平局，但我怎么能得到这一举动，将导致我赢得？我的点类是一个简单的类有2个坐标X，Y和我想得到答案作为一个点，所以我可以后面说一些像game.Do_Move(myPoint)。如何从TicTacToe中的Min Max中提取最佳移动？

如果有些功能并不明显：

game.IsFinished() - 如果赢/输/平局别的否则

game.Score(turn)返回true - 返回-1/0/1的情况下，是一赔/战平/赢得下一个举动

game.Generate_Moves()球员 - 返回与可移动

列表

game.Do_Move() - 无效应用于移动到游戏

周

game.Undo_Move() - 为自己的谈判

来源

2012-02-10 Dementor

如果在游戏树的根节点上调用的minimax函数同时返回选定的移动和分数，那就足够了。对于游戏树的所有其他节点，该功能只需要返回分数。因此通常的做法是实现两个稍微不同的极小极小函数 - Look at Note #2 in the description to this NegaMax Framework。
应用到您的极小的界面，你会以下附加功能：

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-13 21:22:52

你需要应用minimax theorem.

基本上，你必须做出一个游戏树，在树中的每个节点是板位置，而每个孩子的结果合法举动。叶节点（游戏结束时）将根据game.score（）得分，并且一个玩家试图选择沿着通往高分的路径移动，而另一个玩家试图选择迫使低得分了。这个定理将帮助你看到如何严格地应用这个想法。

来源

2012-02-10 15:04:11 Novak

这个想法是，我的计划的作品，告诉我，如果我（与双方球员）有机会赢/拉或其他球员可以赢。在我用X做出第一步之后，它告诉我它将以平局结束，但是如果我为O选择一个随机的坏方块，它会告诉我它为X等赢了一场胜利。因此，该算法的工作原理，缓慢顺便说一句，但它的作品。它需要所有可能的方块，并且宣布我的最佳尝试，但是我想要获得算法在获胜状态下的路径。 – Dementor 2012-02-10 17:35:55

对，如此从赢得的叶子回溯树木。 – Novak 2012-02-10 20:37:48

如何从TicTacToe中的Min Max中提取最佳移动？

回答

相关问题