Нужна помощь с реализацией алгоритма Minimax для игры Connect Four. c#
Код самой игры без интерфейса, довольно объемный. Пытался реализовать несколько вариантов алгоритма, ничего не выходит. Игра - четыре в ряд. Суть игры - собрать 4 элемента в ряд на доске(диагонали тоже считаются). Основной метод поиска хода для бота - minimax. Данный метод ищет столбец(col) - самый рациональный для бота ход. В моей реализации он выдает абсолютно рандомные значения, не зависящие от ситуации на доске. ДЕЛАЛ ПО ВИДЕО! Там на питоне. Тайминг (50:42) https://www.youtube.com/watch?v=MMLtza3CZFM&t=4473s
private void Shift(int[,] copyBoard, int x,int y, int CurrPlayer) // ход
{
copyBoard[x, y] = CurrPlayer;
}
private bool isPossible(int[,] copyBoard, int x) // проверка на возможность хода
{
if (copyBoard[x, 0] != 0)
return false;
else
return true;
}
public int Winner(int[,] b) // проверка на победу
{
for (int x = size - 1; x >= 0; x--)
{
for (int y = size - 1; y >= 0; y--)
{
if (b[x, y] != 0 &&
(VerticalConnectFour(b, x, y) || HorizontalConnectFour(b, x, y) || ForwardDiagonalConnectFour(b, x, y) || BackwardDiagonalConnectFour(b, x, y)))
return b[x, y];
}
}
return 0;
}
private bool VerticalConnectFour(int[,] _board, int x, int y) // вертикальная проверка
{
if (_board[x, y] == 0)
return false;
int count = 1;
int rowCursor = x - 1;
while (rowCursor >= 0 && _board[rowCursor, y] == _board[x, y])
{
count++;
rowCursor--;
}
rowCursor = x + 1;
while (rowCursor < size && _board[rowCursor, y] == _board[x, y])
{
count++;
rowCursor++;
}
if (count < 4)
return false;
return true;
}
private bool HorizontalConnectFour(int[,] _board,int x, int y) // горизонтальная проверка
{
if (_board[x, y] == 0)
return false;
int count = 1;
int yPtr = y - 1;
while (yPtr >= 0 && _board[x, yPtr] == _board[x, y])
{
count++;
yPtr--;
}
yPtr = y + 1;
while (yPtr < size && _board[x, yPtr] == _board[x, y])
{
count++;
yPtr++;
}
if (count < 4)
return false;
return true;
}
private bool ForwardDiagonalConnectFour(int[,] _board, int x, int y) // по диагонали
{
if (_board[x, y] == 0)
return false;
int count = 1;
int xPtr = x - 1;
int yPtr = y + 1;
while (xPtr >= 0 && yPtr < size && _board[xPtr, yPtr] == _board[x, y])
{
count++;
xPtr--;
yPtr++;
}
xPtr = x + 1;
yPtr = y - 1;
while (xPtr < size && yPtr >= 0 && _board[xPtr, yPtr] == _board[x, y])
{
count++;
xPtr++;
yPtr--;
}
if (count < 4)
return false;
return true;
}
private bool BackwardDiagonalConnectFour(int[,] _board, int x, int y) // по диагонали в обратную сторону
{
if (_board[x, y] == 0)
return false;
int count = 1;
int xPtr = x + 1;
int yPtr = y + 1;
while (xPtr < size && yPtr < size && _board[xPtr, yPtr] == _board[x, y])
{
count++;
xPtr++;
yPtr++;
}
xPtr = x - 1;
yPtr = y - 1;
while (xPtr >= 0 && yPtr >= 0 && _board[xPtr, yPtr] == _board[x, y])
{
count++;
xPtr--;
yPtr--;
}
if (count < 4)
return false;
return true;
}
private bool isFull(int[,] b) // проверка на заполнение доски
{
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (b[i, j] == 0)
return false;
}
}
return true;
}
private List<int> row_arr(int[,] b, int r) // создает список из определенной строки
{
List<int> arr = new List<int>();
for (int i = 0; i < size; i++)
{
arr.Add(b[i, r]);
}
return arr;
}
private List<int> col_arr(int[,] b, int r) // создает список из определенного столбца
{
List<int> arr = new List<int>();
for (int i = 0; i < size; i++)
{
arr.Add(b[r, i]);
}
return arr;
}
private int ListCheck(List<int> l, int c) // проверка колонки/ столбца на заполненность фишками определенного игрока(c)
{
int count = 0;
for (int i = 0; i < l.Count; i++)
{
if (l[i] == c)
count++;
}
return count;
}
private List<int> TakeFour(List<int> l, int idx) // берет четыре элемента из строки/ столбца от определенного индекса
{
List<int> a = new List<int>();
for (int i = 0; i < 4; i++)
{
a.Add(l[i + idx]);
}
return a;
}
private int CompScore(List<int> four, int curr)
{
int score = 0;
if (ListCheck(four, curr) == 4)
score += 100;
else if (ListCheck(four, curr) == 3 && ListCheck(four, 0) == 1)
score += 10;
else if (ListCheck(four, curr) == 2 && ListCheck(four, 0) == 2)
score += 5;
if (ListCheck(four, SwitchPlayer(curr)) == 3 && ListCheck(four, 0) == 1)
score -= 80;
return score;
}
private int score_position(int[,] b, int curr) // вычисляет важность определенной позиции(для алгоритма)
{
int score = 0;
List<int> center = new List<int>();
for (int i = 0; i < size; i++)
{
center.Add(b[size / 2, i]);
}
int center_count = ListCheck(center, curr);
score += center_count * 6;
for (int i = size - 1; i >= 0; i--)
{
List<int> row = row_arr(b, i);
for (int j = 0; j < size - 3; j++)
{
List<int> four = TakeFour(row, j);
score += CompScore(four, curr);
}
}
for (int i = 0; i < size; i++)
{
List<int> col = col_arr(b, i);
for (int j = 0; j < size - 3; j++)
{
List<int> four = TakeFour(col, j);
score += CompScore(four, curr);
}
}
for (int c = 0; c < size - 3; c++)
{
for (int r = 0; r < size - 3; r++)
{
List<int> four = new List<int>();
for (int i = 0; i < 4; i++)
{
four.Add(b[c + i, r + i]);
}
score += CompScore(four, curr);
}
}
for (int c = 0; c < size - 3; c++)
{
for (int r = 0; r < size - 3; r++)
{
List<int> four = new List<int>();
for (int i = 0; i < 4; i++)
{
four.Add(b[c + i, r + 3 - i]);
}
score += CompScore(four, curr);
}
}
return score;
}
private bool is_terminal(int[,] b) // проверка на победу/заполненность
{
if (Winner(b) != 0 || isFull(b))
return true;
else
return false;
}
public int GetAIMove(int curr) // вспомогательный метод для получения хода
{
int[,] cop = (int[,])board.Clone();
int sc = minimax(cop, 4, true, curr);
return col;
}
private List<int> get_valid_locations(int[,] copyBoard) // получает возможные для хода столбцы
{
List<int> a = new List<int>();
for (int i = 0; i < size; i++)
{
if (isPossible(copyBoard, i))
a.Add(i);
}
return a;
}
private int get_next_open_row(int[,] copyBoard, int x) // ищет свободную ячейку в столбце x.
{
for (int i = size - 1; i >= 0; i--)
{
if (copyBoard[x, i] == 0)
return i;
}
return -1;
}
private int minimax(int[,] copyBoard, int depth, bool maximazing, int curr) // сам алгоритм
{
List<int> validloc = get_valid_locations(copyBoard);
int a = Winner(copyBoard);
if (depth == 0 || is_terminal(copyBoard))
{
if (is_terminal(copyBoard))
{
if (a == curr)
return 10000000;
else if (a == SwitchPlayer(curr))
return -10000000;
else
return 0;
}
else
{
int sc = score_position(copyBoard, curr);
return sc;
}
}
if (maximazing)
{
int val = -int.MaxValue;
int new_score = val;
foreach(int c in validloc)
{
int r = get_next_open_row(copyBoard, c);
int[,] cop = (int[,])copyBoard.Clone();
Shift(cop, c, r, curr);
new_score = minimax(cop, depth - 1, false, SwitchPlayer(curr));
if (new_score > val)
{
val = new_score;
col = c;
}
}
return new_score;
}
else
{
int val = int.MaxValue;
int new_score = val;
foreach (int c in validloc)
{
int r = get_next_open_row(copyBoard, c);
int[,] cop = (int[,])copyBoard.Clone();
cop[c, r] = curr;
new_score = minimax(cop, depth - 1, true, SwitchPlayer(curr));
if (new_score > val)
{
val = new_score;
col = c;
}
}
return new_score;
}
}
private int SwitchPlayer(int curr) // меняем игрока
{
return curr == 2 ? 1 : 2;
}