Սեղանի խաղ Արհեստական բանականություն. Minimax ալգորիթմ `8 քայլ

2024 Հեղինակ: John Day | [email protected]. Վերջին փոփոխված: 2024-01-30 09:47

Երբևէ մտածե՞լ եք, թե ինչպես են պատրաստված այն համակարգիչները, որոնց դեմ խաղում եք շախմատում կամ շաշկիում: Դե, մի նայեք այս Instructable- ից, որովհետև այն ցույց կտա ձեզ, թե ինչպես կարելի է պատրաստել պարզ, բայց արդյունավետ արհեստական բանականություն (AI) `օգտագործելով Minimax ալգորիթմը: Օգտագործելով Minimax ալգորիթմը ՝ AI- ն լավ ծրագրված և մտածված քայլեր է կատարում (կամ գոնե նմանակում է մտքի գործընթացին): Այժմ ես պարզապես կարող եմ ձեզ տալ իմ պատրաստած AI- ի ծածկագիրը, բայց դա հաճելի չէր լինի: Ես կբացատրեմ համակարգչի ընտրության հիմքում ընկած տրամաբանությունը:

Այս Ուղեցույցում ես ձեզ կներկայացնեմ այն քայլերով, թե ինչպես կարելի է արհեստական ինտելեկտ պատրաստել Օթելլոյի համար (AKA Reversi) պիթոնում: Նախքան այս նախագծին անդրադառնալը, դուք պետք է միջանկյալ պատկերացում ունենաք, թե ինչպես կոդավորել Python- ում: Ահա մի քանի լավ կայքեր, որոնց պետք է նայեք, որպեսզի պատրաստվեք ձեզ այս Ուղեցույցին. W3schools or learnpython: Այս հրահանգի վերջում դուք պետք է ունենաք արհեստական ինտելեկտ, որը հաշվարկված քայլեր կկատարի և պետք է կարողանա հաղթել մարդկանցից շատերին:

Քանի որ այս Instructable- ը հիմնականում զբաղվելու է, թե ինչպես անել AI, ես չեմ բացատրի, թե ինչպես նախագծել խաղը python- ում: Փոխարենը, ես կտրամադրեմ այն խաղի կոդը, որտեղ մարդը կարող է խաղալ մեկ այլ մարդու դեմ և փոփոխել այն, որպեսզի դուք կարողանաք խաղալ այնպիսի խաղ, որտեղ մարդը խաղում է AI- ի դեմ:

Ես սովորեցի, թե ինչպես ստեղծել այս AI- ն ամառային ծրագրի միջոցով Columbia SHAPE- ում: Ես այնտեղ լավ ժամանակ անցկացրեցի, այնպես որ նայեք նրանց վեբ կայքին ՝ տեսնելու, արդյոք ձեզ կհետաքրքրի:

Այժմ, երբ մենք լոգիստիկայից դուրս եկանք, եկեք սկսենք կոդավորումը:

(Ես մի քանի նշումներ եմ դնում նկարների վրա, այնպես որ համոզվեք, որ դրանք նայեք)

Պարագաներ

Սա հեշտ է.

1) համակարգիչ ՝ պիթոնի միջավայրով, ինչպիսին է Spyder- ը կամ IDLE- ը

2) Ներբեռնեք Othello խաղի ֆայլերը իմ GitHub- ից

3) Ձեր ուղեղը տեղադրեց համբերությամբ

Քայլ 1: Ներբեռնեք անհրաժեշտ ֆայլերը

Երբ մուտք եք գործում իմ GitHub, դուք պետք է տեսնեք 5 ֆայլ: Ներբեռնեք բոլոր 5 -ը և տեղադրեք բոլորը նույն թղթապանակում: Նախքան խաղը գործարկելը, բացեք լրտեսող միջավայրի բոլոր ֆայլերը:

Ահա թե ինչ են անում ֆայլերը.

1) othello_gui.py այս ֆայլը ստեղծում է խաղատախտակ խաղացողների համար խաղալու համար (լինի դա մարդ, թե համակարգիչ)

2) othello_game.py այս ֆայլը խաղում է երկու համակարգիչ միմյանց դեմ առանց խաղատախտակի և ցույց է տալիս միայն հաշիվը և տեղափոխման դիրքերը

3) ai_template.py սա այն վայրն է, որտեղ դուք պետք է տեղադրեք ձեր ամբողջ ծածկագիրը `ձեր AI- ն ստեղծելու համար

4) randy_ai.py սա նախադրյալ արհեստական ինտելեկտ է, որը պատահաբար ընտրում է իր քայլերը

5) othello_shared.py մի փունջ նախապես պատրաստված գործառույթներ, որոնք կարող եք օգտագործել ձեր արհեստական ինտելեկտը դարձնելու համար, օրինակ `ստուգել առկա շարժումները, հաշիվը կամ տախտակի վիճակը

6) Երեք այլ ֆայլեր ՝ Puma.py, erika_5.py և nathan.py, համապատասխանաբար իմ, Էրիկայի և Նաթանի կողմից պատրաստված SHAPE ծրագրից, դրանք երեք տարբեր AI են ՝ եզակի կոդերով:

Քայլ 2. Ինչպես բացել և խաղալ Python Othello

Բոլոր ֆայլերը բացելուց հետո էկրանի ներքևի աջ անկյունում մուտքագրեք «run othello_gui.py» և սեղմեք enter IPython վահանակում: Կամ Mac տերմինալում մուտքագրեք «python othello_gui.py» (իհարկե, ճիշտ պանակում հայտնվելուց հետո): Այնուհետև ձեր էկրանին պետք է հայտնվի տախտակ: Այս ռեժիմը մարդու և մարդու ռեժիմն է: Լույսը երկրորդն է դառնում, իսկ մութը `առաջինը: Եթե շփոթված եք, նայեք իմ տեսանյութին: վերևում կա յուրաքանչյուր գույնի սալիկի հաշիվը: Խաղալու համար կտտացրեք վավեր տեղափոխման տարածություն ՝ այնտեղ սալիկ տեղադրելու համար, այնուհետև համակարգիչը տվեք ձեր հակառակորդին, ով նույնը կանի և կրկնի:

Եթե չգիտեք, թե ինչպես խաղալ Օթելլո, կարդացեք այս կանոնները ծայրահեղ տախտակների վեբ կայքից.

Սևը միշտ առաջինն է շարժվում: Քայլը կատարվում է խաղացողի գույնի սկավառակ խաղատախտակի վրա տեղադրելով այն դիրքում, որը «դուրս է մղում» հակառակորդի մեկ կամ մի քանի սկավառակ: Սկավառակը կամ սկավառակների շարանը գերազանցվում են, երբ ծայրերում շրջապատված են հակառակ գույնի սկավառակներով: Սկավառակը կարող է գերազանցել մեկ կամ մի քանի տողերի ցանկացած քանակի սկավառակ ՝ ցանկացած ուղղությամբ (հորիզոնական, ուղղահայաց, անկյունագծային)… (ավարտեք կարդալ իրենց կայքում)

Բուն խաղի և այս պիթոնի խաղի միջև տարբերությունն այն է, որ երբ մեկ խաղացողի համար վավեր քայլեր չեն մնում, խաղն ավարտվում է:

Այժմ, երբ կարող եք խաղը խաղալ ընկերոջ հետ, եկեք ստեղծենք AI, որի հետ կարող եք խաղալ:

Քայլ 3. Minimax ալգորիթմ. Սցենարների ստեղծում

Նախքան խոսել այն մասին, թե ինչպես գրել սա կոդով, եկեք անցնենք դրա հիմքում ընկած տրամաբանությունը: Minimax ալգորիթմը որոշումներ կայացնելու, հետևելու ալգորիթմ է և սովորաբար օգտագործվում է երկու խաղացողի, հերթափոխի վրա հիմնված խաղերում: Այս արհեստական ինտելեկտի նպատակն է գտնել հաջորդ լավագույն քայլը և հետևյալ լավագույն քայլերը մինչև խաղը շահելը:

Հիմա ինչպե՞ս կարող էր ալգորիթմը որոշել, թե որ շարժումն է լավագույն քայլը: Կանգ առեք և մտածեք, թե ինչպես կընտրեիք հաջորդ քայլը: Մարդկանց մեծ մասը կընտրեր այն քայլը, որը նրանց կտար առավելագույն միավորներ, այնպես չէ՞: Կամ, եթե նրանք մտածեին առաջ, նրանք կընտրեին այն քայլը, որը կստեղծեր իրավիճակ, որտեղ նրանք կարող էին ավելի շատ միավորներ հավաքել: Վերջին մտածելակերպը այն եղանակն է, թե ինչպես է մտածում Minimax ալգորիթմը: Այն առաջ է նայում խորհրդի բոլոր ապագա կազմավորումներին և կատարում է այն քայլը, որը կհանգեցներ առավելագույն միավորների:

Ես սա անվանեցի հետադարձ ալգորիթմ, որովհետև այն սկսվում է նախ ստեղծելով և գնահատելով բոլոր ապագա տախտակների վիճակները `իրենց հարակից արժեքներով: Սա նշանակում է, որ ալգորիթմը խաղը կխաղա այնքան, որքան անհրաժեշտ է (շարժումներ կատարելով իր և հակառակորդի համար), մինչև խաղի յուրաքանչյուր սցենար չխաղա: Տախտակի բոլոր վիճակները (սցենարները) հետևելու համար մենք կարող ենք նկարել մի ծառ (նայեք նկարներին): Վերը նկարում պատկերված ծառը Connect 4 խաղի պարզ օրինակ է: Տախտակի յուրաքանչյուր կոնֆիգուրացիա կոչվում է տախտակի վիճակ, իսկ ծառի վրա դրա տեղը `հանգույց: Treeառի ներքևի բոլոր հանգույցները բոլոր շարժումները կատարելուց հետո տախտակի վերջին վիճակն են: Ակնհայտ է, որ որոշ խաղատախտակներ ավելի լավն են մեկ խաղացողի համար, քան մյուսը: Այսպիսով, այժմ մենք պետք է ստիպենք AI- ին ընտրել, թե որ խորհրդի վիճակին է ցանկանում հասնել:

Քայլ 4. Minimax. Խորհրդի կազմաձևերի գնահատում

Խորհրդի պետություններին արժեքներ հաղորդելու համար մենք պետք է սովորենք խաղի ռազմավարությունները, որոնք այս խաղում են. Այս դեպքում `Օթելլոյի ռազմավարությունները: Քանի որ այս խաղը հակառակորդի և ձեր սկավառակները շրջելու պայքար է, սկավառակի լավագույն դիրքերն այն են, որոնք կայուն են և չեն կարող շրջվել: Անկյունը, օրինակ, այն վայրն է, որտեղ սկավառակի տեղադրման ժամանակ այն չի կարող փոխվել մյուս գույնի: Այսպիսով, այդ տեղը չափազանց արժեքավոր կլիներ: Այլ լավ դիրքերը ներառում են տախտակի կողքերը, որոնք թույլ կտան ձեզ շատ քարեր վերցնել: Այս կայքում կան ավելի շատ ռազմավարություններ:

Այժմ մենք կարող ենք արժեքներ հատկացնել յուրաքանչյուր խորհրդի պետական խորհրդի պաշտոններին: Երբ դիրքը զբաղեցնում է AI- ի կտորը, ապա դուք որոշակի քանակությամբ միավորներ եք տալիս `կախված դիրքից: Օրինակ, տախտակի վիճակ, որտեղ AI- ի կտորը անկյունում է, կարող եք տալ 50 միավոր բոնուս, բայց եթե այն անբարենպաստ տեղում լիներ, կտորը կարող է ունենալ 0. արժեք ՝ հաշվի առնելով բոլոր արժեքները դիրքերը, դուք նշանակում եք խորհրդի վիճակը: Օրինակ, եթե AI- ն անկյունում ունի մի կտոր, ապա տախտակի վիճակը կարող է ունենալ 50 միավոր, մինչդեռ մեկ այլ տախտակի վիճակ, որի մեջտեղում գտնվում է AI- ի կտորը, ունի 10 միավոր:

Կան բազմաթիվ եղանակներ դա անելու համար, և ես ունեմ երեք տարբեր հեվրիստիկա ՝ տախտակի կտորները գնահատելու համար: Ես խրախուսում եմ ձեզ կատարել ձեր սեփական տիպի էվրիստիկա: Երեք տարբեր արտադրողների կողմից իմ github- ում երեք տարբեր արհեստական ինտելեկտներ եմ վերբեռնել ՝ երեք տարբեր հեվիստիկայով ՝ Puma.py, erika5.py, nathanh.py:

Քայլ 5. Minimax ալգորիթմ. Ընտրելով լավագույն քայլը

Այժմ լավ կլիներ, եթե AI- ն կարողանար ընտրել բոլոր քայլերը `ամենաբարձր գնահատականով խորհրդի վիճակին հասնելու համար: Բայց հիշեք, որ AI- ն նաև ընտրում էր հակառակորդի քայլերը, երբ ստեղծում էր տախտակի բոլոր վիճակները, և եթե հակառակորդը խելացի է, դա թույլ չի տա AI- ին հասնել տախտակի ամենաբարձր գնահատականին: Փոխարենը, խելացի հակառակորդը կանի այն քայլը, որով AI- ն կգնա տախտակի ամենացածր վիճակին: Ալգորիթմում մենք երկու խաղացողներին անվանում ենք առավելագույնի հասցնող և նվազագույնի հասցնող նվագարկիչ: Արհեստական ինտելեկտը կլինի առավելագույնի հասցնող խաղացողը, քանի որ ցանկանում է իր համար առավելագույն միավորներ ստանալ: Մրցակիցը կլինի նվազագույնի հասցնող խաղացողը, քանի որ հակառակորդը փորձում է կատարել այն քայլը, որտեղ AI- ն ստանում է ամենաքիչ միավորները:

Երբ ստեղծվում են տախտակի բոլոր վիճակները և արժեքները նշանակվում են տախտակներին, ալգորիթմը սկսում է համեմատել տախտակի վիճակները: Նկարներում ես ստեղծեցի մի ծառ, որը ներկայացնում էր, թե ինչպես է ալգորիթմը ընտրելու իր քայլերը: Մասնաճյուղերի յուրաքանչյուր պառակտում տարբեր քայլ է, որը կարող է խաղալ AI- ն կամ հակառակորդը: Հանգույցների տողերից ձախ, ես գրեցի, թե արդյոք առավելագույն կամ նվազեցնող նվագարկիչը գնում է: Ներքեւի տողը տախտակի բոլոր պետություններն են `իրենց արժեքներով: Այդ հանգույցներից յուրաքանչյուրի ներսում կա մի թիվ, և դրանք այն միավորներն են, որոնք մենք տալիս ենք յուրաքանչյուր տախտակին:

Սահմանումներ. Ծնողական հանգույց - հանգույց, որը հանգեցնում է կամ ստեղծում է ստորև գտնվող հանգույցները. երեխաների հանգույցների ծագումը `նույն ծնողական հանգույցից բխող հանգույցները

Դատարկ հանգույցները ներկայացնում են, թե որ շարժումը AI- ն կստիպի հասնել տախտակի լավագույն վիճակին: Այն սկսվում է ձախակողմյան հանգույցի երեխաների համեմատությամբ `10, -3, 5. Քանի որ առավելագույն խաղացողը կանի քայլը, նա կընտրի այն քայլը, որն իրեն կտա առավելագույն միավորներ. 10. Այսպիսով, մենք այնուհետև ընտրում և պահում ենք այն շարժվել գրատախտակի միավորով և գրել այն մայր հանգույցում: Հիմա, երբ 10 -ը ծնողական հանգույցում է, այժմ հերթը նվազագույնի հասցնող խաղացողներինն է: Այնուամենայնիվ, այն հանգույցը, որի հետ մենք կհամեմատեինք 10 -ը, դատարկ է, ուստի մենք պետք է նախ գնահատենք այդ հանգույցը, մինչև նվազագույնի հասցնող նվագարկիչը կարողանա ընտրել: Այսպիսով, մենք վերադառնում ենք առավելագույնի հասցնող խաղացողի հերթին և համեմատում ենք հարակից հանգույցի երեխաներին ՝ 8, -2: Maximizing- ը կընտրի 8 -ը, և մենք դա գրում ենք դատարկ ծնողական հանգույցում: Այժմ, երբ ալգորիթմն ավարտել է իր վերևի հանգույցի երեխաների դատարկ տարածքների լրացումը, նվազեցնող խաղացողը կարող է համեմատել այդ երեխաներին `10 և 8 և ընտրել 8 -ը: Այնուհետև ալգորիթմը կրկնում է այս գործընթացը մինչև ամբողջ ծառը լցված: Այս օրինակի վերջում մենք ունենք 8 հաշիվը: Դա տախտակի ամենաբարձր վիճակն է, որը կարող է խաղալ արհեստական ինտելեկտը `ենթադրելով, որ հակառակորդն օպտիմալ է խաղում: Այսպիսով, AI- ն կընտրի առաջին քայլը, որը տանում է դեպի տախտակի 8 -րդ վիճակ, և եթե հակառակորդը խաղում է օպտիմալ կերպով, AI- ն պետք է կատարի բոլոր քայլերը `8 -րդ տախտակին հասնելու համար (հետևեք իմ նկարների գրառումներին)

Ես գիտեմ, որ դա շատ էր: Եթե դուք այն տեսակներից եք, ովքեր ինչ -որ բան հասկանալու համար պետք է ինչ -որ մեկի հետ խոսեն, ահա մի քանի տեսանյութ, որոնք ես դիտել եմ ՝ օգնելու ինձ հասկանալ դրա հիմքում ընկած գաղափարը ՝ 1, 2, 3:

Քայլ 6. Minimax ալգորիթմ. Կեղծ կոդ

Հասկանալով minimax ալգորիթմի հիմքում ընկած տրամաբանությունը ՝ վիքիպեդիայից նայեք այս կեղծ կոդին (բոլոր կոդերի համար համընդհանուր գործառույթներին).

գործառույթը minimax (հանգույց, խորություն, maximizingPlayer) է

եթե խորությունը = 0 կամ հանգույցը տերմինալ հանգույց է, ապա

վերադարձնել հանգույցի էուրիստական արժեքը

եթե maximizingPlayer ապա

արժեքը `= −∞

հանգույցի յուրաքանչյուր երեխայի համար արեք

արժեքը `= առավելագույնը (արժեքը, նվազագույնը (երեխա, խորությունը` 1, ԿԵAL))

վերադարձի արժեքը

այլ (* նվազագույնի հասցնել նվագարկիչը *)

արժեքը `= +

հանգույցի յուրաքանչյուր երեխայի համար արեք

արժեքը `= րոպե (արժեքը, նվազագույնը (երեխա, խորությունը` 1, UEՇՄԱՐՏԻԿ))

վերադարձի արժեքը

Սա ռեկուրսիվ ֆունկցիա է, այսինքն ՝ այն իրեն անվերջ կանչում է մինչև կանգառի կետին հասնելը: Նախ, գործառույթը վերցնում է երեք արժեք ՝ հանգույցը, խորությունը և ում հերթն է: Հանգույցի արժեքն այն վայրն է, որտեղ ցանկանում եք, որ ծրագիրը սկսի որոնումը: Խորությունն այն է, թե որքան հեռու եք ցանկանում, որ ծրագիրը որոնի: Օրինակ, իմ ծառի օրինակում այն ունի 3 խորություն, քանի որ 3 քայլից հետո որոնել է տախտակի բոլոր վիճակները: Իհարկե, մենք կցանկանայինք, որ AI- ն ստուգեր տախտակի յուրաքանչյուր վիճակ և ընտրեր հաղթող հաղթանակ, բայց խաղերի մեծ մասում, որտեղ կան հազարավոր, եթե ոչ միլիոնավոր տախտակի կազմաձևեր, ձեր տանը նոութբուքը չի կարողանա մշակել այդ բոլոր կազմաձևերը: Այսպիսով, մենք սահմանափակում ենք AI- ի որոնման խորությունը և թող այն անցնի տախտակի լավագույն վիճակին:

Այս կեղծ ծածկագիրը վերարտադրում է այն գործընթացը, որը ես բացատրել եմ նախորդ երկու քայլերում: Հիմա եկեք սա մի քայլ առաջ անենք և սա ուղղենք Python կոդով:

Քայլ 7: Կատարեք ձեր AI Ai_template.py- ով

Նախքան իմ Minimax AI- ի կոդին նայելը, փորձեք ինքնուրույն AI- ն պատրաստել ai_template.py ֆայլով և այն կեղծ կոդով, որի մասին մենք խոսեցինք վերջին քայլում: Ai կաղապարում կան երկու գործառույթ ՝ def minimax_min_node (տախտակ, գույն) և def minimax_max_node (տախտակ, գույն): Մինիմաքս ֆունկցիան ինքնուրույն կանչելու փոխարեն, մենք ունենք երկու տարբեր գործառույթներ, որոնք զանգահարում են միմյանց: Տախտակի վիճակները գնահատելու հերիստիկա ստեղծելու համար դուք պետք է ստեղծեք ձեր սեփական գործառույթը: Othello_shared.py ֆայլում կան նախադրյալ գործառույթներ, որոնք կարող եք օգտագործել ձեր AI- ն կառուցելու համար:

Երբ ունեք ձեր արհեստական ինտելեկտը, փորձեք այն գործարկել ՝ randy_ai.py: Երկու ais միմյանց դեմ աշխատելու համար մուտքագրեք «python othello_gui.py (տեղադրեք ai ֆայլի անունը).py (տեղադրեք ֆայլի անունը).py« mac »տերմինալում կամ մուտքագրեք« run othello_gui.py (տեղադրեք ai ֆայլի անունը).py (տեղադրեք ֆայլի անունը).py և համոզվեք, որ ճիշտ գրացուցակում եք: Բացի այդ, նայեք իմ տեսանյութին ճշգրիտ քայլերի համար:

Քայլ 8: AI- ի դեմ պայքարելու ժամանակն է:

Այժմ ձեռք բերեք ձեր համակարգչի ընկերների մի խումբ և ստիպեք նրանց նախագծել իրենց սեփական AI- ն: Այնուհետև կարող եք մրցույթ անցկացնել և ձեր AI- ն ավարտել այն: Հուսանք, որ նույնիսկ եթե չկարողանաք կառուցել ձեր սեփական AI- ն, կարողացաք հասկանալ, թե ինչպես է աշխատում minimax ալգորիթմը: Եթե ունեք որևէ հարց, ազատ զգալ տեղադրեք ցանկացած հարց ստորև բերված մեկնաբանություններում: