关于为Vexed关卡编写求解器的建议
Vexed 是一款很受欢迎的益智游戏，有很多版本可供选择（其中一些是 GPL 免费软件）。它非常适合小屏幕设备，像 Android 和 iOS 都有版本。我是在 PalmOS 平台上发现这个游戏的。
为了好玩，我想写一个程序来解决 Vexed 的关卡。
Vexed 是一个滑块拼图游戏。简单来说，规则如下：
0) 每一关都是一个方格网，周围有不可通过的边界。在每一关中，会有一些实心方块，这些是不能移动的。还有一些不同颜色的块，它们可能放在底边、实心方块上，或者放在其他颜色的块上。大多数关卡是 8x8 或更小。
1) 你唯一能做的就是将一个块向左或向右滑动。每个块移动经过的方格都算作一次移动。
2) 有重力。如果你滑动一个块后，它不再放在实心方块或其他块上，它会掉落，直到落在另一个块、实心方块或底边上。注意，你永远不能把它抬起来。
3) 任何时候，如果两个或更多相同颜色的块接触，它们会消失。注意，可能会出现连锁反应：如果一个支撑块消失，放在上面的块会掉落，这可能导致更多相同颜色的块接触并消失。
4) 目标是让所有块在最少的移动次数内消失。每一关都有一个“标准分数”，告诉你最少需要多少次移动。（在原来的 PalmOS 游戏中，“标准分数”不一定是最少的，但在我现在玩的 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 的标签，但如果你觉得我应该使用其他东西，请告诉我，我会考虑的！
这是“Variety 25 Pack”中的一个关卡的 ASCII 艺术；第 48 关，“黑暗领主”。我能解决大多数关卡，但这一关让我很头疼。这个关卡的标准分数是 25 次移动，但我还没有解决它！
__________
|## g####|
|## # b##|
|## # p##|
|#g ###|
|bp ###|
|p# p g |
==========
在这张图中，边界是下划线、竖线和等号。填充方块是 '#'。空白区域是空格字符。彩色块分别是 'g'（绿色）、'b'（蓝色）和 'p'（紫色）。
顺便说一下，我可能会让求解器的输入文件格式是关卡的 ASCII 艺术，就像这样，但没有那些麻烦的边框字符。
谢谢任何建议！
编辑：
我已经接受了一个答案。感谢给我提供答案的人。
这是一个半暴力求解器。它没有使用 A*，但它在树的分支中剪掉了不盈利的部分。
它读取一个简单的文本文件，里面包含关卡数据。一个字母代表一个块，'_'（下划线）代表一个开放空间，'#' 代表一个填充空间。
#!/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__
在我的电脑上，它几乎在 10 秒内解决了“黑暗领主”，考虑了 14252 种不同的棋盘配置。我用的是 Python 2.x，而不是 Python 3，因为我想尝试用 PyPy 看看速度会变得多快。
接下来我应该着手将 A* 应用到这个问题上。我想我可以制定一个指标，比如“将一个橙色块移动到另一个橙色块附近比远离它更好”，并尝试将其融入。但我确实希望所有解决方案都能显示出来，所以也许我已经完成了。（如果有三个解决方案都是最少移动次数，我想看到所有三个。）
欢迎对这个 Python 程序提出意见。我写这个程序时很开心！
编辑：我确实尝试过用 PyPy，但直到现在我才更新这个。在我用 PyPy 的电脑上，求解器可以在 10 秒内用 CPython 解决“黑暗领主”关卡；用 PyPy 则降到了 4 秒。最酷的是，我可以看到加速的过程，因为 JIT 开始工作：这个程序在运行时会打印点，在 PyPy 下我可以看到点的速度开始较慢，然后加速。PyPy 真不错。
2 个回答
你可以把这个问题转化成一个经典的规划问题（使用PDDL语法）。这样的话，你就可以试试一些免费的规划工具。
比如，可以试试这个 Fast Forward。
在学习 维基百科 的内容时，可能比直接研究实际的源代码要好。A* 算法在那儿写得很清楚。不过，这样做是不是有点偷懒呢？
像所有好的想法一样，回头看，A* 实际上是相当明显的。尝试自己推导这个算法是很有趣的，过程中会有一些不错的见解。下面是你可以如何理解它：
首先，写一个暴力求解器。你需要在更高级的版本中用到你写的大部分内容：一个游戏状态，以及描述如何从一个状态转到另一个状态。你还需要去掉重复的状态。你应该有一个队列，用来存放待考虑的状态，还有一个集合，记录你已经处理过的状态，以及一个结构来保存到目前为止找到的最佳解决方案。还有一个方法，用来从队列中取出一个状态，并生成这个状态的“邻居”状态（可以从这个状态到达的状态）。这就是经典人工智能算法的基本结构。要注意的是，你实际上是在“生成”或“探索”一个巨大的图。
接下来，添加一个简单的剪枝算法：如果某个状态只剩下一个颜色的方块，就没有必要再考虑它了。看看你能否想出其他的剪枝算法（也就是那些将状态标记为“不可解”的算法）。一个好的剪枝算法可以消除很多无意义的状态，从而证明运行剪枝本身所花的时间是值得的。
然后，引入一个启发式评分：给每个状态打个分，告诉你这个状态看起来有多“好”——还需要多少步骤才能解决。把你的队列改成 优先队列。这样，你就可以优先考虑“看起来最好的”状态，这样程序应该能更快找到一个解决方案。不过，第一次找到的解决方案可能并不是最好的，所以为了确保找到最佳方案，你仍然需要运行整个程序。
记录到达每个状态所需的最小成本（移动次数）。如果你找到了一条更好的路径，记得更新它。优先处理那些成本和启发式评分之和最低的状态；这些状态更有可能导致更好的解决方案。
接下来就是 A* 算法了。你需要修改你的启发式函数，使其 不会高估 到达目标的距离，也就是说，它可以低于你实际需要的移动次数，但不能高于。然后，注意如果你找到了一个解决方案，它的启发式评分将是 0。而且，任何状态如果其成本和启发式评分之和超过了解决方案的成本，就无法导致更好的解决方案。因此，你可以剪枝这个状态。但由于你是按顺序处理状态的，一旦达到这个阈值，你可以直接停止并返回，因为队列中的其他状态也会被剪枝。
现在剩下的就是完善你的启发式函数：它永远不能高估，但给出的估计越好，A* 算法所需的时间就越少。启发式函数越好，你的结果就越好。要注意启发式函数的计算时间不要太长——你可不想用暴力法生成解决方案，尽管那样会得到完美的答案 :)
如果你能看到这里，维基百科还有更多讨论和可能的改进。不过，此时你能做的最佳改进可能来自于提升启发式函数的表现。