21-06-2017 door: Daan Veraart
Mensen neigen nog vaak het idee te hebben dat de generatie die na hun komt, minder is dan hun eigen generatie. Misschien is dat toevallig voor jouw generatie wel waar, maar over het algemeen wordt de mensheid gemiddeld met de generaties, slimmer, sterker, sneller en ouder. Tenminste dat lijkt toch redelijk evident als je naar bijvoorbeeld wereldrecords kijkt, of naar het feit dat ik voor dit blog een computer zelf heb laten leren om boter-kaas-en-eieren te spelen, dat was een paar generaties geleden toch ondenkbaar. Dat de volgende generatie beter presteert dan de vorige is ook meteen hoe ik dat heb gedaan. In deel 2 van leren duelleren ga ik het hebben over een genetisch algoritme. De nieuwe bots kun je vinden op de volgende link: http://undercover.horse/tictactwo/
Maar eerst even een stukje administratie. Uit de reacties op mijn vorige blog begreep ik dat velen van jullie dachten dat Marlies deel 2 zou schrijven. Zoals jullie nu merken is dat niet het geval. Het oorspronkelijke plan was dat ik in dit deel iets meer uitleg zou geven over mijn algoritme, Marlies over haar algoritme, en dat ik dat dan aan elkaar zou knippen en plakken met hier en daar een stukje begeleidende tekst. De planning heeft alleen wat last gehad van mooi weer, vakantie en sociale verplichtingen, die niet in alle gevallen verplicht waren. Hierdoor is Marlies’ algoritme achterin de queue gekomen (dat is een briljant woordgrapje, maar je zult hem pas na Marlies’ blog snappen, maar geloof me, briljant). Dat betekent dat als je hier was voor het stukje van Marlies, dat ik je helaas danig (kijk ook een briljant woordgrapje, maar hier is dan weer geen voorkennis voor nodig) teleur moet stellen. Marlies schrijft deel 3, en dan zullen we dus de algoritmes op elkaar los laten, maar vandaag dus eerst deel 2: Survival of the fittest: kunstmatige selectie en intelligentie.
Charles Darwin, bij sommige misschien wel bekend, onderscheidt in zijn boek ‘on the Origin of Species’ (1859) twee soorten selectie die de evolutie aandrijven. Natuurlijke selectie, zoals het in de natuur gaat, en kunstmatige selectie zoals de mens dat doet bij bijvoorbeeld dure hondenrassen. Beide staven ze echter op dezelfde genetische principes. De ‘beste stukjes’ blijven over, en de ‘slechtste stukjes’ genetisch materiaal sterft langzaam af. Wat iets een goed stukje maakt is zeker in de biologie nogal een rekbaar begrip, maar heel kort door de bocht is dat hoe het werkt.
Dat idee wordt in de kunstmatige intelligentie geïmplementeerd middels een genetisch algoritme. Een genetisch algoritme werkt volgens volgend principe:
– Je begint met een zwik ‘bots’ met verschillende eigenschappen
– Je laat de bots los in de wereld waarin ze moeten overleven
– Je geeft de bots een score (de zogenaamde fitness score) aan de hand van hoe goed ze het doen
– Je laat de bots met een lage fitness score uitsterven, en die met een hoge fitness score laat je zichzelf voorplanten
– Bij het voortplanten laat je de bots muteren
– Zodra de huidige generatie voldoet aan je eisen stop je met het proces en de bots die je dan overhebt hebben de ‘juiste’ waardes.
Dat principe werkt niet helemaal geweldig met mijn boter-kaas-en-eieren spelletje, maar omdat volgens mij een genetisch algoritme een stuk makkelijk uit te leggen is dan bijvoorbeeld een neuraal netwerk, heb ik wat dichterlijke vrijheid toegepast en ga ik jullie laten zien hoe dat werkt.
Eerst kies ik een zwik aan mogelijke spel verlopen. Een mogelijk spelverloop is bijvoorbeeld [4, 8, 0, 6, 7, 2, 1, 3, 5]. In dit spelverloop kiest speler 1 als eerst vakje 4, vervolgens kiest speler 2 vakje 8, dan speler 1 vakje 0, etc. De volgende afbeelding laat zien welk vakje welke is:
Boter-kaas-en-eieren experts zullen direct gezien hebben dat nadat speler 1 vakje 1 heeft gekozen hij 3 op een rij heeft (1,4,7) en dat de opties die daarna komen dus helemaal niet meer kunnen. Maar onze kunstmatige intelligentie is geen boter-kaas-en-eieren expert, sterker nog, hij kent de spelregels niet, zover hij ‘weet’ is dit een geldig spelverloop. De manier waarop ik de begin set maak is al volgt: Ik bereken alle mogelijkheden waarin de getallen 0 tot en met 8 in een volgorde kunnen staan (dat zijn er 362880) en dan geef ik elke combinatie een kans van 30 procent om in de begin set te komen. Vervolgens kopieer ik die set zodat ik 2 sets van ongeveer 100.000 spelverlopen heb. Eentje voor wanneer de AI begint, en eentje voor wanneer de tegenstander begint. Dit alles gebeurt voordat er een zet is gedaan, dus mogelijk dat je computer even bezig is als je een geneticAI speler kiest.
Vervolgens kijk ik naar het huidige spelverloop. Maak ik een verzameling van alle spelverlopen die voldoen aan het huidige spelverloop, en kies een willekeurige bot uit. Ik neem de volgende zet uit dat spelverloop en kies die. Als voorbeeld stel we zitten in het begin van het spel en de tegenstander heeft vakje 2 gekozen. Dan kijk ik in mijn verzameling met spelverlopen waar de tegenstander begint en daar zie ik 3 spelverlopen die beginnen met een 2:
[2, 8, 0, 6, 7, 4, 1, 3, 5] en [2, 4, 8, 0, 6, 7, 1, 3, 5] en [2, 8, 6, 0, 7, 4, 1, 3, 5]
Daar kies ik er willekeurig eentje van, bijvoorbeeld de eerste, de zet die ik dan ga zetten is de 8. De tegenstander is dan weer en kiest de 6. Ik ga opnieuw kijken welke spelverlopen ik nog heb. Het spel verloop is nu [2, 8, 6] waar ik net spelverloop 1 had gekozen kan dit nu niet meer, alleen spelverloop 3 is nu nog geldig, dus kies ik die, en zet ik de 0.
Dat proces herhaal ik tot dat het spelletje me vertelt dat het spel voorbij is. Zodra het spel afgelopen is, geef ik het huidige spelverloop een fitness waarde. 1 als ik heb gewonnen, 0 als ik gelijk heb gespeeld, en -1 als ik heb verloren.
Zo speel ik een aantal spelletjes, tot dat ik er een X-aantal heb gespeeld. Nu is het tijd voor een nieuwe generatie. Omdat er ik een heleboel spelverlopen nog niet heb gespeeld en die dus nog geen fitness score hebben laat ik die ongemoeid. Ik kijk alleen maar naar de spelverlopen met een negatieve fitness score, en ik wissel de laatste zet die ik heb gemaakt om met een willekeurige andere zet. Op basis van deze mutaties heb ik een nieuwe generatie. Dit blijf ik herhalen tot er geen spelverlopen meer zijn met een negatieve fitness waarde.
Iedereen die al naar de nieuwe bots heeft gekeken zal zijn opgevallen dat er 2 versies zijn. GeneticAI1 en geneticAI2, het verschil zit hem in hoe de mutatie werkt. In versie 1 wordt de zet verwisseld met een willekeurig andere zet. In versie 2 wordt er een lijst bijgehouden van spelverlopen met een positieve fitness score. Bij de mutatie wordt het spelverloop dat gemuteerd wordt vergeleken met een spelverloop met een positieve fitness code en wordt er alleen verwisseld met een zet die niet in het spelverloop met de positieve fitness score zit. Voorbeeldje? Voorbeeldje: Spelverloop waarbij de AI begint dat gemuteerd moet worden is: [4, 8, 0, 5, 6, 2, 1, 3, 7], spelverloop met een positieve fitness score: [4, 8, 0, 5, 2, 6, 1, 7, 3]. Het spelverloop heeft verloren na zet 6, zet 6 moet dus verwisseld worden met een andere zet. In versie 1 had dat elke zet kunnen zijn, en had je dus bijvoorbeeld spelverloop [6, 8, 0, 5, 4, 2, 1, 3, 7] kunnen krijgen. In versie 2 mag dat niet omdat de 4 in het winnende spelverloop op dezelfde plek zit, er mag daar alleen met de 2, 7 of de 3 gewisseld worden.
Nu hoor ik sommige van jullie denken: “Ik vraag me af hoe dat er in code uit ziet”, sommige andere hoor ik denken: “Dit is me al vaag en ingewikkeld genoeg, ik hoop niet dat hij ook nog code laat zien”, weer sommige andere: “Hmm ik heb honger, ik vraag me af of er nog iets lekkers in de kast ligt” en één iemand: ”Jemig wat een verhaal, moet ik ook zo’n enorm verhaal aan elkaar ratelen?“. Voor groep 4 heb ik een geruststellende mededeling: Nee Marlies, natuurlijk niet. Aan groep 3 zou ik adviseren gewoon even in de kast te kijken, het geheel is al complex genoeg voor op een volle maag, op een lege maag zou ik het iedereen afraden. Voor groep 2, geen zorgen als ik de code ga bespreken zitten we hier morgen nog. Voor groep 1 heb ik dan nog wel een klein beetje goed nieuws, je kunt de code zelf bekijken op respectievelijk http://undercover.horse/tictactwo/geneticAI.js en http://undercover.horse/tictactwo/geneticAI2.js en in versie zit nog wat extra commentaar zodat het hopelijk redelijk te volgen is. Ook zie je dan nog dat er een truc in zit voor als een spelverloop niet bestaat. Mocht je nou desondanks nog vragen, suggesties of opmerkingen er over hebben, mail me gerust.
Leuk zo’n kunstmatige intelligentie, maar werkt het überhaupt wel, en wat heb je er eigenlijk aan? Goede vragen, al zeg ik het en stel ik ze zelf. Nou heb ik het algoritme tijdens het schrijven van dit blog laten spelen tegen voorkeur2 en de voortgang een beetje bijgehouden, en dat ziet er als volgt uit:
In het begin werden de meeste spelletjes verloren. Tegenover 50 verloren spelletjes stond 1 gewonnen spel en 10 gelijkspellen. Dat was te verwachten, het is een lerend algoritme, en leren kost tijd. Dat zie je ook mooi terug in de verdere verloop van de spellen, vooral in het aantal gelijkspellen. Voor wie het zich niet meer uit het vorige blog kan herinneren, voorkeurAI2 gebruikt altijd dezelfde volgorde van zetten, maar als hij een kans ziet om te winnen of een verlies te voorkomen doet hij dat. Het is voor het algoritme dus makkelijker om gelijk te spelen, en daar wordt hij ook niet voor bestraft, immers alleen spelverlopen met een negatieve fitness score worden gemuteerd. Maar het algoritme gaat ook steeds meer winnen, eerst was het tegenover 50 verloren spellen 1, op het laatst is het tegenover 7 verloren spellen 1. En uiteindelijk zal het algoritme vaker winnen dan verliezen
Het algoritme werkt dus, het leert, maar wat heeft dat voor zin? Zoals ik in het vorige blog al zei, voor dit specifieke voorbeeld niet zo veel. Het MiniMax-algoritme is snel genoeg om alle mogelijke zetten te voorzien en geeft dus altijd de beste zet terug. Toch wint het nooit van voorkeurAI2 omdat het ervan uitgaat dat voorkeurAI2 de best mogelijk zet gaat doen, terwijl deze dat niet altijd doet. Echter verliest MiniMax nooit, wat een duidelijk voordeel heeft. Maar ondanks dat het in dit voorbeeld niet heel zinvol is kan je er wel iets leuks aan zien. Ik heb het algoritme niks uitgelegd van de spelregels. Het enige wat het van tevoren ‘weet’ is dat je alleen maar een leeg vakje mag kiezen. Vervolgens vertel ik het zodra hij verloren, gewonnen of gelijk gespeeld heeft, maar meer niet. Maar het MiniMax-algoritme moest weten wat de waarde van een zet was, en dus moest weten wanneer er gewonnen zou worden, kent hij impliciet de spelregels. Ook voorkeurAI2 weet dat hij drie op een rij moet krijgen en zijn tegenstander niet. Je kunt een genetisch algoritme dan ook uitstekend gebruiken als je zelf het antwoord niet, of niet precies weet.
Dat is de grote kracht van kunstmatige intelligentie, het kan dingen leren die je zelf niet weet. Hoewel we nog niet bang hoeven te zijn voor filmscenario’s als Skynet uit Terminator of WarGames (Shall we play a game?), omdat kunstmatige intelligenties heel erg specifiek één ding leren, worden ze wel heel goed in dat ene specifieke ding. Er is daarom niemand meer die kan winnen van de beste kunstmatige intelligenties met schaken, jeopardy en sinds kort ook GO. Maar al die rekenkracht kan je natuurlijk ook voor praktischere dingen inzetten. Zo gaat er een bekende anekdote dat de Amerikaanse supermarktketen Target alle verkopen van klanten bij hield en een algoritme uit al die data vast liet stellen of de klant zwanger was of niet, en ze op basis daarvan kortingsbonnen stuurde voor baby artikelen. Op het laatst was het algoritme zo goed dat het in sommige gevallen eerder wist dat een vrouw zwanger was dan de vrouw zelf. Helaas blijkt deze anekdote niet waar, het algoritme is opgesteld door een statisticus en was niet zelflerend, en er gaan nog wel geruchten dat vaders er door Target coupons achter kwamen dat hun dochter zwanger was, maar in hoeverre dat waar is, is ook nog maar de vraag. Maar dit is wel iets dat prima met een KI-algoritme gedaan had kunnen worden.
Je zult steeds meer te maken krijgen met kunstmatige intelligenties, zelfs als je het zelf niet door hebt. Bijvoorbeeld de video’s die YouTube je aanraadt om te kijken, daarvan weten de mensen bij YouTube zelf niet op basis waarop dat gebeurt, dat zit allemaal verwerkt in een kunstmatig intelligent algoritme. Dat klinkt heel spannend, maar ik hoop dat ik met dit blog heb laten zien, dat het allemaal geen magie is. Tenminste volgens mij is het geen magie, ik weet natuurlijk niet wat mijn tegenstander in de strijd gaat gooien. Marlies?