Применяем на практике знания, полученные на курсе MIT 6.00x (edx.org)

в 10:08, , рубрики: EdX, python, Алгоритмы, алгоритмы поиска, игры для iphone, Учебный процесс в IT, метки: , , ,

В комментариях к моему посту про курс 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 

Вот такая простенькая задача. Хе-хе, было подумал я, минуты три на решение. Через несколько дней я крепко чесал в затылке и пытался родить какую-нибудь действующую тактику. Задача, ****, не решалась. Придется применять питон.

Из курсов я вынес, что во всех поисковых задачах нужно решить всего три подзадачи (господи, кому я это рассказываю — это ж, наверное, азы):

  1. Закодировать состояние системы
  2. Проверить, является ли определенное состояние решением
  3. Сгенерировать следующие состояния

Что-то бился я, бился с кодированием состояния, и в итоге остановился на простой строке в 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

Источник

Поделиться

* - обязательные к заполнению поля