Leren programmeren (duel)leren (deel 1)

15-05-2017 door: Daan Veraart

Leren programmeren (duel)leren (deel 1)

Nu ik inmiddels bezig ben met mijn 3de blog, is het misschien wel handig om uit te leggen wat het overkoepelende idee achter de blogs is. Trouwe lezers zullen inmiddels de gelijkenissen in de titel zijn opgevallen. Wees gerust, ik heb niet de illusie dat ik met een paar blogs van mijn lezers software developers kan maken. De titel is dan ook niet leren programmeren. Wat ik wel probeer, waarschijnlijk met afwisselend succes, is het idee van programmeren wat minder mysterieus te maken. In deel 2 van deze blog hoop ik daar nog een stapje bovenop te doen, en uit te leggen hoe kunstmatige intelligentie werkt. In een poging om dat geen saaie lap tekst te maken heb ik de hulp ingeroepen van één van mijn collega’s, Marlies. We gaan allebei een ‘kunstmatige intelligentie’ schrijven en die nemen het dan tegen elkaar op in een potje boter-kaas-en-eieren.

Voordat het echter zover is eerst deel 1: boter-kaas-en-eieren.
Voordat de bots voor deel 2 geschreven kunnen worden, is er het spel boter-kaas-en-eieren nodig waarmee de bots kunnen communiceren. Dat spel kun je hier spelen: tictactoe en als je wilt kan je de code voor het spelletje hier vinden: tictactoe.zip. Ik denk dat iedereen de regels van het spel wel kent, maar voor de vorm, en omdat het vrij simpel is, leg ik het nog een keer uit. Er zijn 2 spelers, elke speler mag om de beurt een vakje kiezen, dat is voor de rest van het spel zijn vakje. Wie het eerst 3 vakjes op een rij heeft (horizontaal, verticaal of diagonaal) wint. Zijn alle vakjes bezet en heeft geen van beide 3 op een rij, dan is het gelijkspel.

Op dit moment zijn er 6 bots die je kan kiezen: Human, RandomAI, VoorkeurAI, VoorkeurAI2, VoorkeurAI3 en MinmaxAI. Als je human kiest dan moet je zelf een vakje kiezen als je aan de beurt bent, als je een bot kies doet die een zet. Voordat ik omschrijf wat de bots doen en hoe ‘goed’ ze zijn is het het leukst als je zelf het spelletje speelt tegen de verschillende bots en kijkt of je de tactiek die ze gebruiken kan ontdekken, en welke vervolgens het succesvolst is. Ik wacht wel even.




Klaar? Ok, mijn verwachting is dat je van de RandomAI sowieso hebt kunnen winnen maar niet van MinmaxAI. Ik zal kort toelichten hoe de verschillende bots werken.

RandomAI
RandomAI is de simpelste van de bots, de bot krijgt het huidige speelbord binnen, kijkt welke vlakjes beschikbaar zijn en kiest er daarvan willekeurig eentje. Tegen de random bot is het makkelijk om expres te verliezen of te winnen, maar verdacht lastig om gelijk te spelen, terwijl als je een beetje goed bent in het spelletje dat tegen een menselijke tegenstander eigenlijk altijd de uitslag is.

VoorkeurAI
VoorkeurAI is niet veel complexer dan RandomAI, deze bot heeft een vaste voorkeur voor welke vakjes hij wil hebben. Hij gaat deze voorkeur af en zodra er eentje beschikbaar is, claimt hij die.
Zijn voorkeur is als volgt:

Voor een simpele tactiek is dit helemaal nog niet zo slecht en je zal zien als je RandomAI tegen VoorkeurAI laat spelen dat VoorkeurAI meestal wint. Zelf zul je, als je dit weet echter makkelijk kunnen winnen, je kunt immers altijd de onderste rij (in de afbeelding dus 3,5,8) kiezen en winnen.

VoorkeurAI2
VoorkeurAI2 is al iets beter dan de andere 2 bots, hij heeft namelijk een win/verlies algoritme, als hij het spelletje kan winnen door een vlakje te kiezen, kiest hij deze. Zo niet, dan kijkt hij of de tegenstander kan winnen door een vlakje te kiezen, en zo ja dan kiest hij deze. Zo niet, dan valt hij terug op de tactiek van zijn kleine broertje en kiest hij de eerste lege op basis van dezelfde voorkeursvolgorde. Deze wint alles van VoorkeurAI en doet het een stuk beter tegen RandomAI. Je zult zien dat je ook van deze bot nog wel kunt winnen, maar je moet wel van te voren een goede tactiek bedenken!

VoorkeurAI3
VoorkeurAI3 is een beetje een instinker, als je er tegen gespeeld hebt, zal je waarschijnlijk het gevoel hebben dat hij iets beter is dan 2, ook al weet je niet precies waarom. In werkelijkheid is deze bot hetzelfde als VoorkeurAI2, met als enige verandering dat met een trucje hij er iets langer over doet om een oplossing uit de voorkeursvolgorde te halen.
Hier ga ik straks op verder, maar eerst laat ik Marlies de werking van de volgende bot uitleggen, die heeft zij namelijk gemaakt. Deze bot is de reden waarom we eigenlijk voor dit spelletje geen kunstmatige intelligentie nodig hebben. Er is namelijk een beter manier: Het minmax-algoritme.

MinmaxAI
De MinmaxAI bot gebruikt het minmax-algortime. Om dit algoritme te kunnen gebruiken, is er een aantal eigenschappen die een spelletje moet hebben. De eerste is dat jij wilt winnen, maar waarom speel je anders ook een spelletje, en dat je tegenstander ook wilt winnen, maar waarom speelt hij anders ook een spelletje, en dat de winst van de één betekent dat de ander verliest. Daarnaast is het nodig om ieder mogelijk vervolg van het spelletje te kunnen bepalen (dat is bij dit spel vrij makkelijk omdat het er niet veel zijn, alleen de eerste zet kost even wat tijd om uit te rekenen), en is het nodig om een waarde te kunnen hangen aan het einde van het spelletje.

Op het moment dat hij een zet moet doen, bedenkt het minmax-algoritme voor iedere mogelijke zet wat hiervan het gevolg is voor het vervolg van het spelletje. Op basis van dit vervolg, heeft een zet een bepaalde waarde. Zo heeft winst een waarde van +10, verlies een waarde van -10, en gelijkspel een waarde van 0. Daar waar jij probeert om deze waarde zo hoog mogelijk te maken, of dus te maximaliseren, probeert jouw tegenstander juist het omgekeerde te doen; oftewel te minimaliseren.

Op deze manier kan je ook voor een zet die er niet voor zorgt dat het spelletje is afgelopen een waarde bepalen. Als het spelletje nog niet is afgelopen, kan je namelijk beredeneren wat de tegenstander zal gaan doen, namelijk proberen om op een uitkomst met een zo laag mogelijke waarde uit te komen. Als hij echter het spelletje ook niet afmaakt, is het weer jouw beurt, en probeer jij juist weer op een zo hoog mogelijke waarde uit te komen. Als jij dan het spelletje niet afmaakt … enfin, je begrijpt het idee.

Echter missen we nu nog een essentieel onderdeel. Op dit moment heeft het winnen in de volgende zet dezelfde waarde als het winnen in een zet over vier beurten, namelijk +10. Daarnaast is de volgende beurt verliezen evenveel, of eigenlijk even weinig, waard als verliezen over vier beurten, namelijk -10. Tijd voor een voorbeeldje, als jij al twee vakjes op een rij hebt, is het niet zo handig om niet het derde vakje erbij te kiezen. Dat derde vakje kiezen, moet dus eigenlijk een hogere waarde hebben dan niet dat derde vakje kiezen. Ander voorbeeldje, als de tegenstander vakjes op een rij heeft, is het niet zo handig als je niet zelf het derde vakje kiest, anders wint hij namelijk zodra hij aan zet is. Oftewel, wel dat derde vakje kiezen moet een hogere, of minder lage, waarde hebben dan niet dat derde vakje kiezen.

Om hier rekening mee te houden, wordt de waarde van de uitkomst niet alleen bepaald door de uitkomst zelf, maar ook door het aantal beurten dat het nog kost om tot deze uitkomst te komen. Winnen in de volgende beurt krijgt dus een waarde van +10, terwijl winnen over vier beurten de waarde van +10 – 4 krijgt. Het omgekeerde is het geval voor verliezen. De volgende beurt verliezen is -10 punten, en pas over vier beurten verliezen heeft een waarde van -10 + 4. Hierdoor zal het algoritme winnen wanneer dat kan, en zorgen dat het niet de volgende beurt verliest.

Dankje Marlies voor deze heldere uitleg.
Deze tactiek maakt het minmax-algoritme onverslaanbaar. Immers hij berekent alle mogelijkheden, gaat uit van het scenario dat zijn tegenstander net zo goed is als hij en kiest dan de beste zet. Hoewel we hier een algoritme hebben dat altijd de beste zet doet, zal er niet zo snel iemand zijn die het kwalificeert als een intelligent algoritme. Maar als het maken van de slimste beslissing geen intelligentie is, wat dan wel?

Groot voordeel, daarover is geen algemene consensus, dus je mag zelf kiezen wat je intelligent noemt en als iemand het daar niet mee eens is, komt dat omdat hij/zij zelf niet intelligent genoeg is. Ik hoop dat je tegen voorkeurAI2 en 3 hebt gespeeld, en mijn voorspelling dat je het gevoel had dat 3 slimmer aanvoelde dan 2 uit is gekomen. Het illustreert namelijk iets mafs. Hoewel het niet zo is, lijkt de ene bot slimmer dan de andere. Dat kan door twee dingen komen:

1. De naam: Omdat voorkeurAI2 duidelijk slimmer is dan 1, zal 3 nog wel weer beter zijn. Dit is een hele menselijke vergissing waar veel reclamemakers graag gebruik van maken. Dit is ook de reden waarom we over een paar jaar scheermesjes hebben met acht mesjes, met namen als elemental fusion power daimond stealh razor deluxe hybrid. Want stom genoeg werkt het.

2. Het algoritme doet er langer over om een ‘moeilijke’ beslissing te nemen. Dit is iets wat je ziet gebeuren en je maakt een aanname waarom dat zo is: Het algoritme moet langer nadenken/rekenen over de keuze. Dat is echter niet zo, wat er in werkelijkheid gebeurt is dat het algoritme een willekeurig getal neemt tussen de 0 en 1, en als dat groter is dan 0,05 slaat hij een cyclus over. Het spelletje werkt met ongeveer 60 cycli per minuut, en dus duurt het even voordat hij daadwerkelijk zijn zet kiest.

Door ‘na te denken’ over de zet lijkt het algoritme menselijker, en wordt daarom sneller gezien als intelligent. In 1950 bedacht briljant wiskundige Alan Turing de Turing test. De Turing test werkt grofweg als volgt: Twee mensen voegen je toe op WhatsApp, geen van beide wil (video)bellen en je mag met beide 10 minuten appen. Na die 10 minuten moet je zeggen welk van deze 2 mensen ook echt een mens is en welke stiekem een computer. Als maar genoeg mensen het verschil niet kunnen onderscheiden tussen de mens en de computer dan is de computer intelligent.

Dat blijkt nog helemaal niet zo makkelijk, want als je iemand vraagt wat 23598 keer 123987 is en hij/zij komt direct met het goede antwoord, dan gaat al snel het vermoeden dat hij te goed kan rekenen en dus een computer is. Dus worden de bots trucjes aangeleerd, ze doen langer over rekensommen en maken bewust fouten. Maar dan ben je er nog lang niet, we zijn als mensen misschien niet zo goed in hoofdrekenen, het voeren van een conversatie kunnen we over het algemeen wel een stuk beter dan een computer. Er zijn veel projecten die deze uitdaging aangaan een voorbeeld is www.cleverbot.com. Chatten met cleverbot voelt als een discussie met mijn bijna 3-jarige nichtje, die als je vraagt of ze 2 handen heeft, heel stellig zegt: “Nee 3!”, terwijl ze evenveel vingers ophoudt als ze zondag jaren oud wordt. Nou klinkt dat niet zo bijzonder, maar dat betekent dat, volgens Turings redenatie, cleverbot de intelligentie heeft van een bijna 3-jarig meisje.

De Turing test wordt door veel mensen nog steeds gezien als de graadmeter voor intelligentie, maar hoewel we dat nog niet gehaald hebben vinden veel mensen het het doorstaan van de Turing niet genoeg om iets intelligent te noemen. Die vinden dat een intelligentie zou moeten kunnen functioneren in de echte wereld.
Nou wil ik niet voor Marlies praten, maar dat gaat mij wat te ver voor een blog. Wat wij gaan doen is een kleine doch zeer belangrijke subset van intelligentie, leren. We gaan allebei een algoritme schrijven dat na het spelen van potjes steeds beter wordt. Idealiter begint de bot zo goed als RandomAI en eindigt hij zo goed als MinmaxAI. Ik weet niet hoe het met jou zit Marlies, maar ik vrees dat ik hem niet zo goed ga krijgen als MinmaxAI, aan de andere kant verwacht ik wel dat hij kan winnen van mijn nichtje, ook al is ze inmiddels 3 als het algoritme af is. Kan het algoritme daarom beter leren dan mijn nichtje? Of beter nog, is het intelligent? Dat mag je zelf beslissen. Ik ben allang blij als het niet genadeloos verslagen wordt door dat van Marlies.

Wil je zelf ook een bot maken? In de zip-file staat een dummyAI, die doet nu nog helemaal niets, maar als je dummyAI.js aanpast kan je hem wel alles laten doen wat je wilt! Dus mocht je na het vorige blog de smaak van het programmeren te pakken hebben, maak van het duel een 3-strijd, laat je met de andere bots als voorbeeld inspireren en maak je eigen bot. Dan kan je in het volgend blog kijken hoe die zich verhoudt tegen die van ons! Mocht je een bot maken, zou ik het superleuk vinden als je je oplossing mailt. Het meest leer je immers van elkaar.

Rest me nog de competitie heel veel succes te wensen. Marlies, je hebt tot het volgende blog, succes, je tijd gaat nú in!

Volg ons op

© Orcado B.V. | 1999 - 2017