Lauamäng Tehisintellekt: Minimaxi algoritm: 8 sammu

2024 Autor: John Day | [email protected]. Viimati modifitseeritud: 2024-01-30 08:47

Kas olete kunagi mõelnud, kuidas arvutid, mille vastu males või kabes mängite, on tehtud? Ärge otsige sellest juhendist kaugemale, sest see näitab teile, kuidas luua minimaalset maksimumalgoritmi kasutades lihtsat, kuid tõhusat tehisintellekti (AI)! Minimaxi algoritmi kasutades teeb tehisintellekt hästi planeeritud ja läbimõeldud liigutusi (või vähemalt jäljendab mõtteprotsessi). Nüüd võiksin teile lihtsalt anda oma tehtud AI koodi, kuid see poleks lõbus. Selgitan arvuti valikute loogikat.

Selles juhendis tutvustan teile juhiseid Othello (AKA Reversi) tehisintellekti loomiseks pythonis. Enne selle projektiga tegelemist peaks teil olema vahepealne arusaam sellest, kuidas pythonis kodeerida. Siin on mõned head veebisaidid, mida vaadata selle juhendi ettevalmistamiseks: w3schools või learnpython. Selle juhendi lõpus peaks teil olema tehisintellekt, mis teeks arvutatud käike ja suudaks võita enamiku inimesi.

Kuna see juhend sisaldab peamiselt tehisintellekti loomist, ei hakka ma selgitama, kuidas mängu pythonis kujundada. Selle asemel annan ma mängu koodi, kus inimene saab mängida teise inimese vastu ja muuta seda nii, et saate mängida mängu, kus inimene mängib tehisintellekti vastu.

Selle AI loomise õppisin läbi Columbia SHAPE suveprogrammi. Mul oli seal tore, nii et vaadake nende veebisaiti, et näha, kas olete huvitatud.

Nüüd, kui oleme logistika teelt ära saanud, alustame kodeerimist!

(Panin piltidele paar märkust, nii et vaadake neid kindlasti)

Tarvikud

See on lihtne:

1) Pythoni keskkonnaga arvuti, näiteks Spyder või IDLE

2) Laadige Othello mängu failid alla minu GitHubist

3) Teie aju on varustatud kannatlikkusega

Samm: laadige alla vajalikud failid

Minu GitHubi sisenedes peaksite nägema 5 faili. Laadige alla kõik 5 ja asetage need kõik samasse kausta. Enne mängu käivitamist avage kõik spyderi keskkonnas olevad failid.

Failid teevad järgmist.

1) othello_gui.py see fail loob mängulaua, kus mängijad saavad mängida (olgu see inimene või arvuti)

2) othello_game.py see fail mängib ilma arvutitahvlita kaks arvutit üksteise vastu ning näitab ainult tulemust ja liigutuspositsioone

3) ai_template.py see on koht, kuhu paned kogu oma koodi, et teha oma AI

4) randy_ai.py see on eelvalmis tehisintellekt, mis valib oma käigud juhuslikult

5) othello_shared.py hunnik eelvalmistatud funktsioone, mida saate kasutada oma tehisintellekti loomiseks, näiteks olemasolevate käikude, tulemuste või tahvli oleku kontrollimiseks

6) Kolm muud faili: Puma.py, erika_5.py ja nathan.py, mille tegin mina, Erika ja Nathan vastavalt programmist SHAPE, need on kolm erinevat unikaalsete koodidega AI -d

Samm: kuidas Python Othellot avada ja mängida

Kui olete kõik failid avanud, tippige ekraani paremasse alumisse nurka "run othello_gui.py" ja vajutage IPython Console'i sisestusklahvi. Või tippige Maci terminalis "python othello_gui.py" (muidugi, kui olete õiges kaustas). Seejärel peaks teie ekraanile ilmuma tahvel. See režiim on inimene vs inimene. Valgus läheb teiseks ja pimedus esimeseks. Vaadake minu videot, kui olete segaduses. iÜlaosas on iga värviplaadi skoor. Mängimiseks klõpsake kehtivat liikumisruumi, et asetada plaat sinna ja seejärel andke arvuti oma vastasele, kes teeb sama ja kordab.

Kui te ei tea, kuidas Othellot mängida, lugege neid reegleid ultralaudade veebisaidilt:

Must liigub alati esimesena. Liigutamiseks pannakse mängijavärvi ketas lauale asendisse, mis "külgneb" ühe või mitme vastase kettaga. Ketas või kettarida on ääristatud, kui see on otstest ümbritsetud vastupidist värvi ketastega. Plaat võib ületada suvalise arvu plaate ühes või mitmes reas mis tahes suunas (horisontaalne, vertikaalne, diagonaal)…. (lõpetage lugemine nende veebisaidil)

Erinevus algse mängu ja selle pythonimängu vahel on see, et kui ühele mängijale pole ühtegi kehtivat käiku jäänud, lõpeb mäng

Nüüd, kui saate mängu koos sõbraga mängida, teeme tehisintellekti, millega saate mängida.

3. samm: Minimaxi algoritm: stsenaariumide loomine

Enne kui räägime sellest, kuidas seda koodis kirjutada, vaatame üle selle taga oleva loogika. Minimaalse algoritm on otsuste tegemise, tagantjärele jälgimise algoritm ja seda kasutatakse tavaliselt kahe mängijaga käigupõhistes mängudes. Selle AI eesmärk on leida järgmine parim käik ja järgmised parimad käigud, kuni see mängu võidab.

Kuidas saaks algoritm nüüd kindlaks teha, milline käik on parim käik? Peatu ja mõtle, kuidas valiksid järgmise sammu. Enamik inimesi valiks selle sammu, mis annaks neile kõige rohkem punkte, eks? Või kui nad mõtleksid edasi, valiksid nad sammu, mis looks olukorra, kus nad saaksid veelgi rohkem punkte. Viimane mõtteviis on viis, kuidas Minimaxi algoritm mõtleb. See vaatab kõiki tulevasi plaadiseadistusi ette ja teeb sammu, mis tooks kõige rohkem punkte.

Ma nimetasin seda tagasitõmbamisalgoritmiks, sest see algab kõigepealt kõigi tulevaste tahvli olekute loomisest ja hindamisest koos nendega seotud väärtustega. See tähendab, et algoritm mängib mängu nii palju kui vaja (teeb liigutusi endale ja vastasele), kuni iga mängu stsenaarium on mängitud. Kõigi tahvli olekute (stsenaariumide) jälgimiseks saame joonistada puu (vaata piltidelt). Puu ülaltoodud pildil on lihtne näide Connect 4 mängust. Iga tahvli konfiguratsiooni nimetatakse tahvli olekuks ja selle kohta puul nimetatakse sõlmeks. Kõik puu allosas olevad sõlmed on pärast kõigi käikude tegemist plaadi lõplikud olekud. Ilmselgelt on mõned lauaseisud ühele mängijale paremad kui teisele. Niisiis, nüüd peame laskma AI -l valida, millisele juhatuse olekule ta soovib jõuda.

Samm 4: Minimax: tahvli konfiguratsioonide hindamine

Juhatusriikidele väärtuste andmiseks peame õppima mängitava mängu strateegiaid: antud juhul Othello strateegiaid. Kuna see mäng on vastase ja teie ketaste pööramise lahing, on parimad kettapositsioonid need, mis on stabiilsed ja mida ei saa ümber pöörata. Näiteks nurk on koht, kus plaati asetades ei saa seda teise värviga muuta. Seega oleks see koht väga väärtuslik. Muud head positsioonid hõlmavad tahvli külgi, mis võimaldaksid teil võtta palju kive. Sellel veebisaidil on rohkem strateegiaid.

Nüüd saame määrata väärtused iga juhatuse osariigi juhatuse positsioonidele. Kui positsiooni hõivab tehisintellekti tükk, annate sõltuvalt positsioonist teatud arvu punkte. Näiteks pardal, kus tehisintellekti tükk on nurgas, saate anda 50 punkti boonust, kuid kui see oleks ebasoodsas kohas, võib tüki väärtus olla 0. Pärast kõigi väärtuste arvessevõtmist positsioonidele, määrate juhatuse olekule väärtuse. Näiteks kui tehisintellekti nurgas on tükk, võib tahvli olekul olla skoor 50, samal ajal kui teise tahvli oleku puhul, kus tehisintellekti tükk on keskel, on skoor 10.

Selleks on palju viise ja mul on plaaditükkide hindamiseks kolm erinevat heuristikat. Soovitan teil teha oma tüüpi heuristika. Laadisin oma githubi üles kolm erinevat AI -d kolme erineva heuristikaga: Puma.py, erika5.py, nathanh.py.

5. samm: Minimaxi algoritm: parima käigu valimine

Nüüd oleks tore, kui tehisintellekt saaks lihtsalt valida kõik liigutused, et jõuda kõrgeima punktisummaga lauaseisundisse. Kuid pidage meeles, et tehisintellekt valis ka kõigi lauaseisundite genereerimisel vastase käigud ja kui vastane on tark, ei lase see tehisintellektil jõuda kõrgeima laua skoorini. Selle asemel teeks nutikas vastane sammu, et AI läheks madalaimale lauale. Algoritmis nimetame kahte mängijat maksimeerivaks mängijaks ja minimeerivaks mängijaks. Tehisintellekt oleks maksimeeriv mängija, kuna ta soovib enda jaoks kõige rohkem punkte saada. Vastane oleks minimeeriv mängija, kuna vastane üritab teha sammu seal, kus tehisintellekt saab kõige vähem punkte.

Kui kõik tahvli olekud on loodud ja tahvlitele väärtused määratud, hakkab algoritm tahvli olekuid võrdlema. Piltidel lõin puu, mis esindab seda, kuidas algoritm oma käike valib. Iga harude jagunemine on erinev käik, mida AI või vastane saab mängida. Sõlmede ridadest vasakule kirjutasin, kas maksimeeriv või minimeeriv mängija läheb. Alumine rida on kõik tahvli olekud koos nende väärtustega. Kõigi nende sõlmede sees on number ja need on hinded, mille määrame igale tahvlile: mida kõrgemad need on, seda parem on AI -l.

Definitsioonid: vanemsõlm - sõlm, mis loob või loob sõlmed selle alla; lastesõlmede päritolu - sõlmed, mis pärinevad samast lähtesõlmest

Tühjad sõlmed tähistavad seda, millist AI -d liigutatakse, et jõuda parimale tahvli olekule. See algab vasakpoolseima sõlme laste võrdlemisest: 10, -3, 5. Kuna maksimeeriv mängija teeks käigu, valiks ta käigu, mis annaks talle kõige rohkem punkte: 10. Seega valime ja salvestame selle liikuge tahvli skooriga ja kirjutage see vanemasõlme. Nüüd, kui 10 on vanemasõlmes, on nüüd minimeerivate mängijate kord. Sõlm, millega 10 võrdleksime, on aga tühi, nii et enne minimeerimismängija valimist peame selle sõlme kõigepealt hindama. Niisiis läheme tagasi maksimeeriva mängija käigu juurde ja võrdleme külgneva sõlme lapsi: 8, -2. Maksimeerimine valib 8 ja me kirjutame selle tühjasse vanemasõlme. Nüüd, kui algoritm on lõpetanud selle kohal oleva sõlme laste tühjade kohtade täitmise, saab minimeeriv mängija neid lapsi võrrelda - 10 ja 8 ning valida 8. Seejärel kordab algoritm seda protsessi, kuni kogu puu on täidetud. Selle näite lõpus on meil skoor 8. See on kõrgeim lauaseisund, mida AI saab mängida eeldusel, et vastane mängib optimaalselt. Seega valib tehisintellekt esimese käigu, mis viib kaheksa laua olekusse ja kui vastane mängib optimaalselt, peaks tehisintellekt mängima kõik käigud, et jõuda tahvli olekusse 8. (Järgige märkusi minu piltidel)

Ma tean, et seda oli palju. Kui olete üks neist tüüpidest, kellel on vaja, et keegi teiega räägiks, et millestki aru saada, siis siin on paar videot, mida ma vaatasin, et aidata mul mõista selle taga olevat ideed: 1, 2, 3.

6. samm: Minimaxi algoritm: pseudokood

Kui olete aru saanud minimaalse algoritmi loogikast, vaadake seda pseudokoodi (kõikidele koodidele universaalsed funktsioonid) Vikipeediast:

funktsiooni minimax (sõlm, sügavus, maksimeeriv mängija) on

kui sügavus = 0 või sõlm on terminalisõlm siis

tagastab sõlme heuristilise väärtuse

kui maksimeeridaPlayer siis

väärtus: = −∞

teha iga sõlme lapse kohta

väärtus: = max (väärtus, minimax (alam, sügavus - 1, VÄÄR))

tagasiväärtus

muu (* mängija minimeerimine *)

väärtus: = +∞

teha iga sõlme lapse kohta

väärtus: = min (väärtus, minimax (alam, sügavus - 1, TRUE))

tagasiväärtus

See on rekursiivne funktsioon, mis tähendab, et see kutsub ennast ikka ja jälle, kuni jõuab peatuspunkti. Esiteks võtab funktsioon kolm väärtust, sõlm, sügavus ja kelle kord see on. Sõlme väärtus on koht, kust soovite, et programm hakkaks otsima. Sügavus on see, kui kaugele soovite programmi otsida. Näiteks minu puunäites on selle sügavus 3, kuna see otsis pärast 3 käiku läbi kõik tahvlite olekud. Loomulikult tahaksime, et tehisintellekt kontrolliks kõiki tahvli olekuid ja valiks võitnud võidu, kuid enamikus mängudes, kus on tuhandeid, kui mitte miljoneid laua konfiguratsioone, ei saa teie kodus olev sülearvuti kõiki neid konfiguratsioone töödelda. Niisiis, piirame AI otsingusügavust ja laseme selle parimal plaadiseisundil.

See pseudokood kordab protsessi, mida selgitasin kahes eelmises etapis. Nüüd teeme selle sammu edasi ja parandame selle python -koodis.

Samm 7: tehke oma AI Ai_template.py abil

Enne minu Minimax AI-koodi vaatamist proovige oma AI-faili ja ai-template.py ning pseudokoodi, millest me viimases etapis rääkisime, oma AI-d luua. Ai -mallil on kaks funktsiooni, mida nimetatakse: def minimax_min_node (tahvel, värv) ja def minimax_max_node (tahvel, värv). Selle asemel, et minimax -funktsioon end rekursiivselt kutsuks, on meil kaks erinevat funktsiooni, mis üksteist kutsuvad. Juhatuse olekute hindamiseks heuristika loomiseks peate looma oma funktsiooni. Failis othello_shared.py on eelvalmis funktsioonid, mida saate kasutada oma AI loomiseks.

Kui olete oma tehisintellekti saanud, proovige seda kasutada, randy_ai.py. Kahe ais üksteise vastu käivitamiseks tippige Mac -terminali "python othello_gui.py (sisestage ai failinimi).py (sisestage failinimi).py" või tippige "run othello_gui.py (sisestage ai failinimi).py) (sisestage failinimi).py "ja veenduge, et olete õiges kataloogis. Vaadake ka minu videost täpseid samme.

8. samm: aeg AI -d võidelda

Nüüd hankige oma arvutisõpradest hunnik ja pange nad kujundama oma tehisintellekti! Siis saate korraldada võistluse ja lasta oma tehisintellekt välja heita. Loodetavasti, isegi kui te ei saaks oma AI -d luua, suutsite mõista, kuidas minimax -algoritm töötab. Kui teil on küsimusi, postitage need küsimused allpool olevatesse kommentaaridesse.