Vexed 是一款流行的益智游戏，有许多版本（其中一些是 GPL 自由软件）。它非常适合小屏幕设备；有适用于 Android、iOS 等平台的版本。我是在 PalmOS 平台上发现它的。
为了娱乐，我想编写一个能够解决 Vexed 关卡的求解器。
Vexed 是一款方块滑动益智游戏。以下是其规则的简述：
0) 每个关卡都是一个由不可逾越的边界围成的正方形网格。在任何关卡中，都会有一些实心方块，这些方块是无法通过的。还有一些不同颜色的方块；这些方块可能位于底部边界上、位于实心方块上，或者位于其他方块（不同颜色）上。大多数关卡都是 8×8 或更小。
1) 你能采取的唯一动作是将一个方块向左或向右滑动。方块移动的每个方格计为一步。
2) 存在重力。如果你滑动一个方块后，它不再位于实心方块或其他方块上，它将下落，直到它落在另一个方块、一个实心方块或底部边界上。请注意，你永远不能再把它抬起来。
3) 任何时候，两个或多个相同颜色的方块接触时，它们就会消失。请注意，可以形成连锁反应：如果一个支撑方块消失，位于其上的方块将会下落，这可能导致更多相同颜色的方块接触并因此消失。
4) 目标是以最少的步数使所有方块消失。每个关卡都有一个“标准分数”，它告诉你最少的步数。（在最初的 PalmOS 游戏中，“标准分数”不一定是最小值，但在我现在玩的 Android 版本中，它就是最小值。）
以下是包含 PalmOS 游戏源代码的 SourceForge 项目：
http://sourceforge.net/projects/vexed/
我是一位经验丰富的软件开发人员，但我还没有真正做过任何 AI 方面的工作（路径查找、问题解决等）。因此，我正在寻找建议，以使我朝着正确的方向前进。
目前，我可以看到两种基本的策略可以追求：
0) 编写一个蛮力求解器，可能使用 C 语言以提高速度，它可以处理每个游戏的所有可能的解决方案，并返回所有解决方案的列表，最佳解决方案优先。这会是一个合理的方法吗，或者所有可能的移动总数会使它太慢？我认为不存在大于 10×10 的关卡。
1) 学习一些 AI 算法，并以巧妙的方式应用它们来解决问题，可能使用 Python。
请注意，PalmOS Vexed 的源代码包含一个求解器。根据作者的说法，“求解器使用 A* 算法和剪枝启发式方法来寻找解决方案。”
http://www.scottlu.com/Content/Vexed.html
因此，我可以追求的一种策略是研究 A* 算法，然后研究现有求解器的 C++ 代码，并尝试从中学习。
我将使用 Python 和 C 标签标记此问题，但如果你认为我应该使用其他东西，请提出你的理由，我会考虑的！
以下是来自“Variety 25 Pack”的关卡的美术字符画；第 48 关，“Dark Lord”。我能够解决大多数关卡，但是这一个关卡，嗯，让我很恼火。此关的标准分数是 25 步，但我还没有完全解决它！
__________
|## g####|
|## # b##|
|## # p##|
|#g ###|
|bp ###|
|p# p g |
==========
在此图中，边界是下划线、竖线和等号字符。填充的方块是“#”。开放空间是空格字符。彩色方块是“g”（绿色）、“b”（蓝色）和“p”（紫色）。
顺便说一句，我可能会使求解器的输入文件格式为关卡的美术字符画，就像这样，但没有那些挑剔的线条边框字符。
感谢任何建议！
编辑：
我已经接受了一个答案。感谢各位给我的答案。
这是一个半蛮力求解器。它没有使用 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 秒内解决了“Dark Lord”问题，考虑了 14252 种不同的棋盘配置。我使用 Python 2.x 而不是 Python 3 编写，因为我想尝试使用 PyPy 并查看它的速度有多快。
接下来我应该致力于将 A* 算法应用于此。我想我可以制定一个指标，例如“将橙色方块朝另一个橙色方块移动比远离更好”，并尝试将其纳入。但我确实希望所有解决方案都弹出，所以也许我已经完成了。（如果存在三个都是最小移动次数的解决方案，我希望看到所有三个。）
我欢迎对此 Python 程序发表评论。我写得很开心！
编辑：我确实用 PyPy 尝试了这一点，但我从未更新到目前为止。在我使用 PyPy 的计算机上，求解器可以使用 CPython 在 10 秒内解决“黑暗领主”关卡；使用 PyPy 降至 4 秒。最酷的部分是我可以看到 JIT 启动时的速度提升：该程序在工作时会打印点，在 PyPy 下，我可以看到点开始时较慢，然后只是加速。PyPy 很漂亮。
回答：
研究维基百科可能比研究实际源代码更好。A*在那里写得很清楚。但这感觉像作弊，不是吗？
像所有好主意一样，A* 实际上在回顾时非常明显。尝试解决这个问题很有趣，并且一路走来有一些不错的见解。以下是如何实现它：
编写蛮力求解器。您需要在更高级的版本中编写大部分内容：游戏状态，以及从一个状态到另一个状态的描述。您最终还会删除重复状态。您应该有一个队列，用于考虑的状态，一个已经完成的状态集，以及用于保存到目前为止找到的最佳解决方案的结构。以及一种从队列中获取状态并生成状态的“相邻”状态（可从中到达的状态）的方法。这是经典 AI 算法的基本结构。请注意，您实际上是在这里“生成”或“探索”一个巨大的图。
之后，添加一个简单的修剪算法：如果某个状态仅剩一个颜色的方块，则无需进一步考虑。看看您是否可以提出其他修剪算法（即，将状态标记为“无法解决”的算法）。一个好的修剪算法将消除许多毫无意义的状态，从而证明运行修剪本身所花费的时间是合理的。
然后，引入启发式分数：用一个数字对每个状态进行排名，该数字告诉您该状态看起来“有多好”——大约需要多少更多的解决。使您的队列成为优先级队列。这将使您可以首先考虑“看起来最好”的状态，因此该程序应更快地找到一个解决方案。但是，找到的第一个解决方案实际上可能不是最好的解决方案，因此，为确保您找到最好的解决方案，您仍然需要运行整个程序。
存储您到达每个状态所花费的最小成本（移动次数）。如果您找到更好的路径，请记住更新它。首先采用成本及其启发式分数之和最低的状态；这些更有可能导致更好的解决方案。
A* 算法来了。您需要修改您的启发式函数，使其不会高估到目标的距离，即它可以低于您实际需要的移动次数，但不能高于。然后，请注意，如果您找到了解决方案，它的启发式分数将为 0。并且，任何成本及其启发式之和大于解决方案成本的状态都无法导致更好的解决方案。因此，您可以修剪该状态。但是，由于您正在按顺序获取状态，因此一旦达到该阈值，您就可以停止并返回，因为队列中的所有其他状态也将被修剪。
现在剩下的就是完善您的启发式：它永远不能高估，但是它给出的估计越好，A* 所花费的时间就越少。启发式越好，结果越好。请注意，启发式完成不会花费太多时间——您不会希望，例如，通过蛮力生成解决方案，即使它会给出完美的答案 
如果您走到了这一步，维基百科还会提供更多讨论和可能的改进。但是，您目前可以做的最好的改进可能来自改进启发式函数。
