1

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");
    }
}
Kevin Lee
  • 1,104
  • 3
  • 13
  • 33
  • 1
    possible duplicate of [How do I compare strings in Java?](http://stackoverflow.com/questions/513832/how-do-i-compare-strings-in-java) – jlordo Apr 23 '13 at 16:38
  • @jlordo: +1. But I think without more details the OP might get confused... @Kevin: Have a look at this (and similar) lines in your code: `if (state.player == "X") {` – Axel Apr 23 '13 at 16:45
  • Oh yeah of course. That was a silly mistake. However, X still wins after I've changed it. – Kevin Lee Apr 23 '13 at 17:13
  • `== true` is redundant, e.g. you can just replace `state.board.lineExists() == true` with `state.board.lineExists()`. – Bernhard Barker Apr 24 '13 at 08:01
  • Wikipedia has a helpful article (with pseudocode) on the minimax algorithm. If you implement that correctly, you should just need to check if the game is over and implement the appropriate score. – Jared Nielsen Apr 29 '13 at 16:18
  • Just briefly looked over the code. I wasn't clear how deep you are recursing, you should be explore at least a few levels deep, if not the whole tree. Also, I am pretty sure that if player 1 plays a perfect game then player 2 can only hope for a tie so player 2 should have a non-zero valuation for a tie, maybe .5 or .7 - you'll have to tune that. – Toaster May 30 '13 at 11:10

0 Answers0