Board Game Artipisyal na Katalinuhan: ang Minimax Algorithm: 8 Mga Hakbang

2024 May -akda: John Day | [email protected]. Huling binago: 2024-01-30 13:12

Naisip mo ba kung paano ginawa ang mga computer na nilalaro mo laban sa chess o mga pamato? Kaya't huwag nang tumingin sa malayo kaysa sa Maituturo na ito sapagkat ipapakita nito sa iyo kung paano gumawa ng isang simple ngunit mabisang artipisyal na katalinuhan (AI) gamit ang Minimax Algorithm! Sa pamamagitan ng paggamit ng Minimax Algorithm, mahusay na pinaplano at naisip ng AI ang mga galaw (o hindi bababa sa ginagaya ang isang proseso ng pag-iisip). Ngayon, maibibigay ko lang sa iyo ang code para sa AI na ginawa ko, ngunit hindi iyon magiging masaya. Ipapaliwanag ko ang lohika sa likod ng mga pagpipilian ng computer.

Sa Instructable na ito, ilalakad kita sa mga hakbang kung paano gumawa ng isang AI para sa Othello (AKA Reversi) sa sawa. Dapat kang magkaroon ng isang intermediate na pag-unawa sa kung paano mag-code sa sawa bago harapin ang proyektong ito. Narito ang ilang magagandang mga website na titingnan upang maihanda ka para sa Maituturo na ito: w3schools o Learnpython. Sa pagtatapos ng Instructable na ito, dapat kang magkaroon ng isang AI na gagawing kinakalkula ang mga galaw at dapat talunin ang karamihan sa mga tao.

Dahil ang Instructable na ito ay pangunahing makikipag-usap sa kung paano gumawa ng isang AI, hindi ko ipaliwanag kung paano mag-disenyo ng isang laro sa sawa. Sa halip, bibigyan ko ang code para sa laro kung saan ang isang tao ay maaaring maglaro laban sa ibang tao at baguhin ito upang maaari kang maglaro ng isang laro kung saan ang isang tao ay naglalaro laban sa AI.

Natutunan ko kung paano likhain ang AI sa pamamagitan ng isang program sa tag-init sa Columbia SHAPE. Nagkaroon ako ng magandang panahon doon kaya tingnan ang kanilang website upang malaman kung magiging interesado ka.

Ngayon na nakuha na namin ang logistics sa daan, magsimula tayong mag-coding!

(Naglagay ako ng ilang mga tala sa mga imahe kaya tiyaking tingnan ang mga ito)

Mga gamit

Madali ito:

1) Computer na may kapaligiran na sawa tulad ng Spyder o IDLE

2) I-download ang mga file para sa Othello game mula sa aking GitHub

3) Na-install ang iyong utak na may pasensya

Hakbang 1: I-download ang Kinakailangan na Mga File

Kapag nagpunta ka sa aking GitHub, dapat mong makita ang 5 mga file. I-download ang lahat ng 5 at ilagay ang lahat sa iisang folder. Bago namin patakbuhin ang laro, buksan ang lahat ng mga file sa kapaligiran ng spyder.

Narito kung ano ang ginagawa ng mga file:

1) othello_gui.py lumilikha ang file na ito ng game board para mapaglaruan ng mga manlalaro (maging tao man o computer)

2) othello_game.py ang file na ito ay nagpe-play ng dalawang computer laban sa bawat isa nang walang gameboard at ipinapakita lamang ang iskor at ilipat ang mga posisyon

3) ai_template.py ito ay kung saan mo ilalagay ang lahat ng iyong code upang gawin ang iyong AI

4) randy_ai.py ito ay isang premade AI na pipiliin ang mga galaw nito nang sapalaran

5) othello_shared.py isang pangkat ng mga paunang pag-andar na maaari mong magamit upang gawin ang iyong AI tulad ng upang suriin ang mga magagamit na paggalaw, ang iskor, o estado ng board

6) Ang tatlong iba pang mga file: Puma.py, erika_5.py, at nathan.py, na ginawa ko, Erika, at Nathan ayon sa pagkakasunod mula sa SHAPE program, ito ang tatlong magkakaibang AI na may natatanging mga code

Hakbang 2: Paano Magbukas at Maglaro ng Python Othello

Kapag nabuksan mo na ang lahat ng mga file, sa kanang sulok sa ibaba ng screen, i-type ang "run othello_gui.py" at pindutin ang enter sa IPython Console. O sa Mac terminal, i-type ang "python othello_gui.py" (pagkatapos mong nasa tamang folder syempre). Pagkatapos ang isang board ay dapat na mag-pop up sa iyong screen. Ang mode na ito ay ang mode ng tao kumpara sa tao. Ang ilaw ay pumapangalawa at madilim muna. Tingnan ang aking video kung nalilito ka. i Sa tuktok, mayroong marka ng bawat kulay na tile. Upang maglaro, mag-click sa isang wastong lugar ng paglipat upang maglagay ng isang tile doon at pagkatapos ay bigyan ang computer sa iyong kalaban na gagawin ang pareho at ulitin.

Kung hindi mo alam kung paano laruin ang Othello, basahin ang mga patakarang ito mula sa website ng ultra boards:

Palagi munang gumagalaw si Itim. Ang isang paglipat ay ginawa sa pamamagitan ng paglalagay ng isang disc ng kulay ng manlalaro sa pisara sa isang posisyon na "out-flanks" isa o higit pa sa mga disc ng kalaban. Ang isang disc o hilera ng mga disc ay outflanked kapag napapaligiran ito sa mga dulo ng mga disc ng kabaligtaran na kulay. Ang isang disc ay maaaring lumampas sa anumang bilang ng mga disc sa isa o higit pang mga hilera sa anumang direksyon (pahalang, patayo, dayagonal)…. (tapusin ang pagbabasa sa kanilang website)

Ang pagkakaiba sa pagitan ng orihinal na laro at ng larong sawa na ito ay kapag walang wastong paggalaw na natitira para sa isang manlalaro natatapos ang laro

Ngayon na maaari mong i-play ang laro sa isang kaibigan, gumawa tayo ng isang AI na maaari mong i-play.

Hakbang 3: Minimax Algorithm: Bumubuo ng Mga Scenario

Bago pag-usapan kung paano isulat ito sa code, tingnan natin ang lohika sa likod nito. Ang minimax algorithm ay isang paggawa ng desisyon, back-tracking algorithm at karaniwang ginagamit sa dalawang laro, turn-based na mga laro. Ang layunin ng AI na ito ay upang mahanap ang susunod na pinakamahusay na paglipat at ang sumusunod na pinakamahusay na mga gumagalaw hanggang sa manalo ito sa laro.

Ngayon paano matutukoy ng algorithm kung aling paglipat ang pinakamahusay na paglipat? Itigil at isipin kung paano mo pipiliin ang susunod na paglipat. Karamihan sa mga tao ay pipiliin ang paglipat na magbibigay sa kanila ng pinakamaraming puntos, tama ba? O kung iniisip nila nang maaga, pipiliin nila ang paglipat na magtatakda ng isang sitwasyon kung saan makakakuha sila ng mas maraming mga puntos. Ang huling paraan ng pag-iisip ay ang paraan kung paano iniisip ang Minimax Algorithm. Inaasahan nito ang lahat ng mga pag-setup ng board sa hinaharap at gumagawa ng paglipat na hahantong sa pinakamaraming puntos.

Tinawag ko ito na isang backtracking algorithm, sapagkat nagsisimula ito sa pamamagitan ng unang paglikha at pagsusuri sa lahat ng mga estado ng lupon sa hinaharap sa kanilang mga nauugnay na halaga. Nangangahulugan ito na ang algorithm ay maglalaro ng laro hangga't kinakailangan nito (paggawa ng mga paggalaw para sa sarili at kalaban) hanggang sa ang bawat sitwasyon ng laro ay nilaro. Upang subaybayan ang lahat ng mga estado ng board (mga sitwasyon), maaari kaming gumuhit ng isang puno (tingnan ang mga larawan). Ang puno sa larawan sa itaas ay isang simpleng halimbawa ng isang laro ng Connect 4. Ang bawat pagsasaayos ng board ay tinatawag na isang estado ng board at ang lugar nito sa puno ay tinatawag na isang node. Ang lahat ng mga node sa ilalim ng puno ay ang pangwakas na estado ng board pagkatapos na gawin ang lahat ng mga galaw. Malinaw na ang ilang mga estado ng lupon ay mas mahusay para sa isang manlalaro kaysa sa iba. Kaya, ngayon kailangan naming gawin ang AI na pumili kung aling lupon ng estado ang nais nitong puntahan.

Hakbang 4: Minimax: Sinusuri ang Mga Configurasyon ng Lupon

Upang mabigyan ng mga halaga ang mga estado ng lupon, kailangan nating malaman ang mga diskarte ng larong aming nilalaro: sa kasong ito, ang mga diskarte ng Othello. Dahil ang larong ito ay isang laban ng pag-flip ng kalaban at ng iyong mga disc, ang pinakamagandang posisyon sa disc ay ang mga matatag at hindi ma-flip. Ang sulok, halimbawa, ay ang lugar kung saan kapag inilagay ang isang disc hindi ito maaaring baguhin sa ibang kulay. Kaya, ang lugar na iyon ay magiging napakahalaga. Ang iba pang magagandang posisyon ay kasama ang mga gilid ng board na magpapahintulot sa iyo na kumuha ng maraming mga bato. Mayroong higit pang mga diskarte sa website na ito.

Ngayon ay maaari kaming magtalaga ng mga halaga sa mga posisyon para sa bawat lupon ng estado ng lupon. Kapag ang isang posisyon ay inookupahan ng piraso ng AI, pagkatapos ay magbibigay ka ng isang tiyak na bilang ng mga puntos depende sa posisyon. Halimbawa ang mga posisyon, itatalaga mo ang lupon ng estado ng isang halaga. Halimbawa, kung ang AI ay may isang piraso sa sulok ang estado ng board ay maaaring magkaroon ng iskor na 50 habang ang isa pang estado ng board na may piraso ng AI sa gitna ay may markang 10.

Maraming mga paraan upang magawa ito, at mayroon akong tatlong magkakaibang heuristics upang suriin ang mga piraso ng board. Hinihimok kita na gumawa ng iyong sariling uri ng heuristic. Nag-upload ako ng tatlong magkakaibang AI sa aking github ng tatlong magkakaibang gumagawa, na may tatlong magkakaibang heuristics: Puma.py, erika5.py, nathanh.py.

Hakbang 5: Minimax Algorithm: Pagpili ng Pinakamahusay na Pagkilos

Ngayon magiging maganda kung pipiliin lamang ng AI ang lahat ng mga paggalaw upang makapunta sa estado ng board na may pinakamataas na iskor. Ngunit tandaan na ang AI ay pumipili din ng mga galaw para sa kalaban noong bumubuo ito ng lahat ng mga estado ng board at kung ang kalaban ay matalino, hindi nito papayagan ang AI na makapunta sa pinakamataas na iskor sa board. Sa halip, ang isang matalinong kalaban ay gagawa upang ang AI ay pumunta sa pinakamababang estado ng board. Sa algorithm, tinawag namin ang dalawang manlalaro na isang maximizing player at isang minimizing player. Ang AI ay magiging maximizing player dahil nais nitong makuha ang pinakamaraming puntos para sa sarili nito. Ang kalaban ay magiging minimizing player dahil sinusubukan ng kalaban na ilipat ang paglipat kung saan nakakakuha ang AI ng kaunting mga puntos.

Kapag nabuo ang lahat ng mga estado ng lupon at ang mga halaga ay naitalaga sa mga board, nagsisimula ang algorithm na ihambing ang mga estado ng board. Sa mga larawan, lumikha ako ng isang puno upang kumatawan sa kung paano pipiliin ng algorithm ang mga galaw nito. Ang bawat split sa mga sanga ay isang iba't ibang mga ilipat ang AI o ang kalaban ay maaaring maglaro. Sa kaliwa ng mga hilera ng mga node, isinulat ko kung pupunta ang pag-maximize o pag-minimize ng manlalaro. Sa ilalim na hilera ay ang lahat ng mga estado ng board na may kanilang mga halaga. Sa loob ng bawat isa sa mga node na iyon ay isang numero at iyon ang mga marka na itinatalaga namin sa bawat board: mas mataas ang mga ito, mas mabuti para sa AI.

Mga kahulugan: parent node - isang node na nagreresulta o lumilikha ng mga node sa ibaba nito; ang pinagmulan ng mga node ng mga bata - ang mga node na nagmula sa parehong node ng magulang

Ang mga walang laman na node ay kumakatawan sa aling ilipat ang gagawin ng AI upang makapunta sa pinakamahusay na estado ng board. Nagsisimula ito sa paghahambing ng mga bata sa kaliwang node: 10, -3, 5. Dahil ang pag-maximize ng manlalaro ay lilipat, pipiliin nito ang paglipat na bibigyan ito ng pinakamaraming puntos: 10. Kaya, pipiliin at iimbak namin iyon ilipat sa marka ng pisara at isulat ito sa node ng magulang. Ngayon na ang 10 ay nasa parent node, ito ay ngayon ang pagliit ng mga manlalaro. Gayunpaman, ang node na ihahambing namin sa 10 ay walang laman, kaya kailangan naming suriin muna ang node na iyon bago pumili ang minimizing player. Kaya bumalik kami sa turn ng maximizing player at ihambing ang mga bata sa katabing node: 8, -2. Pipili ang pag-maximize ng 8 at isusulat namin iyon sa walang laman na node ng magulang. Ngayon na natapos na ng algorithm ang pagpuno sa walang laman na mga puwang para sa mga bata ng isang node sa itaas nito, maaaring ihambing ng pinaliit na manlalaro ang mga batang iyon - 10 at 8 at piliin ang 8. Pagkatapos ay inuulit ng algorithm ang prosesong ito hanggang sa mapunan ang buong puno. Sa pagtatapos ng halimbawang ito, mayroon kaming iskor 8. Iyon ang pinakamataas na estado ng board na maaaring i-play ng AI upang ipagpalagay na ang kalaban ay mahusay na naglalaro. Kaya pipiliin ng AI ang unang paglipat na humahantong sa 8 lupon ng estado, at kung ang kalaban ay mahusay na naglalaro, dapat i-play ng AI ang lahat ng mga paggalaw upang makasakay sa estado ng 8. (Sundin ang mga tala sa aking mga larawan)

Alam kong marami iyon. Kung ikaw ay isa sa mga uri na kailangang magkaroon ng isang tao makipag-usap sa iyo upang maunawaan ang isang bagay, narito ang isang pares ng mga video na pinanood ko upang matulungan akong maunawaan ang ideya sa likod nito: 1, 2, 3.

Hakbang 6: Minimax Algorithm: Pseudocode

Matapos mong maunawaan ang lohika sa likod ng minimax algorithm, tingnan ang pseudocode na ito (ang mga pagpapaandar na pandaigdigan sa lahat ng mga code) mula sa wikipedia:

pagpapaandar ng minimax (node, lalim, maximizingPlayer) ay

kung ang lalim = 0 o node ay isang terminal node pagkatapos

ibalik ang heuristic na halaga ng node

kung ang pag-maximize ngPlayer pagkatapos

halaga: = −∞

para sa bawat anak ng node gawin

halaga: = max (halaga, minimax (bata, lalim - 1, MALI))

halaga ng pagbabalik

iba pa (* minimizing player *)

halaga: = + ∞

para sa bawat anak ng node gawin

halaga: = min (halaga, minimax (bata, lalim - 1, TUNAY))

halaga ng pagbabalik

Ito ay isang recursive function, nangangahulugang tinatawag nito ang sarili nito nang paulit-ulit hanggang sa maabot nito ang isang hintuan. Una, ang pagpapaandar ay tumatagal ng tatlong mga halaga, ang node, lalim, at kaninong turn ito. Ang halaga ng node ay ang lugar kung saan mo nais na magsimulang maghanap ang programa. Ang lalim ay kung hanggang saan mo nais maghanap ng programa. Halimbawa, sa aking halimbawa ng punungkahoy mayroon itong lalim ng 3, sapagkat hinanap nito ang lahat ng mga estado ng board pagkatapos ng 3 paggalaw. Siyempre, nais naming suriin ng AI ang bawat estado ng lupon at pumili ng panalong panalo, ngunit sa karamihan ng mga laro kung saan may libu-libo kung hindi milyun-milyong mga pagsasaayos ng board, hindi mapoproseso ng iyong laptop sa bahay ang lahat ng mga pagsasaayos na iyon. Kaya, nililimitahan namin ang lalim ng paghahanap ng AI at pinupuntahan namin ang pinakamahusay na estado ng board.

Ang pseudocode na ito ay muling ginagawa ang proseso na ipinaliwanag ko sa nakaraang dalawang mga hakbang. Ngayon ay gawin natin ito ng isang hakbang nang higit pa at itama ito sa python code.

Hakbang 7: Paggawa ng Iyong AI Sa Ai_template.py

Bago tingnan ang aking Minimax Ai code, kumuha ng isang crack sa pagsubok na gawin ang iyong sariling AI gamit ang ai_template.py file at ang pseudo-code na pinag-usapan natin sa huling hakbang. Mayroong dalawang mga pag-andar sa ai template na tinatawag na: def minimax_min_node (board, color) at def minimax_max_node (board, color). Sa halip na magkaroon ng minimax function na tawagin itong recursively, mayroon kaming dalawang magkakaibang pag-andar, na kung saan tawagan ang bawat isa. Upang likhain ang heuristic upang suriin ang mga estado ng board, kakailanganin mong lumikha ng iyong sariling pag-andar. Mayroong isang pagpapaandar na premade sa othello_shared.py file na maaari mong gamitin upang mabuo ang iyong AI.

Kapag mayroon ka ng iyong AI, subukang patakbuhin ito, randy_ai.py. Upang magpatakbo ng dalawang ais laban sa bawat isa, i-type ang "python othello_gui.py (ipasok ang pangalan ng file).py (ipasok ang pangalan ng file).py" sa terminal ng mac o i-type ang "patakbuhin othello_gui.py (ipasok ang isang file name).py (ipasok ang pangalan ng file).py "at tiyaking nasa tamang direktoryo ka. Gayundin, tingnan ang aking video para sa eksaktong mga hakbang.

Hakbang 8: Oras upang Gumawa ng AI Fight

Ngayon kumuha ng isang bungkos ng iyong mga kaibigan sa computer at gawin silang disenyo ng kanilang sariling AI! Pagkatapos ay maaari kang gumawa ng isang kumpetisyon at ilabas ang iyong AI. Inaasahan kong, kahit na hindi mo mabuo ang iyong sariling AI, naintindihan mo kung paano gumagana ang minimax algorithm. Kung mayroon kang anumang mga katanungan, huwag mag-atubiling mag-post ng anumang mga katanungan sa mga komento sa ibaba.