Dit is het vervolg op de blog over reinforcement learning met C’pn Jesse.

In het vorige blog legde ik Reinforcement Learning volgens het Q-learning algoritme uit met een eenvoudig voorbeeld. Maar wat als we het nu eens een stukje ingewikkelder maken?

Hiervoor kijken we naar een zogenaamde ‘pijlenrace’. Het enige wat je nodig hebt is ruitjespapier en een pen. Je tekent een racebaan op het papier en je kunt los (of je doet het natuurlijk lekker online)!

Bron

Racen gaat in de volgende stappen:

  1. Verleng in gedachten de pijl met dezelfde lengte en richting als de vorige stap.
  2. Kies vervolgens of je nog wilt bijsturen naar een van de acht omliggende kruisingen.
  3. Verleng de pijl en check:
    • Gefinished? Goed gedaan, gewonnen!
    • Gechrashed? Helaas, je hebt verloren…
    • Nog altijd op de baan? Ga terug naar stap 1

Een voorbeeld:

De eerste 3 beurten van speler blauw

Q-learning bij de pijlenrace

Net als bij C’pn Jack voorzien we het Q-learning algoritme van een aantal definities:

  • Toestand: X-coördinaat + Y coördinaat + X-snelheid + Y-snelheid.
  • Acties: Elke beurt heeft de speler de keuze uit 9 acties (de groene bolletjes): linksboven, midden boven, rechtsboven, links van het midden, etc.
  • Beloningen: +1000 voor een finish, -1000 voor een crash.

En natuurlijk een baan om op te racen:

De ruitjes zijn 40 pixels groot

Elke poging begint bij de finish en eindt bij een crash of finish. Ik laat het algoritme 1000 pogingen lopen om te kijken hoe goed deze werkt. Helaas komt het algoritme niet veel verder dan dit soort kunstwerken:

Na 1000 pogingen, is dit de beste route…

Wat blijkt? Het enige wat het algoritme hier leert, is om op de baan te blijven. Wat het algoritme moet leren – de kortste weg naar de finish – lukt niet.

Beloningen 2.0

Ik voeg daarom twee beloningen toe:

  • -1000 voor een ‘verkeerde’ finish (bij de start eerst naar links en dan naar rechts).
  • +10 voor elke coördinaat dichterbij de finish. Dit is een zogenaamde tussentijdse beloning.

Met deze toegevoegde beloningen, lukt het wel:

Na 16.143 pogingen, met toegevoegde beloningen.

Tijd om het algoritme het vuur aan de schenen te leggen. Moeilijker maken is makkelijk, ik maak gewoon de ruitjes steeds kleiner:

Ruitjes zijn 20 pixels groot. Resultaat na 98.954 pogingen.
Ruitjes zijn 10 pixels groot. Resultaat na 352.262 pogingen.
Ruitjes zijn 5 pixels groot. Resultaat na 1.681.212 pogingen.

Telkens weer weet het algoritme de snelste weg naar de finish te vinden.

Tijd is geld

Het vinden van deze snelste weg, kost alleen wel steeds meer tijd. Kijk maar eens naar de volgende tabel:

Breedte cel (pixels)4020105
Aantal pogingen16.14398.954352.2621.681.212
Benodigde tijd364 ms2.583 ms33 sec8,5 min
Groote Q-tabel (rijen)3552.58117.697106.136

Wanneer het aantal verschillende toestanden toeneemt, blijven de resultaten dus nog steeds goed, maar wordt het algoritme als snel onbruikbaar vanwege de benodigde rekentijd.

Bovendien werkt de beste oplossing alleen voor deze baan en niet voor andere banen.

Tijd om iets anders te proberen. Tijd voor Driving Dave. Meer over Dave in het volgende blog.

Je eigen racebaan

Benieuwd wat het algoritme kan? Ontwerp je eigen racebaan en ontdek het zelf!

Eigen baan: Grootte ruitjes:

Wanneer je een eigen baan uploadt, denk dan aan het volgende: Zorg dat deze 700 pixels breed en 400 pixels hoog is. Gebruik puur wit (#ffffff) voor de baan, puur zwart (#000000) voor de rand en puur rood (#ff0000) voor de start/finish. Maak van de start/finish een verticale lijn. Zorg er wel voor dat er een weg van start naar finish mogelijk is :).

Veel plezier!

Code beschikbaar op: https://github.com/gkruiger/arrowrace