Mahjong-ის ამოხსნადობის ალგორითმი: როგორ მუშაობს

Mahjong-ის ამოხსნადობის ალგორითმი არის გადაწყვეტილების პროცედურა, რომელიც განსაზღვრავს, შესაძლებელია თუ არა მოცემული Mahjong solitaire-ის დაფის სრულად გასუფთავება ფილის წყვილების თანმიმდევრული შეხამებითა და მოცილებით თამაშის წესების მიხედვით. იმის გაგება, თუ რა არის Mahjong-ის ამოხსნადობის ალგორითმი, ნიშნავს ერთ-ერთ ყველაზე საინტერესო პრობლემასთან შეჯახებას კომბინატორულ თამაშთა თეორიაში: ეს კითხვა ფორმალურად NP-complete არის სრულ ინფორმაციაზე დაყრდნობით, რაც ნიშნავს, რომ ცნობილი არცერთი ალგორითმი არ წყვეტს მას ეფექტურად ყველა შესაძლო დაფის კონფიგურაციისთვის. რეალური პროგრამული უზრუნველყოფა ამ ბარიერს გვერდს უვლის ევრისტიკებით, განმეორებითი ცდებითა და სარეზერვო სტრატეგიებით. თეორიულ სირთულესა და პრაქტიკულ სათამაშოობას შორის არსებული სხვაობა ზუსტად ის სივრცეა, სადაც ყველაზე სასარგებლო ინჟინერია ხდება.

რას გვეუბნება გამოთვლითი სირთულე Mahjong-ის ამოხსნადობაზე?

გამოთვლითი სირთულე არის პრობლემის კომპიუტერისთვის ამოხსნის სირთულის ფორმალური შესწავლა. აქ განსაკუთრებით მნიშვნელოვანია ორი სირთულის კლასი: NP და PSPACE.

NP-complete აღწერს პრობლემებს, სადაც ამოხსნის შემოწმება სწრაფია, მაგრამ მისი პოვნა შეიძლება ექსპონენციალურ დროს მოითხოვდეს. სრულ ინფორმაციაზე დაფუძნებული Mahjong solitaire გადაწყვეტილების პრობლემა NP-complete არის: მოცემულია დაფა, სადაც ყველა ფილის მდებარეობა ცნობილია — შესაძლებელია თუ არა ყველა ფილის მოცილება? ეს შედეგი ნიშნავს, რომ არ არსებობს ალგორითმი, რომელიც გარანტირებულად და სწრაფად უპასუხებს ამ კითხვას ყველა შესაძლო განლაგებისთვის.

PSPACE-complete კიდევ უფრო რთული კლასია. მოცილების ალბათობის მაქსიმიზაცია PSPACE-complete არის და PSPACE-hard-ია n-ის ნებისმიერ დადებით ხარისხამდე მიახლოების სიზუსტით. ეს შედეგი გამორიცხავს თუნდაც მიახლოებითი ამოხსნების პოლინომიურ დროში მუშაობას, თუ სირთულის თეორიის ფუნდამენტური დაშვებები არ დაინგრევა.

აი, რას ნიშნავს ეს ორი შედეგი პრაქტიკაში:

• გადაწყვეტილების ვერსია (შეიძლება თუ არა ამ დაფის გასუფთავება?) არის NP-complete. ზუსტი ამომხსნელები უარეს შემთხვევაში ექსპონენციალურ დროს აწყდებიან.
• ოპტიმიზაციის ვერსია (რომელი თანმიმდევრობა მაქსიმუმამდე ზრდის გასუფთავების ალბათობას?) არის PSPACE-complete. ის გადაწყვეტილების ვერსიაზე მკვეთრად რთულია.
• ამოხსნადობის ზუსტი შემოწმება უარეს შემთხვევაში ექსპონენციალურ ან მეხსიერებაზე მძიმე გამოთვლას მოითხოვს. პრაქტიკული ამომხსნელები ეყრდნობიან ევრისტიკებს ან განლაგების შეზღუდვებს.
• ამოხსნადობა დამოკიდებულია პრობლემის ფორმულირებასა და თამაშის მოდელზე. არცერთი უნივერსალური ალგორითმი არ ერგება 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-complete გადაწყვეტილების მიღებიდან ალბათურ მსჯელობაზე გადააქვს. ეს მთლიანად ცვლის თამაშის ხასიათს.
• დეველოპერები, რომლებსაც Mahjong-ის AI ალგორითმები ესმით, შეუძლიათ სირთულის მორგება იმით, თუ რამდენად აგრესიულად ანიჭებს კონსტრუქციული გენერატორი უპირატესობას მრავალ ვალიდურ ამოხსნის გზის მქონე განლაგებებს.

ალგორითმულ თეორიასა და მოთამაშის გამოცდილებას შორის კავშირი პირდაპირია. მძლავრი ამოხსნადობის ალგორითმით გენერირებული დაფა სამართლიან თავსატეხს გაძლევთ. მის გარეშე შექმნილი დაფა შეიძლება შეუძლებელი იყოს და თქვენ ვერასოდეს გაიგებთ, რატომ წააგეთ.

ძირითადი დასკვნები

Mahjong-ის ამოხსნადობის ალგორითმი გადაწყვეტილების პრობლემებისთვის NP-complete არის, ხოლო ოპტიმიზაციისთვის PSPACE-complete, რაც ევრისტიკულ და განმეორებით ცდებზე დაფუძნებულ მეთოდებს ერთადერთ პრაქტიკულ გზად აქცევს ამოხსნადი დაფების მისაღებად წარმოების პროგრამულ უზრუნველყოფაში.

რატომ არ გეყოფათ მხოლოდ თეორია უკეთესი Mahjong-ის თამაშის შესაქმნელად

მე საკმაო დრო დავხარჯე იმის ანალიზზე, როგორ ხორციელდება Mahjong-ის ამოხსნადობა პრაქტიკაში, და განსხვავება აკადემიურ სირთულის შედეგებსა და იმას შორის, რასაც ინჟინრები რეალურად უშვებენ, თვალშისაცემია. NP-complete და PSPACE-complete მტკიცებულებები ინტელექტუალურად დამაკმაყოფილებელია. ისინი გეუბნებიან რაღაც ჭეშმარიტსა და მნიშვნელოვანს პრობლემის შესახებ. მაგრამ ისინი არ გეუბნებიან, როგორ შექმნათ თამაში, რომელიც მოთამაშეებს მოეწონებათ.

რაც აღმოვაჩინე, არის ის, რომ განმეორებით ცდებზე დაფუძნებული მიდგომა კომპრომისი კი არა, ამ კლასის პრობლემისთვის სწორი პასუხია. როცა თქვენი ძიების სივრცე 150 კვადრილიონ კონფიგურაციას შეიცავს, ყველა მათგანის დათვალიერება არ გჭირდებათ. გჭირდებათ სწრაფი გენერატორი, რომელიც უმეტესად წარმატებულია, იაფი ვერიფიკატორი, რომელიც წარუმატებლობას იჭერს, და სარეზერვო გზა, რომელიც მიწოდებას უზრუნველყოფს. ასეთი არქიტექტურა წარმოებაში უფრო საიმედოა, ვიდრე ნებისმიერი ზუსტი ამომხსნელი იქნებოდა.

შეხედულება, რომ შეხამებების დაფიქსირების შემდეგ სვლის თანმიმდევრობა ამოხსნადობაზე არ მოქმედებს, ამ სივრცეში ყველაზე ნაკლებად დაფასებული შედეგია. ეს ნიშნავს, რომ თითქოს თანმიმდევრული პრობლემა კომბინატორულ პრობლემად შეგიძლიათ გადააქციოთ, ხოლო კომბინატორული პრობლემები კარგად რეაგირებს შეზღუდვების გავრცელებასა და ჭრაზე. თუ Mahjong-ის ამომხსნელს ქმნით ან თავსატეხური თამაშების სირთულეს სწავლობთ, სწორედ აქედან დაიწყეთ.

ჩემი რჩევა ყველასთვის, ვისაც ამოხსნადობის შემოწმების იმპლემენტაცია სურს: არ დაიწყოთ სირთულის ლიტერატურით. დაიწყეთ მოქმედი განმეორებითი ციკლით, დააკვირდით, რამდენად ხშირად ირთვება თითოეული სარეზერვო ეტაპი, და შემდეგ მოარგეთ სისტემა. თეორია გეუბნებათ ჭერს. გაზომვა გეუბნებათ, სად ხართ რეალურად.

— დმიტრო რომანიუკი

ითამაშეთ Mahjong-ის თავსატეხები, რომლებიც ამოხსნად დაფის გენერაციაზეა აგებული

ყველა თავსატეხი Mahjong Online Club-ზე გენერირდება სწორედ იმ ამოხსნადობაზე ორიენტირებული მიდგომით, რომელიც ამ სტატიაშია აღწერილი. არცერთი დაფა არ მოგეწოდებათ ამომხსნელის ვალიდაციის ეტაპის გავლის გარეშე. ეს ნიშნავს, რომ ყოველი თამაში, რომელსაც იწყებთ, მოსაგებია, ხოლო ყოველი წარუმატებლობა სტრატეგიის პრობლემაა და არა გაფუჭებული განლაგება.

შეგიძლიათ უფასოდ ითამაშოთ Mahjong პირდაპირ ბრაუზერში, რეგისტრაციის გარეშე. პლატფორმა შექმნილია ყურადღების გამფანტველის გარეშე გამოცდილებისთვის, რომელიც კონცენტრაციასა და შაბლონების ამოცნობას უწყობს ხელს. თუ გსურთ აქ აღწერილი ალგორითმული კონცეფციები პრაქტიკაში გამოიყენოთ, ეს სწორედ ის ადგილია.

ხშირად დასმული კითხვები

რა არის Mahjong-ის ამოხსნადობის ალგორითმი?

Mahjong-ის ამოხსნადობის ალგორითმი არის გამოთვლითი პროცედურა, რომელიც განსაზღვრავს, შესაძლებელია თუ არა Mahjong solitaire-ის დაფის სრულად გასუფთავება ყველა ფილის წყვილის შეხამებითა და მოცილებით. ამ პრობლემის გადაწყვეტილების ვერსია ფორმალურად NP-complete არის სრულ ინფორმაციაზე დაყრდნობით.

როგორ მუშაობს Mahjong-ის ამოხსნადობა მათემატიკურად?

ამოხსნადობა დამოკიდებულია 36 ფილის კატეგორიაზე შეხამების არჩევანზე, სადაც თითოეულს 3 შესაძლო შეხამება აქვს, რაც დაახლოებით 150 კვადრილიონ საერთო კონფიგურაციას ქმნის. რადგან სვლის თანმიმდევრობა შედეგს არ ცვლის, როცა შეხამებები უკვე განსაზღვრულია, ამომხსნელები ყურადღებას ამახვილებენ შეხამების შეზღუდვებზე და არა სვლების თანმიმდევრობაზე.

რატომ ვერ წყვეტს პროგრამა Mahjong-ის დაფებს ზუსტად ყოველ ჯერზე?

ამოხსნადობის ზუსტი შემოწმება უარეს შემთხვევაში ექსპონენციალურ გამოთვლას მოითხოვს, რაც რეალურ დროში მომუშავე თამაშის ძრავებისთვის არაპრაქტიკულია. წარმოების სისტემები იყენებენ კონსტრუქციულ გენერატორებს 2,000-მდე განმეორებითი ცდითა და სარეზერვო ეტაპებით, რათა უზრუნველყონ სათამაშო დაფა ზუსტი მტკიცებულების გარეშე.

რა განსხვავებაა np-complete-სა და pspace-complete-ს შორის Mahjong-ში?

გადაწყვეტილების პრობლემა (შეიძლება თუ არა ამ დაფის გასუფთავება?) არის NP-complete. ოპტიმიზაციის პრობლემა (რომელი თანმიმდევრობა მაქსიმუმამდე ზრდის გასუფთავების ალბათობას?) არის PSPACE-complete, რაც მკვეთრად უფრო რთული კლასია და ეფექტურ მიახლოებით ალგორითმებსაც გამორიცხავს.

როგორ უკავშირდება Mahjong-ის თამაშის სტრატეგიები ამოხსნადობის ალგორითმებს?

მოთამაშეები, რომლებიც უპირატესობას ანიჭებენ შეზღუდული ხელმისაწვდომი პარტნიორების მქონე ფილებს და თავს არიდებენ ფილის ჯგუფების იზოლაციას, იყენებენ იმავე შეზღუდვების ჭრის ლოგიკას, რასაც ალგორითმული ამომხსნელები. იმის გაგება, როგორ არის ამოხსნადობა სტრუქტურირებული, სტრატეგიულ გადაწყვეტილებებს უფრო გააზრებულსა და ნაკლებად ვარაუდზე დამოკიდებულს ხდის.

რეკომენდებული

• როგორ ვითამაშოთ Mahjong Solitaire — წესები, ფილი და სტრატეგია
• რატომ ანგრევს ფილის იზოლაცია Mahjong-ის თამაშებს ყველა მოთამაშისთვის
• Mahjong Titans-ის ჩიტები: ამომხსნელები, მინიშნებები და ნამდვილი მოკლე გზები
• რა არის Mahjong-ის მიზანი? წესები და სტრატეგია