Программирование приложений на android 

Пятнашки, алгоритм решения игры

Пятнашки — это головоломка, которая представляет собой набор из 15 костяшек с числами в квадратной коробке c полем 4x4. Одна ячейка остается пустой.
Цель игры — упорядочить костяшки по номерам, перемещая их в коробке. Желательно сделать как можно меньше перемещений.

Игру Пятнашки ("15 puzzle") изобрёл в 1880 г. Нойес Чэпман (Noyes Chapman).

Под упорядоченным понимаем состояние 1, 2, 3, ... , 15, 0. Его называют терминальным или конечным.



Всего значений - 16 (вместе с нулем), поэтому возможны 16! различных состояний для этой игры. 20 922 789 888 000, в общем 21 триллион состояний. Но оказывается не всякое состояние можно привести к терминальному.

[внешняя ссылка]

Пусть дана некоторая позиция на доске:



где один из элементов равен нулю и обозначает пустую клетку .
Рассмотрим перестановку:



(т.е. перестановка чисел, соответствующая позиции на доске, без нулевого элемента)
Обозначим через N количество инверсий в этой перестановке (т.е. количество таких элементов и , что , но ).

Далее, пусть K — номер строки, в которой находится пустой элемент



Тогда, решение существует тогда и только тогда, когда N + K чётно.

Короче говоря только половину возможных состояний игры можно привести к терминальному состоянию

Согласно правилам мы можем изменять состояние игры перемещая фишки на свободное место. Из такого вот состояния нельзя перейти в терминальное по правилам игры.



Поменяли местами фишки 14 и 15

У пятнашек есть очевидное "тупое" решение - методом перебора. Его называют - поиск в ширину.

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



На рисунке изображена игра 3*3

В чем наша "фишка" ?

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

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

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

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

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

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

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

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

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

У "реальных" узлов есть дочерние узлы на дереве состояний, у "виртуальных" потомков нет.

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

Собственно "перескок". На дереве он осуществляется легко. Каждый раз при определении очередного хода мы анализируем состояние дочерних узлов текущего состояния. Но выбор осуществляется не только среди них, а среди всех "нераскрытых" узлов дерева. То есть всех узлов для которых еще не определенны потомки.

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

Вот собственно и весь алгоритм. Теперь можно заняться реализацией.

Статья, реализация на java

[внешняя ссылка]

Немножко разберем код программы

Начнем сначала. Класс State. Код можно здесь посмотреть

[внешняя ссылка]

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

Каждый экземпляр объекта State состоит из двух состояний, получается вложенная структура. То есть каждый State хранит в себе все состояния начиная от своего и кончая стартовым. Получается "матрешка", расход памяти большой.

Далее уже в классе FifteenState описываем процедуру которая определяют состояние игрового поля для экземпляра класса. Метод setField()

нужен пример на коленке
Хеллоу ворд!
:)
тут какойто копипаст сплошной

А что именно не нравится ? Вроде бы все просто

Что происходит когда мы вызываем метод contains()?

Язык Java использует оператор == для сравнения объектов в списке с указанным объектом. Если он находит соответствие, метод возвращает значение true; в противном случае возвращается false. Поскольку мы сравниваем примитивы, он может найти соответствие, основанное на целочисленных значениях (помните, что оператор == сравнивает примитивы по их значению).

Это хорошо для примитивов, но что если мы хотим сравнить содержимое объектов? Оператор == не сделает это. Для сравнения содержимого объектов мы должны перегрузить метод equals() класса. Это означает, что нужно создать метод с точно такой же сигнатурой, что и у метода одного из ваших суперклассов, но реализовать метод по другому. Если сделать это, вы сможете сравнивать содержимое двух объектов

[внешняя ссылка]

Для того чтобы сравнивать между собой объекты TState переопределен метод equals

Код:

@Override     public boolean  equals(Object obj) {         if (obj == null || !(obj instanceof FifteenState)) {             return false;         }         return hash == obj.hashCode();     }

и определено значение для поля hash

Код:

public void setField(byte[] field) {         this.field = field;         hash = Arrays.hashCode(field);     }

Это сделано в классе FifteenState

[внешняя ссылка]

Что есть рациональное поведение в игре "Пятнашки"?

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

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

я пилять два дня разбирался как на яве под андроид прокручиваемый список сделать :)))) среда разработки Эклипс
а тут пятнашки :)))))

Я от "Пятнашек" - балдею и тащюсь

Назовем решением игры последовательную запись состояний от начала до конца.

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

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

Каждое состояние в игре может иметь от двух до четырех возможных связанных с ним продолжений.

Еще одно замечание можно сделать к процессу игры.

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

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

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

Линия выходит из "старшего" состояния и входит в "младшее" состояние.

"Старшее", это которое поближе к корню дерева, начальному состоянию поиска.

Направление поиска определяется выбором среди узлов дерева (состояний), которые не имеют исходящих линий.

Среди всех возможных путей надо выбрать один узел. Вопрос выбора решается вычислением веса для всех "концевых" состояний. Вес состояния это g+h. Где g - расстояние от узла до корня дерева (начального состояния игры), h - количество фишек не на своих местах

Создание консольного проекта в Eclipse

[внешняя ссылка]



Вывод результата. Первый массив - начальное состояние, последний - конечное

Код:

1   2   7   3    5   6   11   4    9   10   0   8    13   14   15   12    1   2   7   3    5   6   0   4    9   10   11   8    13   14   15   12    1   2   0   3    5   6   7   4    9   10   11   8    13   14   15   12    1   2   3   0    5   6   7   4    9   10   11   8    13   14   15   12    1   2   3   4    5   6   7   0    9   10   11   8    13   14   15   12    1   2   3   4    5   6   7   8    9   10   11   0    13   14   15   12    1   2   3   4    5   6   7   8    9   10   11   12    13   14   15   0

Зависимость производительности поиска от точности эвристической функции

[внешняя ссылка]

Эвристики для игры "Пятнашки"

[внешняя ссылка]