понедельник, 20 сентября 2010 г.

Исследование решения игры "пятнашки"

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

Хотя алгоритм поиска решения я сделал (он не идеальный, но достаточно хороший для тех условий, в которых он будет применяться), пятнашки затянули, и мне захотелось перебрать
все возможные расстановки пятнашек. Тогда можно было бы, например, проверить,
действительно ли максимум ­– 80 ходов. Так как количество вариантов –– 16! (это
примерно 20,9 триллиона), необходимо либо значительно сократить пространство
перебора (это – интересная задача для математика), либо оптимизировать хранение
информации о пройдённых вариантах. Эта оптимизация мне, как программисту,
показалась очень интересной задачей. Я потратил достаточно много времени на
неё, но пока не сделал. Так как практического смысла в ней уже нет, я её
отложил и ради развлечения перебрал все варианты для варианта пятнашек 4 на 3.
Т.е. когда необходимо собрать поле


1

2


3

4

5


6

7

8

9

10

11




Результатами этого эксперимента я и хочу поделиться.

Итак, для пятнашек 4*3 существует 12! вариантов, это чуть больше 479 миллионов. Ровно для половины этих вариантов не существует решения, так как у них другая чётность, чем у комбинации, приведённой выше. При таком количестве вариантов достаточно было завести три битовых массива по 60 МБ и реализовать функции для кодирования расстановки числом и
раскодирования обратно. Для задачи 4*4 я пробовал разные варианты такой функции, чтобы добиться большей локальности, т.е. чтобы расстановки, получаемые за один ход из текущей имели коды, как можно более близкие числовые к коду текущей расстановки. Для 4*3 это не имеет существенного значения. Главное, чтобы любое число от 0 до 12!-1 соответствовало одной своей комбинации.

Поиск шёл в ширину, начиная с расстановки-решения.

Максимальное количество ходов, необходимое для решения любой комбинации правильной чётности оказалось равно 53. Достаточно неплохо, учитывая, что максимум суммы расстояний от каждой плашки до её места в решении равен 37. Т.е. если можно было бы каждый ход перемещать любую плашку на одну клетку не взирая на то, что клетка занята, то максимальное количество ходов было бы 37.

Количество вариантов, решаемых за n и менее шагов (обозначим его S(n)), при увеличении n
сначала растёт быстро, затем всё медленнее: до 5 шагов – в два и более раза за шаг, до 27 шагов – в 1.5 и более раза. Если обозначить количество вариантов, которые можно решить ровно за n шагов за С(n), то максимум C(n) будет около 22 миллионов. N при этом равно 36. Меня это удивило, я думал будет симметрично, т.е. С(n) будет равно C(nmax- n).

Для пятнашек 4*4 S(n) растёт быстрее, чем степень двойки довольно долго – до 13 шага включительно. Мне удалось построить варианты для 4*4 до 29-го шага. Там S(29) равно примерно 822 миллионам, S(28) – 465 млн., т.е. в 1.74 раза меньше.

Количество комбинаций, решаемых за 53 хода – не 1, как я предполагал, а 18. У всех у них сумма расстояний по горизонтали от каждой плашки до её места в решении равна 21 (максимально возможное – 22).

До 28 шагов включительно попадаются комбинации, в которых сумма расстояний по вертикали от каждой плашки до её места в решении равно 4. Например, надо 28 шагов чтобы решить


5

2

3

8

1

6

7


4

9


10

11




В общем, вот, такая занимательная задачка и такие занимательные результаты. Если у кого есть идеи, как за разумное время перебрать варианты для 4*4 – интересно было бы услышать. Мне удалось придумать только как сократить количество вариантов с 20,9 до 6,5 триллионов. Соответственно, для перебора понадобится 1,6 терабайта памяти. Если бы удалось придумать хорошую функцию перестановка -> число, которая обеспечила бы близкие значения для близких перестановок, можно было бы хранить данные на диске без больших потерь в производительности. Кто что может предложить?
Михаил Машуков. 
Так же см. https://docs.google.com/document/pub?id=1Z3wx4s4lHqJ656iXmDNdUuLNR_MkIAb-qRFodh-UA8c

2 комментария:

  1. приветствую.. очень бы хотелось узнать об этом поподробнее, в частности, какие структуры и типы данных были использованы, а то мой вариант структуры занимает сегодня 18Б (на один узел) и при таком размере я не могу выйти даже на 25 уровней.. начинал же я с 44Б на узел.. использую деревья, а альтернативу я пока не нашёл.. думаю, как структуру сохранять в файл, вероятно, что этот вариант может чем-то мне помочь..

    ОтветитьУдалить
  2. отбой.. :) задачу решил заменой одной проблемы другой.. память не использую вообще (5МБ на всю программу).. будет интересно - пиши.. :) всех благ..

    ОтветитьУдалить