私はTicTacToeのMin Maxから自分の最善の動きを引き出すことができますか？

Question

 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)のようなものを言うことができるように、答えを得たいと思います。

一部の機能が明らかにされていない場合には：

game.IsFinished() - trueを返す勝利/紛失した場合/それ以外の他の描く

game.Score(turn) - リターン-1/0/1場合は、/失う/ドローです次の動き

game.Generate_Moves()を持つプレイヤーのために勝つ -

をゲームへの移行を適用し、ボイド - 利用できる移動

game.Do_Move()のリストを返します。

game.Undo_Move() - 交渉自体の

Answer 1

ゲームツリーのルートノードで呼び出されるミニマックス関数が、選択された移動とスコアの両方を返すのであれば十分でしょう。ゲームツリーの他のすべてのノードでは、関数はスコアを返すだけでよい。したがって、普通の方法は2つの少し異なるminimax関数 - Look at Note #2 in the description to this NegaMax Frameworkを実装することです。あなたは、各反復でgameのコピーを作成するので、それが必要とされていないように私がUndo_Moveへの呼び出しを削除した

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

注：追加の機能を以下のだろう、あなたのミニマックスインターフェイスに適用
。

Answer 2

あなたは基本的には、ツリー内の各ノードは、ボードの位置で、それぞれの子は、Aの結果であるゲーム木を、確認する必要がありminimax theorem.

を適用する必要があります法的な動き。リーフノード（ゲームが終了した場所）はgame.score（）に従ってスコアを持ち、一方のプレイヤーは高いスコアにつながるパスを下ろして移動しようとしていますが、もう一方のプレイヤーは低いスコア。この定理は、そのアイデアを厳格に適用する方法を理解するのに役立ちます。