Впервые на самом деле пользуюсь сайтом, поэтому, если я что-то не так делаю, я заранее извиняюсь и постараюсь исправить это, руководствуясь указаниями. В настоящее время я работаю над своим старшим проектом. Это игра, очень похожая на крестики-нолики, но высота и ширина доски имеют переменные размеры, а количество в строке, необходимое для выигрыша, также является переменным (все выбирается пользователем с помощью jcomboboxes).
проблема в том, что метод miniMax часто выбирает уже выбранную плитку. Я не совсем уверен, как выяснить источник проблемы, проведя немало часов исследований. Мне просто нужно указать правильное направление на способ поиска источника, но я с радостью приму любую помощь, какую только смогу получить
прилагается ниже код. Я предоставил весь код программы, чтобы ее можно было легко скомпилировать и протестировать. Если это неправильно, я прошу прощения, дайте мне знать, и я исправлю.
Я нашел различные примеры реализации минимаксного алгоритма и в конечном итоге использовал его по следующей ссылке: Простейший алгоритм MiniMax для TicTacToe AI в Java
Я также пытался реализовать следующее: https://medium.com/@pelensky/unbeatable-tic-tac-toe-minimax-in-java-e1ad687ed821
но это привело к многочисленным ошибкам переполнения стека, которые я не мог понять, как разумно смягчить, не переделывая весь алгоритм.
В настоящее время я работаю с первым, и он работает в определенной степени, но ИИ, похоже, не принимает разумных решений и часто пытается выбрать уже выбранную плитку.
import java.awt.Dimension;
import java.awt.GridLayout;
import java.awt.Window;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import javax.swing.*;
public class Konnexion extends JPanel
{
ArrayList<JButton> buttons = new ArrayList<JButton>();
private static int totalButtons;
private JLabel winStat;
private JLabel lossStat;
protected JLabel drawStat;
JPanel gameBoard;
JButton exitButton;
int wins = 0;
int losses = 0;
int draws = 0;
Game game;
public Konnexion(int height, int width, int connects, String ai)
{
JPanel gameStats = new JPanel();
gameStats.setLayout(new GridLayout(1,3));
winStat = new JLabel("Wins: " + wins);
lossStat = new JLabel("Losses: " + losses + " ");
drawStat = new JLabel("Draws: " + draws);
gameStats.add(winStat);
gameStats.add(lossStat);
gameStats.add(drawStat);
add(gameStats);
totalButtons = (height * width) - 1;
gameBoard = new JPanel();
gameBoard.setLayout(new GridLayout(height,width));
initializebuttons();
add(gameBoard);
JPanel menuButtons = new JPanel();
menuButtons.setLayout(new GridLayout(1,1));
exitButton = new JButton();
exitButton.setText("Exit Game");
exitButton.addActionListener(new buttonListener());
menuButtons.add(exitButton);
add(menuButtons);
game = new Game(totalButtons, height, width, connects, ai);
}
public void initializebuttons()
{
for(int i = 0; i <= totalButtons; i++)
{
buttons.add(i, new JButton());
buttons.get(i).setText("");
buttons.get(i).setPreferredSize(new Dimension(75,75));
buttons.get(i).addActionListener(new buttonListener());
gameBoard.add(buttons.get(i));
}
}
public void resetButtons()
{
for(int i = 0; i <= totalButtons; i++)
{
buttons.get(i).setText("");
}
game.resetGameState();
}
private class buttonListener implements ActionListener
{
public void actionPerformed(ActionEvent e)
{
JButton buttonClicked = (JButton)e.getSource(); //get the particular button that was clicked
if (buttonClicked.getText().equals(""))
{
buttonClicked.setText(Game.getSymbol(game.getCurrentPlayer()));
game.setMarker(buttons.indexOf(buttonClicked), game.getSymbol(game.getCurrentPlayer()));
if (Game.getSymbol(game.getCurrentPlayer()).equals("X"))
{
game.changeCurrentPlayer();
if (game.hasWon("X", Game.cells)) {
wins++;
winStat.setText("Wins: " + wins);
JOptionPane.showConfirmDialog(null, "Player X Wins!!!");
resetButtons();
game.resetGameState();
}
}
else
{
game.changeCurrentPlayer();
if (game.hasWon("O", Game.cells)) {
losses++;
lossStat.setText("Losses: " + losses + " ");
JOptionPane.showConfirmDialog(null, "Player O Wins!!!");
resetButtons();
game.resetGameState();
}
}
if (game.getCurrentPlayer() == 2) {
game.printArrays();
game.copyGameState();
//System.out.println(game.miniMax(game.getCurrentPlayer()));
buttons.get(game.miniMax(game.getCurrentPlayer())).doClick();
}
}
else if (buttonClicked.equals(exitButton))
{
Window window = SwingUtilities.getWindowAncestor(exitButton);
window.dispose();
try {
new MainMenu();
} catch (IOException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
}
else
{
JOptionPane.showMessageDialog(buttonClicked, "That tile has already been selected!");
}
if (game.checkDraw())
{
draws++;
drawStat.setText("Draws: " + draws);
JOptionPane.showConfirmDialog(null, "It was a Draw!!!");
resetButtons();
}
}
}
}
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
public class Game {
public static int ROWS;
public static int COLS;
public static int WIN_SIZE;
public static int currentPlayer;
public static String[][] cells; //Game state array
String[][] node; //copy of the game state used for minimax method
public Game(int totalButtons, int height, int width, int connects, String difficulty) {
ROWS = height;
COLS = width;
WIN_SIZE = connects;
currentPlayer = 1;
cells = new String[ROWS][COLS];
node = new String[ROWS][COLS];
resetGameState(cells);
resetGameState(node);
}
public void setMarker(int space, String marker) {
int col = space % COLS;
int rows = space / COLS;
cells[rows][col] = marker;
}
public void changeCurrentPlayer() {
if (currentPlayer == 1)
{
currentPlayer = 2;
}
else if (currentPlayer == 2)
{
currentPlayer = 1;
}
}
public int getCurrentPlayer() {
return currentPlayer;
}
public static String getSymbol(int playerNum) {
if (playerNum == 1)
return "X";
else
return "O";
}
public void resetGameState() {
currentPlayer = 1;
for (int i = 0; i < cells.length; i++) {
for (int j = 0; j < cells[i].length; j++) {
cells[i][j] = "-";
}
}
}
public static void resetGameState(String[][] gameState) {
for (int i = 0; i < gameState.length; i++) {
for (int j = 0; j < gameState[i].length; j++) {
gameState[i][j] = "-";
}
}
}
/**
*
* @param theSeed Value expected in each cell
* @param row Row index to check
* @param col Col index to check
* @param count Number of consecutive elements found in the line.
* @param rowIncrement Increment to the row index for the next evaluation
* @param colIncrement Increment to the col index for the next evaluation
* @return true if there is a winner combination in the line, otherwise false.
*/
private boolean checkLine(String theSeed, int row, int col, int count, int rowIncrement, int colIncrement, String[][] gameCheck) {
if (!areValidIndexes(row, col)) {
return false;
}
if (theSeed.equals(gameCheck[row][col])) {
count++;
if (count >= WIN_SIZE) {
return true;
} else {
return checkLine(theSeed, row + rowIncrement, col + colIncrement, count, rowIncrement, colIncrement, gameCheck);
}
} else {
return false;
}
}
private boolean areValidIndexes(int row, int col) {
if (row >= 0 && row < ROWS &&
col >= 0 && col < COLS) {
return true;
}
return false;
}
private boolean checkRow(String theSeed, int row, int col, String[][] gameCheck) {
return checkLine(theSeed, row, col, 0, 1, 0, gameCheck);
}
private boolean checkColumn(String theSeed, int row, int col, String[][] gameCheck) {
return checkLine(theSeed, row, col, 0, 0, 1, gameCheck);
}
private boolean checkForwardDiagonal(String theSeed, int row, int col, String[][] gameCheck) {
return checkLine(theSeed, row, col, 0, 1, 1, gameCheck);
}
private boolean checkBackwardDiagonal(String theSeed, int row, int col, String[][] gameCheck) {
return checkLine(theSeed, row, col, 0, -1, 1, gameCheck);
}
public boolean hasWon(String theSeed, String[][] gameCheck) {
for (int row = 0; row < ROWS; row++) {
for (int col = 0; col < COLS; col++) {
if (checkRow(theSeed, row, col, gameCheck) ||
checkColumn(theSeed, row, col, gameCheck) ||
checkForwardDiagonal(theSeed, row, col, gameCheck) ||
checkBackwardDiagonal(theSeed, row, col, gameCheck)) {
return true;
}
}
}
return false;
}
public boolean checkDraw()
{
String s = "";
for (String[] r : cells) {
for (String t : r) {
s += t;
}
}
if (!s.contains("-"))
{
return true;
}
return false;
}
public static boolean checkDraw(String[][] node)
{
String s = "";
for (String[] r : node) {
for (String t : r) {
s += t;
}
}
if (!s.contains("-"))
{
return true;
}
return false;
}
public int checkWin(String[][] gameState) {
if (hasWon("X", gameState))
{
return 1;
}
else if (hasWon("O", gameState))
{
return 2;
}
else
{
return 0;
}
}
public void copyGameState() {
for (int i = 0; i < cells.length; i++) {
for (int j = 0; j < cells[i].length; j++) {
node[i][j] = cells[i][j];
}
}
}
public static int[] getAvailableSpaces() {
String s = "";
for (int i = 0; i < cells.length; i++) {
for (int j = 0; j < cells[i].length; j++) {
if (cells[i][j].equals("-"))
s += ((j * COLS) + i) + ", ";
}
}
String[] split = s.split(", ");
int[] availableSpaces = new int[split.length];
for (int i = 0; i < split.length; i++)
availableSpaces[i] = Integer.parseInt(split[i]);
return availableSpaces;
}
public void resetSpace(int space) {
int col = space % COLS;
int rows = space / COLS;
cells[rows][col] = "-";
}
public int miniMax(int playerNum)
{
//printArrays();
int victor = checkWin(cells); // returns 0 if game is ongoing, 1 for p1, 2 for p2, 3 for tie.
if(victor != 0) //game over
{
return Score(victor);
}
if(playerNum == 2) //AI
{
int bestVal = Integer.MAX_VALUE;
int bestSpot = 0;
for(int i = 0; i < cells.length; i++)
for (int j = 0; j < cells[i].length; j++)
{
if(!cells[i][j].equals("-"))
continue;
cells[i][j] = getSymbol(playerNum);
int value = miniMax(1);
if(value < bestVal)
{
bestVal = value;
bestSpot = (j * COLS) + i;
System.out.println("Best Value: " + bestVal);
System.out.println("Best Spot: " + bestSpot);
}
cells[i][j] = "-";
}
return bestSpot;
}
else
{
int bestVal = Integer.MIN_VALUE;
int bestSpot = 0;
for(int i = 0; i < cells.length; i++)
for(int j = 0; j < cells[i].length; j++)
{
if(!cells[i][j].equals("-"))
continue;
cells[i][j] = getSymbol(playerNum);
int value = miniMax(2);
if(value > bestVal)
{
bestVal = value;
bestSpot = (j * COLS) + i;
}
cells[i][j] = "-";
}
return bestSpot;
}
}
private int Score(int gameState)
{
if(gameState ==2) //O wins.
return 10;
else if(gameState==1) //X wins
return -10;
return 0;
}
public void printArrays() {
String s = "cells: ";
String l = "node: ";
for (int i = 0; i < cells.length; i++) {
for (int j = 0; j <cells[i].length; j++) {
s += cells[i][j];
l += node[i][j];
}
}
System.out.println(s);
System.out.println(l);
}
}