Chess negamax算法来回移动棋子。怎么了？

Question

好的，所以我会承认，这件事会持续一段时间。我正在为C＃编写一个国际象棋引擎，其最终目标包括实施UCI。我已经达到了这样的程度，在给定董事会的情况下，引擎会生成所有有效移动的列表;然而，我的评估代码似乎很挣扎，因为当与自己对抗时，引擎会移动两边的两个棋子，然后在两边来回移动棋子。我将概述下面的程序的关键部分，以便最好地让你理解我的代码在什么条件下被调用和使用，希望它能帮助你回答我的问题。

这只是我的界面调用的主要方法，这里没有什么令人兴奋的。

class BreezeEngine 
{ 
    // Declares Piece Values 
    public const int pawn = 1, knight = 4, bishop = 6, rook = 8, queen = 16, king = 60; 
    public const int toDepth = 4; 
    public static void BoardGen(string mode) 
    { 
     Board chessBoard = new Board(new int[8, 8] { 
      { 8, 4, 6,16,60, 6, 4, 8 }, 
      { 1, 1, 1, 1, 1, 1, 1, 1 }, 
      { 0, 0, 0, 0, 0, 0, 0, 0 }, 
      { 0, 0, 0, 0, 0, 0, 0, 0 }, 
      { 0, 0, 0, 0, 0, 0, 0, 0 }, 
      { 0, 0, 0, 0, 0, 0, 0, 0 }, 
      {-1,-1,-1,-1,-1,-1,-1,-1 }, 
      {-8,-4,-6,-16,-60,-6,-4,-8 } 
      }, 0, true, true, true); 
     PlayGame(chessBoard, true); 
     return; 
    } 

这种方法工作得很好。 它返回格式为 x1，y1，x2，y2，权重 的移动列表此方法生成的权重是任何被杀死的数值。如果您有问题，请告诉我。

private static List<int[]> CalcFutures(Board chessBoard) 
    { 
     // Move generation stuff. 
    } 

这种方法尚未完成（因为它不处理易位或顺便），但它基本上只是从任何给定的移动新的董事会对象。

private static Board MoveToBoard(int[] move, Board board) 
    { 
     int[,] newBoard = new int[8, 8]; 
     Array.Copy(board.Pieces(), newBoard, 64); 
     newBoard[move[3], move[2]] = newBoard[move[1], move[0]]; 
     newBoard[move[1], move[0]] = 0; 
     if (newBoard[move[3], move[2]] == pawn && move[3] == 7) newBoard[move[3], move[2]] = queen; 
     if (newBoard[move[3], move[2]] == -pawn && move[3] == 0) newBoard[move[3], move[2]] = -queen; 
     return new Board(newBoard, board.Depth() + 1, !board.IsTurn(), true, true); 
    } 

此代码可能不是必需的，但我将它包含在错误导致错误的机会中。这只是一个非常基本的用户界面，可以让我与我的引擎玩游戏，或者让引擎自己玩。

private static void PlayGame(Board chessBoard, bool demo) 
    { 
     int[] move = new int[5]; 
     if (!(chessBoard.IsTurn() || demo)) 
     { 
      Console.WriteLine("Type in your move one integer at a time: x1,y1,x2,y2"); 
      move[0] = Convert.ToInt32(Console.ReadLine()); 
      move[1] = Convert.ToInt32(Console.ReadLine()); 
      move[2] = Convert.ToInt32(Console.ReadLine()); 
      move[3] = Convert.ToInt32(Console.ReadLine()); 
     } 
     else 
     { 
      Console.WriteLine("Calculating Move..." + chessBoard.IsTurn()); 
      move = Evaluate(CalcFutures(chessBoard), chessBoard); 
     } 
     if (Math.Abs(chessBoard.Pieces()[move[3], move[2]]) == king) 
     { 
      if (chessBoard.IsTurn()) Console.Write("White Wins"); 
      else Console.Write("Black Wins"); 
      return; 
     } 
     chessBoard = MoveToBoard(move, chessBoard); 
     chessBoard.SetDepth(0); 

     for (int i = 0; i < 8; i++) 
     { 
      for (int j = 0; j < 8; j++) 
      { 
       Console.Write(chessBoard.Pieces()[i, j].ToString().PadLeft(3, ' ')); 
      } 
      Console.WriteLine(); 
     } 

     PlayGame(chessBoard, demo); 
    } 
} 

现在，我将介绍评估算法本身之前的一个简短切线。这是您在整个代码中许多其他时间参考的主板对象。它包含棋盘阵列以及定义游戏当前状态所需的其他变量。

class Board 
{ 
    bool isTurn; 
    bool castling; 
    bool enemyCastling; 
    int[,] pieces = new int[8, 8]; 
    int weight = 0; 
    int depth; 
    public Board(int[,] inBoard, int inDepth, bool inIsTurn, bool inCastling, bool inEnemyCastling) 
    { 
     Array.Copy(inBoard, pieces, 64); 
     isTurn = inIsTurn; 
     castling = inCastling; 
     enemyCastling = inEnemyCastling; 
     depth = inDepth; 
    } 
    public int Weight() 
    { 
     int sum = 0; 
     foreach (int i in pieces) 
      sum += i; 
     weight = sum; 
     return weight; 
    } 
    public int[,] Pieces() { return pieces; } 
    public bool IsTurn() { return isTurn; } 
    public void ToggleTurn() { isTurn = !isTurn; return; } 
    public int Depth() { return depth; } 
    public void SetDepth(int inDepth) 
    { 
     depth = inDepth; 
    } 
} 

现在，我已经列出我的程序的其他部分，这里是评估方法本身。代码接收一个移动列表，如果它到了应该搜索的最远的深度，它就会返回绝对值最大的那个。如果它不在最底层，它只会产生一份期货清单，对于它收到的期货清单中的每一笔交易，再次调用自己。然后将返回的值添加到原始移动的重量，并与迄今为止找到的最佳移动进行比较。但是，我一直在使用这种方法，而且我猜这是因为我误解了negamax应该如何工作，或者我一直在某处犯了一个错字。任何想法发生了什么？

private static int[] Evaluate(List<int[]> futures, Board chessBoard) 
    { 
     int[] bestMove = new int[5]; 
     bestMove[0] = 30; 
     if (chessBoard.Depth() >= toDepth) 
     { 
      foreach (int[] move in futures) 
      { 
       if (Math.Abs(move[4]) > Math.Abs(bestMove[4])) 
       { 
        Array.Copy(move, bestMove, 5); 
       } 
      } 
     } 
     else 
     { 
      foreach (int[] move in futures) 
      { 
       Board newBoard = MoveToBoard(move, chessBoard); 
       int[] testMove = Evaluate(CalcFutures(newBoard), newBoard); 
       move[4] += testMove[4]; 
       if (bestMove[0] == 30) bestMove = move; 
       if (chessBoard.IsTurn()) 
       { 
        if (move[4] > bestMove[4]) 
        { 
         Array.Copy(move, bestMove, 5); 
        } 
       } 
       else 
       { 
        if (move[4] < bestMove[4]) 
        { 
         Array.Copy(move, bestMove, 5); 
        } 
       } 
      } 
     } 
     return bestMove; 
    } 

Answer 1

您正在评估错误。你必须确保任何一方都在挑选自己最美好的未来。老实说，minimax很容易实现给你的移动数据结构。这是固定的评估功能。

public static int[] Evaluate(List<int[]> futures, Board chessBoard) 
    { 
     int[] bestMove = new int[5]; 
     Random rndMove = new Random(); 
     Array.Copy(futures[rndMove.Next(futures.Count)], bestMove, 5); 
     if (chessBoard.Depth() == toDepth) 
     { 
      if (chessBoard.IsTurn()) 
      { 
       // Maximum 
       //bestMove[4] = -1000000; 
       foreach (int[] move in futures) 
       { 
        if (move[4] > bestMove[4]) 
        { 
         Array.Copy(move, bestMove, 5); 
        } 
       } 
      } 
      else 
      { 
       // Minimum 
       //bestMove[4] = 1000000; 
       foreach (int[] move in futures) 
       { 
        if (move[4] < bestMove[4]) 
        { 
         Array.Copy(move, bestMove, 5); 
        } 
       } 

      } 
     } 
     else 
     { 

      if (chessBoard.IsTurn()) 
      { 
       // Maximum 
       //bestMove[4] = -1000000; 
       foreach (int[] move in futures) 
       { 
        if (Math.Abs(chessBoard.Pieces()[move[3], move[2]]) == king) return move; 
        Board newBoard = MoveToBoard(move, chessBoard); 
        move[4] += Evaluate(CalcFutures(newBoard), newBoard)[4]; 
        if (move[4] > bestMove[4]) 
        { 
         Array.Copy(move, bestMove, 5); 
        } 
       } 
      } 
      else 
      { 
       // Minimum 
       //bestMove[4] = 1000000; 
       foreach (int[] move in futures) 
       { 
        if (Math.Abs(chessBoard.Pieces()[move[3], move[2]]) == king) return move; 
        Board newBoard = MoveToBoard(move, chessBoard); 
        move[4] += Evaluate(CalcFutures(newBoard), newBoard)[4]; 
        if (move[4] < bestMove[4]) 
        { 
         Array.Copy(move, bestMove, 5); 
        } 
       } 
      } 
     } 
     //Console.WriteLine(bestMove[4]); 
     return bestMove; 
    }