AI

Boter-Kaas-Eieren met AI-‘light’

Het is een bekend en ogenschijnlijk eenvoudig spelletje, maar hoe verhoog je de kans op winst? En wat als de computer je daarbij zou kunnen helpen? Bijvoorbeeld door een algoritme te gebruiken dat leert van eerdere zetten, een milde vorm van Artificial Intelligence; AI-‘light’.

Deze ZIP file bevat zo’n implementatie. In Python 2.7 geschreven, eenvoudig van opzet en met aansturing via een standaard cmd-line interface. Voor het opstarten type: ‘python bke.py <CR>’;

  • Het BKE speelbord wordt weergegeven als een 3×3 blok van cijfers (0…2, 3…5, 6…8) voor de lege plekken, en letters om de bezette posities van de speler (‘U’) en van de computer (‘C’) aan te duiden.
  • Een cmd-line interface om Uw volgende zet op te vragen.
  • Na elke zet wordt wat statische informatie weergeven.

Zodra U Uw zet heeft ingegeven gaat de computer aan de slag voor het bedenken van een tegenzet; beoordelen…

  1. of er een zet mogelijk is waarmee het spel direct gewonnen wordt -> low-hanging-fruit
  2. of er een zet mogelijk is waarmee het spel bij de volgende zet van de tegenstander verloren wordt -> damage control
  3. wat de meest kansrijke vervolgzet is door te leren van eerdere spelbeurten -> AI-‘light’

Tijdens elke speelronde wordt een ASCII string opgebouwd met daarin de achtereenvolgende zetten. Na elke speelronde wordt deze reeks afgesloten met de eindscore en wordt de reeks toegevoegd aan een lijst met de uitslagen van vorige speelrondes. Ter illustratie: [“U0-C1-U4-C8-U3-C5-U6-U”, “U1-C7-U4-C5-U0-C2-U8-U”]. In de eerste speelronde deed de speler de 1e zet op positie ‘0’, de computer deed de 2e zet op positie ‘1’, daarna weer de speler op positie ‘4’, etc. In eerste instantie kan de speler nog makkelijk winnen. Maar na elke ronde wordt de computer slimmer door de eerdere beurten te analyseren.

Na elke zet wordt gekeken of deze reeks van zetten al eens eerder uitgespeeld is, wat zoal de vervolgzetten na de huidige zet waren en wat daarvan de einduitkomsten waren. Uiteraard worden ook rotatie- en spiegelsymetrie in de analyse meegenomen. Kansrijke zetten worden bevoordeeld en kansarme zetten worden benadeeld. Uit alle mogelijkheden wordt de meest kansrijke zet gekozen. Uiteindelijk leert de computer hiermee zoveel mogelijk partijen te winnen, of op zijn om minst gelijkspel te halen.

Als er een reeks gespeeld wordt die nog niet eerder is voorgekomen, dan kiest de computer (nu nog) een random vervolgzet. Hier zit nog ruimte voor verbetering, bijvoorbeeld door te onderzoeken of er een zet mogelijk is die bij een daaropvolgende beurt alsnog tot winst leidt, of liefst eentje die meer dan een winstkans biedt. Wordt vervolgd…

Andere voorbeelden: