Mchezo wa Bodi Akili ya bandia: algorithm ya Minimax: Hatua 8

2024 Mwandishi: John Day | [email protected]. Mwisho uliobadilishwa: 2024-01-30 12:51

Umewahi kujiuliza jinsi kompyuta unazocheza dhidi ya chess au cheki zinafanywa? Usiangalie zaidi ya hii inayoweza kufundishwa kwani itakuonyesha jinsi ya kutengeneza ujasusi rahisi lakini mzuri wa bandia (AI) ukitumia Minimax Algorithm! Kwa kutumia Alima ya Minimax, AI hufanya mipango iliyopangwa vizuri na kufikiria (au angalau kuiga mchakato wa mawazo). Sasa, ningeweza kukupa nambari ya AI ambayo nilitengeneza, lakini hiyo haitakuwa ya kufurahisha. Nitaelezea mantiki nyuma ya uchaguzi wa kompyuta.

Katika Agizo hili, nitakutembea kupitia hatua za jinsi ya kutengeneza AI ya Othello (AKA Reversi) katika chatu. Unapaswa kuwa na uelewa wa kati wa jinsi ya kuweka nambari katika chatu kabla ya kushughulikia mradi huu. Hapa kuna tovuti kadhaa nzuri kuangalia ili kukuandalia hii ya kufundisha: w3schools au learnpython. Mwisho wa Agizo hili, unapaswa kuwa na AI ambayo itafanya hatua zilizohesabiwa na inapaswa kuwashinda wanadamu wengi.

Kwa kuwa Agizo hili litashughulikiwa haswa na jinsi ya kutengeneza AI, sitakuwa nikielezea jinsi ya kubuni mchezo katika chatu. Badala yake, nitakuwa nikitoa nambari ya mchezo ambapo mwanadamu anaweza kucheza dhidi ya mwanadamu mwingine na kuirekebisha ili uweze kucheza mchezo ambapo mwanadamu anacheza dhidi ya AI.

Nilijifunza jinsi ya kuunda AI hii kupitia mpango wa majira ya joto huko Columbia SHAPE. Nilikuwa na wakati mzuri huko kwa hivyo angalia wavuti yao ili uone ikiwa utavutiwa.

Sasa kwa kuwa tumeondoa vifaa, wacha tuanze kuweka alama!

(Ninaweka noti kadhaa kwenye picha ili uhakikishe kuzitazama)

Vifaa

Hii ni rahisi:

1) Kompyuta iliyo na mazingira ya chatu kama Spyder au IDLE

2) Pakua faili za mchezo wa Othello kutoka kwa GitHub yangu

3) Ubongo wako na uvumilivu umewekwa

Hatua ya 1: Pakua faili za lazima

Unapoingia kwenye GitHub yangu, unapaswa kuona faili 5. Pakua zote 5 na uziweke zote kwenye folda moja. Kabla ya kuendesha mchezo, fungua faili zote kwenye mazingira ya kijasusi.

Hapa ndivyo faili zinavyofanya:

1) othello_gui.py faili hii inaunda bodi ya mchezo kwa wachezaji kucheza kwenye (iwe binadamu au kompyuta)

2) othello_game.py faili hii hucheza kompyuta mbili dhidi ya kila mmoja bila ubao wa mchezo na inaonyesha alama tu na nafasi za kusonga

3) ai_template.py hapa ndipo utakapokuwa unaweka nambari yako yote kutengeneza AI yako

4) randy_ai.py hii ni AI ya mapema ambayo huchagua hatua zake bila mpangilio

5) othello_shared.py rundo la kazi zilizopangwa tayari ambazo unaweza kutumia kutengeneza AI yako kama kuangalia hatua zinazopatikana, alama, au hali ya bodi

6) Faili zingine tatu: Puma.py, erika_5.py, na nathan.py, iliyotengenezwa na mimi, Erika, na Nathan mtawaliwa kutoka kwa mpango wa SHAPE, hizi ni AI tatu tofauti zilizo na nambari za kipekee

Hatua ya 2: Jinsi ya kufungua na kucheza Python Othello

Mara baada ya kufungua faili zote, kwenye kona ya chini ya kulia ya skrini, andika "run othello_gui.py" na uingie kuingia kwenye Dashibodi ya IPython. Au kwenye terminal ya Mac, andika "python othello_gui.py" (baada ya kuwa kwenye folda sahihi). Kisha bodi inapaswa kutokea kwenye skrini yako. Hali hii ni hali ya kibinadamu dhidi ya binadamu. Mwanga huenda pili na giza kwanza. Angalia video yangu ikiwa umechanganyikiwa. Juu, kuna alama ya kila tile ya rangi. Ili kucheza, bonyeza nafasi halali ya kusonga ili kuweka tile hapo na kisha mpe kompyuta mpinzani wako ambaye atafanya vivyo hivyo na kurudia.

Ikiwa haujui kucheza Othello, soma sheria hizi kutoka kwa wavuti ya bodi kuu:

Nyeusi daima huenda kwanza. Hoja inafanywa kwa kuweka diski ya rangi ya mchezaji kwenye ubao katika nafasi ambayo "nje" ya diski moja au zaidi ya mpinzani. Diski au safu ya diski hutolewa wakati imezungukwa mwisho na rekodi za rangi tofauti. Diski inaweza kuzunguka idadi yoyote ya rekodi katika safu moja au zaidi kwa mwelekeo wowote (usawa, wima, ulalo)…. (maliza kusoma kwenye wavuti yao)

Tofauti kati ya mchezo wa asili na mchezo huu wa chatu ni kwamba wakati hakuna hatua halali kushoto kwa mchezaji mmoja mchezo unaisha

Sasa kwa kuwa unaweza kucheza mchezo na rafiki, wacha tufanye AI ambayo unaweza kucheza nayo.

Hatua ya 3: algorithm ya Minimax: Inazalisha Matukio

Kabla ya kuzungumza juu ya jinsi ya kuandika hii kwa nambari, wacha tuangalie mantiki nyuma yake. Algorithm minimax ni kufanya maamuzi, nyuma-kufuatilia algorithm na ni kawaida kutumika katika mbili-wachezaji, kugeuka-msingi michezo. Lengo la AI hii ni kupata hoja bora inayofuata na hatua zifuatazo bora hadi itakaposhinda mchezo.

Sasa ni vipi algorithm itaamua ni hoja gani ni hoja bora? Simama na fikiria jinsi ungependa kuchagua hoja inayofuata. Watu wengi wangechagua hoja ambayo itawapa alama nyingi, sivyo? Au ikiwa walikuwa wanafikiria mbele, wangechagua hoja ambayo ingeweka hali ambapo wangeweza kupata alama zaidi. Njia ya mwisho ya kufikiria ni njia jinsi Minimax Algorithm inavyofikiria. Inatazama mbele kwa mipangilio yote ya bodi ya baadaye na hufanya hoja ambayo itasababisha alama nyingi.

Niliita hii algorithm ya kurudi nyuma, kwa sababu inaanza kwa kuunda na kutathmini kwanza majimbo yote ya bodi ya baadaye na maadili yao yanayohusiana. Hii inamaanisha kuwa algorithm itacheza mchezo kama inavyotakiwa (kujipigia hatua na mpinzani) hadi kila hali ya mchezo imecheza. Kuweka wimbo wa majimbo yote ya bodi (matukio), tunaweza kuchora mti (angalia kwenye picha). Mti kwenye picha hapo juu ni mfano rahisi wa mchezo wa Unganisha 4. Kila usanidi wa bodi inaitwa hali ya bodi na mahali pake kwenye mti huitwa nodi. Node zote chini ya mti ni bodi za mwisho baada ya kufanya harakati zote. Ni wazi kwamba majimbo mengine ya bodi ni bora kwa mchezaji mmoja kuliko mwingine. Kwa hivyo, sasa lazima tuifanye AI ichague hali ya bodi ambayo inataka kufika.

Hatua ya 4: Minimax: Kuchunguza Mipangilio ya Bodi

Ili kutoa maadili kwa majimbo ya bodi, lazima tujifunze mikakati ya mchezo ambao tunacheza: katika kesi hii, mikakati ya Othello. Kwa sababu mchezo huu ni vita ya kupindua mpinzani wako na rekodi zako, nafasi nzuri za diski ndio zilizo sawa na haziwezi kupinduliwa. Kona, kwa mfano, ni mahali ambapo diski ikiwekwa haiwezi kubadilishwa kuwa rangi nyingine. Kwa hivyo, doa hilo lingekuwa la thamani sana. Nafasi zingine nzuri ni pamoja na pande za bodi ambayo itakuruhusu kuchukua mawe mengi. Kuna mikakati zaidi kwenye wavuti hii.

Sasa tunaweza kugawa maadili kwa nafasi kwa kila bodi ya serikali ya bodi. Wakati nafasi inamilikiwa na kipande cha AI, basi unapeana idadi kadhaa ya alama kulingana na nafasi. Kwa mfano, hali ya bodi ambayo kipande cha AI kiko kona, unaweza kutoa bonasi ya alama 50, lakini ikiwa ilikuwa mahali pabaya, kipande hicho kinaweza kuwa na thamani ya 0. Baada ya kuzingatia maadili yote ya nafasi, unapeana bodi hali ya thamani. Kwa mfano, ikiwa AI ina kipande kwenye kona hali ya bodi inaweza kuwa na alama 50 wakati bodi nyingine iliyo na kipande cha AI katikati ina alama 10.

Kuna njia nyingi za kufanya hivyo, na nina hesabu tatu tofauti za kutathmini vipande vya bodi. Ninakuhimiza utengeneze aina yako ya utaalam. Nilipakia AI tatu tofauti kwenye github yangu na watunga tatu tofauti, na heuristics tatu tofauti: Puma.py, erika5.py, nathanh.py.

Hatua ya 5: Algorithm ya Minimax: Kuchagua Hoja Bora

Sasa itakuwa nzuri ikiwa AI ingeweza kuchagua tu harakati zote za kufikia hali ya bodi na alama ya juu zaidi. Lakini kumbuka kwamba AI pia ilikuwa ikichagua hatua za mpinzani wakati ilikuwa ikizalisha majimbo yote ya bodi na ikiwa mpinzani ni mwerevu, haitamruhusu AI kufikia alama ya juu kabisa ya bodi. Badala yake, mpinzani mzuri angefanya hoja kuifanya AI iende kwenye hali ya chini kabisa. Katika algorithm, tunawaita wachezaji wawili mchezaji anayeongeza na mchezaji anayepunguza. AI itakuwa mchezaji anayeongeza kwani inataka kupata alama nyingi yenyewe. Mpinzani atakuwa mchezaji anayepunguza kwani mpinzani anajaribu kufanya hoja ambapo AI inapata alama chache zaidi.

Mara tu majimbo yote ya bodi yanapozalishwa na maadili yamepewa bodi, hesabu huanza kulinganisha majimbo ya bodi. Katika picha hizo, niliunda mti kuwakilisha jinsi algorithm ingechagua hatua zake. Kila mgawanyiko katika matawi ni hoja tofauti AI au mpinzani anaweza kucheza. Kushoto kwa safu za nodi, niliandika ikiwa mchezaji anayeongeza au kupunguza anaenda. Mstari wa chini ni majimbo yote ya bodi na maadili yao. Ndani ya kila nodi hizo kuna idadi na hizo ndio alama tunazoweka kwa kila bodi: kadiri zilivyo juu, ni bora kwa AI kuwa nayo.

Ufafanuzi: node ya mzazi - node inayosababisha au kuunda nodi chini yake; asili ya nodi za watoto - nodi ambazo hutoka kwa node ya mzazi huyo huyo

Node tupu zinawakilisha ambayo itahamia AI kufanya ili kufikia hali bora ya bodi. Huanza kwa kulinganisha watoto wa nodi ya kushoto kabisa: 10, -3, 5. Kwa kuwa mchezaji anayeongeza anaweza kufanya hoja hiyo, ingechagua hoja ambayo ingeipa alama zaidi: 10. Kwa hivyo, tunachagua na kuhifadhi hiyo songa na alama ya bodi na uiandike katika nodi ya mzazi. Sasa kwa kuwa 10 iko kwenye node ya mzazi, sasa wachezaji wanaopunguza wanageuka. Walakini, node ambayo tunalinganisha 10 haina kitu, kwa hivyo tunapaswa kutathmini nodi hiyo kwanza kabla ya mchezaji anayepunguza kuchagua. Kwa hivyo tunarudi kwa zamu ya mchezaji anayeongeza na kulinganisha watoto wa node iliyo karibu: 8, -2. Kuongeza kutaamua 8 na tunaandika hiyo katika node ya mzazi tupu. Sasa kwa kuwa algorithm imekamilisha kujaza nafasi tupu kwa watoto wa nodi iliyo juu yake, mchezaji anayepunguza anaweza kulinganisha watoto hao - 10 na 8 na kuchagua 8. algorithm kisha inarudia mchakato huu hadi mti mzima ujazwe. Mwishoni mwa mfano huu, tuna alama ya 8. Hiyo ndiyo hali ya juu zaidi ambayo AI inaweza kucheza kudhani mpinzani anacheza vizuri. Kwa hivyo AI itachagua mwendo wa kwanza ambao unaongoza kwa hali ya bodi 8, na ikiwa mpinzani anacheza vyema, AI inapaswa kucheza kila hatua ili ufike kwenye hali ya bodi 8. (Fuata maelezo kwenye picha zangu)

Najua hiyo ilikuwa mengi. Ikiwa wewe ni moja wapo ya aina ambazo zinahitaji mtu azungumze nawe kuelewa kitu, hizi ni video kadhaa ambazo nilitazama kunisaidia kuelewa wazo nyuma ya hii: 1, 2, 3.

Hatua ya 6: Algorithm ya Minimax: Pseudocode

Baada ya kuelewa mantiki nyuma ya algorithm ya minimax, angalia pseudocode hii (kazi ambazo ni za kawaida kwa nambari zote) kutoka kwa wikipedia:

kazi minimax (nodi, kina, kuongeza Kicheza) ni

ikiwa kina = 0 au nodi ni nodi ya terminal basi

kurudi thamani ya urithi wa nodi

ikiwa inaongeza Kicheza basi

thamani: = −∞

kwa kila mtoto wa nodi fanya

thamani: = max (thamani, minimax (mtoto, kina - 1, FALSE))

thamani ya kurudi

vinginevyo (* kupunguza mchezaji *)

thamani: = + ∞

kwa kila mtoto wa nodi fanya

thamani: = min (thamani, minimax (mtoto, kina - 1, KWELI))

thamani ya kurudi

Hii ni kazi ya kujirudia, ikimaanisha kuwa inajiita tena na tena hadi ifike mahali pa kusimama. Kwanza, kazi inachukua maadili matatu, nodi, kina, na zamu ya nani. Thamani ya nodi ni mahali ambapo unataka programu ianze kutafuta. Ya kina ni umbali gani unataka mpango utafute. Kwa mfano, katika mfano wangu wa mti ina kina cha 3, kwa sababu ilitafuta bodi zote baada ya hatua tatu. Kwa kweli, tungependa AI iangalie kila hali ya bodi na kuchagua ushindi, lakini katika michezo mingi ambayo kuna maelfu ikiwa sio mamilioni ya usanidi wa bodi, kompyuta yako ndogo nyumbani haitaweza kusindika usanidi huo wote. Kwa hivyo, tunazuia utaftaji wa utaftaji wa AI na tuende kwa hali bora ya bodi.

Pseudocode hii inazalisha tena mchakato ambao nilielezea katika hatua mbili zilizopita. Sasa wacha tuchukue hatua hii zaidi na sawa katika nambari ya chatu.

Hatua ya 7: Kutengeneza AI yako na Ai_template.py

Kabla ya kuangalia nambari yangu ya Minimax AI, chukua ufaulu kujaribu kutengeneza AI yako mwenyewe na faili ya ai_template.py na nambari ya uwongo tuliyozungumzia katika hatua ya mwisho. Kuna kazi mbili kwenye kiolezo cha ai kinachoitwa: def minimax_min_node (bodi, rangi) na def minimax_max_node (bodi, rangi). Badala ya kuwa na kazi ya minimax inajiita tena kwa kurudia, tuna kazi mbili tofauti, ambazo huitana. Kuunda utaalam wa kutathmini majimbo ya bodi, italazimika kuunda kazi yako mwenyewe. Kuna kazi za mapema katika faili ya othello_shared.py ambayo unaweza kutumia kujenga AI yako.

Mara tu unapokuwa na AI yako, jaribu kuiendesha dhidi, randy_ai.py. Ili kuendesha ais mbili dhidi ya kila mmoja, andika "python othello_gui.py (ingiza jina la faili).py (ingiza jina la faili).py" kwenye terminal ya mac au andika "run othello_gui.py (ingiza jina la faili).py (weka jina la faili).py "na uhakikishe kuwa uko kwenye saraka sahihi. Pia, angalia video yangu kwa hatua halisi.

Hatua ya 8: Wakati wa Kufanya Kupambana na AI

Sasa pata kikundi cha marafiki wako wa kompyuta na uwafanye watengeneze AI yao wenyewe! Basi unaweza kufanya mashindano na kuwa na duke yako AI nje. Tunatumahi, hata ikiwa huwezi kujenga AI yako mwenyewe, uliweza kuelewa jinsi algorithm ya minimax inavyofanya kazi. Ikiwa una maswali yoyote, jisikie huru kutuma maswali yoyote kwenye maoni hapa chini.