Ttykuu

I've been researching the minimax algorithm and how it's implemented in Tic-Tac-Toe. But for whatever reason, it loses, on average, 15% of the games against a random bot. Could someone help me figure out what's wrong with my algorithm?

Note: GameController.java, the 'middle man' between TicTacToe.java and my bot, calls the playTurn function in EustorgiusSylwester.java, and expects a integer array of length 2 with the coordinates.

EustorgiusSylwester.java (the bot)

// 0 = empty
// 1 = X
// 2 = O
public class EustorgiusSylwester extends TicTacToePlayer
 public EustorgiusSylwester(String aName, int aPiece) 
 super(aName, aPiece);
 
 public static int getOpp(int p) 
 return ((p == 1) ? 2 : 1);
 
 public static int min(int a, int b) 
 return (a < b) ? a : b;
 
 public static int max(int a, int b) 
 return (a > b) ? a : b;
 
 public static void printBoard(int[][] b) 
 for(int[] x: b) 
 for(int y: x) 
 if(y == 1) 
 System.out.print('X');
 else if(y == 2) 
 System.out.print('O');
 else 
 System.out.print('_');
 
 
 System.out.println();
 
 
 public static boolean won(int[][] b, int p) 
 for(int[] x: b) 
 if(x[0] == x[1] && x[1] == x[2] && x[0] == p) 
 return true;
 
 
 for(int i = 0; i < b.length; i++) 
 for(int j = 0; j < b[i].length; j++) 
 if(b[0][j] == b[1][j] && b[1][j] == b[2][j] && b[1][j] == p) 
 return true;
 
 
 
 if(b[0][0] == b[1][1] && b[0][0] == b[2][2] && b[0][0] == p) 
 return true;
 
 if(b[2][0] == b[1][1] && b[2][0] == b[0][2] && b[0][2] == p) 
 return true;
 
 return false;
 
 public static boolean drawn(int[][] b) 
 for(int[] x: b) 
 for(int y: x) 
 if(y == 0) 
 return false;
 
 
 
 return true;
 
 // -------------------------------------
 public static int eval(int[][] board, int depth, int p, int ai)
 if(won(board, p)) 
 return 10 - depth++;
 else if(won(board, getOpp(p))) 
 return -10 + depth++;
 else if(drawn(board))
 return 0 - depth++;
 
 if(p == ai) 
 int best = -10000;
 for(int i = 0; i < 3; i++) 
 for(int j = 0; j < 3; j++) 
 if(board[i][j] != 0) 
 continue;
 
 board[i][j] = p;
 best = max(best, eval(board, depth++, getOpp(p), ai) - depth);
 board[i][j] = 0;
 
 
 return best;
 else 
 int best = 10000;
 for(int i = 0; i < 3; i++) 
 for(int j = 0; j < 3; j++) 
 if(board[i][j] != 0) 
 continue;
 
 board[i][j] = p;
 best = min(best, eval(board, depth++, getOpp(p), ai) + depth);
 board[i][j] = 0;
 
 
 return best;
 
 
 @Override
 public int[] playTurn() 
 int[][] b = GameController.game.getBoard();
 int p = getPiece();
 int bmI = 0;
 int bmJ = 0;
 int bmEval = -10000;
 for(int i = 0; i < 3; i++) 
 for(int j = 0; j < 3; j++) 
 if(b[i][j] != 0) 
 continue;
 
 b[i][j] = p;
 int eval = eval(b, 0, p, getPiece());
 b[i][j] = 0;
 if(eval > bmEval) 
 bmI = i;
 bmJ = j;
 bmEval = eval;
 
 
 
 printBoard(b);
 System.out.println();
 return new int[] bmI, bmJ;
 

GameController.java

//This class's job is to coordinate between the players and the game code, it is the middle man
//A game object is created, followed by two player objects, then the game is run as the players
//take turns and interact with the game code.

//**THIS IS THE FILE YOU RUN TO PLAY THE GAME**//

import java.util.Scanner;

public class GameController 

 // **PLAYERS ARE SET UP HERE**//
 // To test your bot, replace one of the human players with your bot and play
 // against it
 // p1 is X and goes first
 private static TicTacToePlayer p1 = new RandomPlayer("Joe", 1);
 private static TicTacToePlayer p2 = new EustorgiusSylwester("Paul", 2);

 // Copy of the board from TicTacToe.java for players to access
 private static int[][] board;
 private static int turnTimer = 0;

 // initialize the game
 public static TicTacToe game = new TicTacToe();

 // gets a copy of the game board
 public static int[][] getBoard() 
 board = game.getBoard();

 return board;
 

 public static int getTurnCount() 
 return turnTimer;
 

 // plays a single game, returns the number of the player who won, 3 if tie
 private static int playGame() 
 turnTimer = 0;
 // game plays
 int state = 0; // 0 = ongoing, 1 = X win, 2 = O win, 3 = tie
 while (state == 0) 
 game.placePiece(p1.playTurn(), 1); // x player goes
 turnTimer++;

 // check state after X goes to see if the game ended
 state = game.gameOver();
 if (state != 0) 
 break;
 

 game.placePiece(p2.playTurn(), 2); // O player goes
 turnTimer++;

 state = game.gameOver(); // update state after O goes, while loop condition will handle the check

 if (turnTimer > 50) 
 state = 3;
 System.out.println("Max Turns reached, game ending.");
 
 

 // declare winner
 if (state == 1) 
 System.out.println(p1.getName() + " Won!");
 return 1;
 else if (state == 2) 
 System.out.println(p2.getName() + " Won!");
 return 2;
 else 
 System.out.println("Draw");
 return 3;
 

 

 public static void main(String[] args) 
 System.out.println("+++++++++++++++++++++++");
 System.out.println(p1.getName() + " VS " + p2.getName());
 System.out.println("+++++++++++++++++++++++" + "n");

 System.out.println("How Many Games?");
 Scanner s = new Scanner(System.in);
 int numGames = s.nextInt();
 System.out.println("BEGINn");

 int p1Victories = 0;
 int p2Victories = 0;
 int ties = 0;
 int curWinner = 0;
 for (int i = 0; i < numGames; i++) 
 curWinner = playGame();
 if (curWinner == 1) 
 p1Victories++;
 else if (curWinner == 2) 
 p2Victories++;
 else 
 ties++;
 

 // resets the board before the next game is played
 game.resetBoard();
 

 System.out.println("n++++++++++++");
 System.out.println("FINAL TALLY");
 System.out.println("++++++++++++");
 System.out.println(p1.getName() + " Won " + p1Victories + " Games!");
 System.out.println(p2.getName() + " Won " + p2Victories + " Games!");
 System.out.println("There were " + ties + " Tie Games!");
 s.close();

 

TicTacToe.java

/* This is the main class that contains code for the game
 *
 * Empty space will be represented by a 0
 * X's will be represented by a 1
 * O's will be represented by a 2
 * Anything higher (3+) or lower (-1-) should not be added to the board 
 */

public class TicTacToe 

 private int[][] board; //the TicTacToe board, private to avoid cheating


 public TicTacToe() 
 board = new int[3][3];
 

 //given a row and column, determine if placing a piece there is valid
 //the space must be within the bounds of the board, AND empty
 //return true if it is a legal move, false if illegal
 private boolean isLegalMove(int row, int column) column >= 3) 
 return false;
 
 if (board[row][column] != 0) 
 return false;
 
 return true;
 

 //this method will place a game piece (X or 0) at the row/column
 //piece will be 1 for an X, 2 for an O
 //*IMPORTANT* make sure the move is legal first, don't trust the AI to submit a valid move
 //moves are submitted as a length 2 integer array, first number is the row, second is the column
 public void placePiece(int[] move, int piece) 
 //if a null move is submitted, exit skipping the player's turn
 if (move == null) 
 System.out.println("Illegal Move Attempted");
 return;
 
 int row = move[0];
 int column = move[1];
 if (isLegalMove(row, column)) 
 board[row][column] = piece;
 
 else 
 System.out.println("Illegal Move Attempted");
 
 


 //print out the current board state so the humans can read it
 public void printBoard() 
 int current = 0;
 for (int i = 0; i < 3; i ++) ");
 for (int j = 0; j < 3; j++) 
 current = board[i][j];
 if (current == 0) 
 System.out.print(" " + " 
 else if (current == 1) ");
 
 else if (current == 2) ");
 
 
 System.out.println();

 
 

 //examines the current board and determines if the game is over
 //returns 0 if the game is still going
 //returns 1 if X player wins
 //returns 2 if O player wins
 //returns 3 if the game is a tie
 public int gameOver() 

 for (int i = 0; i < 3; i++) 

 //if no player has 3 in a row, check for tie
 for (int i = 0; i < 3; i ++) 
 for (int j = 0; j < 3; j++) 
 if (board[i][j] == 0) 
 return 0; //there is an empty space on the board, game is still going.

 //Yes I know sometimes draws are inevitable even if there are squares
 //left, but that is outside the scope of this challenge.
 
 
 

 //The game has tied
 return 3;
 

 //returns the number of spaces a given player occupies in a given row
 //row is the row to check, 0 = first, 1 = second, 2 = third
 //player will be 1 for X player 2 for O player
 public int getRowCount(int row, int player) 
 int counter = 0;
 for (int i = 0; i < 3; i++) 
 if (board[row][i] == player) 
 counter++;
 
 

 return counter;
 

 //same as getRowCount but for columns
 public int getColumnCount(int column, int player) 
 int counter = 0;
 for (int i = 0; i < 3; i++) 
 if (board[i][column] == player) 
 counter++;
 
 

 return counter;
 

 //checks if the given player has 3 in a row diagonal
 public boolean getDiagonal(int player) 
 //left to right diagonal
 if (board[0][0] == player && board[1][1] == player && board [2][2] == player) 
 return true;
 
 //right to left diagonal
 if (board[0][2] == player && board[1][1] == player && board [2][0] == player) 
 return true;
 
 return false;
 

 //returns a COPY of the current board for the AI's to read
 //This prevents AI's from having direct access to the board, to cheat for example
 public int[][] getBoard() 
 int[][] boardCopy = new int[3][3];
 for (int i = 0; i < board.length; i++) 
 for (int j = 0; j < board[0].length; j++) 
 boardCopy[i][j] = board[i][j];
 
 
 return boardCopy;
 

 //resets the board to all 0s (empty)
 public void resetBoard() 
 for(int i = 0; i < board.length; i++) 
 for (int j = 0; j < board[0].length; j++) 
 board[i][j] = 0;
 
 
 

TicTacToePlayer.java

//Defines general behavior of all players (AI and Human)
public abstract class TicTacToePlayer 
 private String name; //Player's name
 private int piece; //Piece type, 1 = X, 2 = O

 public TicTacToePlayer(String aName, int aPiece) 
 name = aName;
 piece = aPiece;
 

 public String getName() 
 return name;
 

 public int getPiece() 
 return piece;
 

 //All players must be able to play a turn 
 public abstract int[] playTurn();