Java Minimax Tic-Tac-Toe
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}
0
$begingroup$
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) {
if (row < 0 || row >= 3) {
return false;
}
if (column < 0 || 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 ++) {
System.out.print("| ");
for (int j = 0; j < 3; j++) {
current = board[i][j];
if (current == 0) {
System.out.print(" " + " | ");
}
else if (current == 1) {
System.out.print("X" + " | ");
}
else if (current == 2) {
System.out.print("O" + " | ");
}
}
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++) {
//check if X player has 3 in a row anywhere
if (getRowCount(i, 1) == 3 || getColumnCount(i, 1) == 3 || getDiagonal(1)) {
return 1; //X player won
}
//check if O player has 3 in a row anywhere
if (getRowCount(i, 2) == 3 || getColumnCount(i, 2) == 3 || getDiagonal(2)) {
return 2; //O player won
}
}
//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();
}
java tic-tac-toe ai
asked 15 mins ago
simplicialsimplicial
1
New contributor
simplicial is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
0
$begingroup$
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) {
if (row < 0 || row >= 3) {
return false;
}
if (column < 0 || 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 ++) {
System.out.print("| ");
for (int j = 0; j < 3; j++) {
current = board[i][j];
if (current == 0) {
System.out.print(" " + " | ");
}
else if (current == 1) {
System.out.print("X" + " | ");
}
else if (current == 2) {
System.out.print("O" + " | ");
}
}
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++) {
//check if X player has 3 in a row anywhere
if (getRowCount(i, 1) == 3 || getColumnCount(i, 1) == 3 || getDiagonal(1)) {
return 1; //X player won
}
//check if O player has 3 in a row anywhere
if (getRowCount(i, 2) == 3 || getColumnCount(i, 2) == 3 || getDiagonal(2)) {
return 2; //O player won
}
}
//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();
}
java tic-tac-toe ai
asked 15 mins ago
simplicialsimplicial
1
New contributor
simplicial is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
0
0
0
$begingroup$
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) {
if (row < 0 || row >= 3) {
return false;
}
if (column < 0 || 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 ++) {
System.out.print("| ");
for (int j = 0; j < 3; j++) {
current = board[i][j];
if (current == 0) {
System.out.print(" " + " | ");
}
else if (current == 1) {
System.out.print("X" + " | ");
}
else if (current == 2) {
System.out.print("O" + " | ");
}
}
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++) {
//check if X player has 3 in a row anywhere
if (getRowCount(i, 1) == 3 || getColumnCount(i, 1) == 3 || getDiagonal(1)) {
return 1; //X player won
}
//check if O player has 3 in a row anywhere
if (getRowCount(i, 2) == 3 || getColumnCount(i, 2) == 3 || getDiagonal(2)) {
return 2; //O player won
}
}
//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();
}
java tic-tac-toe ai
asked 15 mins ago
simplicialsimplicial
1
New contributor
simplicial is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
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) {
if (row < 0 || row >= 3) {
return false;
}
if (column < 0 || 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 ++) {
System.out.print("| ");
for (int j = 0; j < 3; j++) {
current = board[i][j];
if (current == 0) {
System.out.print(" " + " | ");
}
else if (current == 1) {
System.out.print("X" + " | ");
}
else if (current == 2) {
System.out.print("O" + " | ");
}
}
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++) {
//check if X player has 3 in a row anywhere
if (getRowCount(i, 1) == 3 || getColumnCount(i, 1) == 3 || getDiagonal(1)) {
return 1; //X player won
}
//check if O player has 3 in a row anywhere
if (getRowCount(i, 2) == 3 || getColumnCount(i, 2) == 3 || getDiagonal(2)) {
return 2; //O player won
}
}
//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();
}
java tic-tac-toe ai
java tic-tac-toe ai
asked 15 mins ago
simplicialsimplicial
1
New contributor
simplicial is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 15 mins ago
simplicialsimplicial
1
New contributor
simplicial is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 15 mins ago
simplicialsimplicial
1
New contributor
simplicial is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 15 mins ago
simplicialsimplicial
1
asked 15 mins ago
simplicialsimplicial
1
1
New contributor
simplicial is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
simplicial is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
simplicial is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
simplicial is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217463%2fjava-minimax-tic-tac-toe%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
simplicial is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
simplicial is a new contributor. Be nice, and check out our Code of Conduct.
simplicial is a new contributor. Be nice, and check out our Code of Conduct.
simplicial is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217463%2fjava-minimax-tic-tac-toe%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
