Vexed は人気のあるパズル ゲームであり、多くのバージョンが利用可能です (一部は GPL フリー ソフトウェア)。小さな画面のデバイスに非常に適しています。バージョンは、Android、iOS などで利用できます。PalmOS プラットフォームで発見しました。
楽しみのために、困ったレベルを解決するソルバーを書きたいと思います。
Vexed は、ブロック スライディング パズル ゲームです。ルールを簡単に説明すると、次のようになります。
0) 各レベルは四角形のグリッドで、通過できない境界線で囲まれています。どのレベルでも、通過できない塗りつぶされた四角がいくつかあります。さまざまな色のブロックがいくつかあります。これらは、下の境界線、黒の正方形、または他のブロック (異なる色) に置かれている可能性があります。ほとんどのレベルは 8x8 以下です。
1) ブロックを左右にスライドさせる操作しかできません。ブロックが移動する各正方形は、1 回の移動としてカウントされます。
2) 重力があります。ブロックをスライドさせた後、ブロックが塗りつぶされた正方形または別のブロックに置かれなくなった場合、ブロックは別のブロック、塗りつぶされた正方形、または下の境界線に収まるまで落下します。二度と持ち上げることはできませんのでご注意ください。
3) 同じ色のブロックが 2 つ以上接触すると、ブロックは消えます。チェーンが可能であることに注意してください: 支持ブロックが消えると、その上に載っていたブロックが落下し、同じ色のブロックがさらに接触して消える可能性があります。
4) 目標は、最小限の手数ですべてのブロックを消すことです。各レベルには、移動の最小数を示す「標準スコア」があります。(元の PalmOS ゲームでは、「パー スコア」は必ずしも最小ではありませんでしたが、最近プレイしている Android バージョンでは最小です。)
これは、ゲームの PalmOS バージョンのソースを含む SourceForge プロジェクトです。
http://sourceforge.net/projects/vexed/
私は経験豊富なソフトウェア開発者ですが、AI に関する作業 (パスファインディング、問題解決など) を実際に行ったことはありません。正しい方向に向けるためのアドバイスを探しています。
現時点では、私が追求すべき基本的な戦略が 2 つあります。
0) すべてのゲームで考えられるすべての解を調べて、すべての解のリスト (最良の解から順に) を返す総当たりソルバを、おそらく速度のために C で作成するだけです。これは合理的なアプローチでしょうか?それとも可能な移動の総数がこれを遅くしすぎますか? 10x10 より大きいレベルは存在しないと思います。
1) いくつかの AI っぽいアルゴリズムを学び、おそらく Python を使用して、問題を解決するためにそれらを巧妙な方法で適用します。
PalmOS Vexed のソースにはソルバーが含まれていることに注意してください。著者によると、「ソルバーは A* とプルーニング ヒューリスティックを使用してソリューションを見つけます。」
http://www.scottlu.com/Content/Vexed.html
したがって、私が追求できる戦略の 1 つは、A* アルゴリズムを研究してから、既存のソルバーの C++ コードを研究し、そこから学ぼうとすることです。
これを Python と C タグでタグ付けしますが、何か他のものを使用する必要があると思われる場合は、売り込みを行ってください。検討します!
「バラエティ25パック」のレベルのアスキーアートです。レベル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__
私のコンピューターでは、14252 の異なるボード構成を考慮して、"Dark Lord" をほぼ正確に 10 秒で解決します。Python 3 ではなく Python 2.x で書いたのは、これを PyPy で試してどれだけ高速になるかを確認したいからです。
次に、これに A* を適用する作業を行う必要があります。「オレンジ色のブロックを別のオレンジ色のブロックに近づけるよりも、別のオレンジ色のブロックに近づける方が良い」のようなメトリックを作成して、それを機能させることができると思います。(最小手数である解が 3 つある場合は、3 つすべてを見たいと思います。)
この Python プログラムに関するコメントを歓迎します。書いてて楽しかった！
編集: PyPy でこれを試しましたが、今まで更新したことはありません。私が PyPy で使用したコンピューターでは、ソルバーは CPython を使用して「Dark Lord」レベルを 10 秒で解決できました。PyPy では 4 秒に短縮されました。クールな部分は、JIT が開始されたときに速度が向上したことです。このプログラムは、動作中にドットを出力します。PyPy では、ドットの開始が遅くなり、その後加速することがわかります。PyPy は気の利いたものです。