I'm currently trying to teach myself the Minimax algorithm, and I tried to implement it in java in tic tac toe. However, there is an error in my algorithm, and I cannot figure out what causes it.
Below is the full source code (Sorry for the text wall!):
public class TicTacToe { private static boolean gameEnded = false; private static boolean player = true; private static Scanner in = new Scanner(System.in); private static Board board = new Board(); public static void main(String[] args){ System.out.println(board); while(!gameEnded){ Position position = null; if(player){ position = makeMove(); board = new Board(board, position, PlayerSign.Cross); }else{ board = findBestMove(board); } player = !player; System.out.println(board); evaluateGame(); } } private static Board findBestMove(Board board) { ArrayList<Position> positions = board.getFreePositions(); Board bestChild = null; int previous = Integer.MIN_VALUE; for(Position p : positions){ Board child = new Board(board, p, PlayerSign.Circle); int current = max(child); System.out.println("Child Score: " + current); if(current > previous){ bestChild = child; previous = current; } } return bestChild; } public static int max(Board board){ GameState gameState = board.getGameState(); if(gameState == GameState.CircleWin) return 1; else if(gameState == GameState.CrossWin) return -1; else if(gameState == GameState.Draw) return 0; ArrayList<Position> positions = board.getFreePositions(); int best = Integer.MIN_VALUE; for(Position p : positions){ Board b = new Board(board, p, PlayerSign.Cross); int move = min(b); if(move > best) best = move; } return best; } public static int min(Board board){ GameState gameState = board.getGameState(); if(gameState == GameState.CircleWin) return 1; else if(gameState == GameState.CrossWin) return -1; else if(gameState == GameState.Draw) return 0; ArrayList<Position> positions = board.getFreePositions(); int best = Integer.MAX_VALUE; for(Position p : positions){ Board b = new Board(board, p, PlayerSign.Circle); int move = max(b); if(move < best) best = move; } return best; } public static void evaluateGame(){ GameState gameState = board.getGameState(); gameEnded = true; switch(gameState){ case CrossWin : System.out.println("Game Over! Cross Won!"); break; case CircleWin : System.out.println("Game Over! Circle Won!"); break; case Draw : System.out.println("Game Over! Game Drawn!"); break; default : gameEnded = false; break; } } public static Position makeMove(){ Position position = null; while(true){ System.out.print("Select column(x-axis). 0, 1 or 2: "); int column = getColOrRow(); System.out.print("Select row(y-axis). 0, 1 or 2: "); int row = getColOrRow(); position = new Position(column, row); if(board.isMarked(position)) System.out.println("Position already marked!"); else break; } return position; } private static int getColOrRow(){ int ret = -1; while(true){ try{ ret = Integer.parseInt(in.nextLine()); } catch (NumberFormatException e){} if(ret < 0 | ret > 2) System.out.print("\nIllegal input... please re-enter: "); else break; } return ret; } } public enum PlayerSign{ Cross, Circle } public enum GameState { Incomplete, CrossWin, CircleWin, Draw } public final class Position { public final int column; public final int row; public Position(int column, int row){ this.column = column; this.row = row; } } public class Board { private char[][] board;
Here is the result when I run the program (Computer is circle):
[ ][ ][ ] [ ][ ][ ] [ ][ ][ ] Select column(x-axis). 0, 1 or 2: 1 Select row(y-axis). 0, 1 or 2: 1 [ ][ ][ ] [ ][x][ ] [ ][ ][ ] Child Score: 0 Child Score: 0 Child Score: 0 Child Score: 0 Child Score: 0 Child Score: 0 Child Score: 0 Child Score: 0 [o][ ][ ] [ ][x][ ] [ ][ ][ ] Select column(x-axis). 0, 1 or 2: 0 Select row(y-axis). 0, 1 or 2: 1 [o][ ][ ] [x][x][ ] [ ][ ][ ] Child Score: -1 Child Score: 0 Child Score: 0 Child Score: -1 Child Score: -1 Child Score: -1 [o][ ][o] [x][x][ ] [ ][ ][ ] Select column(x-axis). 0, 1 or 2:
As you can see after the first move, the computer thinks that no matter what step it takes, it can get a draw (Score = 0).
In the second move, I put a cross on column 0, row 1. For some reason, the computer then thinks that there are two possible steps to achieve a draw (Score = 0) and only four moves to play (Score = -1). Then he makes the wrong move, thinking that he will get a draw.
At first, I thought that something was wrong with the hasWon method, but I checked all 8 ways to get three lines, and they are all correct.
I suspect that the problem exists somewhere in the findBestMove, max or min methods, but I could not pinpoint what caused it.
I would really appreciate it if someone could say what is causing the error, or give any suggestions on how best to debug my recursive algorithm.