Een computer een puzzel laten oplossen heeft iets fascinerends. Kan ik ook niets aan doen. Kan ik wel iets méé doen.
Een van de kleinste puzzels die ik ken is boter-kaas-en-eieren (noemden wij vroeger precies wat het is, namelijk: kruisje-nul, ik bedoel: wat hebben boter, kaas en eieren nu met dit spel te maken? Maar goed, dat geheel terzijde). Of in het Engels: Tic-Tac-Toe. Het zou toch leuk zijn om hiervoor een AI te maken, nietwaar?
Baseline
Eerst maar eens een baseline trekken. Want wat zijn nu eigenlijk de kansen voor beide spelers, als beide spelers zo maar wat doen?
| Stand einde spel | Kans |
| X wint | 61% |
| O wint | 26% |
| Gelijkspel | 13% |
X begint en dat heeft een duidelijk voordeel. Vanwege de willekeur aan zetten kan O toch nog in meer dan een 1/4 van de gevallen winnen.
Een AI zou beter moeten kunnen scoren dat dit. Een meest ‘domme’ vorm van AI is ‘brute force‘: het simpelweg doorrekenen van alle mogelijkheden en dan van al die mogelijkheden de beste pakken. Dit doorrekenen kost wel tijd, maar dit is typisch iets wat een computer snel kan. Tenminste, als het aantal mogelijkheden binnen de perken blijft.
| Aantal plaatsen op het bord | 9 |
| Mogelijkheden per plaats op het bord (X, O of leeg) | 3 |
| Totaal aantal mogelijkheden | 3^9 = 19.683 |
Theoretisch zijn er een krappe 20.000 mogelijkheden. Theoretisch, want hier zitten ook ‘illegale’ spelsituaties bij, waarin er na winst van X of O toch nog is doorgespeeld. In de praktijk slechts 5478 spelsituaties mogelijk. Dit is voor een mens niet te doen, maar voor een computer geen probleem. Maar hoe moet de computer nu bepalen van al die mogelijkheden wat de beste zet is? Wat wat is eigenlijk een goede zet?
Intelligent Force
Een handig algoritme om de beste zet te bepalen, is het Minimax algoritme. Volgens dat algoritme doet de elke speler zijn best om met elke zet de kans op de beste uitkomst voor zichzelf zo hoog mogelijk te houden, terwijl de kans op de beste uitkomst voor de ander zo laag mogelijk wordt gehouden.
Als je Tic-Tic-Toe perfect speelt, kunt je niet verliezen. Als twee spelers Tic-Tac-Toe perfect spelen, kunnen ze beiden niet verliezen, dus zal elk spel eindigen in gelijkspel. En jawel, een simulatie van 1000 spellen met verschillende speelwijzen bevestigt dit:
| Speelwijze X | X wint | gelijkspel | O wint | Speelwijze O |
| Minimax | 0% | 100% | 0% | Minimax |
| Minimax | >99% | 0% | <1% | Willekeurig |
| Willekeurig | 0% | 19% | 81% | Minimax |
| Willekeurig | 58% | 13% | 28% | Willekeurig |
Het Minimax algoritme programmeren in Javascript voor Tic-Tac-Toe was leuk, maar hier zelf tegen spelen is natuurlijk niets aan: je kunt simpelweg niet winnen. Niet overtuigd? Probeer het zelf:
Het heeft iets ‘oneerlijks’ om tegen aan AI te spelen die in minder dan een seconde alle 5478 spelsituaties doorrekent, nietwaar? Tijd voor een AI die meer ‘menselijk’ is. Tijd voor een AI die we wat kunnen leren.
Wordt vervolgd in een volgend blog over C’pn Jesse.
Code beschikbaar op: https://github.com/gkruiger/tictactoe
