Tic Tac Toe на Arduino с AI (минимакс алгоритъм): 3 стъпки

2024 Автор: John Day | [email protected]. Последно модифициран: 2024-01-30 07:53

В тази инструкция ще ви покажа как да изградите игра на Tic Tac Toe с AI с помощта на Arduino. Можете да играете срещу Arduino или да гледате Arduino да играе срещу себе си.

Използвам алгоритъм, наречен "минимакс алгоритъм", който може да се използва не само за изграждане на AI за Tic Tac Toe, но и за различни други игри като Four in a Row, пулове или дори шах. Игри като шах са много сложни и изискват много по -усъвършенствани версии на алгоритъма. За нашата игра Tic Tac Toe можем да използваме най -простата версия на алгоритъма, която въпреки това е доста впечатляваща. Всъщност AI е толкова добър, че е невъзможно да победим Arduino!

Играта е лесна за изграждане. Имате нужда само от няколко компонента и скицата, която съм написал. Добавих и по -подробно обяснение на алгоритъма, ако искате да разберете как работи.

Стъпка 1: Създайте и играйте

За да изградите играта Tic Tac Toe, ще ви трябват следните компоненти:

• Arduino Uno
• 9 WS2812 RGB светодиода
• 9 бутона за натискане
• някои жични и джъмперни кабели

Свържете компонентите, както е показано на скицата на Fritzing. След това качете кода във вашия Arduino.

По подразбиране Arduino поема първия завой. За да направят нещата малко по -интересни, първият ход се избира произволно. След първия ход, Arduino използва алгоритъма за минимакс, за да определи възможно най -добрия ход. Започвате нова игра, като нулирате Arduino.

Можете да гледате как Arduino „мисли“, като отворите серийния монитор. За всеки възможен ход алгоритъмът изчислява рейтинг, който показва дали този ход ще доведе до печалба (стойност 10) или загуба (стойност -10) за Arduino или равенство (стойност 0).

Можете също да гледате как Arduino играе срещу себе си, като декомментирате реда "#define DEMO_MODE" в самото начало на скицата. Ако качите модифицираната скица, Arduino прави първия ход на случаен принцип и след това използва алгоритъма за минимакс, за да определи най -добрия ход за всеки играч във всеки ход.

Имайте предвид, че не можете да спечелите срещу Arduino. Всяка игра или ще завърши наравно, или ще загубите, ако направите грешка. Това е така, защото алгоритъмът винаги избира възможно най -добрия ход. Както може би знаете, играта на Tic Tac Toe винаги ще завърши наравно, ако и двамата играчи не допуснат грешка. В демо режим всяка игра завършва наравно, защото, както всички знаем, компютрите никога не правят грешки;-)

Стъпка 2: Минимаксният алгоритъм

Алгоритъмът се състои от два компонента: функция за оценка и стратегия за търсене. Функцията за оценка е функция, която присвоява числова стойност на позициите на борда. Ако позицията е крайна позиция (т.е. позиция, в която или синият играч, или червеният играч е спечелил или където нито един играч не е спечелил), функцията за оценка е много проста: Да кажем, че Arduino играе в синьо, а човекът играе в червено. Ако позицията е печеливша позиция за синьо, функцията присвоява стойност 10 на тази позиция; ако това е печеливша позиция за червено, функцията присвоява стойност -10 на позицията; и ако позицията е равен, функцията присвоява стойност 0.

Когато е ред на Arduino, той иска да избере ход, който максимизира стойността на функцията за оценка, защото максимизирането на стойността означава, че ще предпочете печалба пред равенство (10 е по -голямо от 0) и ще даде равенство пред загуба (0 е по -голямо от -10). По аналогичен аргумент опонентката иска да играе по такъв начин, че да минимизира стойността на функцията за оценка.

За неокончателна позиция алгоритъмът изчислява стойността на функцията за оценка чрез рекурсивна стратегия за търсене. Започвайки от текущата позиция, той последователно симулира всички ходове, които синият и червеният играч могат да предприемат. Това може да се визуализира като дърво, както е на диаграмата. Когато стигне до крайна позиция, той започва да отстъпва, пренасяйки стойността на функцията за оценка от по -ниското ниво на рекурсия към по -високото ниво на рекурсия. Той определя максималната (ако в съответната рекурсивна стъпка е ред на синия играч) или минималната (ако в съответната рекурсивна стъпка е ред на червения играч) на стойностите на функцията за оценка от по -ниското ниво на рекурсия до позицията на по -високо ниво на рекурсия. И накрая, когато алгоритъмът приключи с отстъпването и отново стигна до текущата позиция, той предприема този ход (или един от ходовете), който има максималната стойност на функцията за оценка.

Това може да звучи малко абстрактно, но всъщност не е толкова трудно. Помислете за позицията, показана в горната част на диаграмата. В първата стъпка на рекурсия има три различни хода, които синьото може да предприеме. Синьото се опитва да увеличи максимално стойността на функцията за оценка. За всеки от ходовете, които синьото може да направи, има два хода, които червеният може да направи. Червеното се опитва да сведе до минимум стойността на функцията за оценка. Помислете за хода, при който синият играе в горния десен ъгъл. Ако червените играят в централната кутия, червените печелят (-10). Ако, от друга страна, червеният играе в централната долна кутия, синият ще спечели в следващия ход (10). Така че, ако синьото играе в горния десен ъгъл, червеното ще играе в централното поле, тъй като това минимизира стойността на функцията за оценка. Аналогично, ако синьото играе в централното долно поле, червеното отново ще свири в централното поле, защото това минимизира функцията за оценка. Ако, от друга страна, синият играе в централната кутия, няма значение кой ход червеният ще вземе, синият винаги ще спечели (10). Тъй като синьото иска да увеличи максимално функцията за оценка, тя ще играе в централното поле, тъй като тази позиция води до по-голяма стойност на функцията за оценка (10) от другите два хода (-10).

Стъпка 3: Отстраняване на неизправности и допълнителни стъпки

Ако натиснете бутон и светне различен светодиод от този, съответстващ на бутона, вероятно или сте смесили проводниците на щифтове A0-A2 или 4-6, или сте свързали светодиодите в грешен ред.

Също така имайте предвид, че алгоритъмът не винаги избира ход, който ще позволи на Arduino да спечели възможно най -бързо. Всъщност прекарах известно време в отстраняване на грешки в алгоритъма, защото Arduino не избра ход, който би бил печеливш ход. Отне ми известно време, докато разбрах, че вместо това е избрал ход, който гарантира, че ще спечели един ход по -късно. Ако искате, можете да опитате да промените алгоритъма, така че той винаги да предпочита печеливш ход пред по -късна печалба.

Възможно разширение на този проект би било да се използва алгоритъмът за изграждане на AI за 4x4 или дори 5x5 Tic Tac Toe. Имайте предвид обаче, че броят на позициите, които алгоритъмът трябва да изследва, нараства много бързо. Ще трябва да намерите начини да направите функцията за оценка по -интелигентна, като присвоите стойности на позиции, които не са окончателни, въз основа на вероятността позицията да е добра или лоша за въпросния играч. Можете също така да опитате да направите търсенето по -интелигентно, като спрете рекурсията по -рано, ако ходът се окаже по -малко достоен за по -нататъшно проучване от алтернативните ходове.

Arduino вероятно не е най -добрата платформа за такива разширения поради ограничената си памет. Рекурсията позволява на стека да расте по време на изпълнение на програмата и ако стекът се увеличи твърде много, това може да повреди паметта на програмата, което да доведе до сривове или неправилно поведение. Избрах Arduino за този проект главно защото исках да видя дали може да се направи и за образователни цели, а не защото е най -добрият избор за този вид проблеми.