Я пытаюсь написать решатель на C # .NET для игры под названием Flowerz. Для справки, вы можете сыграть в MSN здесь: http://zone.msn.com/gameplayer/gameplayer.aspx?game=flowerz . Я пишу это для удовольствия, а не для какого-либо задания или чего-либо связанного с работой. Из-за этого единственным ограничением является мой компьютер (ядро Intel i7 с 8 ГБ ОЗУ). Насколько мне известно, ему не нужно никуда бежать.
Короче, его правила таковы:
- Там очередь заполнена цветными цветами. Его длина произвольна
- На очередь нельзя повлиять
- Очередь генерируется в начале уровня
- Цветы имеют один или два цвета.
- Если есть два цвета, то есть внешний цвет и внутренний цвет. В случае двух цветов внешний цвет используется для соответствия.
- Если есть совпадение, то внешний цвет исчезает, и цветок теперь является цветком одного цвета того же цвета, что и внутренний цветок.
- Цель игры - создать спички из трех (или более) одного цвета
- Когда цветок одного цвета является частью матча, он удаляется с игрового поля, создавая пустое пространство
- Вы можете сопоставить один цветной цветок с внешним цветом двухцветного цветка. В этом случае исчезает один цветной цветок, внешний цвет двухцветного цветка исчезает, а внутренний цвет остается
- Вы выигрываете раунд, когда очередь пуста, и осталось хотя бы одно пустое место
- Возможны каскадные матчи. Каскад - это когда три (или более) внешних цветка исчезают, и когда их внутренние цвета образуют другую цепочку из 3 (или более цветов).
- Игровое поле всегда 7х7
- Некоторые места на поле покрыты камнями
- Вы не можете поместить цветы на скалах
- Очередь также может содержать лопату, которую можно использовать для перемещения любого размещенного цветка в незанятое пространство.
- Вы должны использовать лопату, но на самом деле вам не нужно перемещать цветок: совершенно законно положить его обратно туда, откуда он пришел
- Очередь также может содержать цветную бабочку. Когда вы используете эту бабочку на цветке, тогда цветок приобретает цвет бабочки
- Применение бабочки к цветку с двумя цветами приводит к тому, что цветок приобретает только один цвет, а именно цвет бабочки.
- Вы можете тратить бабочки на пустое место или цветок, который уже имеет этот цвет
- Очистка поля не выигрывает игру
Задача решателя проста: найти способ очистить очередь, используя как можно больше оставшихся пробелов на игровом поле. По сути, ИИ играет в эту игру для меня. Результатом решателя является список найденных ходов. Меня не интересует оценка, но выживание как можно дольше, поэтому мне интересны ходы, которые оставляют как можно больше открытых пространств.
Излишне говорить, что пространство поиска быстро увеличивается с увеличением очереди, поэтому о грубой силе не может быть и речи. Очередь начинается с 15 и увеличивается с 5 каждые два или три уровня, если я правильно помню. И, конечно же, размещение первого цветка в (0,0), а второго в (0,1) отличается от размещения первого в (1,0) и второго цветка в (0,0), особенно когда поле уже заполнено цветами из более раннего раунда. Такое простое решение может иметь значение при принятии или нет.
У меня есть следующие вопросы:
- Что это за проблема? (подумайте о коммивояжере, рюкзаке или о какой-то другой комбинаторной проблеме). Знание этого может сделать мой Google-фу чуть лучше.
- Какой алгоритм может дать мне хорошие результаты, быстро?
Что касается последнего: сначала я пытался написать свой собственный эвристический алгоритм (в основном: как бы я решил его, если бы знал очередь?), Но это приводило ко многим крайним случаям и подсчету совпадений, которые я мог бы пропустить.
Я думал об использовании генетического алгоритма (потому что я, по крайней мере, знаю, как его использовать ...), но у меня возникают некоторые проблемы с выбором двоичного представления платы. Тогда есть проблема кроссовера, но она может быть решена с помощью упорядоченного оператора кроссовера или аналогичного типа операции.
Я предполагаю, что решатель всегда должен знать конфигурацию платы и очередь, которую он пытается очистить.
Я знаю несколько других эвристических алгоритмов, таких как нейронные сети и системы нечеткой логики, но мне не хватает опыта, чтобы знать, какой из них лучше всего подходит, или есть другие, которые лучше подходят для поставленной задачи.
Ответы:
На первый взгляд , мне кажется, это проблема поиска одного агента . То есть: у вас есть один агент (ИИ «игрок»). Существует игровое состояние, представляющее состояние игрового поля и очереди, и у вас есть функция-преемник, которая может генерировать новые состояния из данного состояния.
Есть также критерий цели, который говорит вам, когда состояние является «решенным» состоянием. А стоимость пути - стоимость перехода в заданное состояние (в данном случае всегда «1 ход»).
Одной из типичных головоломок такого типа является 15 Puzzle . И типичный способ ее решения - это информированный поиск - например, классический эвристический поиск A * и его варианты.
Однако есть проблема с этим на первый взгляд подходом. Алгоритмы типа A * предназначены для того, чтобы дать вам кратчайший путь к цели (например, наименьшее количество ходов). В вашем случае, количество ходов всегда фиксировано - нет кратчайшего пути - так эвристический поиск будет просто дать вам на пути к более завершенной игре.
То, что вы хотите, это последовательность ходов, которая дает вам наилучшее завершенное состояние игры.
Итак, что вы должны сделать, это немного перевернуть проблему. Вместо игрового поля, являющегося «состоянием», последовательность ходов становится «состоянием». (То есть: поместить элементы в очередь в позиции «D2, A5, C7, B3, A3, ...»)
Это означает, что нам все равно, как генерируются эти состояния. Сама доска является второстепенной, требуется только для оценки качества данного состояния.
Это превращает проблему в задачу оптимизации , которая может быть решена с помощью локального алгоритма поиска (который в основном означает создание состояний вокруг заданного состояния и выбор наилучшего состояния, не заботясь о пути между состояниями.)
Прототипом головоломки такого рода является головоломка « Восемь королев» .
В этом классе задач вы ищете пространство состояний, чтобы найти хорошее решение, где «хорошо» оценивается целевой функцией (также называемой функцией оценки или, для генетических алгоритмов, функцией пригодности ).
Для вашей задачи целевая функция может возвращать значение от 0 до N для количества элементов в очереди, которые были израсходованы до достижения состояния сбоя (где N - длина очереди). И, в противном случае, значение N + M, где M - количество пробелов, оставшихся на доске после того, как очередь пуста. Как таковое - чем выше значение, тем «объективно лучше» решение.
(Стоит отметить, что на данный момент вы должны оптимизировать дерьмо из кода, запускающего игру - который превращает состояние в готовую доску, которую можно использовать для целевой функции.)
Что касается примеров локальных алгоритмов поиска : Базовая схема - это поиск с подъемом на холм, который принимает данное состояние, изменяет его и перемещается к следующему состоянию, которое дает лучший результат.
Очевидно, что это может застрять в локальных максимумах (и тому подобное). В этой форме это называется жадным локальным поиском . Существует множество вариантов решения этой и других проблем (в Википедии вы уже рассмотрели ). Некоторые из них (например, локальный поиск луча ) отслеживают сразу несколько состояний.
Одним из конкретных вариантов этого является генетический алгоритм ( Википедия ). Основные шаги для генетического алгоритма:
Генетический алгоритм решение чувствует , как он может быть подходящим для вашей проблемы - с некоторой корректировкой. Самая большая трудность, которую я вижу, заключается в том, что с приведенным выше строковым представлением вы обнаружите, что переключение хвостовых половин состояний с очень разными передними половинами может привести к «мертвым» состояниям (из-за противоречивых движений между двумя половинами это приводит к в низком фитнес-балле).
Возможно, можно преодолеть эту проблему. Одна мысль, которая приходит на ум, - это повышение вероятности того, что государства с подобными передними половинами станут племенными парами. Это может быть так же просто, как сортировка размножающейся популяции штатов, прежде чем объединить их в пару. Также может помочь постепенное перемещение вероятного положения кроссовера от начала до конца строки по мере увеличения числа поколений.
Также может оказаться возможным представить ходы в состоянии, которое более устойчиво (возможно, даже полностью неуязвимо) к тому, чтобы встретить состояние отказа "квадрат заполнен". Возможно представление ходов в виде относительных координат от предыдущего хода. Или, имея ходы, выберите ближайшее пустое место к данной позиции.
Как и в случае со всеми нетривиальными проблемами ИИ, подобными этой, это потребует значительных усилий.
И, как я уже говорил, другой важной задачей является просто оптимизация вашей целевой функции. Ускорение этого процесса позволит вам выполнять поиск на большом пространстве и искать решения для игр с более длинными очередями.
Для этого ответа, в частности, чтобы понять всю терминологию, мне нужно было найти учебник по искусственному интеллекту университета «Искусственный интеллект: современный подход», разработанный Расселом и Норвигом. Не уверен, что это «хорошо» (у меня нет других текстов ИИ для сравнения), но это не плохо. По крайней мере, он довольно большой;)
источник
Категоризация
Ответ не прост. Теория игр имеет несколько классификаций для игр, но, похоже, не существует четкого соответствия 1: 1 для этой игры специальной теории. Это особая форма комбинаторной проблемы.
Это не коммивояжер, который будет принимать решение о заказе, в котором вы посещаете «узлы» с определенной стоимостью, чтобы добраться до следующего узла из последнего. Вы не можете изменить порядок очереди, и вам не нужно использовать все поля на карте.
Рюкзак не совпадает, потому что некоторые поля становятся пустыми при помещении некоторых предметов в «рюкзак». Так что, возможно, это какая-то расширенная форма, но, скорее всего, из-за этого алгоритмы не будут применимы.
Википедия дает некоторые советы по классификации здесь: http://en.wikipedia.org/wiki/Game_theory#Types_of_games
Я бы классифицировал это как «проблему оптимального управления в дискретном времени» ( http://en.wikipedia.org/wiki/Optimal_control ), но я не думаю, что это поможет вам.
Алгоритмы
Если вы действительно знаете полную очередь, вы можете применить алгоритмы поиска по дереву. Как вы сказали, сложность проблемы растет очень быстро с длиной очереди. Я предлагаю использовать алгоритм типа «Поиск в глубину (DFS)», который не требует большого количества памяти. Поскольку для вас значение не имеет значения, вы можете просто остановиться, найдя первое решение. Чтобы решить, какую ветвь искать сначала, вы должны применить эвристику для упорядочения. Это означает, что вы должны написать функцию оценки (например: количество пустых полей; чем сложнее это поле, тем лучше), которая дает оценку, чтобы сравнить, какой следующий шаг является наиболее перспективным.
Тогда вам нужны только следующие части:
Вот неполная справочная реализация для поиска в глубину:
Этот код не проверен на работоспособность, не является ни компилируемым, ни полным. Но это должно дать вам представление, как это сделать. Наиболее важной работой является функция оценки. Чем сложнее, тем неправильнее «пытается» алгоритм попытается (и должен будет отменить) позже. Это чрезвычайно снижает сложность.
Если это слишком медленно, вы также можете попытаться применить некоторые методы игр с двумя людьми как HashTables. Для этого вам придется вычислять (итеративный) ключ хеш-функции для каждого оцениваемого состояния игры и отмечать состояния, которые не приводят к решению. Например, каждый раз, когда метод Search () возвращает «ноль», необходимо создать запись HashTable, и при входе в Search () вы будете проверять, достигнуто ли это состояние до сих пор без положительного результата, и в этом случае возвращать «ноль» без дальнейшее расследование. Для этого вам понадобится огромная хеш-таблица, и вам придется принимать «коллизии хешей», которые могут привести к тому, что вы, вероятно, не найдете существующее решение, но это очень маловероятно, если ваши хеш-функции достаточно хороши и ваша таблица достаточно большой (это риск вычислимого риска).
Я думаю, что нет другого алгоритма для решения этой проблемы (как описано вами) более эффективным, если предположить, что ваша функция оценки является оптимальной ...
источник