I've been trying to learn MiniMax through using TicTacToe as it seems like that is one of the most used examples out there. I'm starting off without pruning to try and get the hang of it. I have 2 AIs playing against each other but X always wins. I think the problem is that they are not playing defensively and I'm not quite sure how to implement that. Below is the code, I also have some other class files but I don't think they're needed unless it is requested. Thanks very much.
import java.util.*;
public class TicTacToe {
GameState gameState; // Current game state
int totalNodesExpanded; // Total number of nodes expanded in
// search so far
int levelNodesExpanded; // Number of nodes expanded to explore this
// level of the tree (i.e. all
// non-pruned successors of the current
// state)
public TicTacToe() {
gameState = new GameState();
ArrayList<Coordinate> moves = new ArrayList<Coordinate>();
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
moves.add(new Coordinate(i,j));
}
}
gameState.player = "X";
gameState.moves = moves;
totalNodesExpanded = 0;
levelNodesExpanded = 0;
}
/*
* Return a list of the states reachable in one move from the
* current state.
*/
public ArrayList getSuccessorStates(GameState state) {
ArrayList<GameState> result = new ArrayList<GameState>();
for (int i = 0; i < state.moves.size(); i++) {
Coordinate c = (Coordinate) state.moves.get(i);
GameState s = makeMove(state, c);
s.moveMade = c;
result.add(s);
}
return result;
}
/*
* Perform a move to "c" from the given "state" (checking that the
* move is valid in the current state)
*/
public GameState makeMove(GameState state, Coordinate c) {
GameState result = null;
ArrayList newMoves = (ArrayList) state.moves.clone();
if (newMoves.contains(c)) {
newMoves.remove(c);
result = new GameState();
result.moves = newMoves;
TicTacToeBoard newBoard = (TicTacToeBoard) state.board.clone();
if (state.player.equals("X")) {
newBoard.markX(c.x, c.y);
result.player = "O";
} else {
newBoard.markO(c.x, c.y);
result.player = "X";
}
result.board = newBoard;
} else {
System.out.println("ERROR: attempt to make invalid move");
}
return result;
}
/*
* Make the next move, determined using minimax.
* Print out information about the search progression.
*/
public void makeMiniMaxMove() {
totalNodesExpanded += levelNodesExpanded;
levelNodesExpanded = 0;
GameState state = gameState;
ArrayList<GameState> states = getSuccessorStates(state);
int best = 0;
int temp = 0;
for (GameState s : states) {
if (state.player.equals("X")) {
best = -1;
temp = min(s);
if (temp > best) {
best = temp;
gameState.next = s;
}
if (best == 1)
break;
}
else {
best = 1;
temp = max(s);
if (temp < best) {
best = temp;
gameState.next = s;
}
if (best == -1)
break;
}
}
GameState nextState = gameState.next;
System.out.println("Nodes considered: " + levelNodesExpanded);
System.out.println("Move chosen: " + nextState.moveMade);
gameState = makeMove(gameState, nextState.moveMade);
}
private int max(GameState state) {
if (state.board.lineExists() && state.player.equals("X"))
return 1;
else if (state.board.boardFull() == true)
return 0;
else if (state.board.lineExists() && !state.player.equals("X"))
return -1;
levelNodesExpanded++;
ArrayList<GameState> states = getSuccessorStates(state);
int best = -1;
for (GameState s : states) {
int temp = min(s);
if (temp > best) {
best = temp;
gameState.next = s;
}
if (best == 1)
break;
}
return best;
}
private int min(GameState state) {
if (state.board.lineExists() && state.player.equals("O"))
return -1;
else if (state.board.boardFull() == true)
return 0;
else if (state.board.lineExists() && !state.player.equals("O"))
return 1;
levelNodesExpanded++;
ArrayList<GameState> states = getSuccessorStates(state);
int best = 1;
for (GameState s : states) {
int temp = max(s);
if (temp < best) {
best = temp;
gameState.next = s;
}
if (best == -1)
break;
}
return best;
}
public static void main(String[] args) {
TicTacToe board1 = new TicTacToe();
System.out.println("board:\n" + board1.gameState.board + "\n");
while (!(board1.gameState.board.lineExists() ||
board1.gameState.board.boardFull())) {
System.out.println("Current player: " + board1.gameState.player);
System.out.println("Possible moves: " + board1.gameState.moves);
board1.makeMiniMaxMove();
System.out.println("board:\n" + board1.gameState.board + "\n");
}
System.out.println("Total nodes expanded: "
+ board1.totalNodesExpanded);
System.out.println("\n\n\n");
}
}