我是否正確實施了這個極小極大功能？

Question

這是一款跳棋遊戲。請參閱舊版代碼的修訂歷史記錄。

private static Move GetBestMove(Color color, Board board, int depth) 
    { 
     var bestMoves = new List<Move>(); 
     var validMoves = board.GetValidMoves(color); 
     int highestScore = int.MinValue; 
     Board boardAfterMove; 
     int tmpScore; 
     var rand = new Random(); 

     Debug.WriteLine("{0}'s Moves:", color); 

     foreach (var move in validMoves) 
     { 
      boardAfterMove = board.Clone().ApplyMove(move); 

      if(move.IsJump && !move.IsCrowned && boardAfterMove.GetJumps(color).Any()) 
       tmpScore = NegaMax(color, boardAfterMove, depth); 
      else 
       tmpScore = -NegaMax(Board.Opposite(color), boardAfterMove, depth); 

      Debug.WriteLine("{0}: {1}", move, tmpScore); 

      if (tmpScore > highestScore) 
      { 
       bestMoves.Clear(); 
       bestMoves.Add(move); 
       highestScore = tmpScore; 
      } 
      else if (tmpScore == highestScore) 
      { 
       bestMoves.Add(move); 
      } 
     } 

     return bestMoves[rand.Next(bestMoves.Count)]; 
    } 

    private static int NegaMax(Color color, Board board, int depth) 
    { 
     var validMoves = board.GetValidMoves(color); 
     int highestScore = int.MinValue; 
     Board boardAfterMove; 

     if (depth <= 0 || !validMoves.Any()) 
      return BoardScore(color, board); 

     foreach (var move in validMoves) 
     { 
      boardAfterMove = board.Clone().ApplyMove(move); 

      if(move.IsJump && !move.IsCrowned && boardAfterMove.GetJumps(color).Any()) 
       highestScore = Math.Max(highestScore, NegaMax(color, boardAfterMove, depth)); 
      else 
       highestScore = Math.Max(highestScore, -NegaMax(Board.Opposite(color), boardAfterMove, depth - 1)); 
     } 

     return highestScore; 
    } 

    private static int BoardScore(Color color, Board board) 
    { 
     if (!board.GetValidMoves(color).Any()) return -1000; 
     return board.OfType<Checker>().Sum(c => (c.Color == color ? 1 : -1) * (c.Class == Class.Man ? 2 : 3)); 
    } 

我正在嘗試深度爲0，分數對於大概一半的遊戲是正確的，然後突然它開始搞砸了。其中一名球員將開始宣稱他的得分高於實際得分。爲什麼它只能用於半場比賽？！

Answer 1

發現的bug：What could cause this to start miscalculating after awhile?

新代碼：

private static Move GetBestMove(Color color, Board board, int depth) 
{ 
    var bestMoves = new List<Move>(); 
    IEnumerable<Move> validMoves = board.GetValidMoves(color); 
    int highestScore = int.MinValue; 
    Board boardAfterMove; 
    int tmpScore; 
    var rand = new Random(); 

    Debug.WriteLine("{0}'s Moves:", color); 

    foreach (Move move in validMoves) 
    { 
     boardAfterMove = board.Clone().ApplyMove(move); 

     if (move.IsJump && !move.IsCrowned && boardAfterMove.GetJumps(color).Any()) 
      tmpScore = NegaMax(color, boardAfterMove, depth); 
     else 
      tmpScore = -NegaMax(Board.Opposite(color), boardAfterMove, depth); 

     Debug.WriteLine("{0}: {1}", move, tmpScore); 

     if (tmpScore > highestScore) 
     { 
      bestMoves.Clear(); 
      bestMoves.Add(move); 
      highestScore = tmpScore; 
     } 
     else if (tmpScore == highestScore) 
     { 
      bestMoves.Add(move); 
     } 
    } 

    return bestMoves[rand.Next(bestMoves.Count)]; 
} 

private static int NegaMax(Color color, Board board, int depth) 
{ 
    IEnumerable<Move> validMoves = board.GetValidMoves(color); 
    int highestScore = int.MinValue; 
    Board boardAfterMove; 

    if (depth <= 0 || !validMoves.Any()) 
     return BoardScore(color, board); 

    foreach (Move move in validMoves) 
    { 
     boardAfterMove = board.Clone().ApplyMove(move); 

     if (move.IsJump && !move.IsCrowned && boardAfterMove.GetJumps(color).Any()) 
      highestScore = Math.Max(highestScore, NegaMax(color, boardAfterMove, depth)); 
     else 
      highestScore = Math.Max(highestScore, -NegaMax(Board.Opposite(color), boardAfterMove, depth - 1)); 
    } 

    return highestScore; 
} 

private static int BoardScore(Color color, Board board) 
{ 
    if (!board.GetValidMoves(color).Any()) return -1000; 
    return board.OfType<Checker>().Sum(c => (c.Color == color ? 1 : -1) * (c.Class == Class.Man ? 2 : 3)); 
} 

我不是100％相信這完美的作品。它似乎適用於深度0，通常深度1 ...除此之外，我不知道電腦在想什麼。仍然沒有表現出超級智能。

編輯：運行這個和最高速度... NegaMax代理vs隨機。 NegaMax總是贏。觀看「1000」事件的分數。在此之後，他總是在幾圈內贏得勝利，所以它看起來很有效，最後！

Answer 2

有趣的方法，我第一次看到MaxiMax。但是，我在這裏看到了一個問題：

var minMove = GetBestMove(... board.Clone().ApplyMove(move), ...); 
float score = ... BoardScore(color, board.Clone().ApplyMove(minMove)); 

在這段代碼，move和minMove是不同的側面移動，但你在同一級別同樣適用他們在這裏。第二行應該是這樣的：

float score = ... BoardScore(... board.Clone().ApplyMove(move).ApplyMove(minMove)); 

當然你也可以存儲和再利用board.Clone().ApplyMove(move)部分。

但是你仍然沒有信息：在深度100處，你可以在深度99處過濾掉最好的boardScore，但是你不必使用98..0中的任何東西，除非沒有移動（null）你注意到自己那部分出問題了。

嘗試看看一些僞 算法，但所有似乎返回 得分。這使我困惑，因爲我 不想真的想要得分， 我想要得到迴歸。

不過，這是要走的路。樹搜索的主要結果是最佳分支的值。此舉本身只是在根本層面上至關重要。直到你開始實施alpha/beta，那麼你將能夠將最好的分支存儲在一張表中。

我會建議切換到一個普通的NegaMax，
也見this SO question。