სამაგიდო თამაში ხელოვნური ინტელექტი: მინიმაქსის ალგორითმი: 8 ნაბიჯი

2024 ავტორი: John Day | [email protected]. ბოლოს შეცვლილი: 2024-01-30 10:17

ოდესმე გიფიქრიათ იმაზე, თუ როგორ მზადდება კომპიუტერები, რომლებთანაც თამაშობთ ჭადრაკში ან ქვაში? კარგად ნუ შეხედავთ ამ ინსტრუქციულს, რადგან ის გაჩვენებთ თუ როგორ უნდა გააკეთოთ მარტივი, მაგრამ ეფექტური ხელოვნური ინტელექტი (AI) მინიმაქსის ალგორითმის გამოყენებით! მინიმაქსის ალგორითმის გამოყენებით, AI აკეთებს კარგად დაგეგმილ და გააზრებულ ნაბიჯებს (ან სულ მცირე მიბაძავს აზროვნების პროცესს). ახლა მე შემიძლია მოგაწოდოთ კოდი AI, რომელიც მე გავაკეთე, მაგრამ ეს არ იქნება სახალისო. მე ავუხსნი კომპიუტერის არჩევანის ლოგიკას.

ამ ინსტრუქციაში, მე გაგიმხელთ ნაბიჯებს, თუ როგორ უნდა გააკეთოთ AI ოტელოსთვის (AKA Reversi) პითონში. თქვენ უნდა გქონდეთ შუალედური გაგება იმის შესახებ, თუ როგორ უნდა კოდირებდეთ პითონში ამ პროექტთან გამკლავებამდე. აქ არის რამოდენიმე კარგი ვებ – გვერდი, რომლითაც უნდა მოემზადოთ ამ ინსტრუქციისთვის: w3schools or learnpython. ამ ინსტრუქციის ბოლოს, თქვენ უნდა გქონდეთ AI, რომელიც განახორციელებს გათვლილ ნაბიჯებს და უნდა შეეძლოს ადამიანების უმეტესობის დამარცხება.

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

ვისწავლე თუ როგორ უნდა შევქმნა ეს ხელოვნური ინტელექტი საზაფხულო პროგრამის საშუალებით Columbia SHAPE– ში. იქ კარგი დრო გავატარე, ასე რომ გადახედე მათ ვებსაიტს, რომ დაინტერესდე.

ახლა, როდესაც ლოგისტიკა გამოგვივიდა, დავიწყოთ კოდირება!

(მე რამდენიმე შენიშვნა დავდე სურათებში, ასე რომ დარწმუნდით, რომ შეხედეთ მათ)

მარაგები

ეს ადვილია:

1) კომპიუტერი პითონის გარემოთი, როგორიცაა Spyder ან IDLE

2) ჩამოტვირთეთ ფაილები Othello თამაშისთვის ჩემი GitHub– დან

3) თქვენი ტვინი მოთმინებით არის დაყენებული

ნაბიჯი 1: ჩამოტვირთეთ საჭირო ფაილები

როდესაც შედიხარ ჩემს GitHub– ში, უნდა ნახო 5 ფაილი. ჩამოტვირთეთ ხუთივე და განათავსეთ ისინი ერთსა და იმავე საქაღალდეში. თამაშის დაწყებამდე, გახსენით ყველა ფაილი სპაიდერის გარემოში.

აი რას აკეთებს ფაილები:

1) othello_gui.py ეს ფაილი ქმნის სათამაშო დაფას მოთამაშეთა სათამაშოდ (იქნება ეს ადამიანი თუ კომპიუტერი)

2) othello_game.py ეს ფაილი თამაშობს ორ კომპიუტერს ერთმანეთის წინააღმდეგ დაფის გარეშე და მხოლოდ აჩვენებს ანგარიშს და გადაადგილების პოზიციებს

3) ai_template.py ეს არის ის ადგილი, სადაც თქვენ დააყენებთ მთელ კოდს თქვენი AI- ს შესაქმნელად

4) randy_ai.py ეს არის წინასწარ შექმნილი AI, რომელიც ირჩევს თავის მოძრაობებს შემთხვევით

5) othello_shared.py რამოდენიმე წინასწარ დამზადებული ფუნქცია, რომლითაც შეგიძლიათ გამოიყენოთ თქვენი AI, როგორიცაა არსებული მოძრაობების, ქულის ან დაფის მდგომარეობის შემოწმება

6) სამი სხვა ფაილი: Puma.py, erika_5.py და nathan.py, დამზადებული ჩემ მიერ, ერიკასა და ნათანის შესაბამისად SHAPE პროგრამიდან, ეს არის სამი განსხვავებული AI უნიკალური კოდით

ნაბიჯი 2: როგორ გავხსნათ და ვითამაშოთ პითონ ოტელო

მას შემდეგ რაც გახსნით ყველა ფაილს, ეკრანის ქვედა მარჯვენა კუთხეში ჩაწერეთ "run othello_gui.py" და დააჭირეთ IPython კონსოლში enter. ან Mac ტერმინალში, ჩაწერეთ "python othello_gui.py" (რა თქმა უნდა, მას შემდეგ რაც სწორ საქაღალდეში მოხვდებით). შემდეგ თქვენს ეკრანზე უნდა გამოჩნდეს დაფა. ეს რეჟიმი არის ადამიანის და ადამიანის რეჟიმი. სინათლე მიდის მეორე და ბნელი პირველი. ნახეთ ჩემი ვიდეო თუ დაბნეული ხართ. iApple, არის ქულა თითოეული ფერი ფილა. სათამაშოდ, დააწკაპუნეთ მოქმედი გადაადგილების სივრცეზე, რომ მოათავსოთ ფილა და შემდეგ მიეცით კომპიუტერი თქვენს მოწინააღმდეგეს, რომელიც იგივეს გააკეთებს და გაიმეორებს.

თუ არ იცით როგორ ითამაშო ოთილიე, წაიკითხე ეს წესები ულტრა დაფების ვებგვერდიდან:

შავი ყოველთვის პირველი მოძრაობს. სვლა ხდება მოთამაშის ფერის დისკის დაფაზე განთავსებით იმ პოზიციაში, რომელიც "გარს ფლანგავს" მეტოქის ერთ ან მეტ დისკს. დისკი ან დისკი რიგით გამორთულია, როდესაც იგი გარშემორტყმულია ბოლოებში საპირისპირო ფერის დისკებით. დისკს შეუძლია გადააჭარბოს ნებისმიერი რაოდენობის დისკს ერთ ან მეტ სტრიქონში ნებისმიერი მიმართულებით (ჰორიზონტალური, ვერტიკალური, დიაგონალური)…. (დაასრულეთ კითხვა მათ ვებგვერდზე)

განსხვავება ორიგინალ თამაშსა და პითონის თამაშს შორის არის ის, რომ როდესაც ერთი მოთამაშისთვის არ დარჩა მოქმედი მოძრაობები, თამაში მთავრდება

ახლა, როდესაც თქვენ შეგიძლიათ ითამაშოთ თამაში მეგობართან ერთად, მოდით გავაკეთოთ AI, რომლითაც შეგიძლიათ ითამაშოთ.

ნაბიჯი 3: მინიმაქსის ალგორითმი: გენერირების სცენარები

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

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

მე ამას უკანდახევის ალგორითმი ვუწოდე, რადგან ის იწყება ყველა მომავალი დაფის მდგომარეობის შექმნით და შეფასებით მათთან დაკავშირებული ღირებულებებით. ეს ნიშნავს, რომ ალგორითმი თამაშობს იმდენს, რამდენიც სჭირდება (გადადგამს ნაბიჯებს თავისთვის და მოწინააღმდეგისთვის) მანამ, სანამ თამაშის ყველა სცენარი არ დასრულდება. დაფის ყველა მდგომარეობის თვალყურის დევნება (სცენარი), ჩვენ შეგვიძლია დავხატოთ ხე (შეხედეთ სურათებს). ხე ზემოთ მოცემულ სურათზე არის მაგალითი Connect 4 თამაშის. ყველა დაფის კონფიგურაციას ეწოდება დაფის მდგომარეობა და მის ადგილს ხეზე ეწოდება კვანძი. ხის ბოლოში ყველა კვანძი არის დაფის საბოლოო მდგომარეობა ყველა ნაბიჯის გადადგმის შემდეგ. ცხადია, რომ საბჭოს ზოგიერთი შტატი ერთი მოთამაშისთვის უკეთესია, ვიდრე მეორე. ამრიგად, ჩვენ ახლა უნდა ვაიძულოთ AI- მ აირჩიოს, რომელ დაფის სახელმწიფოს სურს მიაღწიოს მას.

ნაბიჯი 4: მინიმაქსი: დაფის კონფიგურაციების შეფასება

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

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

ამის მრავალი გზა არსებობს და მე მაქვს სამი განსხვავებული ევრისტიკული, რომ შევაფასო დაფის ნაწილები. მე გირჩევთ, შეადგინოთ თქვენი საკუთარი სახის ევრისტიკული. სამი განსხვავებული შემქმნელის მიერ ჩემს github– ში ავტვირთე სამი განსხვავებული AI, სამი განსხვავებული ჰერისტიკით: Puma.py, erika5.py, nathanh.py.

ნაბიჯი 5: მინიმაქსის ალგორითმი: საუკეთესო ნაბიჯის არჩევა

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

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

განმარტებები: მშობელი კვანძი - კვანძი, რომელიც იწვევს ან ქმნის მის ქვემოთ კვანძებს; ბავშვთა კვანძების წარმოშობა - კვანძები, რომლებიც ერთი და იგივე მშობლის კვანძიდან მოდის

ცარიელი კვანძები წარმოადგენს იმას, თუ რომელი გადაადგილება მოახდენს AI– ს დაფის საუკეთესო მდგომარეობამდე მისასვლელად. იგი იწყება მარცხენა კვანძის შვილების შედარებით: 10, -3, 5. ვინაიდან მოთამაშე მაქსიმალურად გადადგამს ნაბიჯს, ის ირჩევს სვლას, რომელიც მისცემს მას ყველაზე მეტ ქულას: 10. ამრიგად, ჩვენ ვირჩევთ და ვინახავთ მას გადაადგილება დაფის ანგარიშით და ჩაწერეთ იგი მშობლის კვანძში. ახლა, როდესაც 10 მშობლის კვანძშია, მოთამაშეთა მინიმიზაციის დროა. თუმცა, კვანძი, რომელსაც ჩვენ შევადარებთ 10 -ს, ცარიელია, ამიტომ ჩვენ უნდა შევაფასოთ ეს კვანძი ჯერ მანამ, სანამ მინიმალისტური მოთამაშე აირჩევს. ასე რომ, ჩვენ ვუბრუნდებით მოთამაშის მაქსიმალურ რიგს და ვადარებთ მიმდებარე კვანძის შვილებს: 8, -2. მაქსიმიზაცია აირჩევს 8 -ს და ჩვენ ამას ვწერთ ცარიელი მშობლის კვანძში. ახლა, როდესაც ალგორითმმა დაასრულა ცარიელი ადგილების შევსება მის ზემოთ მდებარე კვანძის ბავშვებისათვის, მინიმიზაციის მოთამაშეს შეუძლია შეადაროს ის ბავშვები - 10 და 8 და აირჩიოს 8. ალგორითმი შემდეგ იმეორებს ამ პროცესს, სანამ მთელი ხე არ შეივსება. ამ მაგალითის დასასრულს, ჩვენ გვაქვს ანგარიში 8. ეს არის ყველაზე მაღალი დაფის მდგომარეობა, რომელსაც AI შეუძლია შეასრულოს, თუ ვივარაუდოთ, რომ ოპონენტი თამაშობს ოპტიმალურად. ასე რომ, AI აირჩევს პირველ ნაბიჯს, რომელიც მივყავართ მე –8 დაფის მდგომარეობამდე და თუ ოპონენტი თამაშობს ოპტიმალურად, AI– მ უნდა შეასრულოს ყველა ნაბიჯი იმისათვის, რომ მიაღწიოს მე –8 მდგომარეობას (მიჰყევით ჩანაწერებს ჩემს სურათებზე)

ვიცი, რომ ბევრი იყო. თუ თქვენ ერთ – ერთი ხართ იმ ტიპებს შორის, რომელთაც სჭირდებათ ვინმესთან საუბარი რომ გაიგოს რამე, აქ არის რამოდენიმე ვიდეო, რომელიც მე ვუყურე, რათა დამეხმაროს ამ იდეის მიღმა: 1, 2, 3.

ნაბიჯი 6: მინიმაქსის ალგორითმი: ფსევდოკოდი

მას შემდეგ რაც გაიგებთ მინიმაქსის ალგორითმის ლოგიკას, გადახედეთ ვიკიპედიიდან ამ ფსევდოკოდს (ფუნქციები, რომლებიც უნივერსალურია ყველა კოდისთვის):

ფუნქცია minimax (კვანძი, სიღრმე, maximizingPlayer) არის

თუ სიღრმე = 0 ან კვანძი არის ტერმინალური კვანძი, მაშინ

კვანძის ევრისტიკული მნიშვნელობის დაბრუნება

თუ maximizingPlayer მაშინ

მნიშვნელობა: = −∞

თითოეული ბავშვის კვანძის გავაკეთოთ

მნიშვნელობა: = მაქსიმალური (მნიშვნელობა, მინიმაქსი (ბავშვი, სიღრმე - 1, FALSE))

დაბრუნების მნიშვნელობა

სხვა (* მოთამაშის მინიმიზაცია *)

მნიშვნელობა: = +∞

თითოეული ბავშვის კვანძის გავაკეთოთ

მნიშვნელობა: = წთ (მნიშვნელობა, მინიმაქსი (ბავშვი, სიღრმე - 1, TRUE))

დაბრუნების მნიშვნელობა

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

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

ნაბიჯი 7: შექმენით თქვენი AI Ai_template.py– ით

სანამ ჩემს Minimax AI კოდს შეხედავ, გაანებე მცდელობა შექმნა შენი საკუთარი AI ai_template.py ფაილით და ფსევდო კოდით, რომელზეც ჩვენ ვისაუბრეთ ბოლო ეტაპზე. აი შაბლონში ორი ფუნქციაა: def minimax_min_node (დაფა, ფერი) და def minimax_max_node (დაფა, ფერი). იმის ნაცვლად, რომ მინიმაქსის ფუნქცია თავისთავად რეკურსიულად გამოვიძახოთ, ჩვენ გვაქვს ორი განსხვავებული ფუნქცია, რომლებიც ერთმანეთს ურეკავენ. დაფის მდგომარეობის შესაფასებლად ევრისტიკული შესაქმნელად, თქვენ უნდა შექმნათ თქვენი საკუთარი ფუნქცია. არსებობს წინასწარ შექმნილი ფუნქციები othello_shared.py ფაილში, რომლითაც შეგიძლიათ გამოიყენოთ თქვენი AI.

მას შემდეგ რაც თქვენ გაქვთ თქვენი AI, სცადეთ მისი გაშვება, randy_ai.py. ორი ais ერთმანეთის საწინააღმდეგოდ გასაშვებად ჩაწერეთ "python othello_gui.py (ჩაწერეთ ai ფაილის სახელი).py (ჩაწერეთ ფაილის სახელი).py" mac ტერმინალში ან ჩაწერეთ "run othello_gui.py (ჩაწერეთ ai ფაილის სახელი).py (ჩაწერეთ ფაილის სახელი).py "და დარწმუნდით, რომ სწორ დირექტორიაში ხართ. ასევე, გადახედეთ ჩემს ვიდეოს ზუსტი ნაბიჯებისთვის.

ნაბიჯი 8: დროა გავაკეთოთ AI ბრძოლა

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