Я пытаюсь реализовать алгоритм minmax для создания ИИ для подключения четырех. У меня с этим немного проблемы, хотя я чувствую, что у меня слишком сложные вещи (и это не работает должным образом), возможно, кто-то здесь может помочь. Сначала я отправлю свой код, а затем проблему, с которой я столкнулся.Minmax для ConnectFour
Это начальный вызов алгоритма MinMax
public int getColumnForMove(ConnectFour game)
{
game.minimax(2, game.getCurrentPlayer(), game);
int column = game.getBestMove();
return column;
}
Это начальный минимаксное метод (он находится внутри класса Четыре в ряд, который не является, где первоначальный метод вызывается из т в отдельный класс AI), который называется и подкласс, который содержит каждый столбец, который перемещается пользователем, а также минимальный/максимальный балл, если он перемещается в этот столбец.
class ColumnsAndScores
{
int column;
int score;
ColumnsAndScores(int column, int score)
{
this.column = column;
this.score = score;
}
}
List<ColumnsAndScores> cas = new ArrayList<>();
public void minimax(int depth, int turn, ConnectFour game)
{
cas = new ArrayList<>();
minimaxHelper(depth, depth, turn, game);
}
Ниже приведены методами, которые получают минимальные или максимальный счет от каждого набора возможных ходов:
public int getMax(List<Integer> list)
{
int max = Integer.MIN_VALUE;
int index = -1;
for (int i = 0; i < list.size(); i++)
{
if (list.get(i) > max)
{
max = list.get(i);
index = i;
}
}
return list.get(index);
}
public int getMin(List<Integer> list)
{
int min = Integer.MAX_VALUE;
int index = -1;
for (int i = 0; i < list.size(); i++)
{
if (list.get(i) < min)
{
min = list.get(i);
index = i;
}
}
return list.get(index);
}
Это фактический метод минимакса (он имеет кучу закомментирован код, который показывает его должен возвращать диапазон значений в зависимости от того, насколько хороша плата, если она не является четкой победой или потерями, но сейчас я просто пытаюсь заставить ее принимать решения на основе победы или потери (если ни одно из этого не происходит в запрошенном глубина делает случайный ход)).
public int minimaxHelper(int originalDepth, int depth, int turn, ConnectFour game)
{
//holds future game states
ConnectFour futureGameState;
//holds the current scores
List<Integer> scores = new ArrayList<>();
//if (not at the lowest depth)
if (depth !=0)
{
if (checkForWin(turn))
{
//return Integer.MAX_VALUE or Integer.MIN_VALUE respectively based on who's turn it is
return (turn % 2 == 0) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
//recursively call getColumnForMove(depth--, otherTurn) for each column if the column isnt full
for (int i = 1; i <= ConnectFour.NUM_OF_COLUMNS; i++)
{
futureGameState = new ConnectFour();
futureGameState.setCurrentGameState(game.getCurrentGameState());
futureGameState.setCurrentPlayer(game.getCurrentPlayer());
if (futureGameState.isValidMove(i))
{
futureGameState.makeMove(i);
futureGameState.switchPlayer();
scores.add(minimaxHelper(originalDepth, depth - 1, futureGameState.getCurrentPlayer(), futureGameState));
}
else //if move isnt valid return the worst possible value so this column doesnt get chosen
{
return (turn % 2 == 0) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
if (depth == originalDepth)
{
ColumnsAndScores newScore;
if (turn % 2 == 0)
newScore = new ColumnsAndScores(i, getMax(scores));
else
newScore = new ColumnsAndScores(i, getMin(scores));
cas.add(newScore);
}
}
if (turn % 2 == 0)
return getMax(scores);
else
return getMin(scores);
}
else
{
if (checkForWin(turn))
{
//return Integer.MAX_VALUE or Integer.MIN_VALUE respectively based on who's turn it is
return (turn % 2 == 0) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
else
{
return 0;
}
//else
//if 3 in a row with 2 open spaces that have pieces under those spaces
//return 100
//else if 3 in a row with 1 open space that has a piece under that space
//return 80;
//else if 3 in a row
//return 60;
//else if 2 in a row
//return 40
//else
//return 0
}
}
и, наконец, это метод, который вызывается искусственным интеллектом, чтобы получить лучший шаг из списка, который Минимаксные добавившие ColumnAndScores тоже.
public int getBestMove()
{
int highestScore = Integer.MIN_VALUE;
int best = -1;
for (int i = 0; i < cas.size(); ++i) {
if (highestScore < cas.get(i).score) {
highestScore = cas.get(i).score;
best = i;
}
}
if (highestScore == 0)
return 1 + ((int) (Math.random() * 7));
else
return best;
}
Хотя я считаю, что есть несколько логических ошибок вещь, которую я имею наибольшие трудности с на данный момент является то, что, когда я futureGameState = new ConnectFour(); futureGameState.setCurrentGameState(game.getCurrentGameState());
Это должно положить его в отдельный экземпляр, так что, когда Затем я делаю ход, который должен продолжаться только для этой ветви дерева и не искажать реальную игру, но это не так. Он меняет фактическое состояние передаваемой игры.