Alpha-Beta Troubles

alpha-beta-trouble.js

function rootSearch (root, game, depth) {
    var alpha = -Infinity;
    var beta = Infinity;
    var moves = getMoves(root, game); // Array[Object{player: number, game: number}, ...]
    var nodeScore;
    var bestMove;

    for (var i = 0, l = moves.length; i < l; i++) {
	nodeScore = alphaBeta(moves[i].player, moves[i].game, depth,
			      alpha, beta, true);

	if (nodeScore > alpha) {
	    alpha = nodeScore;
	    bestMove = moves[i].player;
	}
    }
    return bestMove;
}

function alphaBeta (root, game, depth, alpha, beta, maximizer) {
    if (depth < 1) {
	return score(root, game, maximizer);
    }

    var branches = getMoves(root, game);
    var branch;
    var nextGame;
    var nextNode;
    var nodeScore;
    var rootValue = maximizer ? -Infinity : +Infinity;

    if (branches.length === 0) { // Winning/Losing states are leaf nodes
	return maximizer ? 7 : -7;
    }

    while (branch = branches.pop()) {
	nextGame = branch.game; // Board state
	nextNode = branch.player ^ branch.game; // i.e., opponent
	nodeScore = alphaBeta(nextNode, nextGame, depth - 1,
			      alpha, beta, !maximizer);

	if (maximizer) {
	    rootValue = Math.max(rootValue, nodeScore);
	    alpha = Math.max(rootValue, alpha);
	    if (alpha >= beta) {
		return alpha;
	    }
	} else if (!maximizer) {
	    rootValue = Math.min(rootValue, nodeScore);
	    beta = Math.min(rootValue, beta);
	    if (alpha >= beta) {
		return beta;
	    }
	}
    }

    return rootValue;
}