3
\$\begingroup\$

So I programmed 2048 in python3 and a simple solver, which will just target a high numbers on the board (not the best tactic, I know), but I have the problem, that this move calculation is painfully slow. Any ideas on how to speed this up are appreciated. (The logic should be fine)

from enum import Enum
from typing import List, Tuple


class MoveDirection(Enum):
    UP = (0, -1)
    DOWN = (0, 1)
    LEFT = (-1, 0)
    RIGHT = (1, 0)


BoardType = List[List[int]]
Pos = Size = Tuple[int, int]
Move = Tuple[Pos, Pos, bool]


def move(board: BoardType, direction: MoveDirection) -> Tuple[BoardType, BoardType, List[Move]]:
    old, board = board, [c[:] for c in board]
    size = len(board), len(board[0])
    already_merged = []
    moves = []
    if direction == MoveDirection.UP:
        for x in range(size[0]):
            for y in range(1, size[1]):
                v = board[x][y]
                if v == 0:
                    continue
                board[x][y] = 0
                for ny in reversed(range(0, y)):
                    if board[x][ny] == v and (x, ny) not in already_merged:
                        board[x][ny] = v + 1
                        already_merged.append((x, ny))
                        moves.append(((x, y), (x, ny), True))
                        break
                    elif board[x][ny] != 0:
                        board[x][ny + 1] = v
                        if ny + 1 != y:
                            moves.append(((x, y), (x, ny + 1), False))
                        break
                else:
                    board[x][0] = v
                    moves.append(((x, y), (x, 0), False))
    elif direction == MoveDirection.DOWN:
        for x in range(size[0]):
            for y in reversed(range(size[1] - 1)):
                v = board[x][y]
                if v == 0:
                    continue
                board[x][y] = 0
                for ny in range(y + 1, size[1]):
                    if board[x][ny] == v and (x, ny) not in already_merged:
                        board[x][ny] = v + 1
                        already_merged.append((x, ny))
                        moves.append(((x, y), (x, ny), True))
                        break
                    elif board[x][ny] != 0:
                        board[x][ny - 1] = v
                        if ny - 1 != y:
                            moves.append(((x, y), (x, ny - 1), False))
                        break
                else:
                    board[x][-1] = v
                    moves.append(((x, y), (x, size[1] - 1), False))
    elif direction == MoveDirection.LEFT:
        for y in range(size[1]):
            for x in range(1, size[0]):
                v = board[x][y]
                if v == 0 or x == 0:
                    continue
                board[x][y] = 0
                for nx in reversed(range(0, x)):
                    if board[nx][y] == v and (nx, y) not in already_merged:
                        board[nx][y] = v + 1
                        already_merged.append((nx, y))
                        moves.append(((x, y), (nx, y), True))
                        break
                    elif board[nx][y] != 0:
                        board[nx + 1][y] = v
                        if nx + 1 != x:
                            moves.append(((x, y), (nx + 1, y), False))
                        break
                else:
                    board[0][y] = v
                    moves.append(((x, y), (0, y), False))
    elif direction == MoveDirection.RIGHT:
        for y in range(size[1]):
            for x in reversed(range(size[0] - 1)):
                v = board[x][y]
                if v == 0:
                    continue
                board[x][y] = 0
                for nx in range(x + 1, size[0]):
                    if board[nx][y] == v and (nx, y) not in already_merged:
                        board[nx][y] = v + 1
                        already_merged.append((nx, y))
                        moves.append(((x, y), (nx, y), True))
                        break
                    elif board[nx][y] != 0:
                        board[nx - 1][y] = v
                        if nx - 1 != x:
                            moves.append(((x, y), (nx - 1, y), False))
                        break
                else:
                    board[-1][y] = v
                    moves.append(((x, y), (size[0] - 1, y), False))
    else:
        raise ValueError()
    return old, board, moves

The code in context and with a pygame visualization can be seen here: https://github.com/MegaIng1/2048)

\$\endgroup\$

2 Answers 2

5
\$\begingroup\$

1. Review

  1. There are no docstrings. What does move do? What does it return?

  2. move always returns its first argument as the first element of the returned tuple. This seems pointless since the caller obviously has the argument in hand at the point where move is called.

  3. When raising an exception, it's a good idea to write a message explaining what went wrong. In this case, something like:

    raise ValueError(f"expected a direction but got {direction!r}")
    
  4. The body of move consists of four copies of the movement logic, one for each direction. There are at least three reasons to avoid this kind of repetition:

    (i) it increases the bulk of code and so makes it more time-consuming to read and understand;

    (ii) it makes it harder to change because you have to make corresponding edits to all four copies;

    (iii) it runs the risk of introducing a bug that only affects one of the copies, making it less likely to be discovered in testing.

    The easiest way to merge these four copies is to change the board representation. Instead of representing the board as a list of \$n\$ lists of \$n\$ tile values, represent it as a single list of \$n×n\$ tiles, for example in the \$4×4\$ case you could index the board like this:

    The advantage of this representation is that the indexes for each row and each column (whichever direction it is traversed) form an arithmetic progression, which can be represented by a range object. For example, to go right along the 2nd row we need the indexes 4, 5, 6, and 7, which can be represented by range(4, 8), and to ascend the 3rd column we need the indexes 14, 10, 6, and 2, which can be represented by reversed(range(2, 16, 4)).

    Note that this representation simplifies some of the other code: we only need one indexing operation on each lookup, not two, and copying the board is easier.

  5. Multiple merges are prevented by adding coordinates to the list already_merged. There are three problems with this:

    (i) Python lists do not have an efficient membership test, so that (x, ny) not in already_merged has to potentially compare against every element in the list. It would be more efficient to use a set.

    (ii) Tiles can only merge with tiles on the same row (if moving horizontally) or column (if moving vertically) and so there is no need to keep a set of the coordinates of all merged tiles, just the ones on the current row (or column), for example:

    if direction == MoveDirection.UP:
        for x in range(size[0]):
            already_merged = set()
            # ...
    

    (iii) In fact we only care whether one tile has merged, namely the last tile to move on the current row or column. So with some refactoring it ought to be possible to remember the merge status using a single boolean. See below for how this could be done.

  6. The move logic has three nested loops, for example in the "moving up" case:

    for x in range(size[0]):
        for y in range(1, size[1]):
            # ...
            for ny in reversed(range(0, y)):
    

    This means that if the board is \$n×n\$, the algorithm runs in time \$O(n^3)\$. But if you think about how you would implement this by hand, you'd have two indexes, one representing how far you'd visited in the old row or column, the other representing how far you'd packed in the new row or column. For example, in the "moving left" case you'd start like this (note that the new board starts out empty):

    and then after visiting the first two tiles (and packing one onto the new row), the situation looks like this:

    and at the end of the row you've visited all four tiles and packed two:

    This approach would reduce the complexity of the algorithm to \$O(n^2)\$.

2. Revised code

# Map from direction to function taking (i, n) and returning an
# iterable of indexes for the i'th row or column in the given
# direction on a board of side n.
INDEXES = {
    MoveDirection.UP: (lambda i, n: range(i, n ** 2, n)),
    MoveDirection.DOWN: (lambda i, n: reversed(range(i, n ** 2, n))),
    MoveDirection.LEFT: (lambda i, n: range(i * n, (i + 1) * n)),
    MoveDirection.RIGHT: (lambda i, n: reversed(range(i * n, (i + 1) * n))),
}

def move(old_board, n, direction):
    """Move tiles in the indicated direction.

    Arguments:
    old_board -- game board before the move
    n -- side of square board
    direction -- direction to move

    Returns:
    new_board -- game board after the move
    moves -- list of tuples (from, to, merged) giving the indexes of
       tiles that moved and whether they merged as a result

    """
    new_board = [0] * n ** 2
    moves = []
    for i in range(n):
        indexes = INDEXES[direction](i, n) # indexes of i'th row or column
        new_indexes = iter(indexes)        # corresponding indexes in new board
        k = next(new_indexes)              # target index in new board
        merged = False                     # new_board[k] merged already?
        for j in indexes:
            moving = old_board[j]
            if moving:
                if not merged and moving == new_board[k]:
                    new_board[k] += 1
                    merged = True
                else:
                    if new_board[k]:
                        k = next(new_indexes)
                    new_board[k] = moving
                    merged = False
                if j != k:
                    moves.append((j, k, merged))
    return new_board, moves

Note that this is just a sketch to indicate the approach that I have in mind. In the real program, n is going to be constant for the duration of a game, and so you could generate all the indexing ranges once at the start of the game instead of providing functions to generate them as above.

\$\endgroup\$
1
\$\begingroup\$

As stated by Gareth Rees, you need to reuse as much as the moving parts as possible. I do however not agree with his approach of flattening the board. Here is an alternative approach

You need to split up the code in more parts. One obvious part to split of is the solving of a single row, independent whether it is up, down, right or left.

Solve a single row

The way I approach this is with a slightly modified pairwise itertools recipe

def pairwise_longest(iterable):
    """
    s -> (s0,s1), (s1,s2), (s2, s3), ..., (s_n, None)

    adapted from https://docs.python.org/3/library/itertools.html#itertools-recipes
    """
    a, b = tee(iterable)
    next(b, None)
    return zip_longest(a, b)

def solve_row(row):
    merged = False
    row = filter(None, row)
    for a, b in pairwise_longest(row):
        if not merged and a == b:
            yield a + b
            merged = True
        elif not merged and a != b:
            yield a
        else:
            merged = False

This first filters out all 0's, so it doesn't need to do any fancy indexing, just pairwise iteration over the actual tiles

The functioning of this code can be easily tested independently

assert tuple(solve_row([0,0,0,1])) == (1,)
assert tuple(solve_row([0,1,0,1])) == (2,)
assert tuple(solve_row([0,1,2,1])) == (1, 2, 1,)
assert tuple(solve_row([1,1,2,1])) == (2, 2, 1,)
assert tuple(solve_row([1,1,1,1])) == (2, 2,)
assert tuple(solve_row([1,1,1,0])) == (2, 1,)
assert tuple(solve_row([1,0,1,0])) == (2,)

This should be complemented by a function that pads the row with 0's

def solve_pad(row):
    l = len(row)
    solved = tuple(solve_row(row))
    return solved + (0,) * (l-len(solved))

assert solve_pad([0,0,0,1]) == (1,0,0,0,)
assert solve_pad([0,1,0,1]) == (2,0,0,0,)
assert solve_pad([0,1,2,1]) == (1,2,1,0,)
assert solve_pad([1,1,2,1]) == (2,2,1,0,)
assert solve_pad([1,1,1,1]) == (2,2,0,0,)
assert solve_pad([1,1,1,0]) == (2,1,0,0,)
assert solve_pad([1,0,1,0]) == (2,0,0,0,)

In reality, this function will also need to be able to do the same in reverse

def solve_pad(row, reverse=False):
    l = len(row)
    if reverse:
        row = reversed(row)
    solved = tuple(solve_row(row))
    if reverse:
        solved = tuple(reversed(solved))
        return (0,) * (l-len(solved)) + solved
    return solved + (0,) * (l-len(solved))

There are probably nicer ways to express the reversion, but this one works and I understand it without much problems.

assert solve_pad([0,0,0,1], reverse=True) == (0,0,0,1,)
assert solve_pad([0,1,0,1], reverse=True) == (0,0,0,2,)
assert solve_pad([0,1,2,1], reverse=True) == (0,1,2,1,)
assert solve_pad([1,1,2,1], reverse=True) == (0,2,2,1,)
assert solve_pad([1,1,1,1], reverse=True) == (0,0,2,2,)
assert solve_pad([1,1,1,0], reverse=True) == (0,0,1,2,)
assert solve_pad([1,0,1,0], reverse=True) == (0,0,0,2,)

The board

To represent the whole board, I would use a Board class. Depending of the movement direction, you need to iterate over it row or column wise, and should be able to construct a new board when given columns or rows

class Board:
    def __init__(self, situation):
        self.situation = tuple(map(tuple, situation))

    @classmethod
    def from_rows(cls, rows):
        return cls(rows)

    @classmethod
    def from_columns(cls, columns):
        rows = zip(*columns)
        return cls(rows)

    @property
    def shape(self):
        return len(self.situation), len(self.situation[0])

    @property
    def rows(self):
        yield from self.situation

    @property    
    def columns(self):
        yield from zip(*self.situation)

    def __repr__(self):
        def format_row(row, pad=5, sep='|'):
            return sep.join(f'{item:^{pad}}' for item in row)
        return '\n'.join(map(format_row, self.rows))

Adding the __repr__ makes debugging a lot easier

board = [
    [2,2,0,0],
    [2,2,0,0],
    [2,4,0,0],
    [2,4,0,8],
]
board = Board(board)
  2  |  2  |  0  |  0  
  2  |  2  |  0  |  0  
  2  |  4  |  0  |  0  
  2  |  4  |  0  |  8  

Move

Moving the pieces then becomes rather easy: you need to see whether to use rows or columns, and which function to generate the solution board accordingly, and select whether to reverse the merge or not, and then just call the solve_pad method on each row or column

def move(self, direction):
    if direction in {MoveDirection.LEFT, MoveDirection.RIGHT}:
        items = self.rows 
        func = Board.from_rows
    else:
        items = self.columns
        func = Board.from_columns
    reverse = direction in {MoveDirection.RIGHT, MoveDirection.DOWN}
    items_solved = (solve_pad(item, reverse=reverse) for item in items)
    return func(items_solved)

and can be used like this:

board.move(MoveDirection.UP)
  4  |  4  |  0  |  8  
  4  |  8  |  0  |  0  
  0  |  0  |  0  |  0  
  0  |  0  |  0  |  0
board.move(MoveDirection.DOWN)
  0  |  0  |  0  |  0  
  0  |  0  |  0  |  0  
  4  |  4  |  0  |  0  
  4  |  8  |  0  |  8
board.move(MoveDirection.RIGHT)
  0  |  0  |  0  |  4  
  0  |  0  |  0  |  4  
  0  |  0  |  2  |  4  
  0  |  2  |  4  |  8
board.move(MoveDirection.LEFT)
  4  |  0  |  0  |  0  
  4  |  0  |  0  |  0  
  2  |  4  |  0  |  0  
  2  |  4  |  8  |  0

This approach works for a rectangular and can be easily expanded to a hexagonal board if you find a decent name for the 3rd axis

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.