Үстел ойыны Жасанды интеллект: минимакс алгоритмі: 8 қадам

2024 Автор: John Day | [email protected]. Соңғы өзгертілген: 2024-01-30 10:24

Сіз шахмат немесе дойбыға қарсы ойнайтын компьютерлер қалай жасалынғанын ойлап көрдіңіз бе? Нұсқаулықтан басқа ештеңеге қарамаңыз, ол сізге Minimax алгоритмін қолдана отырып қарапайым, бірақ тиімді жасанды интеллект (АИ) жасауды көрсетеді! Minimax алгоритмін қолдана отырып, AI жақсы жоспарланған және ойластырылған қозғалыстар жасайды (немесе кем дегенде ойлау процесін еліктейді). Енді мен сізге жасанды интеллект кодын бере аламын, бірақ бұл қызықты болмайды. Мен компьютер таңдауының логикасын түсіндіремін.

Бұл нұсқаулықта мен сізге питонда Отеллоға (АКА Реверси) интеллектуалды интеграцияны жасау бойынша қадамдарды көрсетемін. Сіз бұл жобаны шешпес бұрын python -да қалай кодтау керектігін білуіңіз керек. Сізді осы нұсқаулыққа дайындауға арналған бірнеше жақсы веб -сайттар: w3schools немесе learnpython. Нұсқаулықтың соңында сізде есептік қозғалыстар жасайтын және адамдардың көпшілігін жеңе алатын АИ болуы керек.

Бұл нұсқаулық бірінші кезекте АИ қалай жасалатынын қарастыратындықтан, мен питонда ойынның қалай жасалатынын түсіндірмеймін. Оның орнына, мен адам басқа адамға қарсы ойнай алатын ойын кодын беремін және оны адам AI -ге қарсы ойнайтын ойынды ойнау үшін өзгертемін.

Мен бұл AI жасауды Columbia SHAPE жазғы бағдарламасы арқылы үйрендім. Мен онда жақсы уақыт өткіздім, сондықтан олардың веб -сайтына қараңыз, сізді қызықтырады ма?

Енді логистиканы жолдан шығардық, енді кодтауды бастайық!

(Мен суреттерге бірнеше ескертулер қойдым, сондықтан оларды міндетті түрде қараңыз)

Жабдықтар

Бұл оңай:

1) Spyder немесе IDLE сияқты питон ортасы бар компьютер

2) Отелло ойынының файлдарын менің 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 бағдарламасынан жасалған, бұл бірегей кодтары бар үш түрлі АИ.

2 -қадам: Python Отеллоны қалай ашуға және ойнауға болады

Барлық файлдар ашылғаннан кейін, экранның оң жақ төменгі бұрышына «run othello_gui.py» деп теріп, IPython консолінде enter пернесін басыңыз. Немесе Mac терминалында «python othello_gui.py» теріңіз (әрине, сіз дұрыс қалтада болғаннан кейін). Содан кейін экранда тақта пайда болуы керек. Бұл режим адам мен адам режимі болып табылады. Жарық екінші, ал қараңғы - бірінші. Егер сіз түсініксіз болсаңыз, менің бейнеролигімді қараңыз. i Жоғарғы жағында әр түсті тақтайшаның бағасы бар. Ойнау үшін жарамды жылжыту орнын басыңыз, онда плитканы орналастырыңыз, содан кейін компьютерді қарсыласыңызға беріңіз, ол солай жасайды және қайталайды.

Егер сіз Отеллоны қалай ойнауды білмесеңіз, мына ережелерді ультра тақталар сайтынан оқыңыз:

Қара әрқашан бірінші болып қозғалады. Ойыншының түсі бар дискіні тақтаға қарсыластың бір немесе бірнеше дискісін «сыртқа шығаратын» күйге қою арқылы жүреді. Диск немесе дискілер қатары оның шетінде қарама -қарсы түсті дискілермен қоршалған кезде сыртқа шығады. Диск кез келген бағытта (көлденең, тік, диагональ) бір немесе бірнеше қатардағы дискілердің кез келген санын қаптай алады. (оқуды өз веб -сайтында аяқтаңыз)

Түпнұсқа ойын мен бұл питон ойынының айырмашылығы мынада: егер бір ойыншыға жарамды қозғалыстар қалмаса, ойын аяқталады

Енді сіз досыңызбен ойнай аласыз, сіз ойнай алатын AI жасайық.

3 -қадам: Minimax алгоритмі: сценарийлерді құру

Мұны кодқа қалай жазу туралы айтпас бұрын, оның логикасына тоқталайық. Minimax алгоритмі-бұл шешім қабылдау, кері бақылау алгоритмі және әдетте екі ойыншыға арналған, айналымға негізделген ойындарда қолданылады. Бұл АИ -нің мақсаты - ойында жеңіске жеткенше келесі ең жақсы қозғалысты және келесі ең жақсы қадамдарды табу.

Енді алгоритм қай қадам ең жақсы екенін қалай анықтайды? Тоқтаңыз және келесі қадамды қалай таңдайтыныңызды ойлаңыз. Көптеген адамдар ең көп ұпай беретін қадамды таңдайды, иә? Немесе егер олар алдын ала ойлайтын болса, олар одан да көп ұпай жинай алатын жағдайды орнататын қадамды таңдар еді. Соңғы ойлау әдісі - бұл минимакс алгоритмі қалай ойлайды. Ол болашақ тақтаның барлық қондырғыларын күтеді және ең көп ұпайға әкелетін қадам жасайды.

Мен мұны кері шегіну алгоритмі деп атадым, себебі ол алдымен болашақ тақтаның барлық күйлерін байланысты мәндермен құрудан және бағалаудан басталады. Бұл алгоритм ойынның барлық сценарийі ойнағанға дейін ойынды қажет болғанша ойнайтынын білдіреді (өзіне және қарсыласына қимыл жасайды). Тақтадағы барлық жағдайларды (сценарийлерді) қадағалау үшін біз ағаштың суретін саламыз (суреттерді қараңыз). Жоғарыдағы суреттегі ағаш - Connect 4 ойынының қарапайым мысалы. Әр тақта конфигурациясы тақта күйі деп аталады, ал оның ағаштағы орны түйін деп аталады. Ағаштың төменгі жағындағы барлық түйіндер барлық қозғалыстарды жасағаннан кейін тақтаның соңғы күйі болып табылады. Әрине, кейбір ойыншылар бір ойыншы үшін екіншісіне қарағанда жақсы. Сонымен, енді біз АИ -ге қай тақтаға кіргісі келетінін таңдауымыз керек.

4 -қадам: Minimax: тақта конфигурацияларын бағалау

Тақта тақтасына құндылықтар беру үшін біз ойнайтын ойынның стратегиясын үйренуіміз керек: бұл жағдайда Отеллоның стратегиясын. Бұл ойын қарсыластың және сіздің дискілеріңізді аудару шайқасы болғандықтан, дискілердің ең жақсы позициясы - бұл тұрақты және аударылмайтын позициялар. Бұрыш, мысалы, диск орналастырылған кезде оны басқа түске өзгертуге болмайды. Осылайша, бұл орын өте құнды болады. Басқа жақсы позицияларға тастардың көп мөлшерін алуға мүмкіндік беретін тақтаның жақтары кіреді. Бұл веб -сайтта басқа стратегиялар бар.

Енді біз әрбір тақтаның штат тақтасы үшін позицияға мән бере аламыз. AI позициясы орын алған кезде, сіз позицияға байланысты белгілі бір ұпай санын бересіз. Мысалы, АИ бөлігі бұрышта орналасқан тақта күйі, сіз 50 ұпай бонус бере аласыз, бірақ егер ол қолайсыз жерде болса, онда оның мәні 0 болуы мүмкін. Барлық мәндерді ескергеннен кейін позициялар, сіз тақта күйіне мән бересіз. Мысалы, егер АИ бұрышта кесек болса, тақта күйі 50 баллға ие болуы мүмкін, ал АИ бөлігі ортасында басқа тақта күйі - 10.

Мұны істеудің көптеген жолдары бар, менде тақта бөліктерін бағалау үшін үш түрлі эвристика бар. Мен сізге эвристиканың жеке түрін жасауға шақырамын. Мен үш түрлі эвристикаға ие үш түрлі жасаушылардың үш түрлі интеллектуалды интеллектуалды станциясын жүктедім: Puma.py, erika5.py, nathanh.py.

5 -қадам: Minimax алгоритмі: Ең жақсы қозғалысты таңдау

Енді егер AI ең жоғары балл жинайтын тақтаға өту үшін барлық қадамдарды таңдаса жақсы болар еді. Есіңізде болсын, AI барлық тақта күйлерін құрған кезде қарсыластың қозғалысын таңдады, ал егер қарсылас ақылды болса, бұл AI -ге тақтаның ең жоғары ұпайына жетуге мүмкіндік бермейді. Оның орнына, ақылды қарсылас АИ -ді тақтаның ең төменгі күйіне көшіруге мәжбүр болады. Алгоритмде біз екі ойыншыны максимум ойыншы және кішірейтуші ойыншы деп атаймыз. AI максималды ойыншы болады, өйткені ол өзіне ең көп ұпай алғысы келеді. Қарсылас кішірейтетін ойыншы болады, өйткені қарсылас AI ең аз ұпай алатын қадам жасауға тырысады.

Тақтаның барлық күйлері құрылып, тақталарға мәндер берілгеннен кейін, алгоритм тақта күйлерін салыстыра бастайды. Суреттерде мен алгоритмнің қозғалысын қалай таңдауға болатынын көрсететін ағаш жасадым. Бұтақтардағы әрбір бөліну - бұл AI немесе қарсылас ойнай алатын әр түрлі қозғалыс. Түйіндер жолдарының сол жағында мен ойнатқышты ұлғайту немесе кішірейту туралы жаздым. Төменгі қатарда тақтаның барлық мәндері жазылған. Бұл түйіндердің әрқайсысының ішінде сан бар және бұл тақталардың әрқайсысына қойылатын ұпайлар: олар неғұрлым жоғары болса, АИ үшін соғұрлым жақсы болады.

Анықтамалар: ата -аналық түйін - оның астындағы түйіндерді шығаратын немесе жасайтын түйін; балалар түйіндерінің шығу тегі - бір ата -аналық түйіннен шығатын түйіндер

Бос түйіндер AI ең жақсы тақта күйіне жету үшін қандай қозғалыс жасайтынын білдіреді. Ол сол жақтағы түйіннің балаларын салыстырудан басталады: 10, -3, 5. Максималды ойыншы қозғалысты жасайтындықтан, оған ең көп ұпай беретін қозғалысты таңдайды: 10. Сонымен, біз оны таңдап, сақтаймыз. тақта ұпайымен жылжып, оны ата -аналық түйінге жазыңыз. Енді 10 ата -аналық түйінде болғандықтан, енді ойыншыларды азайтады. Дегенмен, біз 10 -ды салыстыратын түйін бос, сондықтан кішірейткіш ойнатқыш таңдамас бұрын алдымен осы түйінді бағалауымыз керек. Біз ойыншының максималды айналымына қайта оралып, көршілес түйіннің балаларын салыстырамыз: 8, -2. Максимумдау 8 таңдайды және біз мұны бос ата -түйінге жазамыз. Енді алгоритм үстіндегі түйіннің балалары үшін бос орындарды толтыруды аяқтады, кішірейткіш ойыншы сол балаларды салыстыра алады - 10 мен 8 және 8 -ді таңдайды. Содан кейін алгоритм бүкіл ағаш толтырылғанша осы процесті қайталайды. Бұл мысалдың соңында бізде 8 балл бар. Бұл қарсылас оңтайлы ойнады деп ойлау үшін АИ ойнай алатын ең жоғары деңгей. Осылайша, AI 8 тақта күйіне әкелетін бірінші қадамды таңдайды, ал егер қарсылас оңтайлы ойнаса, AI 8 -ші күйге өту үшін барлық қимылдарды ойнауы керек. (Менің суреттерімдегі ескертулерді орындаңыз)

Мен бұл көп болғанын білемін. Егер сіз бір нәрсені түсіну үшін сізбен сөйлесуді қажет ететіндердің бірі болсаңыз, мен мұның идеясын түсінуге көмектесу үшін мен көрген бірнеше бейне бар: 1, 2, 3.

6 -қадам: Minimax алгоритмі: псевдокод

Minimax алгоритмінің логикасын түсінгеннен кейін, википедиядан осы псевдокодты (барлық кодтарға әмбебап болатын функцияларды) қараңыз:

minimax функциясы (түйін, тереңдік, maximizingPlayer)

егер тереңдік = 0 немесе түйін терминалдық түйін болса

түйіннің эвристикалық мәнін қайтарады

егер maximizingPlayer болса

мәні: = -∞

түйіннің әр баласы үшін жасайды

мән: = max (мән, минимум (бала, тереңдік - 1, ЖАЛҒАН))

қайтару мәні

else (* ойнатқышты азайту *)

мәні: = +∞

түйіннің әр баласы үшін жасайды

мән: = мин (мән, минимум (бала, тереңдік - 1, РАС)))

қайтару мәні

Бұл рекурсивті функция, яғни ол тоқтау нүктесіне жеткенше өзін қайта -қайта шақырады. Біріншіден, функция үш мәнді қабылдайды, түйін, тереңдік және оның кезегі. Түйін мәні - бұл бағдарлама іздеуді бастағыңыз келетін орын. Тереңдік - бұл бағдарламаны қаншалықты іздеу керек. Мысалы, менің ағаш үлгісінде оның тереңдігі 3 -ке тең, себебі ол 3 жылжудан кейін тақтаның барлық күйін іздеді. Әрине, біз AI әр тақтаның күйін тексеріп, ұтқан жеңісті таңдағанын қалаймыз, бірақ миллиондаған тақта конфигурациялары бар көптеген ойындарда сіздің ноутбукіңіз бұл конфигурацияларды өңдей алмайды. Сонымен, біз АИ іздеу тереңдігін шектейміз және оны тақтаның ең жақсы күйіне жеткіземіз.

Бұл псевдокод алдыңғы екі қадамда түсіндірген процесті жаңғыртады. Енді мұны бір қадам жасайық және оны python кодында түзетейік.

7 -қадам: Ai_template.py көмегімен AI жасау

Менің Minimax AI кодын қарамас бұрын, ai_template.py файлы мен соңғы қадамда біз айтқан псевдо-кодты қолдана отырып, АИ жасауға тырысыңыз. Ай үлгісінде екі функция бар: def minimax_min_node (тақта, түс) және def minimax_max_node (тақта, түс). Минимакс функциясы рекурсивті деп аталудың орнына, бізде бір -бірін шақыратын екі түрлі функция бар. Тақтаның күйін бағалау үшін эвристиканы құру үшін сізге өзіңіздің жеке функцияңызды жасау қажет болады. Othello_shared.py файлында АИ құру үшін пайдалануға болатын алдын ала дайындалған функциялар бар.

Егер сізде AI бар болса, оны randy_ai.py қарсы іске қосып көріңіз. Бір -біріне қарсы екі ais іске қосу үшін Mac терминалына «python othello_gui.py (ai файл атауын енгізіңіз).py (файл атауын енгізіңіз).py» деп теріңіз немесе «run othello_gui.py (ai файл атауын енгізіңіз).py» теріңіз. (файл атауын енгізіңіз).py «және дұрыс каталогта екеніңізге көз жеткізіңіз. Сонымен қатар, нақты қадамдар үшін менің бейнеролигімді қараңыз.

8 -қадам: AI -мен күресетін уақыт

Енді компьютерден көптеген достар тауып, оларды өздерінің интеллектуалды дизайнын жасаңыз! Содан кейін сіз бәсекелестікке қол жеткізе аласыз және сіздің AI -ге герцогты көрсете аласыз. Сіз өзіңіздің жеке интеллектуалдылығыңызды құра алмасаңыз да, сіз minimax алгоритмінің қалай жұмыс істейтінін түсіндіңіз деп үміттенемін. Егер сізде сұрақтар туындаса, төмендегі түсініктемелерде сұрақтар қоюға болады.