#algorithm #mahjong
Вопрос:
Независимо от компоновки, используемой для плиток, есть ли какой-либо хороший способ разделить плитки, чтобы вы могли гарантировать пользователю, что в начале игры существует хотя бы один путь к завершению головоломки и победе в игре?
Очевидно, что в зависимости от действий пользователя они могут отрезать себя от победы. Я просто хочу всегда иметь возможность сказать пользователю, что головоломка выигрышна, если они хорошо играют.
Если вы случайным образом разместите плитки в начале игры, вполне возможно, что пользователь может сделать несколько ходов и больше ничего не сможет сделать. Знание того, что головоломка, по крайней мере, разрешима, должно сделать ее более увлекательной.
Ответ №1:
Поместите все плитки в обратном порядке (т. е. раскройте доску, начиная с середины, работая).
Чтобы еще больше подразнить игрока, вы могли бы сделать это заметно, но на очень высокой скорости.
Комментарии:
1. Это не гарантирует победу, вы все равно можете оказаться в ситуации, когда некоторые плитки невозможно получить, например, ABAB — невозможно получить A, пока вы не получите B, и наоборот
2. Если вы «играете» в игру в обратном порядке, это формирование будет невозможно создать, если только две буквы «А» на самом деле не являются частями двух пар, в которых игрок ранее удалил «неправильную».
3. Обратите внимание, что если вы делаете это таким образом, вам нужно размещать плитки попарно, а не по одному. Вы все равно могли бы создать ситуацию, в которой невозможно выиграть, если бы вы поместили плитку, а затем поместили ее пару прямо поверх нее. (Или вы можете просто написать код, чтобы специально исключить эту возможность.)
Ответ №2:
Играйте в игру в обратном порядке.
Случайным образом раскладывайте кусочки пара за парой в тех местах, где вы могли бы сложить их в кучу. Вам понадобится способ узнать, где вам разрешено размещать фрагменты, чтобы в итоге получилась куча, соответствующая какому-то заданному шаблону, но это вам все равно понадобится.
Комментарии:
1. Мне жаль, но я не смог бы потратить достаточно времени на эту проблему, чтобы отдать ей должное. Я бы предпочел не вдаваться в обсуждение «хорошо, но вы подумали о …» в комментарии после редактирования псевдокода и, таким образом, время от времени помещать вопрос 11-летней давности на первую страницу.
2. извини за это. Я написал некоторый код для создания костюмов, но иногда это доходило до мертвой ситуации. поэтому мне интересно, как сгенерировать костюм в обратном порядке.
Ответ №3:
Я знаю, что это старый вопрос, но я столкнулся с этим, когда сам решал проблему. Ни один из приведенных здесь ответов не является вполне совершенным, и некоторые из них имеют сложные оговорки или будут нарушаться при неправильных раскладах. Вот мое решение:
Решите доску (вперед, а не назад) с помощью немаркированных плиток. Удаляйте по две свободные плитки за раз. Поместите каждую удаляемую пару в стопку «совпадающих пар». Часто это все, что вам нужно сделать.
Если вы попадете в тупик (numfreetils == 1), просто сбросьте свой генератор 🙂 Я обнаружил, что обычно не попадаю в тупики, и до сих пор максимальное количество повторных попыток составляло 3 для 10 или около того макетов, которые я пробовал. Как только я выполняю 8 повторных попыток, я сдаюсь и просто случайным образом распределяю остальные плитки. Это позволяет мне использовать один и тот же генератор как для настройки доски, так и для функции перемешивания, даже если игрок облажался и пришел в 100% неразрешимое состояние.
Другое решение, когда вы зашли в тупик, — отступить (выскочить из стопки, заменив плитки на доске), пока вы не сможете выбрать другой путь. Выберите другой путь, убедившись, что вы соответствуете парам, которые удалят исходную блокирующую плитку.
К сожалению, в зависимости от платы это может продолжаться вечно. Если вы в конечном итоге удалите пару, которая напоминает дорогу «без выхода», где все последующие «дороги» являются тупиком, и есть несколько тупиков, ваш алгоритм никогда не завершится. Я не знаю, возможно ли спроектировать доску, в которой это имело бы место, но если это так, то решение все еще есть.
Чтобы решить эту более серьезную проблему, рассматривайте каждое возможное состояние платы как узел в DAG, причем каждая выбранная пара является ребром на этом графике. Выполните случайный обход, пока не найдете конечный узел на глубине 72. Следите за своей историей прохождения, чтобы никогда не повторять спуск.
Поскольку тупики встречаются реже, чем решения с первой попытки в макетах, которые я использовал, сразу приходит на ум гибридное решение. Сначала попробуйте решить ее с минимальным объемом памяти (сохраните выбранные пары в своем стеке). Как только вы зайдете в первый тупик, переходите к полной генерации разметки/ребер при посещении каждого узла (по возможности, ленивая оценка).
Однако я очень мало изучал теорию графов, так что, возможно, есть лучшее решение проблемы случайного обхода/поиска DAG 🙂
Редактировать: Вы на самом деле могли бы использовать любое из моих решений без создания платы в обратном порядке, аля, сообщение от 13 октября 2008 года. У вас все те же предостережения, потому что вы все равно можете оказаться в тупике. Однако создание доски в обратном порядке имеет более сложные правила. например, вы гарантированно провалите настройку, если не начнете хотя бы некоторые ряды с первой фигуры посередине, например, в макете с 1 длинным рядом. Выбор совершенно случайного (законного) первого хода в генераторе прямого решения с большей вероятностью приведет к разрешимой доске.
Комментарии:
1. Это старо, я знаю, но я подкачал свою репутацию только для того, чтобы вернуться и заявить об этом. Решение в обратном направлении имеет много проблем, в то время как решение с использованием этого прямого метода является простым и имеет другие варианты использования, как вы упомянули. Это правильный путь.
2. @DannyB: Спасибо, Дэнни 🙂 Я действительно ценю это!
3. @blubberdibclub — пример патологического случая: 4 слота в ряд рядом друг с другом. Если вы для начала случайным образом размещаете две плитки так, чтобы они соответствовали правилу (C), то вероятность того, что для продолжения потребуется нарушение правила (B), составляет 2:3, и в этом случае у вас будет неразрешимая доска. Каковы ваши правила для тупиковых ситуаций в вашем алгоритме?
4. Отвечая на эту древнюю тему: похоже, это правильный ответ. Кто-то написал исследовательскую статью об этом в 2007 году, в которой дается псевдокод и подробно обсуждается вся эта тема: iivq.net/scriptie/scriptie-bsc.pdf
5. @edave да, определенно. Я пытался сказать то же самое, что и вы, в абзаце после того, который вы процитировали, но из-за моей неуверенности мой текст был неясен. Пройдите через DAG (тщательно, без повторений). Никакой эвристики для выбора пути. Воплощение грубой силы 🙂
Ответ №4:
Единственное, что мне удалось придумать, — это разложить плитки попарно в виде пасьянса Маджонг в обратном порядке. Таким образом, в любой момент во время размещения плитки доска должна выглядеть так, как будто она находится в середине реальной игры (т. Е. Никаких плиток, плавающих на 3 слоя выше других плиток).
Если плитки расположены в одинаковых парах в обратной игре, это всегда должно приводить к по крайней мере одному прямому пути для решения игры.
Я бы хотел услышать другие идеи.
Комментарии:
1. Святое дерьмо… как чертовски быстры эти люди?! Это потрясающе. Я сразу же начал публиковать этот ответ после того, как опубликовал вопрос, и к тому времени, когда я его отправил, уже было ДВА ответа.
2. Это, мой друг, сила <booming_voice>СТЕКОВОГО ПОТОКА<booming_voice></booming_voice>
Ответ №5:
Я считаю, что лучший ответ уже был выдвинут: создать набор, решив его «в обратном порядке», т. Е. Начать с пустой доски, затем добавить пару где — нибудь, добавить другую пару в разрешимой позиции и так далее…
Если вы предпочитаете подход «Большого взрыва» (создание всего набора случайным образом в начале), являетесь очень мужественным разработчиком или просто чувствуете себя мазохистом сегодня, вы могли бы представить все пары, которые вы можете извлечь из данного набора, и как они зависят друг от друга с помощью ориентированного графика.
Оттуда вам нужно будет только получить транзитивное замыкание этого набора и определить, есть ли по крайней мере один путь от хотя бы одной из начальных законных пар, который ведет к желаемому концу (пар плиток не осталось).
Реализация этого решения оставлена в качестве упражнения для читателя 😀
Ответ №6:
Вот правила, которые я использовал в своей реализации.
При построении кучи для каждого лада в паре отдельно найдите ячейки (места), которые являются:
- все ли ячейки на более низких уровнях уже заполнены
- место для второго лада не блокирует первый, учитывая, что первый лад уже установлен на борту
- оба места находятся «по краям» уже построенной кучи:
- ЛИБО имеет по крайней мере одного соседа слева или справа
- ИЛИ это первый лад подряд (все ячейки справа и слева рекурсивно свободны)
Эти правила не гарантируют, что сборка всегда будет успешной — иногда она оставляет последние 2 свободные ячейки самоблокирующимися, и сборку следует повторить (или, по крайней мере, последние несколько ладов). На практике «черепаха» строится не более чем за 6 повторных попыток.
Большинство существующих игр, похоже, ограничивают размещение первых («первых в ряду») ладов где-то посередине. Это позволяет создавать более удобные конфигурации, когда по краям очень длинных рядов нет ладов, которые остаются до последнего хода игрока. Однако «середина» отличается для разных конфигураций.
Удачи 🙂
P.S. Если вы нашли алгоритм, который создает разрешимую кучу за один ход — пожалуйста, дайте мне знать.
Ответ №7:
В игре у вас 144 плитки, каждая из 144 плиток имеет список блоков.. (верхняя плитка в стеке имеет пустой список блоков)
Все допустимые перемещения требуют, чтобы их «текущий__вертикальный_список блоков_» был пустым.. это может быть матрица 144×144, так что 20 кб памяти плюс список ЛЕВЫХ и ПРАВЫХ блоков, также по 20 к каждый.
Создайте допустимую таблицу перемещения из (remaning_tiles) И ((пустой ТЕКУЩИЙ СПИСОК ВЕРТИКАЛЬНЫХ БЛОКОВ) и ((пустой ТЕКУЩИЙ СПИСОК ЛЕВЫХ БЛОКОВ) ИЛИ (пустой ТЕКУЩИЙ СПИСОК ПРАВЫХ БЛОКОВ)))
Выберите 2 случайных плитки из допустимой таблицы перемещений, запишите их, обновите (текущие таблицы Верт, слева и справа), запишите удаленные плитки в стопку
Теперь у нас есть список ходов, которые составляют действительную игру. Назначьте соответствующие типы плиток для каждого из 72 ходов.
для сложных игр следите за тем, когда каждая плитка становится доступной. найти наборы, которые будут (рано рано рано поздно) и (в конце конце конце, в начале), так как это пустое, вы обнаружите, 1 УО 1 и ЛЛ 2 Ле блоков.. от 2 Ле заблокировать, найти начала, которая блокирует любые другие рано (за исключением rightblocking левую шт)
после того как вы получили действительный игра поиграть с заказом.
Ответ №8:
Пасьянс? Просто предположение, но я бы предположил, что вашему компьютеру нужно будет пройти игру(или приблизиться к ней), чтобы определить это.
Другим вариантом может быть наличие нескольких предустановленных макетов(которые позволяют выигрывать в зависимости от вашего текущего уровня).
В какой-то степени вы могли бы попытаться убедиться, что одна из 4 плиток находится не более чем на X слоев ниже другой X.
В большинстве игр, которые я вижу, есть команда «перетасовать», когда кто-то застревает.
Я бы попробовал смешать разные вещи и посмотреть, что работает лучше всего.