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)!
Racen gaat in de volgende stappen:
- Verleng in gedachten de pijl met dezelfde lengte en richting als de vorige stap.
- Kies vervolgens of je nog wilt bijsturen naar een van de acht omliggende kruisingen.
- 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:
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:
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:
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:
Tijd om het algoritme het vuur aan de schenen te leggen. Moeilijker maken is makkelijk, ik maak gewoon de ruitjes steeds kleiner:
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) | 40 | 20 | 10 | 5 |
| Aantal pogingen | 16.143 | 98.954 | 352.262 | 1.681.212 |
| Benodigde tijd | 364 ms | 2.583 ms | 33 sec | 8,5 min |
| Groote Q-tabel (rijen) | 355 | 2.581 | 17.697 | 106.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!
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
