Problems with Alpha Beta for 2048

Question

I'm writing an AI for the game 2048 using Python. It's going a lot slower than I expected. I set the depth limit to just 5 and it still took several seconds to get an answer. At first, I thought my implementations of all the functions were crap, but I figured out the real reason why. There are way more leaves on the search tree than there even possibly should be.

Here is a typical result (I counted the leaves, branches, and number of expansions):

111640 leaves, 543296 branches, 120936 expansions

Branching factor: 4.49242574585

Expected max leaves = 4.49242574585^5 = 1829.80385192 leaves

and another, for good measure:

99072 leaves, 488876 branches, 107292 expansions

Branching factor: 4.55650001864

Expected max leaves = 4.55650001864^5 = 1964.06963743 leaves

As you can see, there are way more leaves on the search tree than how many there would be if I used naive minimax. What is going on here? My algorithm is posted below:

# Generate constants

import sys

posInfinity = sys.float_info.max

negInfinity = -sys.float_info.max

# Returns the direction of the best move given current state and depth limit

def bestMove(grid, depthLimit):

    global limit

    limit = depthLimit

    moveValues = {}

    # Match each move to its minimax value

    for move in Utils2048.validMoves(grid):

        gridCopy = [row[:] for row in grid]

        Utils2048.slide(gridCopy, move)

        moveValues[move] = minValue(grid, negInfinity, posInfinity, 1)

    # Return move that have maximum value

    return max(moveValues, key = moveValues.get)

# Returns the maximum utility when the player moves

def maxValue(grid, a, b, depth):

    successors = Utils2048.maxSuccessors(grid)

    if len(successors) == 0 or limit < depth:

        return Evaluator.evaluate(grid)

    value = negInfinity

    for successor in successors:

        value = max(value, minValue(successor, a, b, depth + 1))

        if value >= b:

            return value

        a = max(a, value)

    return value

# Returns the minimum utility when the computer moves

def minValue(grid, a, b, depth):

    successors = Utils2048.minSuccessors(grid)

    if len(successors) == 0 or limit < depth:

        return Evaluator.evaluate(grid)

    value = posInfinity

    for successor in successors:

        value = min(value, maxValue(successor, a, b, depth + 1))

        if value <= a:

            return value

        b = min(b, value)

    return value

Someone, please help me out. I looked over this code several times and I can't pin down what's wrong.

Answer 1

Here is a paper that discusses the game, maybe it could be useful: cs.put.poznan.pl/mszubert/pub/szubert2014cig.pdf.

You need to provide an example call to itvrplumber.com/programming/runsnakerun to see if you can identify the bottlenecks. ... but try profiling it by following the directions here

If you want to learn both Python and Artificial Intelligence then visit this Artificial Intelligence Master Training Course.