Java - проблема минимаксного алгоритма
Я работаю на TicTackoe доске для практики создания классов, и я столкнулся с проблемой с моим алгоритмом. кажется, он возвращает лучший ход в наступление, но он не играет в оборону. я не знаю, где я испортил и не могу найти его. Здесь я рассмотрел много вещей об этом и сравнил их с симуляционными проектами, но все еще не могу этого понять. вот мой код
package TicTacToe;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
public class Solution {
private static GameBoard currentBoard;
private static Player botPlayer;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String player;
System.out.println("ENTER bot: ");
player = in.next();
if(player.equalsIgnoreCase("X")) {
botPlayer = Player.X;}
else {botPlayer = Player.O;}
String board[] = new String[3];
for(int i = 0; i < 3; i++) {
System.out.println("ENTER board: ");
board[i] = in.next();
}
currentBoard = new GameBoard(3,3, board);
List<Space> OpenSpaces = getOpenSquares(currentBoard);
MakeMove(OpenSpaces);
System.exit(-1);
}
public static List<Space> getOpenSquares(GameBoard GB) {
List<Space> OpenSpaces = new ArrayList<Space>();
for(int r = 0; r < 3; r++) {
for(int c = 0; c < 3; c++) {
if(GB.squares[r][c] == Player.Open) {
OpenSpaces.add(new Space(r,c));
}
}
}
return OpenSpaces;
}
private static Space bestMove;
private static Space currentMove;
private static Space previousMove;
private static void MakeMove(List<Space> OpenSpaces) {
if(OpenSpaces.size() == currentBoard.Size) {
Random random = new Random();
bestMove = new Space(random.nextInt(2),2);
} else {
for(Space child: OpenSpaces) {
currentMove = GetBestMove(currentBoard,botPlayer);
if (currentMove != null){
}else{
continue;}
if(previousMove != null && previousMove.Rank < currentMove.Rank ||
previousMove == null && currentMove != null) {
bestMove = currentMove;
}
previousMove = currentMove;
}
}
if (bestMove != null) {
currentBoard.squares[bestMove.X][bestMove.Y] = botPlayer;
System.out.println("the best move is: " + currentMove.X + " " + currentMove.Y);
}
}
private static Space GetBestMove(GameBoard gb, Player p) {
Space bestSpace = null;
List<Space> cloneOpenSpaces = getOpenSquares(gb);
GameBoard cloneBoard = null;
cloneBoard = gb.Clone();
for(Space Open: cloneOpenSpaces) {
cloneBoard = gb.Clone();
Space newSpace = Open;
cloneBoard.squares[newSpace.X][newSpace.Y] = p;
if(cloneBoard.Winner == Player.Open && cloneOpenSpaces.size() > 0) {
Player InP;
if(p == Player.X) {
InP = Player.O;
}else {
InP = Player.X;
}
Space tempMove = GetBestMove(cloneBoard, InP);
if(tempMove != null){
newSpace.Rank = tempMove.Rank;
}
} else {
if(cloneBoard.Winner == Player.Open) {
newSpace.Rank = 0;
}else if(cloneBoard.Winner == Player.O) {
newSpace.Rank = -1;
}else if(cloneBoard.Winner == Player.X) {
newSpace.Rank = 1;
}
}
System.out.println(newSpace.Rank);
if(bestSpace == null ||
(p == Player.X && newSpace.Rank < ((Space)bestSpace).Rank)||
(p == Player.O && newSpace.Rank > ((Space)bestSpace).Rank)) {
bestSpace = newSpace;
}
}
return (Space)bestSpace;
}
public static enum Player {
X (1),
O (-1),
Open (0);
private final double value;
Player(double value){
this.value = value;
}
}
public static class Space {
public int X;
public int Y;
public double Rank;
public Space(int x, int y) {
this.X = x;
this.Y = y;
Rank = 0;
}
public Space() {
}
}
public static class GameBoard {
public int Rows;
public int getRows() {
return this.Rows;
}
public void setRows(int rows) {
Rows = rows;
}
public int Columns;
public int getColumns() {
return this.Columns;
}
public void setColumns(int columns) {
Columns = columns;
}
public Player[][] squares;
//public Player[x][y]
public Player getPlayer(int x, int y) {
return this.squares[x][y];
}
public void setPlayer(int x, int y, Player player) {
squares[x][y] = player;
}
public boolean Full;
public boolean isFull() {
for(int r = 0; r < 2; r++) {
for(int c = 0; c < 2; c++) {
if (squares[r][c] != Player.Open) {return false;}
}
}
return true;
}
public int Size;
public int getSize() {
return this.Size;
}
public void setSize(int size) {
Size = size;
}
public List<Space> OpenSquares;
public List<Space> getOpenSquares() {
List<Space> OpenSquares = new ArrayList<Space>();
for(int r = 0; r < Rows; r++) {
for(int c = 0; c < Columns; c++) {
if(squares[r][c] == Player.Open) {
OpenSquares.add(new Space(r,c));
}
}
}
return this.OpenSquares;
}
public Player Winner;
public Player getWinner() {
int count = 0;
//columns
for (int x = 0; x < Rows; x++)
{
count = 0;
for (int y = 0; y < Columns; y++) {
count += squares[x][y].value;
}
if (count == 3) {
return Player.X;
}else if (count == -3) {
return Player.O;
}
}
//rows
for (int x = 0; x < Rows; x++) {
count = 0;
for (int y = 0; y < Columns; y++) {
count += squares[y][x].value;
}
if (count == 3) {
return Player.X;
}else if (count == -3) {
return Player.O;
}
}
// Diagonals right to left
count = 0;
count += squares[0][0].value;
count += squares[1][1].value;
count += squares[2][2].value;
if (count == 3) {
return Player.X;
}else if (count == -3) {
return Player.O;
}
// Diagonals left to right
count = 0;
count += squares[0][2].value;
count += squares[1][1].value;
count += squares[2][0].value;
if (count == 3) {
return Player.X;
}else if (count == -3) {
return Player.O;
}
return Player.Open;
}
public GameBoard Clone() {
GameBoard b = new GameBoard(Rows,Columns);
b.squares = (Player[][])this.squares.clone();
b.Winner = getWinner();
return b;
}
// Class initializer
public GameBoard(int boardRows, int boardColumns, String[] board) {
// Set the dimensions
Rows = boardRows;
Columns = boardColumns;
// Create game spaces
squares = new Player[Rows][Columns];
for(int r = 0; r < Rows; r++) {
for(int c = 0; c < Columns; c++) {
//squares[i][n] = Player.Open;
if(board[r].charAt(c) == 'X') {
squares[r][c] = Player.X;
}
if(board[r].charAt(c) == 'O') {
squares[r][c] = Player.O;
}
if(board[r].charAt(c) == '_') {
squares[r][c] = Player.Open;
}
}
}
this.Winner = getWinner();
this.OpenSquares = getOpenSquares();
//Size of the board
this.Size = Rows * Columns;
}
// clone Class initializer
public GameBoard(int boardRows, int boardColumns) {
// Set the dimensions
Rows = boardRows;
Columns = boardColumns;
// Create game spaces
squares = new Player[Rows][Columns];
for(int r = 0; r < Rows; r++) {
for(int c = 0; c < Columns; c++) {
squares[r][c] = Player.Open;
}
}
this.Winner = getWinner();
this.OpenSquares = getOpenSquares();
//Size of the board
Size = Rows * Columns;
}
}
}
все классы внизу. Заранее спасибо за любую помощь и исправления.:)
я сделал это рекурсивным в следующем коде, хотя я все еще не могу выяснить выигрыш.. если значение равно 1, 0 или -1, то если есть многократные ходы с тем же значением, он просто возьмет 1-й, который может Не будь лучшим ходом "блокировка.
private static Space GetBestMove(GameBoard gb, Player p) {
Space bestSpace = null;
List<Space> cloneOpenSpaces = getOpenSquares(gb);
GameBoard cloneBoard = null;
cloneBoard = gb.Clone();
for(Space Open: cloneOpenSpaces) {
cloneBoard = gb.Clone();
Space newSpace = Open;
cloneBoard.squares[newSpace.X][newSpace.Y] = p;
if(cloneBoard.Winner == Player.Open && cloneOpenSpaces.size() > 0) {
Player InP;
if(p == Player.X) {
InP = Player.O;
}else {
InP = Player.X;
}
***Space tempMove = GetBestMove(cloneBoard, InP);***
if(tempMove != null){
newSpace.Rank = tempMove.Rank;
}
Результаты теста следующие
тест 1
ENTER bot:
O
ENTER board:
[ ][O][ ]
ENTER board:
[ ][ ][ ]
ENTER board:
[ ][X][X]
-1.0
-1.0
-1.0
-1.0
-1.0
-1.0
-1.0
-1.0
-1.0
the best move is: 0 2
тест 2
ENTER bot:
O
ENTER board:
[ ][X][X]
ENTER board:
[ ][ ][ ]
ENTER board:
[ ][O][ ]
1.0
1.0
1.0
1.0
1.0
-1.0
1.0
-1.0
-1.0
1.0
-1.0
1.0
1.0
-1.0
-1.0
the best move is: 1 1
1 ответ
Я не запускал твой код, но думаю, я знаю, почему у тебя проблемы. Минимаксный алгоритм является рекурсивным по своей природе. Вы смотрите на каждое открытое пространство и определяете какой-то счет для каждого. Я вижу это в вашем коде. Однако то, что я не вижу, это рекурсия, которая соответствует логике "если я перееду сюда, то какие варианты будет у моего противника во время его следующего хода". Обратите внимание, что вы можете продолжать вызывать одну и ту же функцию подсчета очков, но оценивать опции обоих игроков. Это где вычисления могут стать интенсивными, и где такие вещи, как обрезка вступает в игру. Скажем, я хочу посмотреть на 3 хода вперед. Скажем, изначально есть 5 открытых мест. Для каждого из 5 открытых пространств я изучаю свои варианты и выставляю баллы каждому. Затем я притворяюсь, что двигаюсь туда, и отправляю новую доску через функцию подсчета очков, и предполагаю, что мой противник получит самый высокий ход выигрыша из оставшихся 4 возможных ходов. Затем я притворяюсь, что он перемещается туда, и я снова провожу доску через функцию подсчета очков, теперь с двумя гипотетическими движениями на ней. Вы продолжаете это для набора "глубины" или количества потенциальных ходов и выбираете ход, который приводит к наибольшему значению, предполагая, что противник будет делать то, что вы рассчитали, что они будут.
Я понимаю, что это было многословно, но я надеюсь, что где-то там похоронили немного ценности. Посмотрите на свой код, выясните, где вы забиваете ходы (если вы видите выигрыш, берите его; если вы можете заблокировать выигрыш, берите его и т. Д.). Затем продолжайте вызывать эту функцию, где вы продолжаете добавлять ложные / потенциальные ходы (те, которые имеют наибольшее значение из вашей функции подсчета очков), и как только вы достигнете глубины, вы можете просто выбрать ход, который, вероятно, даст вам наиболее ценный результат.
В основном, в вашем коде, вы должны позвонить GetBestMove(...) однажды из MakeMove(...), Тем не мение, GetBestMove(...) следует многократно звонить сам, с модифицированной доской каждый раз; и каждый раз он будет возвращать лучший ход с учетом гипотетической (или реальной) доски. Чего я не вижу в вашем коде, так это рекурсивного вызова GetBestMove(...)и необходимый уход, который идет вместе с ним. Это объясняет, почему вы получаете только агрессивное поведение; он только смотрит, что является лучшим немедленным ходом, без учета того, что ваш оппонент может сделать, если вы сделаете этот ход!
Если мои предположения неверны, приведите контрольный пример, в котором вы ожидаете некоторого поведения, но получаете что-то другое.