Tic Tac Toe na Arduinu s AI (minimalni algoritam): 3 koraka

2024 Autor: John Day | [email protected]. Zadnja promjena: 2024-01-30 09:37

U ovom Instructable -u pokazat ću vam kako izgraditi igru Tic Tac Toe s AI -om pomoću Arduina. Možete igrati protiv Arduina ili gledati Arduino kako igra protiv sebe.

Koristim algoritam pod nazivom "minimax algoritam", koji se može koristiti ne samo za izradu AI za Tic Tac Toe, već i za razne druge igre poput Four in a Row, dame ili čak šah. Igre poput šaha vrlo su složene i zahtijevaju mnogo profinjenije verzije algoritma. Za našu igru Tic Tac Toe možemo koristiti najjednostavniju verziju algoritma, koja je ipak prilično impresivna. Zapravo, AI je toliko dobar da je nemoguće pobijediti Arduino!

Igru je lako izgraditi. Trebate samo nekoliko komponenti i skicu koju sam napisao. Dodao sam i detaljnije objašnjenje algoritma, ako želite razumjeti kako radi.

Korak 1: Izgradite i igrajte se

Za izradu igre Tic Tac Toe trebat će vam sljedeće komponente:

• Arduino Uno
• 9 WS2812 RGB LED dioda
• 9 tipki
• neke žičane i kratkospojne kabele

Spojite komponente kao što je prikazano na skici Fritzinga. Zatim prenesite kôd na svoj Arduino.

Prema zadanim postavkama, Arduino prvi skreće. Kako bi stvari bile još zanimljivije, prvi potez odabire se nasumično. Nakon prvog poteza, Arduino koristi algoritam minimaksa kako bi odredio najbolji mogući potez. Počinjete novu igru resetiranjem Arduina.

Možete gledati kako Arduino "razmišlja" otvaranjem serijskog monitora. Za svaki mogući potez, algoritam izračunava ocjenu koja pokazuje hoće li taj potez dovesti do pobjede (vrijednost 10) ili gubitka (vrijednost -10) za Arduino ili remija (vrijednost 0).

Također možete gledati kako se Arduino igra sam protiv sebe tako što ćete na samom početku skice komentirati redak "#define DEMO_MODE". Ako učitate izmijenjenu skicu, Arduino nasumično pravi prvi potez, a zatim koristi algoritam minimaksa za određivanje najboljeg poteza za svakog igrača u svakom potezu.

Imajte na umu da ne možete pobijediti protiv Arduina. Svaka će utakmica završiti neriješeno ili ćete izgubiti ako pogriješite. To je zato što algoritam uvijek bira najbolji mogući potez. Kao što možda znate, igra Tic Tac Toe uvijek će završiti neriješeno ako oba igrača ne pogriješe. U demo načinu rada svaka igra završava neriješeno jer, kao što svi znamo, računala nikada ne griješe;-)

Korak 2: Minimaksni algoritam

Algoritam se sastoji od dvije komponente: funkcije procjene i strategije pretraživanja. Funkcija vrednovanja je funkcija koja dodjeljuje numeričku vrijednost pozicijama ploče. Ako je pozicija konačna pozicija (tj. Pozicija na kojoj je pobijedio plavi ili crveni igrač ili gdje nijedan igrač nije pobijedio), funkcija ocjenjivanja je vrlo jednostavna: Recimo da Arduino igra plavo, a ljudski igrač crveno. Ako je pozicija dobitna pozicija za plavo, funkcija toj poziciji dodjeljuje vrijednost 10; ako je dobitna pozicija za crvenu boju, funkcija dodjeljuje vrijednosti -10 poziciji; a ako je pozicija neriješena, funkcija dodjeljuje vrijednost 0.

Kad je na redu Arduino, želi izabrati potez koji maksimizira vrijednost funkcije procjene, jer maksimiziranje vrijednosti znači da će preferirati pobjedu nad remijem (10 je veće od 0) i omogućiti neriješeno nad gubitkom (0 je veće od -10). Analognim argumentom protivnica želi igrati na takav način da minimizira vrijednost funkcije procjene.

Za ne-konačnu poziciju, algoritam izračunava vrijednost funkcije evaluacije pomoću rekurzivne strategije pretraživanja. Polazeći od trenutne pozicije, naizmjence simulira sve poteze koje plavi i crveni igrač mogu poduzeti. To se može vizualizirati kao stablo, kao na dijagramu. Kad dođe do konačnog položaja, počinje se odmaći noseći vrijednost funkcije vrednovanja s niže razine rekurzije na višu razinu rekurzije. Ona dodjeljuje najveće (ako je u odgovarajućem koraku rekurzije na redu plavi igrač) ili minimalne (ako je u odgovarajućem koraku rekurzije na redu crveni igrač) vrijednosti funkcije vrednovanja od donje razine rekurzije do pozicije na višu razinu rekurzije. Konačno, kada algoritam završi korak unatrag i ponovno stigne na trenutnu poziciju, bit će potreban onaj pomak (ili jedan od poteza) koji ima maksimalnu vrijednost funkcije procjene.

Ovo može zvučati pomalo apstraktno, ali zapravo nije tako teško. Razmotrite položaj prikazan na vrhu dijagrama. U prvom koraku rekurzije postoje tri različita poteza koja plava može poduzeti. Plava nastoji maksimizirati vrijednost funkcije procjene. Za svaki potez koji plavi može poduzeti, postoje dva poteza koja crvena može napraviti. Crvena pokušava minimizirati vrijednost funkcije procjene. Razmislite o potezu gdje se plava igra u gornjem desnom kutu. Ako crveni igra u središnjem polju, crveni je pobijedio (-10). S druge strane, ako crvena igra u središnjem donjem okviru, plava će pobijediti u sljedećem potezu (10). Dakle, ako se plava reproducira u gornjem desnom kutu, crvena će se igrati u središnjem okviru, jer to minimizira vrijednost funkcije procjene. Analogno, ako se plava reproducira u središnjem donjem okviru, crvena će se ponovno igrati u središnjem okviru jer to minimizira funkciju ocjenjivanja. S druge strane, ako plava igra u središnjem okviru, nije važno koji potez crvena uzima, plava će uvijek pobijediti (10). Budući da plava boja želi maksimizirati funkciju ocjenjivanja, igrat će se u središnjem okviru jer ta pozicija rezultira većom vrijednošću funkcije ocjenjivanja (10) od druga dva poteza (-10).

Korak 3: Rješavanje problema i daljnji koraci

Ako pritisnete gumb i zasvijetli drugačija LED lampica od one koja odgovara gumbu, vjerojatno ste pomiješali žice na pinovima A0-A2 ili 4-6 ili ste LED diode spojili pogrešnim redoslijedom.

Također imajte na umu da algoritam ne mora uvijek birati potez koji će omogućiti Arduinu da pobijedi što je brže moguće. Zapravo, proveo sam neko vrijeme u ispravljanju pogrešaka algoritma jer Arduino nije odabrao potez koji bi bio dobitni potez. Trebalo mi je neko vrijeme dok nisam shvatio da je umjesto toga odabrao potez koji jamči da će kasnije dobiti jedan potez. Ako želite, možete pokušati izmijeniti algoritam tako da uvijek preferira pobjednički potez u odnosu na kasniji dobitak.

Moguće proširenje ovog projekta bilo bi korištenje algoritma za izradu AI za 4x4 ili čak 5x5 Tic Tac Toe. Međutim, imajte na umu da broj pozicija koje algoritam treba ispitati raste vrlo brzo. Morat ćete pronaći načine da učinite evaluacijsku funkciju inteligentnijom dodjeljujući vrijednosti pozicijama koje nisu konačne, na temelju vjerojatnosti da je pozicija dobra ili loša za dotičnog igrača. Također možete pokušati učiniti pretraživanje inteligentnijim tako što ćete prekinuti rekurziju ranije ako se pokaže da je potez manje vrijedan daljnjeg istraživanja od alternativnih poteza.

Arduino vjerojatno nije najbolja platforma za takva proširenja zbog svoje ograničene memorije. Rekurzija omogućuje rastu hrpe tijekom izvođenja programa, a ako se hrpa previše poveća, može oštetiti memoriju programa, što može dovesti do rušenja ili nestabilnog ponašanja. Odabrao sam Arduino za ovaj projekt uglavnom zato što sam želio vidjeti može li se to učiniti i u obrazovne svrhe, a ne zato što je najbolji izbor za ovu vrstu problema.