Алгоритам за решливост на 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 игрите за сите играчи
• Cheats за Mahjong Titans: решавачи, навестувања и легитимни кратенки
• Која е целта на Mahjong? Правила и стратегија