Мы продолжаем рассматривать темы искусственного интеллекта в приложениях к решению сложных задач. Сегодня мы поговорим об известной игре — Ханойская Башня. Смысл этой игры состоит в том, что имеется три штыря, на первом штыре нанизано несколько дисков разной ширины в виде пирамидки:

hanoi0

Задача состоит в том, чтобы перемещая по одному диску, придти к состоянию, когда все диски находятся на правом штыре:

hanoi1

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

Для трех дисков — эта задача может быть решена минимум за 7 шагов.

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

Добавим очевидное интеллектуальное правило — стараться не делать шагов, которые приводят к ситуациям, в которых мы уже были. Этот подход позволяет избежать ситуаций «туда-сюда», и заставляет программу искать в глубину дерева решений. В результате — мы получаем значительно меньше количество ходов, но все равно можно видеть, как программа «отворачивается» от выигрышных позиций.

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

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

Скачать работающую программу можно по ссылке Hanoi.exe, а исходные тексты на языке C# можно скачать по ссылке Hanoi.rar