Vexed - популярная игра-головоломка, со многими доступными версиями (некоторые из них бесплатное программное обеспечение GPL) Это очень подходит для небольших устройств экрана; доступны версии для Android, iOS и т. д. Я обнаружил это на платформе PalmOS.
Ради интереса, я хотел бы написать решатель, который будет решать уровни Vexed.
Vexed - игра-головоломка с раздвижными блоками. Вот правила в двух словах:
0) Каждый уровень представляет собой сетку квадратов, ограниченных непроходимой границей. На любом уровне будут некоторые сплошные квадраты, которые непроходимы. Есть несколько блоков разных цветов; они могут быть на нижней границе, на сплошных квадратах или на других блоках (другого цвета). Большинство уровней 8x8 или меньше.
1) Единственное действие, которое вы можете предпринять, - сдвинуть блок влево или вправо. Каждый квадрат, пройденный блоком, считается одним ходом.
2) Есть гравитация. Если после скольжения блока он больше не лежит на сплошном квадрате или другом блоке, он будет падать, пока не остановится на другом блоке, сплошном квадрате или нижней границе. Обратите внимание, что вы никогда не сможете снова поднять его.
3) Каждый раз, когда два или более блоков одного цвета касаются друг друга, они исчезают. Обратите внимание, что цепи возможны: если опорный блок исчезнет, упавшие на него блоки упадут, что может привести к соприкосновению и исчезновению большего количества блоков одного цвета.
4) Цель состоит в том, чтобы все блоки исчезли за минимальное количество ходов. Каждый уровень имеет «номинальную оценку», которая говорит вам минимальное количество ходов. (В оригинальной игре PalmOS «номинальная оценка» не обязательно была минимальной, но в версии для Android, в которую я играю в эти дни, она минимальна.)
Вот проект SourceForge с исходным кодом для версии игры для PalmOS:
http://sourceforge.net/projects/vexed/
Я опытный разработчик программного обеспечения, но я не занимался какой-либо работой с ИИ (поиск путей, решение проблем и т. Д.), Поэтому я ищу совет, чтобы направить меня в правильном направлении. .
На данный момент я вижу две основные стратегии, которые я могу реализовать:
0) Просто напишите решатель грубой силы, вероятно, на C для скорости, который проверяет каждое возможное решение для каждой игры и возвращает список всех решений, лучшее из которых первое. Будет ли это разумным подходом, или общее количество возможных ходов сделает это слишком медленным? Я не думаю, что существуют уровни больше 10х10.
1) Изучите некоторые алгоритмы искусственного интеллекта и примените их умным способом для решения проблемы, возможно, с использованием Python.
Обратите внимание, что источник для PalmOS Vexed включает решатель. По словам автора, «решатель использует A * с сокращенной эвристикой для поиска решений».
http://www.scottlu.com/Content/Vexed.html
Итак, одна из стратегий, которую я мог бы применить, - это изучить алгоритм A *, а затем изучить код C ++ для существующего решателя и попытаться извлечь из него уроки.
Я собираюсь пометить это тегами Python и C, но если вы считаете, что мне следует использовать что-то другое, сделайте ваши продажи более точными, и я рассмотрю это!
Вот ASCII-арт уровня "Variety 25 Pack"; уровень 48, "Темный Лорд". Я в состоянии решить большинство уровней, но этот, конечно, меня раздражает. Номинальная оценка для этого уровня составляет 25 ходов, но я еще не решил это вообще!
__________
|## g####|
|## # b##|
|## # p##|
|#g ###|
|bp ###|
|p# p g |
==========
На этом рисунке границы - это подчеркивание, вертикальные черты и символы равенства. Заполненные квадраты - «#». Открытые пробелы являются пробелами. Цветные блоки: «g» (зеленый), «b» (синий) и «p» (фиолетовый).
Между прочим, я, скорее всего, сделаю формат входного файла для решателя ASCII-искусством уровней, вот так, но без суетливых символов границы линии.
Спасибо за любой совет!
EDIT:
Я принял ответ. Спасибо людям, которые дали мне ответы.
Это решатель полубортовой силы. Он не использует 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. Мне было весело писать это!
EDIT: я пробовал это с PyPy, но я никогда не обновлял это до сих пор. На компьютере, который я использовал с PyPy, решатель мог решить уровень «Темного Лорда» за 10 секунд, используя CPython; это уменьшилось до 4 секунд с PyPy. Самое интересное в том, что я мог увидеть ускорение при запуске JIT: эта программа печатает точки во время работы, и в PyPy я вижу, что точки начинаются медленнее, а затем просто ускоряются . PyPy отличный.