我是否正确实施了这个极小极大功能？

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。