Stalo žaidimas Dirbtinis intelektas: „Minimax“algoritmas: 8 žingsniai

2024 Autorius: John Day | [email protected]. Paskutinį kartą keistas: 2024-01-30 10:46

Ar kada susimąstėte, kaip gaminami kompiuteriai, prieš kuriuos žaidžiate šachmatais ar šaškėmis? Neskubėkite ieškoti šios instrukcijos, nes ji parodys, kaip sukurti paprastą, bet veiksmingą dirbtinį intelektą (AI) naudojant „Minimax“algoritmą! Naudodamas „Minimax“algoritmą, AI atlieka gerai suplanuotus ir apgalvotus judesius (arba bent jau imituoja minties procesą). Dabar galėčiau duoti jums mano sukurto AI kodą, bet tai nebūtų smagu. Aš paaiškinsiu kompiuterio pasirinkimo logiką.

Šioje instrukcijoje nurodysiu, kaip sukurti „Othello“(AKA „Reversi“) dirbtinį intelektą dirbant „Python“. Prieš pradėdami šį projektą, turėtumėte gerai suprasti, kaip koduoti „python“. Štai keletas gerų svetainių, į kurias reikia atkreipti dėmesį, norint pasiruošti šiai instrukcijai: „w3schools“arba „learnpython“. Šios instrukcijos pabaigoje turėtumėte turėti AI, kuris atliks apskaičiuotus judesius ir sugebės nugalėti daugumą žmonių.

Kadangi šis „Instructable“pirmiausia bus susijęs su AI kūrimu, neaiškinsiu, kaip sukurti žaidimą „python“. Vietoj to aš duosiu žaidimo, kuriame žmogus gali žaisti prieš kitą žmogų, kodą ir pakeisiu jį taip, kad galėtumėte žaisti žaidimą, kuriame žmogus žaidžia prieš AI.

Aš sužinojau, kaip sukurti šį AI per vasaros programą „Columbia SHAPE“. Aš ten gerai praleidau laiką, todėl pažiūrėkite į jų svetainę ir sužinokite, ar jums bus įdomu.

Dabar, kai mes pašalinome logistiką, pradėkime koduoti!

(Į paveikslėlius įdėjau keletą pastabų, todėl būtinai į jas pažiūrėkite)

Prekės

Tai lengva:

1) Kompiuteris su „Python“aplinka, tokia kaip „Spyder“arba „IDLE“

2) Atsisiųskite „Othello“žaidimo failus iš „GitHub“

3) Jūsų smegenys su kantrybe

1 veiksmas: atsisiųskite būtinus failus

Kai einate į mano „GitHub“, turėtumėte pamatyti 5 failus. Atsisiųskite visus 5 ir įdėkite juos į tą patį aplanką. Prieš paleisdami žaidimą, atidarykite visus failus šnipinėjimo aplinkoje.

Štai ką daro failai:

1) othello_gui.py šis failas sukuria žaidimo lentą, kurioje žaidėjai gali žaisti (nesvarbu, ar žmogus, ar kompiuteris)

2) othello_game.py šis failas žaidžia du kompiuterius vienas prieš kitą be žaidimų lentos ir rodo tik rezultatą ir judėjimo pozicijas

3) ai_template.py čia įdėsite visą savo kodą, kad sukurtumėte savo AI

4) randy_ai.py tai yra iš anksto paruoštas AI, kuris atsitiktinai pasirenka savo judesius

5) othello_shared.py krūva iš anksto paruoštų funkcijų, kurias galite naudoti savo dirbtiniam intelektui sukurti, pvz., Patikrinti galimus judesius, rezultatą ar lentos būseną

6) Trys kiti failai: „Puma.py“, „erika_5.py“ir „nathan.py“, kuriuos aš, Erika ir Nathan padariau atitinkamai iš programos SHAPE, tai trys skirtingi AI su unikaliais kodais

2 veiksmas: kaip atidaryti ir paleisti „Python Othello“

Atidarę visus failus, apatiniame dešiniajame ekrano kampe įveskite „run othello_gui.py“ir paspauskite „Enter“„IPython“konsolėje. Arba „Mac“terminale įveskite „python othello_gui.py“(žinoma, atsidūrę tinkamame aplanke). Tada jūsų ekrane turėtų pasirodyti lenta. Šis režimas yra žmogaus ir žmogaus režimas. Šviesa eina antra, o tamsa - pirma. Pažiūrėkite į mano vaizdo įrašą, jei esate sumišęs. i Viršuje yra kiekvienos spalvos plytelės balas. Jei norite žaisti, spustelėkite galiojančią judėjimo vietą, kad ten įdėtumėte plytelę, tada paduokite kompiuterį savo priešininkui, kuris padarys tą patį ir pakartos.

Jei nežinote, kaip žaisti „Othello“, perskaitykite šias taisykles „ultra boards“svetainėje:

Juoda visada juda pirma. Žingsnis atliekamas padedant žaidėjo spalvos diską ant lentos tokioje padėtyje, kuri „peržengia“vieną ar daugiau priešininko diskų. Diskas arba diskų eilė yra apjuosta, kai galuose juosia priešingos spalvos diskai. Diskas gali aplenkti bet kokį skaičių diskų vienoje ar keliose eilėse bet kuria kryptimi (horizontali, vertikali, įstrižainė)…. (baigti skaityti jų svetainėje)

Skirtumas tarp pradinio žaidimo ir šio „Python“žaidimo yra tas, kad kai vienam žaidėjui nebelieka galiojančių ėjimų, žaidimas baigiasi

Dabar, kai galite žaisti žaidimą su draugu, sukurkime AI, su kuriuo galėsite žaisti.

3 žingsnis: „Minimax“algoritmas: scenarijų kūrimas

Prieš kalbėdami apie tai, kaip tai parašyti kodu, apžvelkime logiką. Minimumx algoritmas yra sprendimų priėmimo, atgalinio sekimo algoritmas ir paprastai naudojamas dviejų žaidėjų, ėjimais pagrįstuose žaidimuose. Šio AI tikslas yra rasti kitą geriausią ėjimą ir sekančius geriausius judesius, kol jis laimės žaidimą.

Dabar kaip algoritmas nustatytų, kuris žingsnis yra geriausias? Sustokite ir pagalvokite, kaip pasirinktumėte kitą žingsnį. Dauguma žmonių pasirinktų tą žingsnį, kuris suteiktų daugiausiai taškų, tiesa? Arba jei jie galvotų į priekį, jie pasirinktų žingsnį, kuris sudarytų situaciją, kai jie galėtų gauti dar daugiau taškų. Pastarasis mąstymo būdas yra „Minimax“algoritmo mąstymo būdas. Jis žvelgia į visas būsimas lentos sąrankas ir daro žingsnį, kuris sudarytų daugiausiai taškų.

Aš tai pavadinau atgaliniu algoritmu, nes jis pirmiausia sukuriamas ir įvertinamas visos būsimos valdybos būsenos su jomis susijusiomis vertėmis. Tai reiškia, kad algoritmas žais žaidimą tiek, kiek reikia (atlikdamas judesius sau ir priešininkui), kol bus įvykdytas kiekvienas žaidimo scenarijus. Norėdami sekti visas lentos būsenas (scenarijus), galime piešti medį (žiūrėkite paveikslėliuose). Aukščiau esančiame paveikslėlyje esantis medis yra paprastas „Connect 4“žaidimo pavyzdys. Kiekviena lentos konfigūracija vadinama lentos būsena, o jos vieta medyje - mazgas. Visi medžio apačioje esantys mazgai yra paskutinės lentos būsenos, atlikus visus judesius. Akivaizdu, kad kai kurios lentos būsenos yra geresnės vienam žaidėjui nei kitam. Taigi, dabar mes turime priversti AI pasirinkti, į kurią valdybos būseną jis nori patekti.

4 žingsnis: „Minimax“: plokštės konfigūracijų įvertinimas

Kad valdybos nariams suteiktume vertybes, turime išmokti žaidimo strategijas: šiuo atveju Othello strategijas. Kadangi šis žaidimas yra priešo ir jūsų diskų vartymo kova, geriausios disko pozicijos yra tos, kurios yra stabilios ir kurių negalima apversti. Pavyzdžiui, kampas yra vieta, kur įdėjus diską jo negalima pakeisti kita spalva. Taigi ta vieta būtų labai vertinga. Kitos geros pozicijos apima lentos šonus, kurie leistų jums paimti daug akmenų. Šioje svetainėje yra daugiau strategijų.

Dabar kiekvienos valdybos valdybos pozicijoms galime priskirti vertes. Kai poziciją užima dirbtinio intelekto gabalas, jūs suteikiate tam tikrą taškų skaičių, priklausomai nuo padėties. Pavyzdžiui, lentoje nurodoma, kad dirbtinio intelekto gabalas yra kampe, galite skirti 50 taškų premiją, tačiau jei ji būtų nepalankioje vietoje, kūrinio vertė gali būti 0. Įvertinus visas pozicijas, jūs priskiriate valdybai būseną. Pvz., Jei dirbtinio intelekto kampe yra gabalas, lentos būsena gali būti 50 balų, o kita plokštės būsena, kurios AI gabalas yra viduryje, turi 10 balų.

Yra daug būdų tai padaryti, ir aš turiu tris skirtingas euristikas, kad galėčiau įvertinti plokštės gabalus. Aš raginu jus sukurti savo euristikos tipą. Į savo „Github“įkėliau tris skirtingus AI, kuriuos sukūrė trys skirtingi gamintojai, turintys tris skirtingas euristines savybes: Puma.py, erika5.py, nathanh.py.

5 žingsnis: „Minimax“algoritmas: geriausio judėjimo pasirinkimas

Dabar būtų malonu, jei AI galėtų tiesiog pasirinkti visus judesius, kad pasiektų aukščiausią balą. Tačiau atminkite, kad dirbtinis intelektas taip pat rinkdavosi priešo judesius, kai generuodavo visas lentos būsenas, o jei priešininkas yra protingas, tai neleis AI pasiekti aukščiausio lentos balo. Vietoj to protingas priešininkas imtųsi veiksmų, kad AI pereitų į žemiausią lentos būseną. Pagal algoritmą abu žaidėjus vadiname maksimaliai didinančiu ir minimalizuojančiu žaidėju. PG būtų didžiausias žaidėjas, nes jis nori gauti kuo daugiau taškų. Priešininkas būtų minimalus žaidėjas, nes priešininkas bando atlikti ėjimą ten, kur AI gauna mažiausiai taškų.

Kai visos plokštės būsenos sugeneruojamos ir lentoms priskiriamos vertės, algoritmas pradeda lyginti plokštės būsenas. Paveiksluose sukūriau medį, kuris parodo, kaip algoritmas pasirenka savo judesius. Kiekvienas padalijimas šakose yra skirtingas AI ar priešininko judesys. Kairėje nuo mazgų eilučių parašiau, ar didinimo ar mažinimo žaidėjas eina. Apatinėje eilutėje yra visos lentos būsenos su jų vertėmis. Kiekvieno iš šių mazgų yra skaičius ir tai yra balai, kuriuos priskiriame kiekvienai iš lentų: kuo jie aukštesni, tuo geriau AI turi.

Apibrėžimai: pirminis mazgas - mazgas, kuris sukuria arba sukuria mazgus po juo; vaikų mazgų kilmė - mazgai, kilę iš to paties pirminio mazgo

Tušti mazgai rodo, kurie AI judės, kad pasiektų geriausią plokštės būseną. Jis prasideda lyginant kairiausio kairiojo mazgo vaikus: 10, -3, 5. Kadangi maksimaliai didinantis žaidėjas atliks ėjimą, jis pasirinks tą ėjimą, kuris jam suteiktų daugiausiai taškų: 10. Taigi, mes pasirenkame ir išsaugome tą judėkite su lentos balu ir įrašykite jį į pirminį mazgą. Dabar, kai 10 yra pagrindiniame mazge, dabar atėjo mažinančių žaidėjų eilė. Tačiau mazgas, su kuriuo galėtume palyginti 10, yra tuščias, todėl pirmiausia turime įvertinti tą mazgą prieš pasirinkdami mažinimo žaidėją. Taigi grįžtame prie maksimizuojančio žaidėjo posūkio ir palyginame gretimo mazgo vaikus: 8, -2. Maksimalizavimas pasirinks 8, o tai įrašysime į tuščią pirminį mazgą. Dabar, kai algoritmas baigė užpildyti tuščias vietas virš jo esančio mazgo vaikams, mažinimo žaidėjas gali palyginti tuos vaikus - 10 ir 8 ir pasirinkti 8. Tada algoritmas kartoja šį procesą, kol bus užpildytas visas medis. Šio pavyzdžio pabaigoje turime 8 balus. Tai aukščiausia lentos būsena, kurią gali žaisti dirbtinis intelektas, darant prielaidą, kad priešininkas žaidžia optimaliai. Taigi AI pasirinks pirmąjį ėjimą, kuris veda į 8 lentos būseną, o jei priešininkas žaidžia optimaliai, AI turėtų atlikti visus judesius, kad pasiektų 8 būsenos būseną. (Sekite pastabas mano nuotraukose)

Žinau, kad tai buvo daug. Jei esate vienas iš tų tipų, kuriems reikia, kad kas nors su jumis kalbėtų, kad ką nors suprastumėte, čia yra keletas vaizdo įrašų, kuriuos aš žiūrėjau, kad padėtų man suprasti šios idėjos esmę: 1, 2, 3.

6 žingsnis: Minimax algoritmas: pseudokodas

Supratę minimax algoritmo logiką, peržiūrėkite šį pseudokodą (funkcijas, kurios yra universalios visiems kodams) iš Vikipedijos:

funkcija minimumx (mazgas, gylis, maksimalus žaidėjas) yra

jei gylis = 0 arba mazgas yra galinis mazgas, tada

grąžina euristinę mazgo vertę

jei maksimizuojate žaidėją, tada

vertė: = −∞

už kiekvieną mazgo vaiką

vertė: = max (vertė, minimumx (vaikas, gylis - 1, FALSE))

grąžinimo vertė

else (* žaidėjo sumažinimas *)

vertė: = +∞

už kiekvieną mazgo vaiką

vertė: = min (vertė, minimumas (vaikas, gylis - 1, TRUE))

grąžinimo vertė

Tai rekursinė funkcija, tai reiškia, kad ji vėl ir vėl skambina, kol pasiekia sustojimo tašką. Pirma, funkcija įgauna tris reikšmes - mazgą, gylį ir kieno eilė. Mazgo reikšmė yra vieta, kurioje norite, kad programa pradėtų ieškoti. Gylis yra tai, kiek norite, kad programa ieškotų. Pavyzdžiui, mano medžio pavyzdyje jo gylis yra 3, nes po 3 judesių jis ieškojo visų lentos būsenų. Žinoma, norėtume, kad AI patikrintų kiekvieną lentos būseną ir pasirinktų laimėtą laimėjimą, tačiau daugumoje žaidimų, kuriuose yra tūkstančiai, jei ne milijonai lentos konfigūracijų, jūsų nešiojamasis kompiuteris namuose negalės apdoroti visų šių konfigūracijų. Taigi, mes apribojame AI paieškos gylį ir leidžiame pasiekti geriausią lentos būseną.

Šis pseudokodas atkuria procesą, kurį paaiškinau ankstesniuose dviejuose žingsniuose. Dabar padarykime tai dar vieną žingsnį ir ištaisykime tai python kode.

7 veiksmas: sukurkite savo AI naudodami Ai_template.py

Prieš pažvelgdami į mano „Minimax“AI kodą, pabandykite sukurti savo AI naudodami failą ai_template.py ir pseudo kodą, apie kurį kalbėjome paskutiniame žingsnyje. Ai šablone yra dvi funkcijos: def minimumx_min_node (lenta, spalva) ir def minimumx_max_node (lenta, spalva). Vietoj to, kad minimax funkcija vadintųsi rekursyviai, mes turime dvi skirtingas funkcijas, kurios viena kitą vadina. Norėdami sukurti euristiką, skirtą įvertinti valdybos būsenas, turėsite sukurti savo funkciją. Othello_shared.py faile yra iš anksto paruoštų funkcijų, kurias galite naudoti kurdami savo AI.

Kai turėsite savo AI, pabandykite jį panaudoti, randy_ai.py. Norėdami paleisti du ais vienas prieš kitą, įveskite „python othello_gui.py (įterpkite ai failo pavadinimą).py (įterpkite failo pavadinimą).py“„Mac“terminale arba įveskite „run othello_gui.py (įterpkite ai failo pavadinimą).py (įterpkite failo pavadinimą).py ir įsitikinkite, kad esate tinkamame kataloge. Taip pat žiūrėkite mano vaizdo įrašą, kad sužinotumėte tikslius veiksmus.

8 žingsnis: laikas kovoti su AI

Dabar susiraskite daugybę savo kompiuterio draugų ir priverskite juos kurti savo AI! Tada galite surengti konkursą ir išsiųsti savo AI kunigaikščiui. Tikimės, kad net jei negalėtumėte sukurti savo AI, sugebėjote suprasti, kaip veikia minimax algoritmas. Jei turite klausimų, nedvejodami rašykite visus klausimus toliau pateiktose pastabose.