Tic Tac Toe në Arduino me AI (Algoritmi Minimax): 3 hapa

2024 Autor: John Day | [email protected]. E modifikuara e fundit: 2024-01-30 12:27

Në këtë Instructable unë do t'ju tregoj se si të ndërtoni një lojë Tic Tac Toe me një AI duke përdorur një Arduino. Ju ose mund të luani kundër Arduino ose të shikoni Arduino të luajë kundër vetes.

Unë jam duke përdorur një algoritëm të quajtur "minimax algorithm", i cili mund të përdoret jo vetëm për të ndërtuar një UA për Tic Tac Toe, por edhe për një sërë lojërash të tjera si Four in a Row, damë apo edhe shah. Lojërat si shahu janë shumë komplekse dhe kërkojnë versione shumë më të rafinuara të algoritmit. Për lojën tonë Tic Tac Toe, ne mund të përdorim versionin më të thjeshtë të algoritmit, i cili megjithatë është mjaft mbresëlënës. Në fakt, AI është aq i mirë sa është e pamundur të mposhtësh Arduino -n!

Loja është e lehtë për tu ndërtuar. Ju duhen vetëm disa përbërës dhe skica që kam shkruar. Unë gjithashtu shtova një shpjegim më të detajuar të algoritmit, nëse doni të kuptoni se si funksionon.

Hapi 1: Ndërtoni dhe luani

Për të ndërtuar lojën Tic Tac Toe do t'ju duhen përbërësit e mëposhtëm:

• Një Arduino Uno
• 9 LED WS2812 RGB
• 9 butona shtypi
• disa kabllo tela dhe kërcyes

Lidhni përbërësit siç tregohet në skicën Fritzing. Pastaj ngarkoni kodin në Arduino tuaj.

Si parazgjedhje, Arduino merr kthesën e parë. Për t'i bërë gjërat pak më interesante, lëvizja e parë zgjidhet rastësisht. Pas lëvizjes së parë, Arduino përdor algoritmin minimalax për të përcaktuar lëvizjen më të mirë të mundshme. Ju filloni një lojë të re duke rivendosur Arduino.

Ju mund të shikoni Arduino "mendoni" duke hapur Monitorin Serial. Për çdo lëvizje të mundshme, algoritmi llogarit një vlerësim që tregon nëse kjo lëvizje do të çojë në fitore (vlerë 10) ose humbje (vlerë -10) për Arduino ose barazim (vlerë 0).

Ju gjithashtu mund të shikoni lojën Arduino kundër vetes duke mos komentuar rreshtin "#define DEMO_MODE" në fillim të skicës. Nëse ngarkoni skicën e modifikuar, Arduino bën lëvizjen e parë rastësisht dhe më pas përdor algoritmin minimalax për të përcaktuar lëvizjen më të mirë për secilin lojtar në çdo kthesë.

Vini re se nuk mund të fitoni kundër Arduino. Çdo lojë ose do të përfundojë në barazim ose do të humbni, nëse bëni një gabim. Kjo ndodh sepse algoritmi zgjedh gjithmonë lëvizjen më të mirë të mundshme. Siç mund ta dini, një lojë Tic Tac Toe gjithmonë do të përfundojë në barazim nëse të dy lojtarët nuk bëjnë gabim. Në modalitetin demo, çdo lojë përfundon në barazim sepse, siç e dimë të gjithë, kompjuterët nuk bëjnë kurrë gabime;-)

Hapi 2: Algoritmi Minimax

Algoritmi përbëhet nga dy përbërës: një funksion vlerësimi dhe një strategji kërkimi. Funksioni i vlerësimit është një funksion që i jep një vlerë numerike pozicioneve të bordit. Nëse pozicioni është një pozicion përfundimtar (p.sh., një pozicion ku ose lojtari blu ose i kuq ka fituar ose ku asnjë lojtar nuk ka fituar), funksioni i vlerësimit është shumë i thjeshtë: Le të themi që Arduino luan blu dhe lojtari njerëzor luan të kuq Me Nëse pozicioni është një pozicion fitues për ngjyrën blu, funksioni i cakton një vlerë 10 atij pozicioni; nëse është një pozicion fitues për të kuqen, funksioni i jep një vlerë -10 pozicionit; dhe nëse pozicioni është barazim, funksioni i cakton një vlerë 0.

Kur i vjen radha Arduino -s, ajo dëshiron të zgjedhë një lëvizje që maksimizon vlerën e funksionit të vlerësimit, sepse maksimizimi i vlerës do të thotë që do të preferojë një fitore mbi një barazim (10 është më e madhe se 0) dhe do të preferojë një barazim mbi humbjen (0 është më e madhe se -10). Me një argument analog, kundërshtari dëshiron të luajë në atë mënyrë që të minimizojë vlerën e funksionit të vlerësimit.

Për një pozicion jo përfundimtar, algoritmi llogarit vlerën e funksionit të vlerësimit me anë të një strategjie kërkimi rekursive. Duke filluar nga pozicioni aktual, ai simulon në mënyrë alternative të gjitha lëvizjet që lojtari blu dhe ai i kuq mund të ndërmarrin. Kjo mund të vizualizohet si një pemë, si në diagram. Kur arrin në një pozicion përfundimtar, ai fillon të tërhiqet, duke mbajtur vlerën e funksionit të vlerësimit nga niveli më i ulët i rekursionit në nivelin më të lartë të rekursionit. Ai cakton maksimumin (nëse në hapin përkatës të rikthimit është radha e lojtarit blu) ose minimumin (nëse në hapin përkatës të rekursionit është radha e lojtarit të kuq) të vlerave të funksionit të vlerësimit nga niveli më i ulët i rekursionit në pozicionin në niveli më i lartë i rekursionit. Së fundi, kur algoritmi të ketë mbaruar hapin prapa dhe të ketë arritur përsëri në pozicionin aktual, ai merr atë lëvizje (ose një nga lëvizjet) që ka vlerën maksimale të funksionit të vlerësimit.

Kjo mund të tingëllojë pak abstrakte, por në fakt nuk është aq e vështirë. Konsideroni pozicionin e treguar në krye të diagramit. Në hapin e parë të rekursionit, ka tre lëvizje të ndryshme që blu mund të ndërmarrë. Blu përpiqet të maksimizojë vlerën e funksionit të vlerësimit. Për secilën prej lëvizjeve që blu mund të bëjë, ka dy lëvizje që mund të marrë e kuqja. E kuqja përpiqet të minimizojë vlerën e funksionit të vlerësimit. Konsideroni lëvizjen ku blu luan në këndin e sipërm të djathtë. Nëse e kuqja luan në kutinë qendrore, e kuqja ka fituar (-10). Nëse, nga ana tjetër, e kuqja luan në pjesën e poshtme të qendrës, bluja do të fitojë në lëvizjen tjetër (10). Pra, nëse bluja luan në këndin e sipërm të djathtë, e kuqja do të luajë në kutinë qendrore, pasi kjo minimizon vlerën e funksionit të vlerësimit. Në mënyrë analoge, nëse bluja luan në kutinë e poshtme qendrore, e kuqja përsëri do të luajë në kutinë qendrore sepse kjo minimizon funksionin e vlerësimit. Nëse, nga ana tjetër, blu luan në kutinë qendrore, nuk ka rëndësi se cilën lëvizje merr e kuqja, bluja gjithmonë do të fitojë (10). Meqenëse bluja dëshiron të maksimizojë funksionin e vlerësimit, do të luajë në kutinë qendrore, meqë ai pozicion rezulton në një vlerë më të madhe të funksionit të vlerësimit (10) sesa dy lëvizjet e tjera (-10).

Hapi 3: Zgjidhja e problemeve dhe hapat e mëtejshëm

Nëse shtypni një buton dhe ndizet një LED i ndryshëm nga ai që i përgjigjet butonit, me siguri ose i keni përzier telat në kunjat A0-A2 ose 4-6, ose i keni lidhur LED-et në rendin e gabuar.

Gjithashtu vini re se algoritmi jo domosdoshmërisht zgjedh gjithmonë një lëvizje që do ta lejojë Arduino të fitojë sa më shpejt që të jetë e mundur. Në fakt, kalova ca kohë duke korrigjuar algoritmin sepse Arduino nuk zgjodhi një veprim që do të kishte qenë një hap fitues. M’u desh pak kohë derisa kuptova se në vend të kësaj kishte zgjedhur një lëvizje që garantonte se do të fitonte një lëvizje më vonë. Nëse dëshironi, mund të përpiqeni të modifikoni algoritmin në mënyrë që ai gjithmonë të preferojë një lëvizje fituese ndaj një fitoreje të mëvonshme.

Një shtrirje e mundshme e këtij projekti do të ishte përdorimi i algoritmit për të ndërtuar një UA për 4x4 apo edhe 5x5 Tic Tac Toe. Sidoqoftë, vini re se numri i pozicioneve që algoritmi duhet të ekzaminojë rritet shumë shpejt. Ju do të duhet të gjeni mënyra për ta bërë funksionin e vlerësimit më inteligjent duke vlerësuar vlerat në pozicionet që nuk janë përfundimtare, bazuar në gjasat që pozicioni të jetë i mirë apo i keq për lojtarin në fjalë. Ju gjithashtu mund të përpiqeni ta bëni kërkimin më inteligjent duke ndaluar rekursionin herët nëse një lëvizje rezulton të jetë më pak e denjë për eksplorim të mëtejshëm sesa lëvizjet alternative.

Arduino ndoshta nuk është platforma më e mirë për shtesa të tilla për shkak të kujtesës së tij të kufizuar. Rekursioni lejon që pirgu të rritet gjatë ekzekutimit të programit dhe nëse pirgu rritet shumë, mund të prishë kujtesën e programit, duke çuar në prishje ose sjellje të çrregullt. Zgjodha Arduino për këtë projekt kryesisht sepse doja të shihja nëse mund të bëhej dhe për qëllime edukative, jo sepse është zgjidhja më e mirë për këtë lloj problemi.