python - 有关为Vexed关卡编写解算器的建议

Question

烦恼是一个流行的益智游戏，有许多版本可用（其中一些是GPL免费软件）。它非常适合小屏幕设备；Android、iOS等版本都有。我是在PalmOS平台上发现的。
只是为了好玩，我想写一个解决方案，将解决烦恼的水平。
烦恼是一个块滑动拼图游戏。简而言之，规则如下：
0）每一层都是一个方格，由一个无法逾越的边界包围。在任何水平面上都会有一些实心方块，它们是不可能的。有一些不同颜色的块；这些块可以放在底部边框上，放在实心正方形上，或者放在其他块（不同颜色）上。大多数级别为8x8或更小。
1）您唯一可以采取的操作是向左或向右滑动块。一个街区的每一个方格都算作一次移动。
2）有重力。如果在您滑动一个块后，它不再停留在一个实心正方形或另一个块上，它将下降，直到它停留在另一个块、实心正方形或底部边框上。注意，你再也抬不起来了。
3）同一颜色的两个或多个色块接触时，它们消失。注意，链条是可能的：如果一个支撑块消失了，它上面的块就会掉下来，这可能会导致更多相同颜色的块接触，从而消失。
4）目标是在最少的移动次数内使所有方块消失。每个关卡都有一个“标准分数”，告诉你最少的移动次数。（在最初的PalmOS游戏中，“par分数”不一定是最低的，但在我现在玩的Android版本中，它是最低的。）
以下是带有PalmOS版本游戏源代码的SourceForge项目：
http://sourceforge.net/projects/vexed/
我是一个经验丰富的软件开发人员，但我还没有做过任何人工智能方面的工作（寻路、解决问题等），所以我在寻求建议，让我的方向正确。
目前，我可以看到两个基本的策略需要我去追求：
0）只需编写一个蛮力解算器，可能是用C语言表示速度，它可以在每个游戏的所有可能的解决方案中滚动，并返回所有解决方案的列表，最好的一个首先。这是一种合理的做法，还是可能的行动总数会使这一进程过于缓慢？我不认为任何级别都大于10x10。
1）学习一些人工智能算法，并以巧妙的方式应用它们来解决问题，可能使用Python。
请注意，PalmOS Vexed的源包含一个解算器。根据作者的说法，“解算器使用带修剪启发式的A*来寻找解决方案。”
http://www.scottlu.com/Content/Vexed.html
因此，我可以研究的一个策略是研究A*算法，然后研究现有求解器的C++代码，并尝试从中学习。
我将用Python和C标记来标记它，但是如果你认为我应该使用其他的东西，那么你的销售策略，我会考虑的！
这里是ASCII艺术的一个水平从“品种25包”；水平48，“黑暗领主”。我能解决大多数问题，但这一个，嗯，让我很恼火。这个级别的标准杆分数是25步，但我还没有解决它！

__________
|## g####|
|## # b##|
|## # p##|
|#g   ###|
|bp   ###|
|p# p g  |
==========

在这张图片中，边框是下划线、竖线和等号字符。填充的方块是“35;”。空格是空格字符。色块是“g”（绿色）、“b”（蓝色）和“p”（紫色）。
顺便说一下，我可能会使输入文件格式的解算器是ASCII艺术的水平，就像这样，但没有繁琐的线边框字符。
谢谢你的建议！
编辑：
我已经接受了一个答复。谢谢给我答案的人。
这是一个半暴力解决方案。它没有使用*但是它正在剪短树上不赚钱的树枝。
它用级别数据读入一个简单的文本文件。一个字母是一个块，一个“”（下划线）是一个开放空间，一个“#”是一个填充空间。

#!/usr/bin/env python
#
# Solve levels from the game Vexed.


from collections import Counter
import sys


level_blocks = set(chr(x) for x in range(ord('a'), ord('z')+1))
level_other = set(['_', '#'])
level_valid = set().union(level_blocks, level_other)


def prn_err(s='\n'):
    sys.stderr.write(s)
    sys.stderr.flush()


def validate_llc(llc):
    if len(llc) == 0:
        raise ValueError, "need at least one row of level data"
    w = len(llc[0])
    if w < 2:
        raise ValueError, "level data not wide enough"
    for i, row in enumerate(llc):
        if len(row) != w:
            s = "level data: row %d is different length than row 0"
            raise ValueError, s % i
        for j, ch in enumerate(row):
            if ch not in level_valid:
                s = "char '%c' at (%d, %d) is invalid" % (ch, i, j)
                raise ValueError, s


class Info(object):
    pass

info = Info()

info.width = 0
info.height = 0
info.spaces = set()
info.boom_blocks = set()
info.best_solution = 9999999999
info.title = "unknown"



class Level(object):
    """
    Hold the state of a level at a particular move.  self.parent points
    to the previous state, from a previous move, so the solver builds a
    tree representing the moves being considered.  When you reach a solution
    (a state where there are no more blocks) you can walk up the tree
    back to the root, and you have the chain of moves that leads to that
    solution."""
    def __init__(self, x):
        if isinstance(x, Level):
            self.blocks = dict(x.blocks)
            self.colors = dict(x.colors)
            self.parent = x
            self.s_move = ''
            self.rank = x.rank + 1
        else:
            if isinstance(x, basestring):
                # allow to init from a one-line "data" string
                # example: "___;___;r_r"
                x = x.split(';')

            # build llc: list of rows, each row a list of characters
            llc = [[ch for ch in row.strip()] for row in x]
            llc.reverse()

            info.width = len(llc[0])
            info.height = len(llc)
            validate_llc(llc)

            # Use llc data to figure out the level, and build self.blocks
            # and info.spaces.  self.blocks is a dict mapping a coordinate
            # tuple to a block color; info.spaces is just a set of
            # coordinate tuples.
            self.blocks = {}
            for y in range(info.height):
                for x in range(info.width):
                    loc = (x, y)
                    c = llc[y][x]
                    if c == '_':
                        # it's a space
                        info.spaces.add(loc)
                    elif c in level_blocks:
                        # it's a block (and the block is in a space)
                        self.blocks[loc] = c
                        info.spaces.add(loc)
                    else:
                        # must be a solid square
                        assert(c == '#')

            # colors: map each block color onto a count of blocks.
            self.colors = Counter(self.blocks.values())

            # parent: points to the level instance that holds the state
            # previous to the state of this level instance.
            self.parent = None

            # s_move: a string used when printing out the moves of a solution
            self.s_move = 'initial state:'

            # rank: 0 == initial state, +1 for each move
            self.rank = 0

            self.validate()

            print "Solving:", info.title
            print
            sys.stdout.flush()

        if self._update():
            print "level wasn't stable!  after updating:\n%s\n" % str(self)

    def lone_color(self):
        return any(count == 1 for count in self.colors.values())

    def is_solved(self):
        return sum(self.colors.values()) == 0

    def validate(self):
        if info.height == 0:
            raise ValueError, "need at least one row of level data"
        if info.width < 2:
            raise ValueError, "level data not wide enough"
        if self.lone_color():
            raise ValueError, "cannot have just one of any block color"
        for x, y in info.spaces:
            if not 0 <= x < info.width or not 0 <= y < info.height:
                raise ValueError, "Bad space coordinate: " + str(loc)
        for x, y in self.blocks:
            if not 0 <= x < info.width or not 0 <= y < info.height:
                raise ValueError, "Bad block coordinate: " + str(loc)
        if any(count < 0 for count in self.colors.values()):
            raise ValueError, "cannot have negative color count!"

        colors = Counter(self.blocks.values())
        for k0 in [key for key in self.colors if self.colors[key] == 0]:
            del(self.colors[k0])  # remove all keys whose value is 0
        if colors != self.colors:
            raise ValueError, "self.colors invalid!\n" + str(self.colors)

    def _look(self, loc):
        """
return color at location 'loc', or '_' if empty, or '#' for a solid sqaure.
A bad loc does not raise an error; it just returns '#'.
        """
        if loc in self.blocks:
            return self.blocks[loc]
        elif loc in info.spaces:
            return '_'
        else:
            return '#'

    def _lookxy(self, x, y):
        loc = x, y
        return self._look(loc)

    def _board_mesg(self, mesg, loc):
        x, y = loc
        return "%s %c(%d,%d)" % (mesg, self._look(loc), x, y)

    def _blocked(self, x, y):
        return self._lookxy(x, y) != '_'

    def _s_row(self, y):
        return ''.join(self._lookxy(x, y) for x in xrange(info.width))
    def data(self, ch_join=';'):
        return ch_join.join(self._s_row(y)
                for y in xrange(info.height - 1, -1, -1))

    # make repr() actually print a representation
    def __repr__(self):
        return type(self).__name__ + "(%s)" % self.data()

    # make str() work
    def __str__(self):
        return self.data('\n')


    def _move_block(self, loc_new, loc_old):
        self.blocks[loc_new] = self.blocks[loc_old]
        del(self.blocks[loc_old])

    def _explode_block(self, loc):
        if loc in info.boom_blocks:
            return

        info.boom_blocks.add(loc)
        color = self.blocks[loc]
        self.colors[color] -= 1

    def _try_move(self, loc, d):
        x, y = loc
        if not d in ('<', '>'):
            raise ValueError, "d value '%c' invalid, must be '<' or '>'" % d

        if d == '<':
            x_m = (x - 1)
        else:
            x_m = (x + 1)
        y_m = y
        loc_m = (x_m, y_m)
        if self._blocked(x_m, y_m):
            return None # blocked, so can't move there

        # Not blocked.  Let's try the move!
        # Make a duplicate level...
        m = Level(self)
        # ...try the move, and see if anything falls or explodes...
        m._move_block(loc_m, loc)
        m._update()
        if m.lone_color():
            # Whoops, we have only one block of some color.  That means
            # no solution can be found by considering this board.
            return None

        # finish the update
        m.s_move = self._board_mesg("move:", loc) + ' ' + d
        m.parent = self
        return m

    def _falls(self, loc):
        x, y = loc
        # blocks fall if they can, and only explode when at rest.

        # gravity loop: block falls until it comes to rest
        if self._blocked(x, y - 1):
            return False # it is already at rest

        while not self._blocked(x, y - 1):
            # block is free to fall so fall one step
            y -= 1

        loc_m = (x, y)
        self._move_block(loc_m, loc)
        return True # block fell to new location

    def _explodes(self, loc):
        x, y = loc
        exploded = False

        color = self._look(loc)
        # look left, right, up, and down for blocks of same color
        for e_loc in [(x-1, y), (x+1, y), (x, y-1)]:
            if e_loc in self.blocks and self.blocks[e_loc] == color:
                self._explode_block(e_loc)
                exploded = True

        if exploded:
            self._explode_block(loc)

        return exploded

    def _update(self):
        c = 0
        while True:
            # TRICKY: sum() works on functions that return a bool!
            # As you might expect, True sums as 1 and False as 0.
            f = sum(self._falls(loc) for loc in self.blocks)
            e = sum(self._explodes(loc) for loc in self.blocks)
            for loc in info.boom_blocks:
                del(self.blocks[loc])
            info.boom_blocks.clear()
            c += f + e
            if (f + e) == 0:
                # no blocks fell or exploded; board is stable, update is done
                break
        return c

    def print_moves(self):
        lst = [self]
        a = self
        while a.parent:
            a = a.parent
            lst.append(a)
        lst.reverse()
        for i, a in enumerate(lst):
            if i:
                print "Move %d of %d" % (i, len(lst) - 1)
            print a.s_move
            print a
            print


    def solve(self):
        c = 0
        seen = set()
        solutions = []

        seen.add(self.data())
        q = []
        if self.is_solved():
            solutions.append(self)
        else:
            q.append(self)

        while q:
            a = q.pop(0)

            # Show dots while solver is 'thinking' to give a progress
            # indicator.  Dots are written to stderr so they will not be
            # captured if you redirect stdout to save the solution.
            c += 1
            if c % 100 == 0:
                prn_err('.')

            if a.rank > info.best_solution:
                # We cannot beat or even match the best solution.
                # No need to think any more about this possibility.
                # Just prune this whole branch of the solution tree!
                continue

            for loc in a.blocks:
                for d in ('<', '>'):
                    m = a._try_move(loc, d)
                    if not m or m.data() in seen:
                        continue

                    if m.is_solved():
                        if info.best_solution > a.rank:
                            print "\nnew best solution: %d moves" % m.rank
                            info.best_solution = a.rank
                        else:
                            print "\nfound another solution: %d moves" % m.rank
                        solutions.append(m)
                    else:
                        seen.add(m.data())
                        q.append(m)
        print
        print "Considered %d different board configurations." % c
        print

        solutions.sort(key=lambda a: a.rank)
        for n, a in enumerate(solutions):
            print "solution %d): %d moves" % (n, a.rank)
            a.print_moves()

        if not solutions:
            print "no solutions found!"


def load_vex_file(fname):
    with open(fname, "rt") as f:
        s = f.next().strip()
        if s != "Vexed level":
            raise ValueError, "%s: not a Vexed level file" % fname
        s = f.next().strip()
        if not s.startswith("title:"):
            raise ValueError, "%s: missing title" % fname
        info.title = s[6:].lstrip()  # remove "title:"
        for s in f:
            if s.strip() == "--":
                break
        return Level(f)



if __name__ == "__main__":
    if len(sys.argv) == 1:
        print "Usage vexed_solver <vexed_level_file.vex>"
        sys.exit(1)

    fname = sys.argv[1]
    level = load_vex_file(fname)
    level.solve()

下面是一个示例级文件：

Vexed level
title: 25-48, "Dark Lord"
--
##_f####
##_#_c##
##_#_p##
#f___###
cp___###
p#_p_f__

在我的电脑上，考虑到14252种不同的电路板配置，它几乎在10秒内就能解决“黑魔王”。我用Python2.x而不是Python3编写，因为我想用PyPy尝试一下，看看它变得有多快。
下一步我应该把A*应用到这个问题上。我想我可以做一个类似于“把一个橘子块移到另一个橘子块比移走更好”的度量，并尝试在其中工作。但我确实希望所有的解决方案都能出来，所以也许我已经完成了。（如果有三个解决方案都是最少的移动次数，我希望看到这三个。）
我欢迎对这个Python程序的评论。我写得很开心！
编辑：我确实尝试过PyPy，但直到现在我才更新过。在我和PyPy一起使用的计算机上，解算器可以用CPython在10秒内解出“黑暗领主”等级；而PyPy的解算速度则下降到4秒。最酷的是，我可以看到JIT启动时的加速：这个程序在工作时打印点，在PyPy下，我可以看到点开始变慢，然后加速。皮比很漂亮。

Answer 1

研究Wikipedia可能比研究实际的源代码要好。A*写得很清楚。但那感觉像是作弊，不是吗？
作为所有的好主意，A*实际上在回顾中相当明显。努力完成这件事很有趣，这一过程中有一些很好的见解。以下是你如何做到的：
写出蛮力解算器。你需要在更高级的版本中写很多东西：游戏状态，以及从一个状态到另一个状态的描述。你也会删除重复的状态。您应该有一个队列，其中包含要考虑的状态、已经完成的状态集，以及保存到目前为止找到的最佳解决方案的结构。以及从队列中获取状态并生成状态的“邻居”状态（可从中访问的状态）的方法。这是经典人工智能算法的基本结构。请注意，您在技术上是在“生成”或“探索”一个巨大的图形。
之后，添加一个简单的剪枝算法：如果一个状态只剩下一个颜色块，则无需进一步考虑它。看看你能不能想出其他的修剪算法（即那些将一个状态标记为“无法解决”的算法）。一个好的剪枝算法将消除许多无意义的状态，从而证明运行剪枝本身所需的时间是合理的。
然后，引入一个启发式得分：用一个数字来给每个州排序，这个数字告诉你这个州看起来有多“好”–关于需要解决多少问题。将您的队列设为apriority queue。这将允许您首先考虑“最佳外观”状态，因此程序应该更快地提出解决方案。但是，找到的第一个解决方案实际上可能不是最好的，所以要确保找到了最好的解决方案，仍然需要运行整个程序。
存储到达每个状态所需的最低成本（移动次数）。如果找到更好的路径，记得更新它。以成本和启发式得分之和最低的州为例，这些州更有可能得到更好的解决方案。
来了一个*。你需要修改你的启发式函数，这样它就不会高估到目标的距离，也就是说，它可以低于你实际需要的移动次数，但不能更高。然后，请注意，如果您找到了一个解决方案，其启发式得分将为0。而且，任何一个状态，如果其成本和启发式的总和大于一个解决方案的成本，都不会导致一个更好的解决方案。所以，你可以删掉这个状态。但是，由于要按顺序获取状态，因此一旦达到该阈值，就可以停止并返回，因为队列中的所有其他状态也将被剪除。
现在剩下的就是完善你的启发式方法：它永远不会高估，但是它给出的更好的估计会减少A*所需的时间。启发式越好，结果越好。注意，启发式不需要花太多时间来完成——你不希望，比如说，用暴力产生解决方案，即使它会给出完美的答案：）
维基百科有更多的讨论和可能的改进，如果你做到这一点。但此时最好的改进可能来自于对启发式函数的改进。