AI менен Arduino боюнча Tic Tac Toe (Minimax Алгоритм): 3 кадам

2024 Автор: John Day | [email protected]. Акыркы өзгөртүү: 2024-01-30 10:42

Бул Нускамада мен сизге Arduino аркылуу AI менен Tic Tac Toe оюнун кантип курууну көрсөтөм. Сиз же Arduino менен ойной аласыз же Arduino өзүнө каршы ойной алат.

Мен "minimax алгоритми" деп аталган алгоритмди колдонуп жатам, аны Tic Tac Toe үчүн AI жасоо үчүн эле эмес, төрт катар, шашки же ал тургай шахмат сыяктуу башка көптөгөн оюндар үчүн колдонсо болот. Шахмат сыяктуу оюндар өтө татаал жана алгоритмдин бир топ такталган версияларын талап кылат. Tic Tac Toe оюнубуз үчүн биз алгоритмдин эң жөнөкөй версиясын колдонсок болот, бирок ошентсе да абдан таасирдүү. Чындыгында, AI ушунчалык жакшы болгондуктан, Arduino'yу жеңүү мүмкүн эмес!

Оюнду куруу оңой. Сизге бир нече компоненттер жана мен жазган эскиз гана керек. Мен алгоритмдин дагы кеңири түшүндүрмөсүн коштум, эгерде анын кандай иштээрин билгиңиз келсе.

1 -кадам: Build жана Play

Tic Tac Toe оюнун куруу үчүн сизге төмөнкү компоненттер керек болот:

• An Arduino Uno
• 9 WS2812 RGB светодиоддору
• 9 баскычтар
• кээ бир зым жана секирүүчү кабелдер

Fritzing эскизинде көрсөтүлгөндөй компоненттерди зым менен жабыңыз. Андан кийин кодду Arduinoго жүктөңүз.

Демейки боюнча, Arduino биринчи кезекти алат. Бир аз кызыктуу кылуу үчүн, биринчи кадам туш келди тандалат. Биринчи кадамдан кийин, Arduino эң жакшы кадамды аныктоо үчүн minimax алгоритмин колдонот. Сиз Arduino баштапкы абалга келтирүү менен жаңы оюнду баштайсыз.

Сиз Arduino сериялык мониторун ачуу менен "ойлонууну" көрө аласыз. Ар бир мүмкүн болгон кыймыл үчүн алгоритм рейтингди эсептейт, бул кадам утуп (10 мааниси) же жоготууга алып келет (Arduino үчүн утушка алып келет (0 мааниси) же 0 мааниси).

Сиз ошондой эле эскиздин башында "#define DEMO_MODE" линиясын чечмелеп, Arduino өзүнө каршы ойногонун көрө аласыз. Эгер сиз өзгөртүлгөн эскизди жүктөсөңүз, Arduino биринчи кадамды туш келди жасайт, андан кийин minimax алгоритмин колдонуп, ар бир оюнчу үчүн эң жакшы кыймылды аныктайт.

Белгилей кетсек, сиз Arduino менен жеңе албайсыз. Ар бир оюн тең чыгуу менен аяктайт же ката кетирсеңиз, утулуп каласыз. Бул алгоритм дайыма мүмкүн болгон эң мыкты кадамды тандайт. Белгилүү болгондой, Tic Tac Toe оюну эки оюнчу тең ката кетирбесе, дайыма тең чыгуу менен аяктайт. Демо режиминде, ар бир оюн тең чыгуу менен аяктайт, анткени баарыбыз билебиз, компьютерлер эч качан ката кетирбейт;-)

2 -кадам: Minimax алгоритми

Алгоритм эки компоненттен турат: баалоо функциясы жана издөө стратегиясы. Баалоо функциясы - тактайдын позициясына сандык маанини ыйгаруучу функция. Эгерде позиция акыркы позиция болсо (б.а. көк оюнчу же кызыл оюнчу утуп алган же эч бир оюнчу утпаган позиция), баалоо функциясы абдан жөнөкөй: Ардуино көк, ал эми адам оюнчусу кызыл ойнойт дейли. Эгерде позиция көк үчүн жеңүүчү позиция болсо, функция ошол позицияга 10 маанисин берет; бул кызыл үчүн утуш позициясы болсо, функция позицияга -10 маанисин берет; жана эгер позиция чүчүкулак болсо, функция 0 маанисин дайындайт.

Кезек Ардуиного келгенде, ал баалоо функциясынын маанисин максималдаштырган кадамды тандап алгысы келет, анткени маанини максималдаштыруу утушту утуп алууну артык көрөт дегенди билдирет (10 0дөн чоң) жана утулууга караганда тең чыгууну (0 -10дон жогору). Окшош аргумент боюнча, каршылаш баалоо функциясынын баалуулугун минималдаштыра турган жолдо ойногусу келет.

Акыркы эмес позиция үчүн алгоритм рекурсивдүү издөө стратегиясы боюнча баалоо функциясынын маанисин эсептейт. Учурдагы абалынан баштап, ал көк оюнчу менен кызыл оюнчу жасай турган бардык кыймылдарды симуляциялайт. Муну диаграммада көрсөтүлгөндөй дарак катары элестетсе болот. Ал акыркы позицияга келгенде, баалоо функциясынын маанисин төмөнкү рекурсиялык денгээлден жогорку рекурсиялык деңгээлге көтөрүп, артка кете баштайт. Ал төмөнкү рекурсиялык денгээлден максималдуу (эгер тиешелүү рекурсия кадамында көк оюнчунун кезеги болсо) же минимумун (эгерде тиешелүү рекурсия кадамында кызыл оюнчунун кезеги болсо) дайындайт. жогорку рекурсиялык деңгээл. Акыр -аягы, алгоритм артка чегинип бүтүп, учурдагы абалына кайтып келгенде, максималдуу баалоо функциясынын маанисине ээ болгон кыймылды (же кыймылдардын бирин) талап кылат.

Бул бир аз абстрактуу угулушу мүмкүн, бирок чындыгында анчалык деле кыйын эмес. Диаграмманын жогору жагында көрсөтүлгөн позицияны карап көрөлү. Биринчи рекурсия кадамында, көк ала турган үч башка кыймыл бар. Blue баалоо функциясынын баалуулугун максималдаштырууга аракет кылат. Көк ала турган ар бир кыймыл үчүн, кызыл ала турган эки кыймыл бар. Кызыл баа берүү функциясынын баалуулугун минималдаштырууга аракет кылат. Көгүлтүр түстүн жогорку оң бурчта ойногонун карап көрөлү. Эгерде кызыл борбордук кутуда ойносо, кызыл утту (-10). Эгерде, тескерисинче, кызыл түстүн борбордук кутусунда ойносо, кийинки кадамда көк утат (10). Демек, эгер көк түстүн жогорку оң бурчунда ойносо, борбордук кутуда кызыл ойнойт, анткени бул баалоо функциясынын маанисин минималдаштырат. Ошо сыяктуу эле, эгер көк борбордун астыңкы кутусунда ойносо, кызыл дагы борбордук кутуда ойнойт, анткени бул баалоо функциясын азайтат. Эгерде, экинчи жагынан, көк түстө борбордук кутуда ойносо, анда кызылдын кайсы кыймылы маанилүү эмес, көк дайыма утат (10). Көк баа берүү функциясын максималдаштыргысы келгендиктен, ал борбордук кутуда ойнойт, анткени бул позиция башка эки кыймылга (-10) караганда баалоо функциясынын чоң маанисине (10) алып келет.

3 -кадам: Мүчүлүштүктөрдү оңдоо жана андан аркы кадамдар

Эгер сиз баскычты жана баскычка туура келгенден башкача жарык диодун күйгүзсөңүз, анда сиз A0-A2 же 4-6 төөнөгүчтөрүндөгү зымдарды аралаштырып алгансыз же LEDди туура эмес тартипте туташтырдыңыз.

Ошондой эле, алгоритм дайыма эле Arduino мүмкүн болушунча тезирээк утуп бере турган кадамды тандап албасын эске алыңыз. Чынында, мен бир аз убакыт алгоритмди оңдоого жумшадым, анткени Arduino жеңиштүү кадам боло турган кадамды тандаган жок. Мен анын ордуна кийинчерээк бир кадамды утуп алаарына кепилдик берген кадамды тандап алганын түшүнгөнгө чейин мага бир аз убакыт өттү. Кааласаңыз, алгоритмди өзгөртүүгө аракет кылсаңыз болот, ал кийинчерээк жеңишке караганда жеңиштүү кадамды дайыма артык көрөт.

Бул долбоордун мүмкүн болгон кеңейтүүсү 4x4, ал тургай 5x5 Tic Tac Toe үчүн AI куруу үчүн алгоритмди колдонуу болмок. Бирок, алгоритмдин текшериши керек болгон позициялардын саны абдан тездик менен өсүп жатканына көңүл буруңуз. Позициянын каралып жаткан оюнчу үчүн жакшы же жаман болуу ыктымалдыгы боюнча, акыркы эмес позицияларга баалуулуктарды берүү менен баалоо функциясын акылдуу кылуу жолдорун табышыңыз керек. Эгерде сиз альтернативдүү кыймылдарга караганда андан аркы изилдөөлөргө азыраак татыктуу болуп калса, сиз рекурсияны эрте токтотуу менен издөөнү акылдуу кылууга аракет кылсаңыз болот.

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