В комментариях к моему посту про курс 6.002x MITx мне задавали вопрос — пригодилось ли изученное в жизни. И я отвечал — да, конечно, вот тут утром пока зубы чистил, RC-константу посчитал… Но пруфов не было. С тех пор я закончил еще два курса — UC Berkeley CS188.1x Introduction to Artificial Intelligence (открыта регистрация на 18 февраля) и MITx: 6.00x Introduction to Computer Science and Programming. И если после CS188.1x я просто был полон эмоций и не знал, куда бы приткнуть свежеполученные знания (кроме как решить задачу о ходе коня), то после прохождения 6.00x подвернулся случай блеснуть.
Дело в том, что я скачал в аппсторе набор головоломок Игры разума. И безнадежно застрял на уровне «Китайские шашки». Можно было найти прохождение в интернете, но это больше не наш метод. Теперь мы сами с усами. Мир никогда больше не будет прежним.
Китайские шашки
Есть поле, на поле стоят фишки. Одна из клеток — пустая. Мы можем перемещаться только съедая шашку на соседней клетке, перепрыгивая через нее. По диагонали кушать шашки нельзя. Исходное состояние:
o o o
o o o
o o o o o o o
o o o . o o o
o o o o o o o
o o o
o o o
Следующий ход возможен, например, такой:
o o o
o o o
o o o o o o o
o . . o o o o
o o o o o o o
o o o
o o o
Вот такая простенькая задача. Хе-хе, было подумал я, минуты три на решение. Через несколько дней я крепко чесал в затылке и пытался родить какую-нибудь действующую тактику. Задача, ****, не решалась. Придется применять питон.
Из курсов я вынес, что во всех поисковых задачах нужно решить всего три подзадачи (господи, кому я это рассказываю — это ж, наверное, азы):
- Закодировать состояние системы
- Проверить, является ли определенное состояние решением
- Сгенерировать следующие состояния
Что-то бился я, бился с кодированием состояния, и в итоге остановился на простой строке в 49 символов длинной:
initState = ' ooo '+' ooo '+'ooooooo'+'o..oooo'+'ooooooo'+' ooo '+' ooo '
Это сильно облегчает решение первого пункта, но грозит проблемами третьем. Ну и ладно. В общем, как нас и учили, пишем класс Problem:
class Problem(object):
def __init__(self, initState):
self.initState = initState
def isGoal(self, state):
if state.count('o') > 1:
return False
else: return True
def generateSuccessors(self, state):
res = []
idx = 0
for c in state:
if c == '.':
##we can move here
res += self.getValidMoves(state, idx)
idx += 1
return res
def getValidMoves(self, state, idx):
res = []
## get North:
if idx in [16,17,18,23,24,25,28,29,30,31,32,33,34,37,38,39,44,45]:
sN = state[:]
if sN[idx-7] == 'o':
if sN[idx-14] =='o':
sN = sN[0:idx-14]+'.'+sN[idx-13:idx-7]+'.'+sN[idx-6:idx]+'o'+sN[idx+1:]
res.append(sN)
## get South:
if idx in [2,3,4,9,10,11,14,15,16,17,18,19,20,23,24,25,30,31,32]:
sS = state[:]
if sS[idx+7] == 'o':
if sS[idx+14] =='o':
sS = sS[0:idx]+'o'+sS[idx+1:idx+7]+'.'+sS[idx+8:idx+14]+'.'+sS[idx+15:]
res.append(sS)
## get West:
if idx in [4,11,16,17,18,19,20,23,24,25,26,27,30,31,32,33,34,39,46]:
sW = state[:]
if sW[idx-1] == 'o':
if sW[idx-2] =='o':
sW = sW[0:idx-2]+'..o'+sW[idx+1:]
res.append(sW)
## get East:
if idx in [2,9,14,15,16,17,18,21,22,23,24,25,28,29,30,31,32,37,44]:
sE = state[:]
if sE[idx+1] == 'o':
if sE[idx+2] =='o':
sE = sE[:idx]+'o..'+sE[idx+3:]
res.append(sE)
return res
def printState(self, state):
res = ''
for x in range(7):
for y in range(7):
res += state[x*7+y]+' '
res+='rn'
print res
Фактически здесь мы определяем начальное значение системы при инициализации проблемы и определяем методы для решения пп 2 и 3. На наше счастье, проверить любое состояние на то, является ли оно решением, предельно просто — считаем, сколько фишек осталось на доске — если больше одной, то надо еще поработать.
А вот с генерацией валидных следующих ходов я немножко помучился, так как строка одномерна, а доска двумерна. И надо это как-то приводить друг к другу. Возможно, даже скорее всего, я набыдлокодил, но в свое оправдание хочу сказать, что я, кажется, смог применить принцип KISS, про который так много читал на хабре. А поэтому идем по доске, на каждой пустой клеточке смотрим по всем направлениям — есть ли две фишки в том направлении. Если да — то заменяем те фишки пустыми местами, а само пустое место — фишкой. И отдаем, как следующий ход.
Несколько наблюдений:
- В этой задаче решение находится всегда на дне графа. А значит breadth-first search всегда будет максимально долгим.
- В этой задаче невозможно прийти в одно из предыдущих состояний. Соответственно можно не париться проверкой на закольцовку графа (см.дальше, все на самом деле интереснее), но просто меня так учили и я это сделал
- К этой задаче не придумывается эвристика. По крайней мере она не придумывается просто. Любой ход приводит к уменьшению количества фишек на 1. Значит можно только по взаимному положению фишек оценить «хорошесть» или «плохость» состояния. А это нетривиально
Поэтому алгоритм будет простенький:
def dfs(p):
fringe = [[p.initState]]
tried = set()
while fringe:
cur = fringe.pop()
tried.add(cur[-1])
for lm in p.generateSuccessors(cur[-1]):
if p.isGoal(lm):
return cur+[lm]
else:
if lm not in tried:
fringe.append(cur+[lm])
return None
Здесь p — это объект класса Problem
p = Problem(initState)
Все готово, запускаем и уходим пить чай. Лет на 12-ть, так как копму предстоит перебрать в самом худшем случае 2^32 комбинаций. Тут я схитрил и сразу же уменьшил количество комбинаций вдвое, сделав первый ход за компьютер и задав начальным состоянием положение фишек уже после первого хода. Дальше я заметил, что доска — центрально симметричная, а значит всегда будет четыре дублирующихся состояния с учетом поворота доски на 90, 180 и 270 градусов. Чуть усложним проверку на расрытые ноды графа:
def rotateField(field):
res = ''
for i in range(7):
for j in range(7):
res += field[7*j+i]
return res
…
if lm not in tried:
lmr = rotateField(lm)
if lmr not in tried:
if rotateField(lmr) not in tried:
if rotateField(lm) not in tried:
fringe.append(cur+[lm])
Ну и все-таки несколько веток я отрезал, включив проверку на состояние, когда на доске есть фишки, но они гарантированно далеко друг от друга и не смогут друг друга сожрать:
o o o
o o o
. . . . . . .
. . . . . . .
. . . . . . .
o o o
o o o
def checkDeadCombinations(state):
''' False = dead
True - combination is OK'''
if '.'*21 in state:
if '.' in state[:14] and '.' in state[-15:]:
return False
if '.'*21 in rotateField(state):
if '.' in state[:14] and '.' in state[-15:]:
return False
Ну вот, теперь есть надежда, что я доживу до того момента, как комп решит за меня эту задачку :-)
Домино
Предыдущую задачку решил, чем привел жену в восхищение, и тут же уткнулся в следующую. Дана коробка костяшек домино (28 штук, стандартная). Надо выбрать 8 костяшек и сложить их в квадрат 4х4, так что получается два вертикально стоящих ряда по четыре костяшки в каждом.
HHHH HHHH
Суммы по строкам, столбцам и диагоналям должны быть равны шести:
Здесь можно применить поиск решения задачи с ограничениями, но, поняв принцип, я так и не научился реализовывать его в коде. Поэтому будем тупо брутфорсить.
Генерим костяшки:
dices = []
for i in range(7):
for j in range(i,7):
dices.append((i,j))
В итоге имеем лист пар типа (0,0), (1,0) и т.д. для каждой косточки домино.
Поскольку сумма в каждой строке равна шести, строк четыре, то нам нужны все комбинации фишек, дающих в сумме 24. Посидел я, поскрипел мозгами на тему того, как составить все эти комбинации, потом вспомнил, что python comes with batteries included и просто нажал на кнопку включения:
def iterWorkingSets(dices):
for cmb in itertools.combinations(dices, 8):
ds = 0
for dice in cmb:
ds += dice[0]
ds += dice[1]
if ds == 24:
yield cmb
В итоге мы отсеяли все комбинации костяшек, которые гарантированно решения не дадут. Дальше я просто перебрал все комбинации и для каждой комбинации попереставлял костяшки, проверяя, нет ли решения:
def checkArr(arr):
diag = 0
idx = 0
##print arr
for row in arr:
diag += row[idx]
idx += 1
if sum(row) != 6:
#print 'row', idx, 'is not 6'
return False
if diag !=6:
#print 'diag 1 is not 6'
return False
diag = 0
idx = 3
arr = arr.transpose()
for row in arr:
diag += row[idx]
idx -= 1
if sum(row) != 6:
#print 'column', idx, 'is not 6'
return False
if diag != 6:
#print 'diag 2 is not 6'
return False
return True
Решения не было. Я запустил еще раз. Решения не было опять. Если бы я курил, я бы пошел покурить. Что-то тут не то, подумал я. Брутфорсер так просто не заборешь, решение быть должно, а значит ошибка в брутфорсере. И стал искать ошибку. Ошибка не находилась. Выпив энное количество кофе, я пошел поиграть в саму игру, чтобы понять — что же я делаю не так. Запустил игру, покидал костяшек на поле и стал их двигать и перевора… ПЕРЕВОРАЧИВАТЬ! Брутфорсер не переворачивал костяшки!
Ой, а как же это, блин, написать? Опять itertools, генерим суперсет для range(6), потом для каждой комбинации прогоняем ее через суперсет, перевертывая костяшки. Ой, мама.
### Я бы никогда не смог так написать
allsubsets = lambda n: list(itertools.chain(*[itertools.combinations(range(n), ni) for ni in range(n+1)]))
for wc in iterWorkingSets(dices):
wc = list(wc)
print 'I here loop through all set of dices that produce 24'
print 'This is comb #', cmbNum, ':'
print wc
cmbNum += 1
for turn in allsubsets(6):
tc = wc[:]
for k in range(6):
if k in turn:
tc[k] = wc[k][::-1]
else:
tc[k] = wc[k]
#print 'This is subcom of comb #', cmbNum, ':'
#print tc
for c in itertools.permutations(tc):
''' I here loop through all re-combinations of the same set'''
allNum = []
for a in c:
allNum+=list(a)
arr = pylab.array(allNum).reshape(4,4)
if checkArr(arr):
print 'Solution:', arr
break
print 'Solution was not found'
Запускаем. Сначала решений нет, так как в сетах присутствуют «тяжелые кости»:
This is comb # 3 :
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 1), (2, 5)]
Solution was not found
Но потом, начиная с энной комбинации, начинают сыпаться решения.
Брутфорсер получился меееедленный, но рабочий.
Ну вот и все. Теперь, если вы спросите меня, пригодились ли мне курсы edx в жизни, я гордо отвечу «Да!» и дам ссылку на эту статью.
Автор: imwode
