Galda spēle Mākslīgais intelekts: minimumax algoritms: 8 soļi

2024 Autors: John Day | [email protected]. Pēdējoreiz modificēts: 2024-01-30 10:54

Vai esat kādreiz domājuši, kā tiek izgatavoti datori, pret kuriem spēlējat šahā vai dambretē? Neskatieties tālāk par šo pamācību, jo tā parādīs, kā izveidot vienkāršu, bet efektīvu mākslīgo intelektu (AI), izmantojot Minimax algoritmu! Izmantojot Minimax algoritmu, AI veic labi plānotas un pārdomātas kustības (vai vismaz atdarina domāšanas procesu). Tagad es varētu vienkārši sniegt jums izveidotā AI kodu, bet tas nebūtu jautri. Es izskaidrošu datora izvēles loģiku.

Šajā pamācībā es jums sniegšu norādījumus par to, kā python izveidot AI Otello (AKA Reversi). Pirms šī projekta risināšanas jums vajadzētu būt vidējai izpratnei par kodēšanu python. Šeit ir dažas labas vietnes, kuras apskatīt, lai sagatavotos šai instrukcijai: w3schools vai learnpython. Šīs pamācības beigās jums vajadzētu būt AI, kas veiks aprēķinātus gājienus un spēs uzvarēt lielāko daļu cilvēku.

Tā kā šī pamācība galvenokārt būs saistīta ar AI izveidi, es nepaskaidrošu, kā izstrādāt spēli python. Tā vietā es došu spēles kodu, kurā cilvēks var spēlēt pret citu cilvēku, un modificēt to tā, lai jūs varētu spēlēt spēli, kurā cilvēks spēlē pret AI.

Es uzzināju, kā izveidot šo AI, izmantojot vasaras programmu Columbia SHAPE. Es tur labi pavadīju laiku, tāpēc apskatiet viņu vietni, lai redzētu, vai jūs tas interesē.

Tagad, kad loģistika tika novērsta, sāksim kodēt!

(Attēlos ievietoju pāris piezīmes, tāpēc noteikti apskatiet tās)

Piegādes

Tas ir vienkārši:

1) Dators ar pitona vidi, piemēram, Spyder vai IDLE

2) Lejupielādējiet spēles Othello failus no mana GitHub

3) Jūsu smadzenes ar pacietību

1. darbība: lejupielādējiet nepieciešamos failus

Ieejot manā GitHub, jums vajadzētu redzēt 5 failus. Lejupielādējiet visus 5 un ievietojiet tos vienā mapē. Pirms spēles palaišanas atveriet visus failus spiegotāja vidē.

Lūk, ko dara faili:

1) othello_gui.py šis fails izveido spēles galdu, kurā spēlētāji var spēlēt (neatkarīgi no tā, vai tas ir cilvēks vai dators)

2) othello_game.py šis fails spēlē divus datorus viens pret otru bez spēļu dēļa un parāda tikai rezultātu un kustību pozīcijas

3) ai_template.py šeit jūs ievietojat visu savu kodu, lai izveidotu savu AI

4) randy_ai.py tas ir iepriekš izgatavots AI, kas nejauši izvēlas savus gājienus

5) othello_shared.py virkne iepriekš izveidotu funkciju, kuras varat izmantot, lai izveidotu savu AI, piemēram, lai pārbaudītu pieejamās kustības, rezultātu vai tāfeles stāvokli

6) Trīs citi faili: Puma.py, erika_5.py un nathan.py, ko es, Ērika un Natans izveidojām attiecīgi no SHAPE programmas, tie ir trīs dažādi MI ar unikāliem kodiem

2. darbība. Kā atvērt un spēlēt Python Othello

Kad esat atvēris visus failus, ekrāna apakšējā labajā stūrī ierakstiet “run othello_gui.py” un nospiediet ievadīšanas taustiņu IPython konsolē. Vai Mac terminālī ierakstiet "python othello_gui.py" (protams, pēc tam, kad esat nokļuvis pareizajā mapē). Pēc tam ekrānā vajadzētu parādīties tāfele. Šis režīms ir cilvēks pret cilvēku. Gaisma iet otrā un tumšā vispirms. Paskaties manu video, ja esi apjukusi. iAugšpusē ir katras krāsas flīzes rezultāts. Lai spēlētu, noklikšķiniet uz derīgas pārvietošanās vietas, lai tur ievietotu flīzi, un pēc tam nododiet datoru pretiniekam, kurš darīs to pašu un atkārtos.

Ja jūs nezināt, kā spēlēt Otello, izlasiet šos noteikumus ultra dēļu vietnē:

Melns vienmēr kustas pirmais. Gājiens tiek veikts, novietojot spēlētāja krāsas disku uz tāfeles tādā stāvoklī, kas "pārspēj" vienu vai vairākus pretinieka diskus. Disks vai disku rinda ir apmales, kad to galos ieskauj pretējas krāsas diski. Disks vienā vai vairākās rindās var pārsniegt jebkuru disku skaitu jebkurā virzienā (horizontāli, vertikāli, pa diagonāli)…. (pabeidziet lasīt viņu vietnē)

Atšķirība starp sākotnējo spēli un šo pitona spēli ir tāda, ka tad, kad vienam spēlētājam nav atlikuši derīgi gājieni, spēle beidzas

Tagad, kad varat spēlēt spēli kopā ar draugu, izveidosim AI, ar kuru varēsit spēlēt.

3. solis: Minimax algoritms: scenāriju ģenerēšana

Pirms runāt par to, kā to ierakstīt kodā, apskatīsim loģiku, kas ir aiz tā. Minimuma algoritms ir lēmumu pieņemšanas, atpakaļejošs algoritms, un to parasti izmanto divu spēlētāju, uz gājieniem balstītās spēlēs. Šī AI mērķis ir atrast nākamo labāko gājienu un sekojošos labākos gājienus, līdz tas uzvar spēlē.

Tagad kā algoritms noteiktu, kurš gājiens ir labākais? Apstājieties un padomājiet, kā jūs izvēlētos nākamo soli. Lielākā daļa cilvēku izvēlētos gājienu, kas viņiem dotu visvairāk punktu, vai ne? Vai arī, ja viņi domātu uz priekšu, viņi izvēlētos gājienu, kas radītu situāciju, kurā viņi varētu iegūt vēl vairāk punktu. Pēdējais domāšanas veids ir veids, kā domā Minimax algoritms. Tas raugās uz visiem turpmākajiem dēļu iestatījumiem un veic gājienu, kas novestu pie visvairāk punktu.

Es to nosaucu par atpakaļejošu algoritmu, jo tas sākas, vispirms izveidojot un novērtējot visus nākamos padomes stāvokļus ar to saistītajām vērtībām. Tas nozīmē, ka algoritms spēlēs spēli tik daudz, cik nepieciešams (veicot gājienus sev un pretiniekam), līdz tiks izspēlēts katrs spēles scenārijs. Lai izsekotu visiem tāfeles stāvokļiem (scenārijiem), mēs varam uzzīmēt koku (skatieties attēlos). Augstāk redzamajā attēlā redzamais koks ir vienkāršs Connect 4. spēles piemērs. Katru dēļa konfigurāciju sauc par dēļa stāvokli, un tā vietu uz koka sauc par mezglu. Visi mezgli koka apakšā ir pēdējie dēļa stāvokļi pēc visu kustību veikšanas. Acīmredzot daži valdes stāvokļi ir labāki vienam spēlētājam nekā otrs. Tātad, tagad mums ir jāliek AI izvēlēties, kurā valdes stāvoklī tas vēlas nokļūt.

4. solis. Minimālais lielums: paneļa konfigurāciju novērtēšana

Lai valdes noteikumiem piešķirtu vērtības, mums jāapgūst spēles stratēģijas, kuras mēs spēlējam: šajā gadījumā Otello stratēģijas. Tā kā šī spēle ir pretinieka un jūsu disku apgriešanas cīņa, labākās disku pozīcijas ir tās, kuras ir stabilas un kuras nevar apgāzt. Piemēram, stūris ir vieta, kur, ievietojot disku, to nevar mainīt uz citu krāsu. Tādējādi šī vieta būtu ārkārtīgi vērtīga. Citas labas pozīcijas ietver dēļa malas, kas ļautu jums ņemt daudz akmeņu. Šajā vietnē ir vairāk stratēģiju.

Tagad mēs varam piešķirt vērtības katras valdes valsts valdes pozīcijām. Kad pozīciju ieņem AI gabals, jūs piešķirat noteiktu punktu skaitu atkarībā no pozīcijas. Piemēram, tablo, kurā AI gabals atrodas stūrī, jūs varat piešķirt 50 punktu prēmiju, bet, ja tas atrastos nelabvēlīgā vietā, gabala vērtība var būt 0. Pēc visu vērtību ņemšanas vērā pozīcijām, jūs piešķirat valdes valstij vērtību. Piemēram, ja mākslīgā intelekta stūrī ir kāds gabals, tāfeles stāvoklim var būt 50 punktu skaits, bet citam dēļa stāvoklim ar AI gabalu pa vidu - 10.

Ir daudz veidu, kā to izdarīt, un man ir trīs dažādas heiristikas, lai novērtētu tāfeles gabalus. Es iesaku jums izveidot savu heiristikas veidu. Es augšupielādēju savā vietnē github trīs dažādus AI ar trim dažādiem veidotājiem ar trim dažādām heiristikām: Puma.py, erika5.py, nathanh.py.

5. solis: minimumax algoritms: labākā gājiena izvēle

Tagad būtu jauki, ja AI varētu vienkārši izvēlēties visus gājienus, lai iegūtu visaugstāko punktu skaitu. Bet atcerieties, ka AI arī izvēlējās pretinieka gājienus, kad tas ģenerēja visus dēļa stāvokļus, un, ja pretinieks ir gudrs, tas neļaus AI sasniegt visaugstāko dēļa rezultātu. Tā vietā gudrs pretinieks izdarītu soli, lai AI nonāktu zemākajā valdes stāvoklī. Algoritmā mēs abus spēlētājus saucam par maksimizējošu spēlētāju un minimizējošu spēlētāju. AI būtu maksimālais spēlētājs, jo tas vēlas iegūt visvairāk punktu sev. Pretinieks būtu minimizējošais spēlētājs, jo pretinieks mēģina veikt gājienu, kur AI iegūst vismazāk punktu.

Kad ir izveidoti visi tāfeles stāvokļi un plāksnēm ir piešķirtas vērtības, algoritms sāk salīdzināt tāfeles stāvokļus. Attēlos es izveidoju koku, lai attēlotu, kā algoritms izvēlēsies savas kustības. Katrs zaru sadalījums ir atšķirīgs AI vai pretinieka gājiens. Pa kreisi no mezglu rindām es uzrakstīju, vai notiek maksimizēšanas vai samazināšanas spēlētājs. Apakšējā rindā ir visi tāfeles stāvokļi ar to vērtībām. Katrā no šiem mezgliem ir skaitlis, un tos punktus mēs piešķiram katram no dēļiem: jo augstāki tie ir, jo labāk AI ir.

Definīcijas: vecāku mezgls - mezgls, kas rada vai rada mezglus zem tā; bērnu mezglu izcelsme - mezgli, kas nāk no viena vecāka mezgla

Tukšie mezgli attēlo, kuru AI pārvieto, lai sasniegtu vislabāko dēļa stāvokli. Tas sākas ar kreisākā mezgla bērnu salīdzināšanu: 10, -3, 5. Tā kā maksimizējošais spēlētājs izdarītu gājienu, tas izvēlētos gājienu, kas tam dotu visvairāk punktu: 10. Tātad, mēs pēc tam izvēlamies un saglabājam to pārvietojieties ar tāfeles rezultātu un ierakstiet to vecāku mezglā. Tagad, kad 10 atrodas vecāku mezglā, tagad ir jāsamazina spēlētāji. Tomēr mezgls, ar kuru mēs salīdzinātu 10, ir tukšs, tāpēc vispirms ir jāizvērtē šis mezgls, pirms minimizējošais spēlētājs var izvēlēties. Tātad mēs atgriežamies pie maksimizējošā spēlētāja kārtas un salīdzinām blakus esošā mezgla bērnus: 8, -2. Maksimizēšana izvēlēsies 8, un mēs to ierakstīsim tukšajā vecāku mezglā. Tagad, kad algoritms ir beidzis aizpildīt tukšās vietas mezgla bērniem virs tā, minimizēšanas spēlētājs var salīdzināt šos bērnus - 10 un 8 un izvēlēties 8. Pēc tam algoritms atkārto šo procesu, līdz viss koks ir aizpildīts. Šī piemēra beigās mums ir rezultāts 8. Tas ir augstākais spēles stāvoklis, ko AI var spēlēt, pieņemot, ka pretinieks spēlē optimāli. Tātad AI izvēlēsies pirmo gājienu, kas noved pie 8 dēļa stāvokļa, un, ja pretinieks spēlē optimāli, AI vajadzētu spēlēt visus gājienus, lai nokļūtu 8. stāvokļa dēļ. (Sekojiet piezīmēm pie maniem attēliem)

Es zinu, ka tas bija daudz. Ja jūs esat viens no tiem, kam ir nepieciešams, lai kāds ar jums sarunājas, lai kaut ko saprastu, šeit ir daži videoklipi, kurus es noskatījos, lai palīdzētu man saprast ideju: 1, 2, 3.

6. solis: minimumax algoritms: pseidokods

Kad esat sapratis minimuma algoritma loģiku, aplūkojiet šo pseidokodu (funkcijas, kas ir universālas visiem kodiem) no wikipedia:

funkcija minimax (mezgls, dziļums, maximizingPlayer) ir

ja dziļums = 0 vai mezgls ir gala mezgls

atgriezt mezgla heiristisko vērtību

ja maksimizējot spēlētāju, tad

vērtība: = −∞

katram mezgla bērnam

vērtība: = max (vērtība, minimumx (bērns, dziļums - 1, FALSE))

atgriešanās vērtība

cits (* spēlētāja minimizēšana *)

vērtība: = +∞

katram mezgla bērnam

vērtība: = min (vērtība, minimumx (bērns, dziļums - 1, TRUE))

atgriešanās vērtība

Šī ir rekursīva funkcija, kas nozīmē, ka tā sevi sauc atkal un atkal, līdz tā sasniedz apstāšanās punktu. Pirmkārt, funkcijai ir trīs vērtības: mezgls, dziļums un tā kārta. Mezgla vērtība ir vieta, kur vēlaties, lai programma sāktu meklēšanu. Dziļums ir tas, cik tālu vēlaties meklēt programmu. Piemēram, manā koka piemērā tā dziļums ir 3, jo pēc 3 gājieniem tas pārmeklēja visus dēļa stāvokļus. Protams, mēs vēlētos, lai AI pārbaudītu katru dēļa stāvokli un izvēlētos uzvarošo uzvaru, taču lielākajā daļā spēļu, kurās ir tūkstošiem, ja ne miljoniem dēļu konfigurāciju, jūsu klēpjdators mājās nevarēs apstrādāt visas šīs konfigurācijas. Tātad, mēs ierobežojam AI meklēšanas dziļumu un novedam pie labākā dēļa stāvokļa.

Šis pseidokods atveido procesu, ko es izskaidroju iepriekšējās divās darbībās. Tagad spersim šo soli tālāk un izlabosim to python kodā.

7. darbība. AI veidošana, izmantojot Ai_template.py

Pirms ieskatāties manā Minimax AI kodā, mēģiniet izveidot savu AI ar ai_template.py failu un pseidokodu, par kuru mēs runājām pēdējā solī. Ai veidnē ir divas funkcijas: def minimax_min_node (tāfele, krāsa) un def minimax_max_node (tāfele, krāsa). Tā vietā, lai minimuma funkcija sevi izsauktu rekursīvi, mums ir divas dažādas funkcijas, kas viena otru sauc. Lai izveidotu heiristiku valdes stāvokļu novērtēšanai, jums būs jāizveido sava funkcija. Failā othello_shared.py ir iepriekš izgatavotas funkcijas, kuras varat izmantot, lai izveidotu savu AI.

Kad esat ieguvis savu AI, mēģiniet to izmantot, randy_ai.py. Lai palaistu divas ais viena pret otru, ierakstiet "python othello_gui.py (ievietojiet ai faila nosaukumu).py (ievietojiet faila nosaukumu).py" Mac terminālī vai ierakstiet "run othello_gui.py (ievietojiet ai faila nosaukumu).py (ievietojiet faila nosaukumu).py "un pārliecinieties, vai atrodaties pareizajā direktorijā. Skatiet arī manu videoklipu, lai uzzinātu precīzas darbības.

8. solis: laiks likt AI cīnīties

Tagad iegūstiet daudz draugu ar datoru un lieciet viņiem izveidot savu AI! Tad jūs varat sarīkot konkursu un aicināt savu AI hercogu. Cerams, pat ja jūs nevarētu izveidot savu AI, jūs varējāt saprast, kā darbojas minimuma algoritms. Ja jums ir kādi jautājumi, lūdzu, ievietojiet tos komentāros.