Завершение минимального A/B к A/B Negamax ⇐ C#

[Anonymous]

Я пытаюсь преобразовать этот код < /p>
using System.Collections.Generic;
using UnityEngine;

public class AI : MonoBehaviour
{
private int numRows = 6;
private int numCols = 7;
private int maxSearch = 6;
public int player1Value = 1;
public int player2Value = -1;

private List GetValidMoves(int[,] board)
{
List moveList = new List();
for (int column = 0; column < numCols; column++)
{
for (int row = numRows - 1; row >= 0; row--)
{
if (board[row, column] == 0)
{
Move move = new Move(row, column);
moveList.Add(move);
break;
}
}
}

return moveList;
}
public void BestMove()
{
Move bestMove = new Move(-1, -1, -99);
int[,] currentPlayfield = Playfield.Instance.CopyCurrentPlayField();

List possibleMoves = new List();
possibleMoves.AddRange(GetValidMoves(currentPlayfield));

foreach (Move move in possibleMoves)
{
move.score = -99;
int[,] simBoard = CreateSimulationBoard(move, currentPlayfield, player2Value);
move.score = MinMax(simBoard, maxSearch, -99, 99, false);

if (move.score > bestMove.score)
{
bestMove = move;
}
}

GameManager.Instance.ColumnsPressed(bestMove.column);
}
private int[,] CreateSimulationBoard(Move move, int[,] board, int player)
{
int[,] simBoard = new int[numRows, numCols];
System.Array.Copy(board, simBoard, board.Length);
simBoard[move.row, move.column] = player;
return simBoard;
}
private int MinMax(int[,] board, int searchDepth, int alpha, int beta, bool isMaximizer)
{
int bestScore = 0;

if (searchDepth == 0 || Playfield.Instance.GameOverCheck(board))
{
bestScore = EvaluateBoard(board, isMaximizer);
return bestScore;
}

if (isMaximizer)
{
bestScore = -99;

foreach (Move move in GetValidMoves(board))
{
int[,] simBoard = CreateSimulationBoard(move, board, player2Value);
bestScore = System.Math.Max(bestScore, MinMax(simBoard, searchDepth - 1, alpha, beta, !isMaximizer));
if (bestScore >= beta)
{
break;
}
alpha = System.Math.Max(alpha, bestScore);
}

return bestScore;
}
else
{
bestScore = 99;

foreach (Move move in GetValidMoves(board))
{
int[,] simBoard = CreateSimulationBoard(move, board, player1Value);
bestScore = System.Math.Min(bestScore, MinMax(simBoard, searchDepth - 1, alpha, beta, !isMaximizer));
if (bestScore = 0; row--)
{
if (board[row, column] == 0)
{
break;
}

if (column < 4)
{
int a = board[row, column];
int b = board[row, column + 1];
int c = board[row, column + 2];
int d = board[row, column + 3];

if (a == b && a == c && a == d)
{
if (isMaximizer)
{
score += a == player1Value ? player2Value : player1Value;
}
else
{
score += a == player2Value ? player1Value : player2Value;
}
}
if (a == b && a == c && d == 0)
{
if (isMaximizer)
{
score += a == player1Value ? player2Value : player1Value;
}
else
{
score += a == player2Value ? player1Value : player2Value;
}
}
}
if (column > 2)
{
int a = board[row, column];
int b = board[row, column - 1];
int c = board[row, column - 2];
int d = board[row, column - 3];

if (a == b && a == c && a == d)
{
if (isMaximizer)
{
score += (a == player1Value ? player2Value : player1Value) * 10;
}
else
{
score += (a == player2Value ? player1Value : player2Value) * 10;
}
}
if (a == b && a == c && d == 0)
{
if (isMaximizer)
{
score += a == player1Value ? player2Value : player1Value;
}
else
{
score += a == player2Value ? player1Value : player2Value;
}
}
}
}
}

return score;
}
private int CheckVertical(int[,] board, bool isMaximizer)
{
int score = 0;

for (int column = 0; column < numCols; column++)
{
for (int row = numRows - 1; row >= 0; row--)
{
if (board[row, column] == 0)
{
break;
}

if (row > 2)
{
int a = board[row, column];
int b = board[row - 1, column];
int c = board[row - 2, column];
int d = board[row - 3, column];

if (a == b && a == c && a == d)
{
if (isMaximizer)
{
score += (a == player1Value ? player2Value : player1Value) * 10;
}
else
{
score += (a == player2Value ? player1Value : player2Value) * 10;
}
}
if (a == b && a == c && d == 0)
{
if (isMaximizer)
{
score += a == player1Value ? player2Value : player1Value;
}
else
{
score += a == player2Value ? player1Value : player2Value;
}
}
}
}
}

return score;
}
private int CheckDiagnal(int[,] board, bool isMaximizer)
{
int score = 0;

for (int column = 0; column < numCols; column++)
{
for (int row = numRows - 1; row >= 0; row--)
{
if (board[row, column] == 0)
{
break;
}

if (row > 2 && column < 4)
{
int a = board[row, column];
int b = board[row - 1, column + 1];
int c = board[row - 2, column + 2];
int d = board[row - 3, column + 3];

if (a == b && a == c && a == d)
{
if (isMaximizer)
{
score += (a == player1Value ? player2Value : player1Value) * 10;
}
else
{
score += (a == player2Value ? player1Value : player2Value) * 10;
}
}
if (a == b && a == c && d == 0)
{
if (isMaximizer)
{
score += a == player1Value ? player2Value : player1Value;
}
else
{
score += a == player2Value ? player1Value : player2Value;
}
}
}
if (row > 2 && column > 2)
{
int a = board[row, column];
int b = board[row - 1, column - 1];
int c = board[row - 2, column - 2];
int d = board[row - 3, column - 3];

if (a == b && a == c && a == d)
{
if (isMaximizer)
{
score += (a == player1Value ? player2Value : player1Value) * 10;
}
else
{
score += (a == player2Value ? player1Value : player2Value) * 10;
}
}
if (a == b && a == c && d == 0)
{
if (isMaximizer)
{
score += a == player1Value ? player2Value : player1Value;
}
else
{
score += a == player2Value ? player1Value : player2Value;
}
}
}
}
}

return score;
}
}
< /code>
в алгоритм negamax сценарий: < /p>
public void BestMove()
{
Move bestMove = new Move(-1, -1, -99);
int[,] currentPlayfield = Playfield.Instance.CopyCurrentPlayField();

List possibleMoves = new List();
possibleMoves.AddRange(GetValidMoves(currentPlayfield));

foreach (Move move in possibleMoves)
{
move.score = -99;
int[,] simBoard = CreateSimulationBoard(move, currentPlayfield, player2Value);
move.score = MinMax(simBoard, maxSearch, -99, 99, player2Value);

if (move.score > bestMove.score)
{
bestMove = move;
}
}

GameManager.Instance.ColumnsPressed(bestMove.column);
}
private int[,] CreateSimulationBoard(Move move, int[,] board, int player)
{
int[,] simBoard = new int[numRows, numCols];
System.Array.Copy(board, simBoard, board.Length);
simBoard[move.row, move.column] = player;
return simBoard;
}
private int MinMax(int[,] board, int searchDepth, int alpha, int beta, int colour)
{
int bestScore = 0;

if (searchDepth == 0 || Playfield.Instance.GameOverCheck(board))
{
bestScore = EvaluateBoard(board, colour);
return bestScore;
}

bestScore = -99;

foreach (Move move in GetValidMoves(board))
{
int[,] simBoard = CreateSimulationBoard(move, board, colour);
bestScore = System.Math.Max(bestScore, -MinMax(simBoard, searchDepth - 1, -beta, -System.Math.Max(alpha, bestScore), GetOppositeColour(colour)));

if (bestScore < alpha) break;
else if (bestScore >= beta) break;

if (bestScore > alpha)
{
alpha = bestScore;
}
}

return bestScore;
}
private int EvaluateBoard(int[,] board, int colour)
{
int score = 0;

score += CheckHorizontal(board, colour);
score += CheckVertical(board, colour);
score += CheckDiagnal(board, colour);

return score;
}
private int CheckHorizontal(int[,] board, int colour)
{
int score = 0;

for (int column = 0; column < numCols; column++)
{
for (int row = numRows - 1; row >= 0; row--)
{
if (board[row, column] == 0)
{
break;
}

if (column < 4)
{
int a = board[row, column];
int b = board[row, column + 1];
int c = board[row, column + 2];
int d = board[row, column + 3];

if (a == b && a == c && a == d)
{
score += a == colour ? 10 : -10;
}
if (a == b && a == c && d == 0)
{
score += a == colour ? 1 : -1;
}
}
if (column > 2)
{
int a = board[row, column];
int b = board[row, column - 1];
int c = board[row, column - 2];
int d = board[row, column - 3];

if (a == b && a == c && a == d)
{
score += a == colour ? 10 : -10;
}
if (a == b && a == c && d == 0)
{
score += a == colour ? 1 : -1;
}
}
}
}

return score;
}
private int CheckVertical(int[,] board, int colour)
{
int score = 0;

for (int column = 0; column < numCols; column++)
{
for (int row = numRows - 1; row >= 0; row--)
{
if (board[row, column] == 0)
{
break;
}

if (row > 2)
{
int a = board[row, column];
int b = board[row - 1, column];
int c = board[row - 2, column];
int d = board[row - 3, column];

if (a == b && a == c && a == d)
{
score += a == colour ? 10 : -10;
}
if (a == b && a == c && d == 0)
{
score += a == colour ? 1 : -1;
}
}
}
}

return score;
}
private int CheckDiagnal(int[,] board, int colour)
{
int score = 0;

for (int column = 0; column < numCols; column++)
{
for (int row = numRows - 1; row >= 0; row--)
{
if (board[row, column] == 0)
{
break;
}

if (row > 2 && column < 4)
{
int a = board[row, column];
int b = board[row - 1, column + 1];
int c = board[row - 2, column + 2];
int d = board[row - 3, column + 3];

if (a == b && a == c && a == d)
{
score += a == colour ? 10 : -10;
}
if (a == b && a == c && d == 0)
{
score += a == colour ? 1 : -1;
}
}
if (row > 2 && column > 2)
{
int a = board[row, column];
int b = board[row - 1, column - 1];
int c = board[row - 2, column - 2];
int d = board[row - 3, column - 3];

if (a == b && a == c && a == d)
{
score += a == colour ? 10 : -10;
}
if (a == b && a == c && d == 0)
{
score += a == colour ? 1 : -1;
}
}
}
}

return score;
}
private int GetOppositeColour(int color)
{
return color == player1Value? player2Value : color;
}

В пределах Minimax One Side пытается максимизировать результат, в то время как другой игрок/компьютер пытается минимизировать (что означает, что они выигрывают). Negamax берет ту же систему, но становится полностью положительным, поэтому все пытаются максимизировать, однако перед переключением игроков (+ возвращаемое значение), позитивность изменяется на отрицательный, потому что все, что хорошо для вашего противника, вероятно, плохо для вас. Negamax действительно пытается выиграть, но не всегда блокирует то, что для меня хорошо, что означает, что он делает основные ошибки, которые потеряют компьютер в игру. Мне нужно избавиться от этих ошибок, я полагаю, что я просто адаптировал часть неправильного пути, но она должна быть близок (я могу ошибать Mathf.min. < /P>
Я пытался работать с (alpha> = beta) break; < /p>
Я переписал функцию оценки, чтобы быть как можно более коротким (это было иначе). Есть мысли? Я действительно ценю любую информацию, для меня это новая тема. Было ли разумнее заняться? Вот что делает компьютер. Супер странно, он принимает правильные решения, но не вовремя. public void BestMove()
{
Move bestMove = new Move(-1, -1, -99);
int[,] currentPlayfield = Playfield.Instance.CopyCurrentPlayField();

foreach (Move move in GetValidMoves(currentPlayfield))
{
move.score = -99;
int[,] simBoard = CreateSimulationBoard(move, currentPlayfield, player2Value);
move.score = MinMax(simBoard, 0, -99, 99, player2Value);

if (move.score > bestMove.score)
{
bestMove = move;
}
}

GameManager.Instance.ColumnsPressed(bestMove.column);
}
private int[,] CreateSimulationBoard(Move move, int[,] board, int player)
{
int[,] simBoard = new int[numRows, numCols];
System.Array.Copy(board, simBoard, board.Length);
simBoard[move.row, move.column] = player;
return simBoard;
}
private int MinMax(int[,] board, int searchDepth, int alpha, int beta, int colour)
{
int bestScore = 0;

if (searchDepth == maxSearch || Playfield.Instance.GameOverCheck(board))
{
bestScore = EvaluateBoard(board, colour);
return bestScore;
}

bestScore = -99;

foreach (Move move in GetValidMoves(board))
{
int[,] simBoard = CreateSimulationBoard(move, board, colour);
bestScore = Mathf.Max(bestScore, -MinMax(simBoard, searchDepth + 1, -beta, -System.Math.Max(alpha, bestScore), GetOppositeColour(colour)));

//Debug info
print(Playfield.Instance.DebugBoard(simBoard));
Debug.Log("colour: " + colour);
Debug.Log("searchDepth: " + searchDepth);
Debug.Log("bestScore: " + bestScore);
Debug.Log("alpha: " + alpha);
Debug.Log("beta: " + beta);

if (bestScore < alpha) break;
else if (bestScore >= beta) break;

alpha = System.Math.Max(alpha, bestScore);
}

return bestScore;
}
< /code>
Как предложено, я также собираюсь посмотреть на негаскую часть. Может быть, это исправляет.
private int NegaMax(int[,] board, int searchDepth, int alpha, int beta, int colour)
{
int bestScore = 0;

if (searchDepth == maxSearchDepth || Playfield.Instance.GameOverCheck(board))
{
bestScore = EvaluateBoard(board, colour);
return bestScore;
}

bestScore = -99;

foreach (Move move in GetValidMoves(board))
{
int[,] simBoard = CreateSimulationBoard(move, board, colour);
bestScore = -NegaMax(simBoard, searchDepth + 1, -beta, -System.Math.Max(alpha, bestScore), GetOppositeColour(colour));
//bestScore = Mathf.Max(bestScore, -NegaMax(simBoard, searchDepth + 1, -beta, -System.Math.Max(alpha, bestScore), GetOppositeColour(colour)));

////Debug info
//print(Playfield.Instance.DebugBoard(simBoard));
//Debug.Log("colour: " + colour);
//Debug.Log("searchDepth: " + searchDepth);
//Debug.Log("bestScore: " + bestScore);
//Debug.Log("alpha: " + alpha);
//Debug.Log("beta: " + beta);

if (bestScore < alpha) break;
else if (bestScore >= beta) break;

alpha = System.Math.Max(alpha, bestScore);
}
//Debug.Log("-------------------");

return bestScore;
}
private int NegaScout(int[,] board, int searchDepth, int alpha, int beta, int colour)
{
int bestScore = 0;

if (searchDepth == maxSearchDepth || Playfield.Instance.GameOverCheck(board))
{
bestScore = EvaluateBoard(board, colour);
return bestScore;
}

bestScore = -99;
int adaptiveBeta = beta;

foreach (Move move in GetValidMoves(board))
{
int[,] simBoard = CreateSimulationBoard(move, board, colour);
int currentScore = -NegaMax(simBoard, searchDepth + 1, -adaptiveBeta, -System.Math.Max(alpha, bestScore), GetOppositeColour(colour));

if (currentScore > bestScore)
{
if (adaptiveBeta == beta || searchDepth >= maxSearchDepth - 2)
{
bestScore = currentScore;
}
else
{
bestScore = -NegaScout(simBoard, searchDepth + 1, -adaptiveBeta, -System.Math.Max(alpha, bestScore), GetOppositeColour(colour));
}

if (bestScore >= beta) return bestScore;
adaptiveBeta = Mathf.Max(alpha, bestScore) + 1;
}
}

return bestScore;
}


Подробнее здесь: https://stackoverflow.com/questions/797 ... -b-negamax