Маджонг шешілгіштік алгоритмі: ол қалай жұмыс істейді

Маджонг шешілгіштік алгоритмі — бұл берілген Маджонг солитер тақтасын ойын ережелеріне сай тақташалар жұптарын біртіндеп сәйкестендіріп, алып тастау арқылы толық тазартуға бола ма, соны анықтайтын шешім қабылдау процедурасы. Маджонг шешілгіштік алгоритмі деген не екенін түсіну комбинаторлық ойын теориясындағы ең қызықты мәселелердің біріне тіреледі: бұл сұрақ формалды түрде NP-толық болып табылады, яғни толық ақпарат жағдайында белгілі барлық мүмкін тақта конфигурациялары үшін оны тиімді шешетін алгоритм әзірге жоқ. Нақты бағдарламалар бұл кедергіні эвристикалар, қайта әрекет ету циклдері және балама стратегиялар арқылы айналып өтеді. Теориялық күрделілік пен практикалық ойнауға жарамдылық арасындағы алшақтық — ең пайдалы инженерлік шешімдер дәл туындайтын жер.

Есептеу күрделілігі маджонг шешілгіштігі туралы не айтады?

Есептеу күрделілігі — мәселені компьютер үшін шешу қаншалықты қиын екенін формалды түрде зерттейтін сала. Мұнда ең маңызды екі күрделілік класы бар: NP және PSPACE.

NP-толық дегеніміз — шешімді тексеру жылдам, бірақ оны табу экспоненциалды уақытты талап етуі мүмкін мәселелер. Толық ақпаратты Маджонг солитеріндегі шешім мәселесі NP-толық: барлық тақта орындары белгілі болған жағдайда, барлық тақташаларды алып тастауға бола ма? Бұл нәтиже кез келген ықтимал орналасу үшін бұл сұраққа жылдам жауап беруге кепілдік беретін алгоритм жоқ екенін білдіреді.

PSPACE-толық — одан да қиын класс. Алып тастау ықтималдығын барынша арттыру PSPACE-толық, әрі кез келген оң тұрақты дәрежедегі n коэффициентіне дейін жуықтау тұрғысынан PSPACE-қиын. Бұл нәтиже күрделілік теориясының іргелі жорамалдары күйремейінше, тіпті жуық шешімдердің де полиномдық уақытта жұмыс істеуін жоққа шығарады.

Бұл екі нәтиженің тәжірибеде нені білдіретіні:

• Шешім нұсқасы (бұл тақтаны тазартуға бола ма?) NP-толық. Дәл шешушілер ең нашар жағдайда экспоненциалды уақытқа тап болады.
• Оңтайландыру нұсқасы (тазарту ықтималдығын ең жоғары ететін тізбек қандай?) PSPACE-толық. Ол шешім нұсқасынан да қиын.
• Дәл шешілгіштікті тексеру ең нашар жағдайда экспоненциалды немесе көп жад қажет ететін есептеуді талап етеді. Практикалық шешушілер оның орнына эвристикаларға немесе орналасу шектеулеріне сүйенеді.
• Шешілгіштік мәселенің қойылымы мен ойын моделіне байланысты. Барлық Маджонг нұсқаларына бірдей әмбебап алгоритм жоқ.

Күрделілік теориясынан шығатын негізгі сабақ — Маджонг шешілмейді деген сөз емес. Мәселе мынада: оны дәл түрде, кез келген тақта үшін шешу есептеу жағынан соншалықты қымбат, сондықтан ешбір өндірістік ойын қозғалтқышы оны тікелей қолданбайды.

Бұл айырмашылық Маджонг бағдарламаларындағы әрбір жобалау шешімін айқындайды. Әзірлеушілер дәлелденген дұрыс жауапты күтпейді. Олар шешілетін тақталарды жоғары ықтималдықпен шығаратын жүйелер құрады да, дәлелдеудің орнына тексереді.

Шешілгіштік қалай модельденеді және комбинаторлық жарылыс неге маңызды?

Маджонг солитерінің математикалық құрылымы тақташаларды жұптастыруға негізделеді. Әр тақташа 36 санаттың біріне жатады, ал әр санатта дәл төрт тақташа бар. Тақтаны тазарту үшін әр тақташа өзінің үш бірдей сыңарының біреуімен жұптасуы керек.

Міне, негізгі комбинаторлық қиындық қадам-қадамымен:

1. Жұптастыру нұсқаларын санау. Төрт бірдей тақташа тобында оларды екі жұпқа бөлуге дәл үш тәсіл бар.
2. Барлық санаттар бойынша көбейту. 36 санат және әрқайсысында 3 нұсқа болғанда, жұптастыру конфигурацияларының жалпы саны 3^36, шамамен 1,5 × 10^17. Бұл шамамен 150 квадриллион комбинация.
3. Толық іздеудің мүмкін еместігін түсіну. Тіпті секундына бір миллиард операция жылдамдықпен барлық конфигурацияны тексеру үшін төрт жылдан астам үздіксіз есептеу қажет болар еді. Бірде-бір ойын қозғалтқышы мұндай шығынды әр тақта үшін көтере алмайды.
4. Жұптастыруды жүріс ретімен шатастырмау. Жұптастырулар бекітілгеннен кейін, алып тастау реті соңғы шешілгіштік нәтижесіне әсер етпейді. Бұл — аса маңызды түсінік. Демек, іздеу кеңістігі жүрістер тізбегімен емес, жұптастыру таңдауларымен анықталады.
5. Іздеуді жұптастыру үлгілеріне шоғырландыру. Ойынды жұптастыру және алып тастау тәуелділігі мәселесі ретінде қайта тұжырымдау арқылы күй кеңістігін қысқарту күрделілікті азайтады. Кеңістік бәрібір үлкен, бірақ әр мүмкін жүріс тізбегін қадағалағаннан әлдеқайда басқаруға келеді.
6. Алдын ала қысуды қолдану. Тиімді шешушілер ағымдағы тақта орналасуына қарай қай тақташалар қолжетімді екенін анықтауға назар аударады, ал теориялық жұптастыру таңдауы қандай болса да, бөгелген тақташалар жұптастыруды физикалық тұрғыдан мүмкін емес ететін тармақтарды қырқып тастайды.

Кәсіби кеңес: Маджонг тақтасын қолмен талдағанда, жеке жүрістерден гөрі жұптастыру міндеттемелері тұрғысынан ойлаңыз. Қай тақташалардың қолжетімді жалғыз жарамды серіктесі бар екенін анықтап, сол жұптастыруларды алдымен бекітіңіз. Бұл алгоритмдік шешушілердің іздеу ағашын қалай қырқатынын қайталайды.

Комбинаторлық жарылыс толық іздеуді іске аспайтындай етеді. Осы шындық барлық практикалық іске асыруларды толық санаудың орнына эвристикалар мен кездейсоқ қайта әрекет ету стратегияларына итермелейді. Осы шектеуді түсіну — кез келген маңызды бағдарламалық контексте түсіндірілетін маджонг алгоритмдерінің негізі.

Нақты іске асырулар шешілетін маджонг тақталарын қалай жасайды?

Өндірістік Маджонг бағдарламалары шешілгіштікті бастапқы қағидалардан дәлелдеуге тырыспайды. Олар нәтижені тексеретін шешушімен бірге жылдам тақта құрастыруды біріктіретін екі қабатты жүйе арқылы шешілгіштікті растайды.

Стандартты архитектура былай жұмыс істейді:

• 1-қабат: конструктивті генерация. Қозғалтқыш шешілетін орналасуларды шығаруға арналған әдіспен тақта құрады. Бұл жылдам, бірақ әрдайым сәтті болатынына кепіл жоқ.
• 2-қабат: шешілгіштікті тексеру. Құрылған тақтада шешуші іске қосылады. Егер тақта тексеруден өтпесе, қозғалтқыш қайта әрекет етеді.
• Қайта әрекет ету циклдері. Кең таралған іске асырулар стратегияны ауыстырмас бұрын buildSolvableWithRetries функциясын 2 000 әрекетке дейін орындайды. Бұл сан теориялық қажеттіліктен емес, тәжірибелік баптаудан шыққан.
• Балама стратегиялар. Негізгі қайта әрекет ету бюджеті таусылғаннан кейін қозғалтқыш өз қайта әрекет ету циклі бар басқа құрастыру алгоритміне ауысады.
• Кездейсоқ тақтаға көшу. Егер бәрі сәтсіз болса, қозғалтқыш кездейсоқ тақта жасап, оған тікелей шешу тексерісін жүргізеді. Бұл әрдайым ойнауға болатын тақта жеткізілетініне кепілдік береді.

Кәсіби кеңес: Егер сіз Маджонг басқатырғыш генераторын жасап жатсаңыз, кері құрастыру тәсілінен бастаңыз: тақташаларды белгілі шешілетін ретпен орналастырып, кейін оларды шектеулер аясында араластырыңыз. Бұл жарамды тақтаны табуға дейін қажет қайта әрекет ету санын айтарлықтай азайтады.

Төмендегі кесте өндірістік код базаларында қолданылатын үш сатылы балама үлгіні қорытындылайды:

Қайталанатын қайта әрекет ету мен балама стратегиялары бар бұл екі қабатты жүйе — шешілетін басқатырғыш тақталарын жеткізудің өндірістік стандарты. Мұндағы инженерлік тәсіл әдейі таңдалады: шешілгіштікті алдын ала дәлелдемеңіз. Жылдам құрыңыз, тез тексеріңіз және қажет болса қайта көріңіз. Бұл тәсіл күрделілік теориясы болжайтын нәрсемен үйлеседі. Дәлелдер қымбат. Тексеру арзан.

Шешілгіштік туралы білім маджонг ойынының стратегиясы мен дизайнын қалай жақсартады?

Шешілгіштіктің қалай жұмыс істейтінін түсіну әзірлеушілердің ойын құру тәсілін де, ойыншылардың маджонг басқатырғыштарын шешу тәсілін де өзгертеді. Бұл екі көзқарас бірін-бірі күшейтеді.

Ойыншы стратегиясы тұрғысынан шешілгіштік туралы түсінік тікелей жақсы шешім қабылдауға әкеледі:

• Қолжетімді серіктестері аз ашық тақташаларды бірінші орынға қойыңыз. Егер тақташаның тек бір қолжетімді сәйкестігі болса, ол жұптастыру бір сәтте жасалуы керек. Оны кешіктіру тақтаны бөгеп тастауы мүмкін.
• Тақташа топтарын оқшаулаудан аулақ болыңыз. Жаңа тақташаларды ашпайтын тақташаларды алып тастау болашақ мүмкіндіктеріңізді азайтады, бірақ жағдайыңызды жақсартпайды. Бұл ұғым тақташа оқшаулануы және оның шешілгіштікті неге әлсірететіні контекстінде терең қарастырылады.
• Жеке жүрістер емес, қабаттар бойынша ойлаңыз. Шешілгіштік бүкіл тақта бойынша жұптастыру міндеттемелеріне байланысты. Екі-үш жүріс алға жоспарлайтын ойыншылар бір тақташа мүмкіндігіне ғана реакция беретіндерден тұрақты түрде жақсы нәтиже көрсетеді.
• Араластыру функцияларын стратегиямен қолданыңыз. Көптеген цифрлық Маджонг ойындары араластыру немесе кеңес беру функциясын ұсынады. Бұл мүмкіндіктер фондық режимде жұмыс істейтін сол шешілгіштік алгоритмдеріне сүйеніп, жарамды жолдың әлі де бар-жоғын тексереді.

Ойын дизайны тұрғысынан шешілгіштік алгоритмдері ойыншы тәжірибесінің сапасын анықтайды:

• Шешілгіштік тексерісінсіз жасалған орналасулар жиі ұтылмайтын тақталарға әкеледі. Мұндай тақталарға тап болған ойыншылар өз шеберлігіне емес, ойынға деген сенімін жоғалтады.
• Тақташалардың орналасуы қиындық деңгейіне тікелей әсер етеді. Ерте кезеңде аз тақташа ашатын дизайндар ойыншыларды тар шешім ағаштарына мәжбүрлеп, Маджонг басқатырғыштарын шешудің тиімді күрделілігін арттырады.
• Тақташа беттері ашылғанға дейін жасырын болатын жасырын ақпарат нұсқалары мәселені NP-толық шешім қабылдаудан ықтималдықтық пайымдауға ауыстырады. Бұл ойынның табиғатын түбегейлі өзгертеді.
• Маджонг ЖИ алгоритмдерін түсінетін әзірлеушілер конструктивті генераторды бірнеше жарамды шешім жолдары бар орналасуларды қаншалықты агрессивті таңдауға болатынын реттеу арқылы қиындықты баптай алады.

Алгоритмдік теория мен ойыншы тәжірибесінің байланысы тікелей. Сенімді шешілгіштік алгоритмімен жасалған тақта сізге әділ басқатырғыш береді. Онсыз жасалған тақта мүмкін емес болуы мүмкін, ал сіз неге жеңілгеніңізді ешқашан білмейсіз.

Негізгі тұжырымдар

Маджонг шешілгіштік алгоритмі шешім мәселелері үшін NP-толық, ал оңтайландыру үшін PSPACE-толық, сондықтан өндірістік бағдарламаларда шешілетін тақталарға жетудің жалғыз практикалық жолы — эвристикалық және қайта әрекет етуге негізделген әдістер.

Неге теорияның өзі сізге жақсырақ маджонг ойынын жасауға көмектеспейді

Мен Маджонг шешілгіштігінің практикада қалай іске асырылатынын талдауға едәуір уақыт жұмсадым, және академиялық күрделілік нәтижелері мен инженерлердің шын мәнінде жеткізетін шешімдері арасындағы алшақтық таңғаларлық. NP-толықтық пен PSPACE-толықтық дәлелдері интеллектуалдық тұрғыдан қанағаттандырады. Олар мәселе туралы шын әрі маңызды нәрсе айтады. Бірақ олар сізге ойыншыларға ұнайтын ойынды қалай жасау керегін айтпайды.

Менің байқағаным — қайта әрекет етуге негізделген тәсіл ымыра емес. Бұл осы мәселе класы үшін дұрыс жауап. Іздеу кеңістігіңізде 150 квадриллион конфигурация болса, олардың бәрін зерттеудің қажеті жоқ. Сізге көбіне сәтті болатын жылдам генератор, сәтсіздікті ұстайтын арзан тексеруші және жеткізуді кепілдейтін балама керек. Мұндай архитектура өндірісте кез келген дәл шешушіден сенімдірек.

Жұптастырулар бекітілгеннен кейін жүріс реті шешілгіштікке әсер етпейтіні туралы түсінік — осы саладағы ең бағаланбайтын нәтиже. Бұл сырттай тізбекті болып көрінетін мәселені комбинаторлық мәселеге айналдыруға болатынын білдіреді, ал комбинаторлық мәселелер шектеулерді тарату мен қырқуға жақсы жауап береді. Егер сіз Маджонг шешушісін жасап жатсаңыз немесе басқатырғыш ойындарының күрделілігін зерттеп жүрсеңіз, осы жерден бастаңыз.

Шешілгіштікті тексеруді енгізгісі келетіндерге менің кеңесім: күрделілік әдебиетінен бастамаңыз. Жұмыс істейтін қайта әрекет ету циклінен бастаңыз, әр балама кезеңнің қаншалықты жиі іске қосылатынын өлшеу үшін оны аспаптаңыз да, содан кейін баптаңыз. Теория сізге шекті көрсетеді. Өлшеу сіздің нақты қай жерде екеніңізді айтады.

— Дмытро Романюк

Шешілетін тақта генерациясына негізделген маджонг басқатырғыштарын ойнаңыз

Mahjong Online Club сайтындағы әр басқатырғыш осы мақалада сипатталған шешілгіштікке басымдық беретін тәсілмен жасалады. Ешбір тақта шешуші тексерісінен өтпей сізге берілмейді. Бұл сіз бастайтын әр ойынның ұтылатын емес, ал әр сәтсіздік стратегия мәселесі екенін білдіреді, бұзылған орналасу емес.

Сіз тегін Маджонгты тікелей браузеріңізде, тіркелусіз ойнай аласыз. Платформа назарды бөлмейтін, шоғырлану мен үлгіні тануды қолдауға арналған тәжірибе төңірегінде құрылған. Егер мұндағы алгоритмдік ұғымдарды тәжірибеде қолданғыңыз келсе, дәл осы жер соған лайық.

Жиі қойылатын сұрақтар

Маджонг шешілгіштік алгоритмі деген не?

Маджонг шешілгіштік алгоритмі — Маджонг солитер тақтасын барлық тақташа жұптарын сәйкестендіріп, алып тастау арқылы толық тазартуға бола ма, соны анықтайтын есептеу процедурасы. Бұл мәселенің шешім нұсқасы толық ақпарат жағдайында формалды түрде NP-толық болып табылады.

Маджонг шешілгіштігі математикалық тұрғыдан қалай жұмыс істейді?

Шешілгіштік 36 тақташа санаты бойынша жұптастыру таңдауларына байланысты, әр санатта 3 ықтимал жұптастыру бар, бұл шамамен 150 квадриллион жалпы конфигурацияны береді. Жұптастырулар бекітілгеннен кейін жүріс реті нәтижені өзгертпейтіндіктен, шешушілер жүріс тізбегіне емес, жұптастыру шектеулеріне назар аударады.

Неге бағдарламалық жасақтама Маджонг тақталарын әрдайым дәл шеше алмайды?

Дәл шешілгіштікті тексеру ең нашар жағдайда экспоненциалды есептеуді талап етеді, бұл нақты уақыттағы ойын қозғалтқыштары үшін тиімсіз. Өндірістік жүйелер ойнауға болатын тақтаны дәлелсіз-ақ кепілдеу үшін 2 000 әрекетке дейін қайта көретін конструктивті генераторлар мен балама сатыларды қолданады.

Маджонгта NP-толық пен PSPACE-толықтың айырмашылығы неде?

Шешім мәселесі (бұл тақтаны тазартуға бола ма?) NP-толық. Оңтайландыру мәселесі (тазарту ықтималдығын ең жоғары ететін тізбек қандай?) PSPACE-толық, бұл одан да қиын класс және тиімді жуықтау алгоритмдерін де жоққа шығарады.

Маджонг ойын стратегиялары шешілгіштік алгоритмдерімен қалай байланысады?

Қолжетімді серіктестері шектеулі тақташаларды бірінші орынға қоятын және тақташа топтарын оқшаулаудан аулақ болатын ойыншылар алгоритмдік шешушілер қолданатын сол шектеулерді қырқу логикасын қолданады. Шешілгіштіктің қалай құрылатынын түсіну стратегиялық шешімдерді анағұрлым саналы әрі кездейсоқ болжамға азырақ тәуелді етеді.

Ұсынылған

• Маджонг солитерін қалай ойнауға болады — ережелер, тақташалар және стратегия
• Неліктен тақташа оқшаулануы барлық ойыншылар үшін Маджонг ойындарын бұзады
• Mahjong Titans cheats: шешушілер, кеңестер және әлі де жұмыс істейтін заңды қысқа жолдар
• Маджонгтың мақсаты қандай? Ережелер мен стратегия