0 votes
1 view
in AI and Deep Learning by (19k points)

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.

1 Answer

0 votes
by (42.1k points)

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 it ... but try profiling it by following the directions here vrplumber.com/programming/runsnakerun to see if you can identify the bottlenecks.