Berends Botje

Als econometrist heb ik een grote interesse in wiskunde, statistiek en optimalisatie. Hierbij vind ik uiteraard moeilijke machine learning technieken als deep learning erg interessant. Een tijdje geleden volgde ik een reinforcement learning cursusje op DataChangers en ik raakte geïnspireerd. Ze kregen het namelijk voor elkaar om bots spellen te laten spelen als Mario (https://www.youtube.com/watch?v=qv6UVOQ0F44) en Go (https://www.youtube.com/watch?time_continue=129&v=tXlM99xPQC8). Hierom besloot ik om de theorie in de praktijk te brengen door zelf een botje vier-op-een-rij te leren spelen.

Hoe werkt reinforcement learning

Binnen machine learning kent men supervised- en unsupervised learning. Bij supervised learning probeert men een of meerdere variabelen te voorspellen aan de hand van andere variabelen, denk hierbij aan regressies en neural networks. Bij unsupervised learning gebruikt men algorithmes die uit zichzelf tot inzichten moeten komen, denk hierbij aan clustering. Een alternatief van deze twee is reinforcement learning. Reinforcement learning geeft een situatie (state) aan een algorithme waarna het algorithme een beslissing (actions) neemt met als doel om een bepaalde beloning (reward) te maximaliseren. Neem het voorbeeld van Mario. De situatie is de plek van onze loodgieter, de tijd die het spel bezig is en een beschrijving van de omgeving van Mario. Dit is de input van ons spel die nodig is voor elke beslissing die het algorithme neemt. De mogelijke beslissingen zijn alle moves die Mario kan doen (oftewel alle knoppen die je kan indrukken). De bot kan beslissen om naar links of rechts te gaan, te springen, te bukken en misschien zit het bloemetje wel in het spel waardoor Mario van die vuurballetjes kan schieten.

blogberendsbotje1

Op basis van de situatie zal het algorithme aan elke mogelijke move een waarde toekennen. De move met de hoogste waarde wordt uitgevoerd. Vervolgens moet aan die beslissing een beloning of straf worden toegewezen. Het doel van Mario is om een stuk naar rechts te lopen, muntjes te pakken, door een hoepel te springen en schijnbaar red je daar dan een prinses mee (unless she’s in another castle). Als het spel registreert dat Mario door de hoepel is gesprongen komt er een hoge beloning, net als dat er een beloning volgt voor elk muntje dat gepakt wordt. Als Mario dood gaat volgt er echter een harde straf waardoor het algorithme in de toekomst de gemaakte keuzes van die poging gaat vermijden.

Hoe werkt de bot

Ik heb de bot geprogrammeerd in Python en ben daarbij eerst begonnen met het programmeren van 4-op-1-rij zelf zodat twee mensen tegen elkaar konden spelen. Daarna heb ik bots geprogrammeerd die tegen elkaar kunnen spelen en zo elkaar trainen. We weten dat we drie dingen nodig hebben voor een algoritme om 4-op-1-rij te spelen: een beschrijving van de situatie, een beschrijving van de mogelijke beslissingen die genomen kunnen worden en een manier om het algoritme te belonen en te straffen.  Je hebt namelijk een bord van 7 kolommen en 6 rijen waar je gekleurde chips in kan gooien. Je maakt dus een matrix met allemaal nullen. Als speler 1 zijn chip ergens laat vallen zet je daar een 1 neer, en als speler 2 dat doet een 2. De mogelijke beslissingen zijn ook simpel: de bot moet gewoon een van de kolommen uitkiezen om zijn chip in te laten vallen. De beloningen zijn interessant. Ik geef de bot een beloning van 500 als hij wint en een beloning van -500 als hij verliest. Elke beurt berekent hij overigens of een zet leidt tot winst of dat hij kan leiden tot verlies waarna hij beloningen en straffen toewijst. Voor een gelijkspel geef ik hem 50. Daarnaast vind ik het suf als hij chips wil plaatsen in volle kolommen dus daar krijgt hij een beloning van -1000 voor. Het doel is nu dus dat de bot in elke situatie de beslissing neemt met de grootste kans op winst.

blogberendsbotje2
Mogelijkheden van het platgeslagen spelbord.
blogberendsbotje3
Bij elke situatie hoort een vector met daarin de verwachte waardes van elke zet.

De magie van reinforcement learning zit niet in complexe berekeningen, maar juist in slimme algoritmes. Er zijn verschillende manieren om het algoritme te trainen. Ik heb er voor gekozen om na de uitslag van een potje alle zetten te nemen die de bot heeft gedaan en daar dan een waardering aan te geven. Zetten vroeg in het potje vind ik minder belangrijk, dus zetten eerder in het potje krijgen een waardering dichter bij nul dan zetten die (bijna) direct tot winst/verlies leiden.   Voor de uiteindelijke waardering van zo’n zet neem ik dan het gemiddelde tussen wat ik al had en wat de nieuwe waardering zou moeten zijn. Op deze manier krijg je een evoluerende waardering die snel reageert op veranderingen in de tactiek zonder het verleden te vergeten.

Resultaten

Het is gebleken dat 4-op-1-rij een erg groot spel is voor een algorithme om te leren. Er bestaan namelijk meer dan honderd biljoen combinaties (dat zijn 14 nullen) van het speelbord terwijl het algorithme voor iedere combinatie moet leren wat het moet doen. Dit betekent dat het algorithme elke combinatie meerdere keren moet tegenkomen om fatsoenlijk te leren wat hij moet doen, en er moeten veel gegevens opgeslagen worden. Voor mijn eigen methode heb ik daarom het spel naar beneden geschaald: een speelbord van 5×6 waarbij je vier op één rij moet krijgen. Zelfs met deze verkleining is het probleem nog erg groot, wat betekent dat hij te veel situaties te weinig tegenkomt om fatsoenlijk te leren wat hij moet doen. Mensen met meer tijd en middelen lossen dit probleem op met deep learning, zo ook de schrijver van de volgende blog: https://towardsdatascience.com/deep-reinforcement-learning-and-monte-carlo-tree-search-with-connect-4-ba22a4713e7a. Ik beschrijf een situatie namelijk zoals hij is. Met deep learning kan je het spelbord generaliseren via een Convoluted Neural Network waardoor je niet van elke situatie apart bij hoeft te houden wat de bot doet. Dit scheelt ontzettend veel tijd en opslag omdat je alleen het Neural Network hoeft bij te houden. Het toepassen van Convoluted Neural Networks is echter een onderwerp voor later.

blogberendsbotje4

Geplaatst in AI

Geef een reactie

Gelieve met een van deze methodes in te loggen om je reactie te plaatsen:

WordPress.com logo

Je reageert onder je WordPress.com account. Log uit /  Bijwerken )

Google photo

Je reageert onder je Google account. Log uit /  Bijwerken )

Twitter-afbeelding

Je reageert onder je Twitter account. Log uit /  Bijwerken )

Facebook foto

Je reageert onder je Facebook account. Log uit /  Bijwerken )

Verbinden met %s