Алгоритъм за решимост на Mahjong: Как работи

Алгоритъмът за решимост на mahjong е процедура за вземане на решение, която определя дали дадена дъска за Mahjong Solitaire може да бъде напълно изчистена чрез последователно съвпадение и премахване на двойки плочки според правилата на играта. Разбирането какво означава алгоритъм за решимост на mahjong означава да се изправим пред един от по-интересните проблеми в комбинаторната теория на игрите: въпросът формално е NP-пълен при пълна информация, което означава, че не е известен алгоритъм, който да го решава ефективно за всички възможни конфигурации на дъската. Реалният софтуер заобикаля тази пречка чрез евристики, цикли за повторен опит и резервни стратегии. Разликата между теоретичната трудност и практическата използваемост е точно мястото, където се случва най-полезната инженерна работа.

Какво ни казва изчислителната сложност за решимостта на mahjong?

Изчислителната сложност е формалното изследване на това колко трудно е даден проблем да бъде решен от компютър. Тук най-важни са две класове сложност: NP и PSPACE.

NP-пълен описва проблеми, при които проверката на решение е бърза, но намирането му може да изисква експоненциално време. Mahjong Solitaire при пълна информация е NP-пълен за задачата за вземане на решение: ако е дадена дъска, при която всички позиции на плочките са известни, могат ли всички плочки да бъдат премахнати? Този резултат означава, че няма алгоритъм, който да гарантира бърз отговор на този въпрос за всяко възможно разположение.

PSPACE-пълен е още по-труден клас. Максимизирането на вероятността за изчистване е PSPACE-пълно и PSPACE-трудно за апроксимация в рамките на фактор n, повдигнат на всяка положителна константа. Този резултат изключва дори приблизителни решения, работещи за полиномиално време, освен ако фундаменталните предположения на теорията на сложността не се сринат.

Ето какво означават тези два резултата на практика:

• Версията за вземане на решение (може ли тази дъска да бъде изчистена?) е NP-пълна. Точните решатели се сблъскват с експоненциално време в най-лошия случай.
• Версията за оптимизация (коя последователност максимизира вероятността за изчистване?) е PSPACE-пълна. Тя е строго по-трудна от версията за вземане на решение.
• Точното проверяване на решимостта изисква експоненциално или силно паметово натоварено изчисление в най-лошия случай. Практическите решатели разчитат вместо това на евристики или ограничения в разположението.
• Решимостта зависи от формулировката на проблема и модела на играта. Няма универсален алгоритъм, който да пасва на всички варианти на Mahjong.

Основният урок от теорията на сложността не е, че Mahjong е нерешим. А че решаването му точно за произволни дъски е изчислително достатъчно скъпо, че нито един продукционен игрови енджин не се опитва да го прави директно.

Това разграничение оформя всяко дизайнерско решение в софтуера за Mahjong. Разработчиците не чакат доказано верен отговор. Те изграждат системи, които създават решими дъски с висока вероятност, а след това проверяват, вместо да доказват.

Как се моделира решимостта и защо комбинаторният взрив е важен?

Математическата структура на Mahjong Solitaire се върти около сдвояването на плочки. Всяка плочка принадлежи към една от 36 категории, а всяка категория съдържа точно четири плочки. За да бъде изчистена дъската, всяка плочка трябва да бъде съчетана с една от трите си еднакви копия.

Ето основното комбинаторно предизвикателство, стъпка по стъпка:

1. Пребройте възможностите за сдвояване. За всяка група от четири еднакви плочки има точно три начина да бъдат сдвоени в две съвпадащи двойки.
2. Умножете през всички категории. При 36 категории и по 3 възможности за всяка, общият брой конфигурации на сдвояване е 3^36, приблизително 1,5 × 10^17. Това е около 150 квадрилиона комбинации.
3. Разпознайте невъзможността на изчерпателното търсене. Проверяването на всяка конфигурация дори при един милиард операции в секунда би отнело над четири години непрекъснато изчисление. Нито един игрови енджин не може да си позволи това за всяка дъска.
4. Отделете сдвояването от реда на ходовете. Редът на премахване не влияе върху крайния резултат за решимост, след като сдвояванията са фиксирани. Това е критично прозрение. То означава, че пространството за търсене се определя от изборите за сдвояване, а не от последователността на ходовете.
5. Фокусирайте търсенето върху моделите на сдвояване. Намаляването на пространството на състоянията чрез преформулиране на играта като проблем на зависимости между сдвояване и премахване намалява сложността. Пространството остава голямо, но е много по-управляемо от проследяването на всяка възможна последователност от ходове.
6. Приложете предварително свиване. Ефективните решатели се фокусират върху това кои плочки са достъпни според текущото разположение на дъската, като отрязват клонове, при които блокираните плочки правят сдвояването физически невъзможно, независимо от абстрактния избор на сдвояване.

Професионален съвет: Когато анализирате ръчно дъска за Mahjong, мислете в термини на ангажименти за сдвояване, а не на отделни ходове. Определете кои плочки имат само един достъпен валиден партньор и първо фиксирайте тези сдвоявания. Това отразява начина, по който алгоритмичните решатели подрязват дървото на търсене.

Комбинаторният взрив прави изчерпателното търсене непрактично. Тази реалност насочва всяка практическа реализация към евристики и стратегии за повторен опит с произволност, вместо към пълно изброяване. Разбирането на това ограничение е основата на алгоритмите за mahjong, обяснени във всеки сериозен софтуерен контекст.

Как реалните реализации генерират решими дъски за mahjong?

Продукционният софтуер за Mahjong не се опитва да докаже решимостта от първи принципи. Той проверява решимостта чрез двуслойна система, която комбинира бързо изграждане на дъската с решател, който проверява резултата.

Стандартната архитектура работи така:

• Слой 1: Конструктивно генериране. Енджинът изгражда дъска чрез метод, проектиран да създава решими разположения. Това е бързо, но не е гарантирано, че ще успее всеки път.
• Слой 2: Проверка на решимостта. Решател се изпълнява върху генерираната дъска. Ако дъската не премине проверката, енджинът опитва отново.
• Цикли за повторен опит. Често срещани реализации изпълняват buildSolvableWithRetries до 2 000 опита, преди да преминат към други стратегии. Тази стойност отразява емпирична настройка, а не теоретична необходимост.
• Алтернативни стратегии. След изчерпване на основния бюджет за повторни опити, енджинът преминава към различен алгоритъм за изграждане със собствен цикъл за повторен опит.
• Резервен вариант с произволна дъска. Ако всичко друго се провали, енджинът генерира произволна дъска и директно изпълнява проверка за решаване върху нея. Това гарантира, че винаги се предоставя игрална дъска.

Професионален съвет: Ако изграждате генератор на пъзели Mahjong, започнете с подход за обратно конструиране: поставете плочките в известен решим ред, а след това ги разбъркайте в рамките на ограниченията. Това драстично намалява броя на повторните опити, необходими преди да се намери валидна дъска.

Таблицата по-долу обобщава трислойния модел с резервни варианти, използван в продукционните кодови бази:

Тази двуслойна система с многократни повторни опити и резервни стратегии е продукционният стандарт за предоставяне на решими пъзел дъски. Инженерният подход тук е умишлен: не доказвайте решимостта предварително. Изграждайте бързо, проверявайте бързо и опитвайте отново при нужда. Този подход съответства на това, което предсказва теорията на сложността. Точните доказателства са скъпи. Проверяването е евтино.

Как знанието за решимостта подобрява стратегиите и дизайна на играта mahjong?

Разбирането как работи решимостта променя както начина, по който разработчиците създават игри, така и начина, по който играчите подхождат към решаването на пъзели Mahjong. Двете гледни точки се подсилват взаимно.

От гледна точка на стратегията на играча прозренията за решимостта се превръщат директно в по-добро вземане на решения:

• Дайте приоритет на откритите плочки с ограничени партньори. Ако една плочка има само едно достъпно съвпадение, това сдвояване трябва да бъде направено в някакъв момент. Отлагането му рискува да блокира дъската.
• Избягвайте да изолирате групи плочки. Премахването на плочки, които не разкриват нови плочки, намалява бъдещите ви възможности, без да подобрява позицията ви. Тази концепция е разгледана подробно в контекста на изолирането на плочки и защо то подкопава решимостта.
• Мислете на слоеве, а не в отделни ходове. Решимостта зависи от ангажиментите за сдвояване върху цялата дъска. Играчите, които планират два или три хода напред, последователно се представят по-добре от тези, които реагират на възможности с една плочка.
• Използвайте функциите за разбъркване стратегически. Повечето дигитални игри Mahjong предлагат функция за разбъркване или подсказка. Тези функции разчитат на същите алгоритми за решимост, работещи във фонов режим, за да потвърдят, че все още съществува валиден път.

От гледна точка на дизайна на играта алгоритмите за решимост определят качеството на преживяването на играча:

• Разположения, генерирани без проверки за решимост, често създават непобедими дъски. Играчите, които се сблъскват с такива, губят доверие в играта, а не в собственото си умение.
• Подредбата на плочките пряко влияе върху трудността. Дизайни, които разкриват по-малко плочки в началото, принуждават играчите в по-тесни дървета на решения, увеличавайки ефективната сложност на решаването на пъзели Mahjong.
• Вариантите с скрита информация, при които лицата на плочките са скрити, докато не бъдат открити, преместват проблема от NP-пълно вземане на решения към вероятностно разсъждение. Това променя напълно характера на играта.
• Разработчиците, които разбират алгоритмите за изкуствен интелект в mahjong, могат да настройват трудността, като регулират колко агресивно конструктивният генератор предпочита разположения с множество валидни пътища за решение.

Връзката между алгоритмичната теория и преживяването на играча е пряка. Дъска, генерирана с надежден алгоритъм за решимост, ви дава честен пъзел. Дъска, генерирана без такъв, може да е невъзможна и никога няма да разберете защо сте се провалили.

Основни изводи

Алгоритъмът за решимост на mahjong е NP-пълен за задачите за вземане на решение и PSPACE-пълен за оптимизация, което прави евристичните методи и методите, базирани на повторни опити, единствения практичен път към решими дъски в продукционния софтуер.

Защо теорията сама няма да ви помогне да създадете по-добра игра mahjong

Прекарвал съм значително време в анализ на това как решимостта на Mahjong се реализира на практика и разликата между академичните резултати за сложност и това, което инженерите действително доставят, е поразителна. Доказателствата за NP-пълнота и PSPACE-пълнота са интелектуално удовлетворяващи. Те ви казват нещо вярно и важно за проблема. Но не ви казват как да създадете игра, която играчите да харесват.

Това, което съм установил, е, че подходът с повторни опити не е компромис. Той е правилният отговор за този клас проблеми. Когато пространството ви за търсене има 150 квадрилиона конфигурации, не е нужно да ги изследвате всички. Нужен ви е бърз генератор, който успява през повечето време, евтин проверяващ механизъм, който улавя грешките, и резервен вариант, който гарантира доставката. Тази архитектура е по-надеждна в продукция от всеки точен решател.

Прозрението, че редът на ходовете не влияе върху решимостта, след като сдвояванията са фиксирани, е най-недооцененият резултат в тази област. Това означава, че можете да сведете привидно последователен проблем до комбинаторен, а комбинаторните проблеми реагират добре на разпространение на ограничения и подрязване. Ако изграждате решател за Mahjong или изучавате сложността на пъзел игрите, започнете оттам.

Съветът ми към всеки, който иска да реализира проверка на решимостта: не започвайте с литературата за сложността. Започнете с работещ цикъл за повторни опити, инструментирайте го, за да измервате колко често се задейства всеки резервен етап, и настройвайте оттам. Теорията ви казва тавана. Измерването ви казва къде всъщност се намирате.

— Димитро Романиук

Играйте пъзели Mahjong, изградени върху генериране на решими дъски

Всеки пъзел в Mahjong Online Club е генериран с подхода „решимостта на първо място“, описан в тази статия. Нито една дъска не ви се предоставя без да премине стъпка за проверка от решател. Това означава, че всяка игра, която започвате, може да бъде спечелена, а всеки провал е проблем на стратегията, а не на счупено разположение.

Можете да играете безплатен Mahjong директно в браузъра си, без да е необходима регистрация. Платформата е изградена около преживяване без разсейване, създадено да подпомага концентрацията и разпознаването на модели. Ако искате да приложите алгоритмичните концепции тук на практика, това е мястото да го направите.

ЧЗВ

Какво е алгоритъм за решимост на mahjong?

Алгоритъмът за решимост на mahjong е изчислителна процедура, която определя дали дъска за Mahjong Solitaire може да бъде напълно изчистена чрез съвпадение и премахване на всички двойки плочки. Версията на този проблем за вземане на решение е формално NP-пълна при пълна информация.

Как работи математически решимостта на mahjong?

Решимостта зависи от изборите за сдвояване в 36 категории плочки, като всяка предлага 3 възможни сдвоявания, което дава приблизително 150 квадрилиона общи конфигурации. Тъй като редът на ходовете не променя резултата, след като сдвояванията са фиксирани, решателите се фокусират върху ограниченията за сдвояване, а не върху последователностите от ходове.

Защо софтуерът не може да решава дъските за mahjong точно всеки път?

Точното проверяване на решимостта изисква експоненциално изчисление в най-лошия случай, което е непрактично за игрови енджини в реално време. Продукционните системи използват конструктивни генератори с цикли за повторен опит до 2 000 опита и резервни етапи, за да гарантират игрална дъска без точно доказателство.

Каква е разликата между np-пълен и pspace-пълен в mahjong?

Проблемът за вземане на решение (може ли тази дъска да бъде изчистена?) е NP-пълен. Проблемът за оптимизация (коя последователност максимизира вероятността за изчистване?) е PSPACE-пълен, което е строго по-труден клас, който също изключва ефективни алгоритми за апроксимация.

Как стратегиите в играта mahjong се свързват с алгоритмите за решимост?

Играчите, които дават приоритет на плочки с ограничен брой достъпни партньори и избягват изолирането на групи плочки, прилагат същата логика за подрязване на ограниченията, която използват алгоритмичните решатели. Разбирането как е структурирана решимостта прави стратегическите решения по-целенасочени и по-малко зависими от догадки.

Препоръчано

• Как се играе Mahjong Solitaire — правила, плочки и стратегия
• Защо изолирането на плочки разваля игрите Mahjong за всички играчи
• Чийтове за Mahjong Titans: решатели, подсказки и легитимни преки пътища
• Каква е целта на Mahjong? Правила и стратегия