Реализация и использование MinMax с четырьмя подряд (connect4) игра

Question

Я пытаюсь реализовать алгоритм MinMax для четырех подряд (или подключить 4 или подключить четыре) игры.

Я думаю, что у меня есть идея, он должен построить дерево возможных досок до определенной глубины, оценить их и вернуть их результат, тогда мы просто возьмем максимум этих баллов.

Итак, aiChooseCol() проверяет счет каждого возможного столбца, вызывая MinMax() и возвращает столбец с максимальным счетом.

Теперь я не был уверен, это правильный способ позвонить MinMax()?

Можно ли проверить temp = Math.Max(temp, 1000);?

Я все еще не сделал эвристическую функцию, но это должно хотя бы признать выигрышный столбец и выбрать его, но в настоящее время он просто выбирает первый свободный столбец слева ... Я не могу понять, что я делать неправильно.

private int AiChooseCol() 
{ 
    int best = -1000; 
    int col=0; 
    for (int i = 0; i < m_Board.Cols; i++) 
    { 
     if (m_Board.CheckIfColHasRoom(i)) 
     { 
      m_Board.FillSignInBoardAccordingToCol(i, m_Sign); 
      int t = MinMax(5, m_Board, board.GetOtherPlayerSign(m_Sign)); 
      if (t > best) 
      { 
       best = t; 
       col = i; 
      } 
      m_Board.RemoveTopCoinFromCol(i); 
     } 

    } 
    return col; 
} 


private int MinMax(int Depth, board Board, char PlayerSign) 
{ 
    int temp=0; 
    if (Depth <= 0) 
    { 
     // return from heurisitic function 
     return temp; 
    } 
    char otherPlayerSign = board.GetOtherPlayerSign(PlayerSign); 

    char checkBoard = Board.CheckBoardForWin(); 
    if (checkBoard == PlayerSign) 
    { 
     return 1000; 
    } 
    else if (checkBoard == otherPlayerSign) 
    { 
     return -1000; 
    } 
    else if (!Board.CheckIfBoardIsNotFull()) 
    { 
     return 0; // tie 
    } 


    if (PlayerSign == m_Sign) // maximizing Player is myself 
    { 
     temp = -1000; 
     for (int i = 0; i < Board.Cols; i++) 
     { 
      if (Board.FillSignInBoardAccordingToCol(i, PlayerSign)) // so we don't open another branch in a full column 
      { 
       var v = MinMax(Depth - 1, Board, otherPlayerSign); 
       temp = Math.Max(temp, v); 
       Board.RemoveTopCoinFromCol(i); 
      } 
     } 
    } 
    else 
    { 
     temp = 1000; 
     for (int i = 0; i < Board.Cols; i++) 
     { 
      if (Board.FillSignInBoardAccordingToCol(i, PlayerSign)) // so we don't open another branch in a full column 
      { 
       var v = MinMax(Depth - 1, Board, otherPlayerSign); 
       temp = Math.Min(temp, v); 
       Board.RemoveTopCoinFromCol(i); 
      } 
     } 
    } 
    return temp; 
} 

Некоторые примечания:

FillSignInBoardAccordingToCol() возвращает логическое значение, если она была успешной.

Тип board имеет массив char[,] с фактической доской и знаками игроков.

Этот код находится в классе AI Player.

Answer 1

Итак, я решил написать свой собственный MinMax Connect 4. Я использовал глубину, чтобы определить ценность выигрыша или потери, так что движение, которое приближает вас к победе или блокировке потери, будет иметь приоритет. Я также решаю, что я буду случайным образом выбирать ход, если более одного имеет ту же эвристику. Наконец, я протянул глубину до 6, так как это то, сколько ходов требуется для поиска возможных путей победы с самого начала.

private static void Main(string[] args) 
{ 
    var board = new Board(8,7); 
    var random = new Random(); 

    while (true) 
    { 
     Console.WriteLine("Pick a column 1 -8"); 
     int move; 
     if (!int.TryParse(Console.ReadLine(), out move) || move < 1 || move > 8) 
     { 
      Console.WriteLine("Must enter a number 1-8."); 
      continue; 
     } 

     if (!board.DropCoin(1, move-1)) 
     { 
      Console.WriteLine("That column is full, pick another one"); 
      continue; 
     } 

     if (board.Winner == 1) 
     { 
      Console.WriteLine(board); 
      Console.WriteLine("You win!"); 
      break; 
     } 

     if (board.IsFull) 
     { 
      Console.WriteLine(board); 
      Console.WriteLine("Tie!"); 
      break; 
     } 

     var moves = new List<Tuple<int, int>>(); 
     for (int i = 0; i < board.Columns; i++) 
     { 
      if (!board.DropCoin(2, i)) 
       continue; 
      moves.Add(Tuple.Create(i, MinMax(6, board, false))); 
      board.RemoveTopCoin(i); 
     } 

     int maxMoveScore = moves.Max(t => t.Item2); 
     var bestMoves = moves.Where(t => t.Item2 == maxMoveScore).ToList(); 
     board.DropCoin(2, bestMoves[random.Next(0,bestMoves.Count)].Item1); 
     Console.WriteLine(board); 

     if (board.Winner == 2) 
     { 
      Console.WriteLine("You lost!"); 
      break; 
     } 

     if (board.IsFull) 
     { 
      Console.WriteLine("Tie!"); 
      break; 
     } 
    } 

    Console.WriteLine("DONE"); 
    Console.ReadKey(); 
} 

private static int MinMax(int depth, Board board, bool maximizingPlayer) 
{ 
    if (depth <= 0) 
     return 0; 

    var winner = board.Winner; 
    if (winner == 2) 
     return depth; 
    if (winner == 1) 
     return -depth; 
    if (board.IsFull) 
     return 0; 


    int bestValue = maximizingPlayer ? -1 : 1; 
    for (int i = 0; i < board.Columns; i++) 
    { 
     if (!board.DropCoin(maximizingPlayer ? 2 : 1, i)) 
      continue; 
     int v = MinMax(depth - 1, board, !maximizingPlayer); 
     bestValue = maximizingPlayer ? Math.Max(bestValue, v) : Math.Min(bestValue, v); 
     board.RemoveTopCoin(i); 
    } 

    return bestValue; 
} 

public class Board 
{ 
    private readonly int?[,] _board; 

    private int? _winner; 

    private bool _changed; 

    public Board(int cols, int rows) 
    { 
     Columns = cols; 
     Rows = rows; 
     _board = new int?[cols, rows]; 
    } 

    public int Columns { get; } 
    public int Rows { get; } 

    public bool ColumnFree(int column) 
    { 
     return !_board[column, 0].HasValue; 
    } 

    public bool DropCoin(int playerId, int column) 
    { 
     int row = 0; 
     while (row < Rows && !_board[column,row].HasValue) 
     { 
      row++; 
     } 

     if (row == 0) 
      return false; 
     _board[column, row - 1] = playerId; 
     _changed = true; 
     return true; 
    } 

    public bool RemoveTopCoin(int column) 
    { 
     int row = 0; 
     while (row < Rows && !_board[column, row].HasValue) 
     { 
      row++; 
     } 

     if (row == Rows) 
      return false; 
     _board[column, row] = null; 
     _changed = true; 
     return true; 
    } 

    public int? Winner 
    { 
     get 
     { 
      if (!_changed) 
       return _winner; 

      _changed = false; 
      for (int i = 0; i < Columns; i++) 
      { 
       for (int j = 0; j < Rows; j++) 
       { 
        if (!_board[i, j].HasValue) 
         continue; 

        bool horizontal = i + 3 < Columns; 
        bool vertical = j + 3 < Rows; 

        if (!horizontal && !vertical) 
         continue; 

        bool forwardDiagonal = horizontal && vertical; 
        bool backwardDiagonal = vertical && i - 3 >= 0; 

        for (int k = 1; k < 4; k++) 
        { 
         horizontal = horizontal && _board[i, j] == _board[i + k, j]; 
         vertical = vertical && _board[i, j] == _board[i, j + k]; 
         forwardDiagonal = forwardDiagonal && _board[i, j] == _board[i + k, j + k]; 
         backwardDiagonal = backwardDiagonal && _board[i, j] == _board[i - k, j + k]; 
         if (!horizontal && !vertical && !forwardDiagonal && !backwardDiagonal) 
          break; 
        } 

        if (horizontal || vertical || forwardDiagonal || backwardDiagonal) 
        { 
         _winner = _board[i, j]; 
         return _winner; 
        } 
       } 
      } 

      _winner = null; 
      return _winner; 
     } 
    } 

    public bool IsFull 
    { 
     get 
     { 
      for (int i = 0; i < Columns; i++) 
      { 
       if (!_board[i, 0].HasValue) 
        return false; 
      } 

      return true; 
     } 
    } 

    public override string ToString() 
    { 
     var builder = new StringBuilder(); 
     for (int j = 0; j < Rows; j++) 
     { 
      builder.Append('|'); 
      for (int i = 0; i < Columns; i++) 
      { 
       builder.Append(_board[i, j].HasValue ? _board[i,j].Value.ToString() : " ").Append('|'); 
      } 
      builder.AppendLine(); 
     } 

     return builder.ToString(); 
    } 
}