Интеллектуальные системы. Алгоритм A* и игра "Пятнашки"

четверг, 22 марта 2012 г.
Повседневная работа современного программиста редко открывает простор для развития творческого мышления. Чаще всего, для решения задач нам достаточно применить проверенное временем решение: паттерн или библиотеку. Знание общепризнанных подходов и практик, библиотек и фреймворков, вот что сегодня является признаком квалификации программиста.

Между тем, красота и волшебство программирования для многих (я уверен, что не одинок в этом) в полной мере раскрывается в решении сложных алгоритмических задач, так редко встречающихся в повседневной практике. И раз уж "гора не идет к Магомету", то Магомет придумает себе задачку самостоятельно!


В качестве задачки для разминки мозгов, я предлагаю попытаться научить компьютер собирать известную головоломку "Пятнашки".

Пятна́шки — популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина стороны коробки в четыре раза больше длины стороны костяшек для набора из 15 элементов (и в три раза больше для набора в 8 элементов), соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры — перемещая костяшки по коробке добиться упорядочивания их по номерам, желательно сделав как можно меньше перемещений.

Ключом, к решению поставленной задачи, станет известный алгоритм поиска по первому наилучшему совпадению на графе А*. Чтобы несколько упростить изложение задачи, я буду рассматривать головоломку с полем размером 3 х 3.

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

Для решения задачи поиска терминальной вершины на графе можно использовать алгоритмы полного перебора (поиск в глубину или ширину), но количество возможных решений(возможных перестановок) скорее всего окажется на столько велико, что результат полного перебора не удастся увидеть до пенсии.

Алгоритм A* позволяет существенно сократить количество состояний для перебора, путем применения некоторой дополнительной информации, эвристики. В качестве такой информации предлагается брать предполагаемое количество перестановок, необходимых для получения терминального состояния.

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

Алгоритм A* предполагает наличие двух списков вершин графа: открытого и закрытого. В первом находятся вершины, еще не проверенные алгоритмом, а во втором те вершины, которые уже встречались в ходе поиска решения.

На каждом новом шаге, из списка открытых вершин выбирается вершина с наименьшим весом. Вес (F) каждой вершины вычисляется как сумма расстояния от начальной вершины до текущей (G) и эвристическое предположение о расстоянии от текущей вершины, до терминальной (H).  Fi = Gi + Hi, где i - текущая вершина (состояние игрового поля).

Для "Пятнашек" можно сделать предположение, что для достижения терминальной вершины, необходимо выполнить перемещений не меньше, чем количество костяшек, находящихся не на своих местах, а расстояние от начальной вершины до текущей рассчитывать как количество сделанных перестановок:
Далее, для выбранной вершины порождаются дочерние вершины(состояния, которые могут быть получены перемещением костяшек на пустую клетку). Каждая вершина имеет ссылку на родительскую, т.е. "помнит" из какого состояния в нее перешли.

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

Последовательность действий повторяется, пока в списке открытых вершин есть хотя бы одна вершина или пока в ходе выполнения алгоритма не встретится терминальная вершина.

Решение на Java.

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

В первую очередь, задачи, решаемые алгоритмом А*, отличаются определением вершин графа(или состояниями). Введем абстрактный класс, инкапсулирующий общее, для любых вершин, поведение:


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


Основываясь на подобных абстракциях, можно реализовать алгоритм А* следующим образом:

package ru.dokwork.algorithms.astar;

import java.util.*;

/**
 * Реализует алгоритм поиска решения А*.
 */
public class Astar <TState extends State, TRules extends Rules<TState>> {

    /**
     * Применяет алгоритм А* для поиска крадчайшего пути до терминального
     * состояния от указанного.
     *
     * @param startState - начальное состояние.
     * @return последовательность состояний от заданного до терминального.
     */
    public Collection<State> search(TState startState) {
        LinkedList<TState> close = new LinkedList<TState>();
        LinkedList<TState> open = new LinkedList<TState>();
        open.add(startState);
        startState.setG(0);
        startState.setH(rules.getH(startState));

        while (!open.isEmpty()) {
            TState x = getStateWithMinF(open);
            if (rules.isTerminate(x)) {
                closedStates = close.size();
                return completeSolution(x);
            }
            open.remove(x);
            close.add(x);
            List<TState> neighbors = rules.getNeighbors(x);
            for (TState neighbor : neighbors) {
                if (close.contains(neighbor)) {
                    continue;
                }
                int g = x.getG() + rules.getDistance(x, neighbor);
                boolean isGBetter;
                if (!open.contains(neighbor)) {
                    neighbor.setH(rules.getH(neighbor));
                    open.add(neighbor);
                    isGBetter = true;
                } else {
                    isGBetter = g < neighbor.getG();
                }
                if (isGBetter) {
                    neighbor.setParent(x);
                    neighbor.setG(g);
                }
            }
        }
        return null;
    }

    /**
     * Создает объект для поиска терминального состояния по указанным правилам.
     *
     * @param rules правила, в соответствии с которыми будет производиться поиск
     *              терминального состояния.
     */
    public Astar(TRules rules) {
        if (rules == null) {
            throw new IllegalArgumentException("Rules can`t be null.");
        }
        this.rules = rules;
    }

    /**
     * Находит вершину в списке open с наименьшим значением веса.
     *
     * @param open список открытых вершин.
     * @return вершину с наименьшим весом.
     */
    private TState getStateWithMinF(Collection<TState> open) {
        TState res = null;
        int min = Integer.MAX_VALUE;
        for (TState state : open) {
            if (state.getF() < min) {
                min = state.getF();
                res = state;
            }
        }
        return res;
    }

    /**
     * Составляет последовательность состояний пройденных от начального
     * состояния до конечного.
     *
     * @param terminate найденное конечное состояние.
     * @return последовательность состояний пройденных от начального
     * состояния до конечного.
     */
    private Collection<State> completeSolution(TState terminate) {
        Deque<TSate> path = new LinkedList<TState>();
        State c = terminate;
        while (c != null) {
            path.addFirst(c);
            c = c.getParent();
        }
        return path;
    }

    private TRules rules;
}
Данное решение несколько не оптимально. Наверняка вы заметили, что информация в списке закрытых вершин избыточна: нас никогда не интересуют детали вершин из этого списка, а только факт принадлежности некоторой вершины к нему. Для этого достаточно хранить не сами вершины, а значения их хеш функций.

Теперь, что касается реализации непосредственно пятнашек. Я не стану приводить здесь весь исходный код, его вы можете посмотреть в репозитории на bitbucket. Остановлюсь только на интересных, на мой взгляд, вещах.

Во первых, само игровое поле удобно представить одномерным массивом, это позволит избежать лишних вложенных циклов и в целом упростит решение. Алгоритм раскрытия вершины (получение ее потомков), в таком случае, получается достаточно прост. Вначале находится индекс пустой клетки, затем вычисляется индекс кости, которая будет перемещена на пустую клетку. Ее индекс вычисляется как сумма индекса пустой клетки и индекса одного из ее соседей. Индексы соседних клеток элементарны: для соседа слева это -1, для соседа справа +1, для соседа сверху -(размер поля), для соседа снизу +(размер поля):

actions = new int[]{-sideSize, sideSize, -1, 1};

/* Выполняется поиск пустой клетки */
int zero = 0;
for (; zero < field.length; zero++) {
    if (field[zero] == 0) {
        break;
    }
    if (zero >= field.length) {
        return null;
    }
}
/* Вычисляется индекс перемещаемой клетки */
int number = zero + action;
/* Проверяется допустимость хода */
if (number < 0 || number >= field.length) {
    return null;
}
if ((action == 1) && ((zero + 1) % sideSize == 0)) {
    return null;
}
if ((action == -1) && ((zero + 1) % sideSize == 1)) {
    return null;
}
/*
 * Создается новый экземпляр поля, на котором меняются местами пустая и
 * перемещаемая клетки
 */
byte[] newField = Arrays.copyOf(field, field.length);
byte temp = newField[zero];
newField[zero] = newField[number];
newField[number] = temp;

return newField;
Во вторых, для генерирования начального состояния, первое, что обычно приходит на ум - это случайное расположение клеток на игровом поле. Но у этого подхода есть существенный недостаток. Если вы уже заглядывали на вики, то знаете, что ровно половину из всех возможных начальных положений пятнашек невозможно привести к собранному виду. То есть, при таком подходе, вы рискуете сгенерировать такое начальное состояние, решение для которого не существует вообще, или поиск решения затянется на неприлично длительное время. Чтобы не портить себе впечатление от проделанной работы, можно пойти другим путем: можно выполнять N случайных, корректных перестановок костяшек, начиная с терминального состояния. Такой подход гарантировано предоставит начальное состояние, обладающее решением и позволит регулировать сложность его поиска:
byte[] generateStartState(FifteenRules rules, int swapCount) {
    int stepCount = swapCount;
    byte[] startState = rules.getTerminateState();

    int[] actions = rules.getActions();
    Random r = new Random();
    while (stepCount > 0) {
        int j = r.nextInt(actions.length);
        byte[] state = rules.doAction(startState, actions[j]);
        if (state != null) {
            startState = state;
            stepCount--;
        }
    }
    return startState;
} 

UPD:  По настоятельной просьбе анонимного читателя, я опишу второй, казалось бы очевидный, способ генерирования начального состояния.

Чтож, остальные детали реализации не должны вызывать трудностей. Однако, хочу заметить, что предложенная эвристика далека от совершенства. Ее можно усовершенствовать, что позволит сократить количество раскрываемых алгоритмом вершин и, соответственно, ускорить его работу. Буду рад увидеть ваши предложения по развитию эвристической оценки в комментариях.

Опробовать решение в действии: FifteenPuzzle.jar.

$ java -jar FifteenPuzzle.jar -h


По мотивам лекций по курсу "Интеллектуальные системы".
                                                    Выражаю личную благодарность Копылову Андрею Валерьевичу, за интересное изложение курса.

28 комментариев :

  1. Очень "интересный" (в кавычках) способ вы предложили для того, чтобы избежать "нерешаемой" начальной раскладки.

    Очень непрофессионально "выполнять N случайных, корректных перестановок костяшек, начиная с терминального состояния" при том, что в той же статье на вики указана формула "критерия собираемости".

    ОтветитьУдалить
  2. И ещё - http://s017.radikal.ru/i409/1208/e7/815ccb05be89.jpg

    ОтветитьУдалить
    Ответы
    1. Интересные замечания. Спасибо) По поводу способа генерирования начального состояния, вам никто не мешает пойти "профессиональным" путем, мне же это (сама задача порождения начального состояния с ответом) не показалось интересным. А вот в картинке Вы, пожалуй, не правы. Движение ряда за раз - это иллюзия, создаваемая настоящими, физическими пятнашками. На самом деле проще рассматривать такой ход как совокупность нескольких. Впрочем, это дело вкуса и не более чем условность.

      Удалить
  3. Можно узнать, почему картинке в первом состоянии, когда не сделано ни одно перемещение(G = 0), H = 5?

    ОтветитьУдалить
    Ответы
    1. Потому, что не на своих местах находятся костяшки 3, 4, 5, 7 и 0. Считать ли 0 за костяшку, на мой взгляд дело каждого, на конечный результат это сказаться не должно.

      Удалить
  4. А может быть и ветвление на три подальших расматриваемых вариантов ?

    ОтветитьУдалить
  5. Этот комментарий был удален автором.

    ОтветитьУдалить
  6. Попробуйте другой критерий определения веса вершины. Не количество костяшек, находящихся не на своих местах, а суммарный путь, который нужно пройти каждой костяшке до своего места. (Для первой вершины из вашего примера H=10) Я устраивал соревнования своего и вашего алгоритмов, разница в числе вершин, которые надо обработать, доходила до порядка. Пятнашка 4x4, тридцать ходов перемешивания (да, я тоже перемешивал случайными ходами):
    мой алгоритм
    Открытый список - 1668
    Закрытый список - 1753
    ваш алгоритм
    Открытый список - 22317
    Закрытый список - 22452

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

      Удалить
  7. Извините, ошибся, H=12. Я не посчитал пустую костяшку, которой идти два шага до своего места в правом нижнем углу.

    ОтветитьУдалить
  8. Реализация на С++ https://gist.github.com/sunloverz/7338003

    ОтветитьУдалить
  9. Скажите мне пожалуйста, а вы вообще пробовали использовать ваш алгоритм на традиционном размере доски, то есть 4х4? Потому что я написал алгоритм А*, используя эвристику не просто "количества костяшек не на своих местах" а совокупный анализ манхэттенского расстояния и линейного конфликта (https://sites.google.com/site/killgamesh666/alghorytms/tag15), и всё равно результаты были неутешительными. При количестве перестановок больше 3-х, программа зависала на полминуты, после чего выдавала сообщение о том, что массив закрытых вершин переполнен (и это при том, что он состоит из 10000 элементов).
    К счастью, решение проблемы имеется - использовать вместо А* IDA*. Суть в том, что это тот же А*, но использующий метод итеративного углубления, реализуемый рекурсивной функцией поиска и постепенно растущим оценочным порогом. Его главное преимущество - массивы открытых и закрытых вершин ему вообще не нужны, а потому он щёлкает пятнашки 4х4 как орехи до тех пор, пока перестановки находятся в районе 30-50. Его главный недостаток - он не всегда находит кратчайшее решение, хотя как правило оно довольно близко к нему. Дело в том, что обычно А* используют на двумерных картах, в то время как пятнашки - аналог девятимерной (в вашем случае) и шестнацатимерной (в моём) карт, и количество рассматриваемых вершин быстро достигает астрономических величин в таких размерностях. IDA* же не рассматривает и не оценивает вершины, а просто их пробегает, пока не споткнётся о порог своей оценки.
    Почитать об IDA* можно в википедии http://ru.wikipedia.org/wiki/IDA*#IDA.2A
    Кстати, хоть и чуть-чуть, но ваша статья мне помогла. Именно вы подсказали мне метод генерации карты, основанный на перестановках, а не на чистом рандоме, благодаря чему теперь я могу регулировать сложность =)

    ОтветитьУдалить
    Ответы
    1. "... Его главный недостаток - он не всегда находит кратчайшее решение, хотя как правило оно довольно близко к нему..."

      Ну, алгоритм приведенный тут, тоже не находит кратчайший путь. Точнее найденный им путь не обязательно будет кратчайшим, хоть автор и заявляет обратное ("Применяет алгоритм А* для поиска _крадчайшего_ пути до терминального * состояния от указанного).

      Удалить
    2. Вообще, применяет для поиска, еще не означает что результат будет ожидаемым. С помощью А* я именно _ищу_ кратчайший путь. Не первый попавшийся, а именно кратчайший. То, что результат может отличаться от моих ожиданий, их, ожиданий, не отменяет :)

      Удалить
  10. Скажите пожалуйста, а как не допустить перемещения шашки с четвертой позиции на третью? Т.е.
    1 2
    3 4 5
    6 7 8

    1 2 3
    4 5
    6 7 8

    ОтветитьУдалить
    Ответы
    1. Комент испортился, т.е. вот так:
      1 2 _
      3 4 5
      6 7 8

      1 2 3
      _ 4 5
      6 7 8

      Удалить
    2. Вродебы нашел в вашем коде. Это оно:
      if ((action == 1) && ((zero + 1) % sideSize == 0)) { return null; }
      if ((action == -1) && ((zero + 1) % sideSize == 1)) { return null; }
      ?

      Удалить
    3. лол, сам бы никогда не додумался до такого колдунства. хотя...

      Удалить
    4. Кажется, помощь уже не нужна? =)

      Удалить
    5. да, спасибо, разобрался.

      Удалить
  11. Попробуйте вместо G нолик вставить. У меня в закрытом и открытом списках получается,
    где-то, по 150 - 300 записей, в среднем. Если следующее состояние есть в закрытом или открытом списке, просто его игнорирую. И да, H рассчитываю как сумму расстояний, пройденных каждой костью к своему месту. Бот щелкает головоломку за две секунды :D

    ОтветитьУдалить
  12. "...Полагаться на волю случая мне не по душе, но выбирать тот или иной подход вам."

    В смысле, полагаться на волю случая? Если расположение шашек на поле не валидно, просто поворачиваете поле "набок" (транспонирование матрицы) и получаете валидное состояние. Так что вполне себе нормальный подход ...

    ОтветитьУдалить
  13. в исходниках ошибка разбора командной строки.

    ОтветитьУдалить
  14. Как ввести числа в вашу программу,копируя ваш пример ,все работает и изменяя ваш пример аналогично все работает,а если вводить сразу так с клавиатуры ничего не работает ,почему так ?

    ОтветитьУдалить
    Ответы
    1. Во-первых спасибо. Благодаря Вам я заметил что потерял файл с помощью в выложенном примере :) Но по поводу вашего вопроса ответить не могу, тк не понимаю что именно не получается сделать? Что конкретно происходит?

      Удалить
    2. Подскажите, почему алгоритм зацикливается на таком начальном состоянии:
      9,13,4,2,10,7,6,11,15,5,12,1,14,8,3,0 и при этом проверку на решение проходит.

      Удалить

Ваше мнение мне искренне интересно. Смелее!

Технологии Blogger.