AI Arduino -да Tic Tac Toe (Minimax алгоритмі): 3 қадам

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

Бұл нұсқаулықта мен сізге Arduino көмегімен AI -мен Tic Tac Toe ойынын қалай құруға болатынын көрсетемін. Сіз Arduino -ға қарсы ойнай аласыз немесе Arduino -ның өзіне қарсы ойынын көре аласыз.

Мен «minimax алгоритмі» деп аталатын алгоритмді қолданамын, оны тек Tic Tac Toe үшін AI құруға ғана емес, сонымен қатар төрт қатар, дойбы немесе тіпті шахмат сияқты басқа да ойындарға қолдануға болады. Шахмат сияқты ойындар өте күрделі және алгоритмнің әлдеқайда жетілдірілген нұсқаларын қажет етеді. Біздің Tic Tac Toe ойыны үшін біз алгоритмнің ең қарапайым нұсқасын қолдана аламыз, дегенмен ол өте әсерлі. Шындығында, AI өте жақсы, сондықтан Arduino -ны жеңу мүмкін емес!

Ойын құрастыру оңай. Сізге бірнеше компоненттер мен мен жазған эскиз қажет. Мен алгоритмнің егжей -тегжейлі түсініктемесін қостым, егер сіз оның қалай жұмыс істейтінін түсінгіңіз келсе.

1 -қадам: Құру және ойнау

Tic Tac Toe ойынын құру үшін сізге келесі компоненттер қажет:

• An Arduino Uno
• 9 WS2812 RGB светодиодтары
• 9 түйме
• кейбір сымдар мен секіргіштер

Fritzing эскизінде көрсетілгендей компоненттерді қосыңыз. Содан кейін кодты Arduino -ға жүктеңіз.

Әдепкі бойынша, Arduino бірінші бұрылысты алады. Біршама қызықты ету үшін бірінші қадам кездейсоқ таңдалады. Бірінші қадамнан кейін Arduino ең жақсы қозғалысты анықтау үшін minimax алгоритмін қолданады. Сіз Arduino -ны қалпына келтіру арқылы жаңа ойын бастайсыз.

Сіз Arduino -ді сериялық мониторды ашу арқылы «ойлайтынын» көре аласыз. Әрбір мүмкін болатын қозғалыс үшін алгоритм бұл қадамның Arduino үшін жеңіске (10 мәні) немесе шығынға (-10 мәні) әкелетінін көрсететін рейтингті есептейді.

Сіз сонымен қатар эскиздің басында «#define DEMO_MODE» жолын түсіндіру арқылы Arduino -ның өзіне қарсы ойынын көре аласыз. Егер сіз өзгертілген эскизді жүктесеңіз, Arduino бірінші қадамды кездейсоқ жасайды, содан кейін минимакс алгоритмін қолданып, әр ойыншының әр қадамдағы ең жақсы қозғалысын анықтайды.

Назар аударыңыз, сіз Arduino -мен жеңе алмайсыз. Әр ойын не тең аяқталады, не қателескен жағдайда ұтылады. Бұл алгоритм әрқашан мүмкін болатын қозғалысты таңдағандықтан. Өздеріңіз білетіндей, егер екі ойыншы да қателеспесе, Tic Tac Toe ойыны әрқашан тең аяқталады. Демо режимде әр ойын тең аяқталады, өйткені біз білеміз, компьютерлер ешқашан қателеспейді;-)

2 -қадам: Минимакс алгоритмі

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

Кезек Ардуинода болғанда, ол бағалау функциясының мәнін жоғарылататын қозғалысты таңдағысы келеді, себебі бұл мәнді ұлғайту оның ұтысты ұтқанды ұнататынын білдіреді (10 0 -ден үлкен) және ұтылысқа теңдікті (0 -10 -дан үлкен). Ұқсас аргумент бойынша қарсылас бағалау функциясының мәнін төмендететін етіп ойнағысы келеді.

Соңғы емес позиция үшін алгоритм рекурсивті іздеу стратегиясы бойынша бағалау функциясының мәнін есептейді. Ағымдағы позициядан бастап ол көк ойыншы мен қызыл ойыншы жасай алатын барлық қозғалыстарды кезекпен модельдейді. Мұны диаграммадағыдай ағаш ретінде көруге болады. Ол соңғы позицияға жеткенде, бағалау функциясының мәнін төменгі рекурсия деңгейінен жоғары рекурсия деңгейіне дейін жеткізе отырып, шегінуді бастайды. Ол бағалау рекурсиясының төменгі деңгейінен максималды (егер сәйкес рекурсия қадамында көк ойыншының кезегі болса) немесе минимумын (егер сәйкес рекурсия сатысында қызыл ойыншының кезегі болса) тағайындайды. рекурсияның жоғары деңгейі. Ақырында, алгоритм артқа шегінуді аяқтап, қайтадан ағымдағы орынға жеткенде, бағалау функциясы максималды мәні бар қозғалысты (немесе қозғалыстардың бірін) алады.

Бұл біршама дерексіз болып көрінуі мүмкін, бірақ іс жүзінде бұл қиын емес. Диаграмманың жоғарғы жағында көрсетілген орынды қарастырыңыз. Бірінші рекурсиялық қадамда көк түс алудың үш түрлі қозғалысы бар. Көк бағалау функциясының мәнін барынша арттыруға тырысады. Көк қозғалыстардың әрқайсысы үшін көк түс, қызыл түсі бар екі қозғалыс бар. Қызыл бағалау функциясының мәнін барынша азайтуға тырысады. Жоғарғы оң жақ бұрышта көк ойнайтын қозғалысты қарастырыңыз. Егер қызыл орталық қорапта ойнаса, қызыл жеңді (-10). Егер, керісінше, қызыл төменгі төменгі қорапта ойнаса, келесі қадамда көк жеңеді (10). Сонымен, егер көк жоғарғы оң жақ бұрышта ойнаса, орталық терезеде қызыл түс ойнайды, себебі бұл бағалау функциясының мәнін азайтады. Дәл осылай, егер орталық төменгі қорапта көк түс ойнаса, қызыл қайтадан ортаңғы қорапта ойнайды, себебі бұл бағалау функциясын азайтады. Егер, керісінше, көгілдір орталық қорапта ойнаса, онда қызылдың қандай қозғалысы маңызды емес, көк әрқашан жеңіске жетеді (10). Көк бағалау функциясын барынша арттырғысы келетіндіктен, ол орталық терезеде ойнайды, себебі бұл позиция басқа екі қозғалысқа (-10) қарағанда бағалау функциясының (10) үлкен мәнін береді.

3 -қадам: Ақаулықтарды жою және қосымша қадамдар

Егер сіз түймені бассаңыз және түймеге сәйкес келетін басқа жарық диоды жанса, сіз A0-A2 немесе 4-6 түйреуіштеріндегі сымдарды араластырып алған боларсыз немесе жарық диодты дұрыс емес тәртіпте қосқан боларсыз.

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

Бұл жобаның мүмкін болатын кеңейтімі 4x4 немесе тіпті 5x5 Tic Tac Toe үшін АИ құру алгоритмін қолдану болады. Алайда, алгоритмді тексеру қажет позициялар саны өте тез өсетінін ескеріңіз. Бұл ойыншы үшін позиция жақсы немесе жаман болу ықтималдығына негізделе отырып, түпкілікті емес позицияларды бағалау арқылы бағалау функциясын неғұрлым ақылды ету жолдарын табу қажет болады. Егер сіз балама қадамдарға қарағанда одан әрі зерттеуге лайық емес болып шықсаңыз, рекурсияны ертерек тоқтату арқылы іздеуді ақылды етуге тырысуға болады.

Ардуино жады шектеулі болғандықтан мұндай кеңейтімдер үшін ең жақсы платформа емес шығар. Рекурсия бағдарламаның орындалуы кезінде стектің өсуіне мүмкіндік береді, ал егер стек тым көбейсе, ол бағдарламаның жадын бұзуы мүмкін, бұл апатқа немесе тәртіпсіздікке әкеледі. Мен Arduino -ны осы жоба үшін таңдадым, себебі мен мұны істеуге болатынын білгім келді және білім беру үшін емес, бұл мәселенің бұл түрі үшін ең жақсы таңдау болғандықтан.