1

I wrote an Expectimax solver for 2048 using the heuristics noted on the top ranking SO post "Optimal AI for 2048".

However, my expectimax algorithm performs maximization correctly but when it hits the expectation loop where it should be simulating all of the possible tile spawns for a move (90% 2, 10% 4) - it does not seem to function as intended.

game2048.prototype.ai = function (theState, depth, playerOne, alpha) {
    var state = this.clone(theState); 
    var moves = this.validMoves(state);

if (moves.length == 0) { // avoid game losing states
    return Number.MIN_VALUE;
}
if (depth == 0) { // base case.
    return this.utility(state);
}

if (playerOne) {
    for (var i = 0; i < moves.length; i++) {
        state.move(moves[i]); // check child state
        var temp = this.ai(state, depth - 1, false, alpha); // find the maximum utility for depth given
        if (alpha > temp) {
            break; // prune the children that we won't choose.
        } 
        alpha = Math.max(temp, alpha);
        state.reset();
    }
    return alpha;
} else { // perform expectation 
    var avg = 0;
    for (var i = 0; i < moves.length; i++) {
        state.addRandomTile();
        state.move(moves[i]);
        avg += this.ai(state, depth - 1, true, alpha);
        state.reset();
    } return avg / moves.length;
}
}

Any ideas on how I could be incorporating expectation incorrectly into this algorithm?

It SHOULD somehow be calculating all possible tile spawns and returning score of an average of all the simulated spawns.

Community
  • 1
  • 1
user3098364
  • 63
  • 1
  • 5
  • 1
    Without you showing `addRandomTile()`, in particular, or describing your intentions and observations? – greybeard Nov 21 '15 at 21:28
  • addRandomTile() just adds a single tile of value 4 or 2 (90% 2, 10% 4) to an open spot on the game board. My goal is to calculate the value of the game board at every simulated tile spawn and return the average. – user3098364 Nov 21 '15 at 23:17

0 Answers0