Dit is het vervolg op de blog over een brute-force AI voor Tic-Tac-Toe.
In de vorige blog ‘leerde’ de computer niets ovet het spel, maar berekende simpelweg alle mogelijk manieren waarop het spel kon verlopen en koos vervolgens de beste mogelijkheid. Wat als we de computer wél iets konden leren?
Reinforcement learning
Er zijn verschillende manieren om een computer iets te leren. Dat heet Machine Learning. Een van de mooiste manieren vind ik Reinforcement Learning. Deze manier van leren komt heel dichtbij de definitie van leren volgens Kolb:
Learning is the process whereby knowledge is created through the transformation of experience
David A. Kolb (1984).
Klinkt misschien ingewikkeld, maar je hebt dit je hele leven al gedaan.
Iedereen heeft wel eens een kind in een box zien spelen. Eerst heeft zo’n kind helemaal niet in de gaten dat hij of zij iets kan met de kleurige speeltjes boven het hoofd. Vaak start het met een onwillekeurige beweging van de arm waardoor het speeltje beweegt of zelfs geluid maakt.
Maar na een tijdje krijgt het kind het door: telkens als ik met mijn hand het speeltje aanraak, maakt het geluid! De ervaringen hebben het kind kennis opgeleverd.
Q-Learning met Cap’n Jesse
Een van de manieren om Reinforcement Learning toe te passen is volgens Q-learning. Hoe dit werkt, leg ik je uit met het volgende verhaal.
Cap’n Jesse heeft als piraat vele schatten verzameld. Eén daarvan heeft hij verborgen op Schateiland. Maar waar? Verder vermoed Cap’n Jesse dat zijn aartsvijand Blauwbaard ergens op het eiland in een hinderlaag ligt.
Het eiland (de omgeving) is ingedeeld in een aantal gebieden (toestanden). Op elk gebied kan Cap’n Jesse iets doen (acties): naar het noorden, oosten, zuiden of westen gaan. Soms levert een actie iets op (positieve beloning): de schat of een gevecht Blauwbaard (negatieve beloning).
In Q-Learning leg je per toestand de acties vast in een Q-Tabel. Cap’n Jesse stelt de tabel. Daarin legt hij de beloningen vast voor alle acties in elke toestanden. Omdat hij nog niets weet, vult hij voor elke beloning een 0 in. Cap’n Jesse besluit dat de schat +100 punten waard is en een gevecht met Blauwbaard -100 punten.
| Actie | ||||
| Toestand | ↑ | ← | ↓ | → |
| Noord-West | 0 | 0 | 0 | 0 |
| Noord | 0 | 0 | 0 | 0 |
| Noord-Oost | 0 | 0 | 0 | 0 |
| Oost | 0 | 0 | 0 | 0 |
| Midden | 0 | 0 | 0 | 0 |
| West | 0 | 0 | 0 | 0 |
| Zuid-West | 0 | 0 | 0 | 0 |
| Zuid | 0 | 0 | 0 | 0 |
Nu alle voorbereidingen zijn getrokken kan Cap’n Jesse op zoek naar de beste route naar zijn schat. Hij gaat op pad en kiest elke keer willekeurig een actie. Na elke actie update hij zijn Q-Tabel. Hier zie je zijn aantekeningen nadat hij vanaf de start tweemaal zuidwaarts en tweemaal oostwaarts is gegaan:
| Actie | ||||
| Toestand | ↑ | → | ↓ | ← |
| Noord-West | 0 | 0 | 0 | 0 |
| Noord | 0 | 0 | 0 | 0 |
| Noord-Oost | 0 | 0 | 0 | 0 |
| Oost | 0 | 0 | 0 | 0 |
| Midden | 0 | 0 | 0 | 0 |
| West | 0 | 0 | -100 | 0 |
| Zuid-West | 0 | 0 | 0 | 0 |
| Zuid | 0 | 100 | 0 | 0 |
Cap’n Jesse prijst zichzelf gelukkig dat hij de schat heeft weten te vinden, maar zijn ontmoeting met Blauwbaard was minder leuk. Hij heeft nog lang niet alle mogelijkheden gehad. Daarom begint hij opnieuw (want dat kan in dit verhaal) en gaat net zolang door totdat hij voor elke toestand alle mogelijke acties heeft uitgevoerd. Als hij klaar is, zien zijn aantekeningen er zo uit:
| Actie | ||||
| Toestand | ↑ | → | ↓ | ← |
| Noord-West | 0 | 0 | 0 | 0 |
| Noord | 0 | 0 | 0 | 0 |
| Noord-Oost | 0 | 0 | 0 | 0 |
| West | 0 | 0 | -100 | 0 |
| Midden | 0 | 0 | 0 | 0 |
| Oost | 0 | 0 | 100 | 0 |
| Zuid-West | 0 | 0 | 0 | 0 |
| Zuid | 0 | 100 | 0 | -100 |
Cap’n Jesse weet nu duidelijk meer, maar is er nog niet helemaal. Hij weet wel dat hij vanaf zijn startpositie niet naar het zuiden moet, maar naar het oosten. Maar dan?
Cap’n Jesse besluit niet langer alleen groene of rode pijlen te zetten bij een schat of gevecht (beloning), maar ook een groene wanneer hij een andere groene pijl tegenkomt. Hij maakt deze pijl van wel iets lichter groen (korting), omdat het volgen van zo’n lichtere pijl niet direct tot de schat of een gevecht leidt (beloning), maar indirect (uitgestelde beloning).
Na een tijdje zien zijn aantekeningen zien er als volgt uit:
| Actie | ||||
| Toestand | ↑ | → | ↓ | ← |
| Noord-West | 0 | 12,5 | 12,5 | 0 |
| Noord | 0 | 25 | 25 | 6,25 |
| Noord-Oost | 0 | 0 | 50 | 12,5 |
| West | 6,25 | 25 | -75 | 0 |
| Midden | 12,5 | 50 | 50 | 12,5 |
| Oost | 25 | 0 | 100 | 25 |
| Zuid-West | 12,5 | 50 | 0 | 0 |
| Zuid | 25 | 100 | 0 | -75 |
Nu weet Cap’n Jesse alles wat hij moet weten. Met ferme passen loopt hij twee keer naar het oosten en dan twee keer naar het zuiden. Hij is Blauwbaard ontlopen en heeft de schat in zijn bezit: een kist vol rum.
Cap’n Jesse neemt een paar van de heerlijke flessen rum mee terug naar zijn schip, en drinkt zoals alleen een piraat dat kan.
Je eigen schateiland
Benieuwd of dit echt werkt? Ontwerp dan hieronder je eigen eiland en laat Cap’n Jesse de beste route ontdekken.
Veel plezier, matey!
Wordt vervolgd in een volgend blog over de Pijlenrace.
Code beschikbaar op: https://github.com/gkruiger/cpnjesse
