2048移动计算

Question

因此，我用python3编写了2048年程序，并编写了一个简单的求解程序，它只针对董事会上的一个高数字(我知道，这不是最好的策略)，但我有一个问题，就是这种移动计算非常缓慢。任何关于如何加快这一进程的想法都会受到赞赏。(逻辑应该很好)

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

上下文中的代码和游戏可视化的代码可以在这里看到：https://github.com/MegaIng1/2048)

Answer 1

正如Gareth所述，您需要尽可能多地重用移动部件。然而，我不同意他把董事会夷为平地的做法。以下是另一种方法

您需要将代码分成更多的部分。分裂的一个明显的部分是解决一排，独立的，无论是上，下，右或左。

解决单行

我的方法是使用稍微修改过的pairwise迭代工具配方。

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

这首先过滤掉所有的0's，所以它不需要做任何花哨的索引，只需要在实际的块上进行成对的迭代。

此代码的功能可以很容易地独立测试。

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,)

这应该得到一个函数的补充，这个函数可以用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,)

实际上，该函数还需要能够反向执行同样的操作。

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))

也许有更好的方法来表达回归，但这一个工作，我理解它没有太多的问题。

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

为了代表整个董事会，我会使用一个Board类。根据移动方向，您需要按行或列顺序迭代，并且在给定的列或行时应该能够构造新的板。

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))

添加__repr__使调试变得更加容易。

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

2件事，2件事

Move

移动这些片段变得非常容易:您需要查看是否使用行或列，以及相应地生成解决方案板的函数，并选择是否反转合并，然后只需在每一行或每列上调用solve_pad方法。

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)

可以这样使用：

board.move(MoveDirection.UP)

4\x{e76f}\x{e76f}

board.move(MoveDirection.DOWN)

0

board.move(MoveDirection.RIGHT)

0

board.move(MoveDirection.LEFT)

4\x{e76f}\x{e76f}\x{e76f

这种方法适用于矩形，如果您为第三轴找到合适的名称，则可以很容易地展开为六角形板。