Внедрение и использование MinMax с игрой четыре в ряд (connect4)
Я пытаюсь реализовать алгоритм MinMax для игры четыре в ряд (или connect4 или connect four).
Я думаю, что я понял это: он должен построить дерево возможных досок до определенной глубины, оценить их и вернуть их счет, тогда мы просто возьмем максимум этих очков.
Так, 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.
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();
}
}