// A domain independant base class for the MiniMax search. Derived class must 
// overwrite domain dependant implementations of the base class methods.
class MiniMax {

    static EMPTY = 0;   // To mark an empty spot on the map.
    static PLAYER1 = 1; // To mark a spot taken on map by first player.
    static PLAYER2 = 2; // To mark a spot taken by second player.

    static WIN = 10;    // The utility value for a winning state.
    static LOSS = -10;  // The utility value for a losing state.

    // The constructor initializes the state of the game with the given map, turn,
    // maximizer, and index. It also initializes the properties that will be
    // calculated during the MiniMax search.
    constructor(map, turn = MiniMax.PLAYER1,
        maximizer = MiniMax.PLAYER1, index = -1) {

        this.map = map;             // The current state of the game map.
        this.turn = turn;           // The player whose turn it is.
        this.maximizer = maximizer; // The player that is trying to maximize.
        this.index = index;         // Optional information about the move.

        // The following properties are calculated during the MiniMax search 
        // and are not part of the initial state.
        this.next = [];     // All possible next moves.
        this.utility = 0;   // The utility value of the state.
    }

    // Enforced interface method that creates a new instance of the class with 
    // a new map, turn, maximizer, and index parameters.
    makeNewInstance(map, turn, maximizer, index) {
        throw new Error("Method 'makeNewInstance()' must be implemented.");
    }

    // Enforced interface method that returns true if the map has a winning 
    // configuration for the player.
    isWinner(player) {
        throw new Error("Method 'isWinner()' must be implemented.");
    }

    // Enforced interface method that returns true if the state is a drawn
    // configuration (nobody wins).
    isDraw() {
        throw new Error("Method 'isDraw()' must be implemented.");
    }

    // Enforced interface method that recalculate all possible moves from the 
    // current state without evaluation of the utility.
    setNextMoves() {
        throw new Error("Method 'setNextMoves()' must be implemented.");
    }

    // The main method that runs the MiniMax search algorithm. It calculates the 
    // utility value of the current state and populates the next array with all 
    // possible moves from the current state. It also recursively calls run() on
    // the next states moves from the current state. It also recursively calls 
    // run() on the next states to calculate their utility values and determine 
    // the best move for the maximizer.
    run() {
        this.next = [];

        // Check the terminal states and return the utility value.
        if (this.isWinner(MiniMax.PLAYER1)) {
            this.utility = (this.maximizer == MiniMax.PLAYER1 ? MiniMax.WIN : MiniMax.LOSS);
            return;
        }
        if (this.isWinner(MiniMax.PLAYER2)) {
            this.utility = (this.maximizer == MiniMax.PLAYER2 ? MiniMax.WIN : MiniMax.LOSS);
            return;
        }
        if (this.isDraw()) {
            this.utility = 0;
            return;
        }

        // Get all possible moves from this state.
        this.setNextMoves();

        // Initialize best_utility with worst to find the best during 
        // the following search.
        let best_utility = (this.turn == this.maximizer) ? -Infinity : Infinity;

        // Loop through available next states.
        for (let next of this.next) {

            // Running MiniMax recursively for each successor state.
            next.run();

            // Save the move with the currently highest utility for maximizer or
            // lowest for minimizer.
            if ((this.turn == this.maximizer && next.utility > best_utility) ||
                (this.turn != this.maximizer && next.utility < best_utility))
                best_utility = next.utility;
        }

        this.utility = best_utility;
    }

    // Get the best move among the shortest best moves. If randomize is true, 
    // it will shuffle the best moves before selecting the first one among them.
    getBest(randomize = false) {
        if (this.next.length) {
            let allbest = this.next.filter(node => node.utility == this.utility);
            if (randomize)
                allbest = shuffleArray(allbest);
            let sorted = allbest.sort((a, b) => a.next.length - b.next.length);
            return sorted[0];
        }
        return null;
    }

    // Serialization method to turn this state object into a string for 
    // debugging or display purposes.
    toString() {
        let os = 'Map: ' + this.map.toString() + '\n' +
            'Index: ' + this.index + '. ' +
            'Turn: player ' + this.turn + '. ' +
            'Maximizer: player ' + this.maximizer + '. ' +
            'Utility: ' + this.utility + '. ' +
            '# of moves: ' + this.next.length;
        return os;
    }
}