8-головоломка - это простая игра с раздвижными плитками, в которой 8 плиток перемешаны в сетку 3 x 3, и игрок должен перемещать плитки, чтобы привести доску в «целевое состояние».

K-головоломка - это просто обобщение игры с 8 головоломками, где k = n * n-1 и n - ширина и высота доски.

Простота правил в отличие от сложности поиска решения делает его одним из типичных приложений A * search для вводных курсов по искусственному интеллекту. Однако большинство курсов, кажется, вводят только базовые эвристики для решения проблемы, такие как количество неуместных плиток или манхэттенское расстояние, а более информированные эвристики не рассматриваются - реализации найти еще труднее. В этом посте я попытаюсь изучить и объяснить некоторые эвристики, с которыми я столкнулся в своем собственном исследовании и которые показались мне интересными.

Линейные конфликты

2 плитки находятся в линейном конфликте, если обе плитки находятся в своих целевых строках или столбцах, и при одинаковых настройках манхэттенской эвристики они должны проходить друг над другом, чтобы достичь своей конечной целевой позиции. Поскольку мы знаем, что в реальной игре, плитки не могут скользить друг по другу.

Если возникнет такой конфликт, то 1 из плиток нужно будет переместиться из вышеупомянутой строки или столбца и обратно, добавив 2 хода к сумме их манхэттенских расстояний.

Формально, 2 плитки tⱼ и tₖ находятся в линейном конфликте, если tⱼ и tₖ находятся на одной линии, целевые позиции tⱼ и tₖ находятся в этой строке, tⱼ находится справа tₖ, а конечная позиция tⱼ находится слева от целевой позиции tₖ.

Что происходит, когда 3 или более плитки находятся в линейном конфликте?

Поскольку допустимая эвристика дает оптимистичное предположение о фактических затратах на решение головоломки, мы выбираем плитку, участвующую в наибольшем конфликте, и сначала выходим из строки (или столбца). Таким образом мы можем минимизировать количество дополнительных ходов.

Детали реализации

Эвристику линейного конфликта легко описать словами, но сложно описать ее реализацию. Исходный псевдокод находится здесь, но я включу мыслительный процесс, лежащий в основе моей собственной реализации. Поехали.

Во-первых, мы можем исключить проблему, чтобы найти только линейные конфликты подряд. Как только мы сможем это сделать, мы можем просто отобразить эту функцию на общей сетке, чтобы получить все конфликты строк данной доски.

def linear_conflicts(self, grid):
    row_conflicts = [self.line_conflicts(row, i) for i, row in enumerate(grid)]
    col_conflicts = [self.line_conflicts(col, i) for i, col in enumerate(self.transpose(grid))]
    return sum(row_conflicts) + sum(col_conflicts)
def transpose(state):
    width = len(state[0])
    return [[state[j][i] for j in range(width)] for i in range(len(state))]
def line_conflicts(self, line, i):
    .
    .
    .

Для каждой плитки в этом ряду мы перебираем все остальные плитки справа от нее и определяем, есть ли перекрытия на их путях. Если тайл, на котором мы находимся, имеет целевой столбец k, и тайл, с которым мы сравниваем, как целевой столбец j, тогда мы проверяем, j ‹К. (Конечно, никогда не может быть случая, когда j = k, поскольку все плитки имеют разную целевую позицию) Поскольку отношения линейного конфликта симметричны, нам не нужно проверьте левую часть плитки, так как этот случай был бы рассмотрен в предыдущей итерации этого цикла.

# main loop
for index, tile in enumerate(line):
    if tile == 0:
        continue
    x, y = dest(tile)
    if index != x:
        # tile is not in target row
        continue
    for k in range(index + 1, self.n):
        other_tile = line[k]
        if other_tile == 0:
            continue
        tx, ty = dest(other_tile)
        if tx == x and ty <= y:
            # there is a pair in conflict!

Теперь мы можем начать рассматривать линейные конфликты в виде графика. Для каждой пары узлов, участвующих в линейном конфликте, мы добавляем прямую и обратную связь этих двух плиток в список смежности, формируя неориентированный граф конфликтов. Затем мы просто берем узел с наибольшей степенью и удаляем его появление среди всех его соседей, каждый раз увеличивая счетчик на 1. Процесс завершается, когда граф становится пустым.

Чтобы распространить это на конфликты столбцов, мы просто транспонируем двумерный массив, представляющий нашу доску, и запускаем здесь тот же алгоритм. Однако мы должны принять во внимание, что индексы целевой позиции должны быть перевернуты, чтобы учесть транспонирование, то есть ((i, j) - ›(j, i)). Итак, мы модифицируем функцию line_conflict, чтобы она использовала функцию, которая дает нам соответствующие координаты положения цели.

Вот полный код, если вы хотите скопировать макароны.

# self.mapping is a hashtable of tile -> goal positions
# self.mapping = dict()
# for i, row in enumerate(self.goal_state):
#     for j, v in enumerate(row):
#         self.mapping[v] = (i, j)
def line_conflict(self, i, line, dest):
        conflicts = 0
        conflict_graph = {}
        for j, u in enumerate(line):
            if u == 0:
                continue
            x, y = dest(u)
            if i != x:
                continue

            for k in range(j + 1, self.n):
                # opposing tile
                v = line[k]
                if v == 0:
                    continue
                tx, ty = dest(v)
                if tx == x and ty <= y:
                    u_degree, u_nbrs = conflict_graph.get(u) or (0, set())
                    u_nbrs.add(v)
                    conflict_graph[u] = (u_degree + 1, u_nbrs)
                    v_degree, v_nbrs = conflict_graph.get(v) or (0, set())
                    v_nbrs.add(u)
                    conflict_graph[v] = (v_degree + 1, v_nbrs)
        while sum([v[0] for v in conflict_graph.values()]) > 0:
            popped = max(conflict_graph.keys(),
                         key=lambda k: conflict_graph[k][0])
            for neighbour in conflict_graph[popped][1]:
                degree, vs = conflict_graph[neighbour]
                vs.remove(popped)
                conflict_graph[neighbour] = (degree - 1, vs)
                conflicts += 1
            conflict_graph.pop(popped)
        return conflicts
def row_dest(self, v):
    return self.mapping[v]                                                   def col_dest(self, v):
    return self.row_dest(v)[::-1]

Оптимизация

Глядя на пирамиду вложенных циклов, становится очевидным, что эвристика манхэттенского расстояния и эвристика линейного конфликта имеют большую сложность выполнения. С помощью разработки программного обеспечения мы можем сделать это лучше.

Обратите внимание, что за каждый ход меняется только 1 плитка. Что касается суммарного манхэттенского расстояния, мы можем просто вычесть предыдущее манхэттенское расстояние для перемещенного тайла и добавить его новое. Это сокращает предыдущее наивное вычисление с O (n²) до O (1).

Также обратите внимание, что перемещение по строке не разрешает конфликты строк, а перемещение по столбцу не разрешает конфликты столбцов. Таким образом, мы можем сократить проверку конфликтов строк только до затронутого столбца или строки, перпендикулярной направлению движения. Это сокращает время выполнения линейных конфликтов с O (n³) проверок в каждом состоянии до O (n²). Это также избавляет от необходимости транспонировать массив на каждом этапе.

Эвристика последней плитки

Еще одна эвристика, которую мы можем дополнительно накапливать на манхэттенском расстоянии, - это эвристика последнего тайла. Это определяется положением доски на последнем ходу.

Если мы рассмотрим конечное положение доски на рис. 1, то мы, естественно, увидим, что единственные возможные ходы, чтобы добраться туда, включают в себя либо 6, либо 8, находящиеся там, где находится пустая плитка. Теперь, если ни 6, ни 8 не находятся в крайнем правом столбце и самом нижнем ряду, подумайте о манхэттенских расстояниях обоих - это не учитывает тот факт, что одна из плиток должна выходить за пределы своего манхэттенского пути в нижний правый угол. угловой, прежде чем вернуться в исходное положение.

Однако, поскольку только 1 из этих 2 плиток должен находиться в позиции «последней плитки», добавляются только 2 хода.

Хотя эта эвристика может показаться тривиальной, исследования показали, что эта эвристика применима примерно в 60% всех состояний головоломки из 24 состояний.

Стоит отметить, что эта эвристика последнего тайла конфликтует с эвристикой линейного конфликта (ага). Например, если 6 находится в линейном конфликте с 5 в среднем ряду для головоломки с 8, 6 может переместиться вниз по строке, чтобы позволить 5 пройти, что означает, что добавление последней эвристики плитки удвоит подсчет дополнительных ходов 6.

Эвристика угловой плитки

Последняя эвристика, которую я собираюсь рассмотреть, - это эвристика угловой плитки, которая утверждает, что если плитка, примыкающая к плиткам в углу, находится в своей целевой позиции (например, 2 на рис. 1), а угловая плитка занята (или верхний левый угол равен не 1), тогда плитка в позиции должна сместиться в сторону, чтобы позволить угловой плитке войти. Это добавляет 2 хода к манхэттенскому расстоянию.

Думаю, лучше всего это объяснить на примере:

Если вы учитываете движения 1, 2 и «X» в реальных условиях игры, возможно ли загнать плитку 1 в угол, не перемещая 2? Предположим, что «X» перемещается вниз, тогда пустая плитка будет в углу, оставляя только выбор: переместить «X» обратно в угол или переместить 2 в угол.

Интересно, что если и 4, и 2 в позиции, то мы можем добавить 4 хода! Ни одна из плиток не может оставаться на своей целевой позиции, пытаясь втиснуть одну.

В то же время эта эвристика также конфликтует с линейными конфликтами, поскольку смещение угловых плиток может быть дважды засчитано, если оно вовлечено в линейный конфликт. В случае с головоломкой 8 также возможно, что конфликт угловой плитки будет дважды засчитан для 1 и 3, если 2 находится в позиции.

В общем, эвристика угловой плитки имеет слишком много краев, и ее сложно реализовать. Фактически, исследователь, который придумал это, упустил последний угол в этой эвристике, поскольку взаимодействия между позиционированными плитками и последней эвристикой и линейным конфликтом плитки просто слишком сложны. Если вы планируете добиться времени выполнения выше среднего, вероятно, не стоит пытаться кодировать это.

Другая эвристика большого мозга

Все эвристики, которые я рассмотрел до сих пор, не требуют использования дополнительной памяти. Однако можно добиться еще большей производительности, найдя кратчайшие возможные решения для набора состояний и используя фактический ответ в качестве эвристики, если какой-либо из узлов совпадает. Это также известно как база данных шаблонов.

Есть несколько вариантов баз данных шаблонов. Некоторые попытки разделить плату на 2–4 раздела и учитывать только кратчайшие расстояния каждого раздела. Другие попытки использовать динамическое разбиение, чтобы найти наилучшую оценку, рассматривая только пары или тройки плиток по отношению к пустой плитке, и каким-то образом свести проблему к проблеме минимального покрытия вершин. Я не буду вдаваться в подробности, потому что сам этого не совсем понимаю.

Благодарности

Все заслуги принадлежат Ханссон, Майер, Юнг за статью о критике решений расслабленных задач для вывода допустимой эвристики, Корф, Тейлор за их статью по эвристике для 24-головоломки и Фельнеру, Корфу, Ханану за статья по аддитивной эвристике образов, с которой я погрузился в кроличью нору допустимых эвристик для k-головоломки.