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.

Schateiland. Linksboven: Cap’n Jesse. Linksonder: Blauwbaard. Rechtsonder: de schat.

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-West0000
Noord0000
Noord-Oost0000
Oost0000
Midden0000
West0000
Zuid-West0000
Zuid0000

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:

Acties: groen – positieve beloning (schat), rood – negatieve beloning (gevecht)
Actie
Toestand
Noord-West0000
Noord0000
Noord-Oost0000
Oost0000
Midden0000
West00-1000
Zuid-West0000
Zuid010000

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:

Alle acties met een beloning voor elke toestand
Actie
Toestand
Noord-West0000
Noord0000
Noord-Oost0000
West00-1000
Midden0000
Oost001000
Zuid-West0000
Zuid01000-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:

Voor elke toestand de actie met de hoogste beloning
Actie
Toestand
Noord-West012,512,50
Noord025256,25
Noord-Oost005012,5
West6,2525-750
Midden12,5505012,5
Oost25010025
Zuid-West12,55000
Zuid251000-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