Expectimax Algorithm for 2048 Not Performing Expectation as Intended?
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.
链接地址: http://www.djcxy.com/p/40194.html上一篇: 什么是算法来解决这个问题？