de Spel Logica

..klaverjassen als een mens.

Klaverjas Trainer bezit een aparte module om voor een speler (ook voor de computer spelers) de 'beste kaart' te kiezen: de 'Trainer Class'. In feite is dat een verzameling van functies die een groot aantal variabelen op een 'intelligente' manier betrekt bij het maken van een 'uit te leggen' beslissing. Toen ik begon was het mijn bedoeling om juist op dit onderwerp (AI - Artificiële Intelligentie) zoveel mogelijk ervaring op te doen. Mijn eerste stap was het verzamelen van de op internet beschikbare informatie hierover.. maar dat viel tegen. Ik kon er weinig bruikbare informatie over vinden en ik ben toen gewoon ergens begonnen. Eigenlijk is me dat best goed bevallen. Het maakte (en maakt) het schrijven van dit spel reuze interessant. Ik zal proberen uit te leggen hoe Klaverjas Trainer uiteindelijk de adviezen en keuzes berekent.

Een voor de hand liggende eerste stap is het bepalen van de kaarten die volgens de spelregels mògen worden opgelegd. Dat zijn er altijd één of meer en daarbij moeten al een aantal belangrijke variabelen worden beoordeeld. Om performance redenen worden de resultaten door Klaverjas Trainer in het geheugen bewaard om bij volgende stappen te worden hergebruikt. De resultaten van stap 1 hangen voor een belangrijk deel af van het aantal kaarten dat al op tafel ligt. Beetje voor de hand liggend, maar degene die mag uitkomen heeft meer vrijheid van handelen dan de andere spelers. De rest kan alleen nog maar bijleggen. Afhankelijk van de kaarten die je daarbij voorhanden hebt mag (of moet) je bekennen, weggooien of als je nog troef hebt, introeven, overtroeven of ondertroeven.

De tweede stap, het bepalen van de te volgen strategie, vergt in verrassend veel gevallen maar een kleine inspanning. In veel situaties mag je bijvoorbeeld maar 1 kaart bijleggen, dat maakt de keuze erg simpel. Maar als het spel vordert en wanneer er meer keuzes zijn wordt het al gauw lastiger. Uitkomen met de Nel kan in sommige gevallen (qua te behalen roem) bijvoorbeeld beter uitpakken dan uitkomen met de Boer. Om daar achter te komen moeten veel mogelijkheden worden doorgerekend. In mijn eerste serieuze poging ging ik er van uit dat de 'ideale' kaart in elke situatie met behulp van kansberekening uiteindelijk wel te vinden zou zijn. De eerste paar versies van Klaverjas Trainer werkten met dat principe maar het resultaat was uitermate onbevredigend.

Later bedacht ik me dat ik beter het menselijk brein kon imiteren. Een bijkomend voordeel daarvan was de mogelijkheid om gedetailleerde adviezen in het spel te verwerken. Die adviezen zijn later uitgegroeid tot een belangrijk onderdeel van het programma, dus deze aanpak blijft er beslist in. Pas later vond ik een spel wat toch een goed werkende rekenmethode lijkt te gebruiken: PK (Potje Kaarten), een DOS spel van Huib Biemond. Zijn aanpak is gebaseerd op het geheel doorrekenen van een relatief klein aantal mogelijke kaartverdelingen. Wel wat traag, maar de demo is zeker overtuigend, en zijn uitleg van de spellogica is reuze interessant. Een beredeneerd advies kun je op zijn manier alleen niet samenstellen.

Hoe speelt een mens eigenlijk?

Welke afwegingen worden er door de 'gemiddelde speler' bij een 'gemiddelde slag' gemaakt? Mijn eigen afwegingen volgend kwam ik op het idee van een beperkt aantal strategieën, die in elke beurt een andere prioriteit krijgen. Je kiest eerst die strategie die jou en je maat in die bepaalde situatie de beste kans op winst geeft. Wanneer die strategie geen duidelijk antwoord heeft, omdat je daar niet de juiste kaarten voor hebt, dan probeer je de daaropvolgende strategie; de op één na beste. Je ervaring wordt vooral gebruikt bij het samenstellen en sorteren van die lijst met strategieën en is ook bepalend voor de snelheid waarmee je speelt. Heel ervaren spelers merken niet eens meer dat ze hun strategie steeds aanpassen, de beste kaart wordt vaak geheel op gevoel (intuïtie) gespeeld.

Voorbeeld: Je maat is gegaan op Schoppen en mag zelf uitkomen. Hij (of zij) komt niet met troef maar met een lage Ruiten. Jij hebt toevallig de Aas van Ruiten en pakt de slag. Dan moet je zelf uitkomen; en een keuze maken. Bij het maken van die keuze sla je (als mens) een heleboel stappen onbewust over, maar als computer moet dat (zucht..) allemaal door de programmeur al vooraf in je programma gestopt zijn. Dat programma "denkt" daarom (en sommige mensen misschien ook) bewust na over elke stap: (1) Troef trekken? Nee, ik ben niet gegaan. (2) Troef spelen? Nee, maat is dan wel gegaan, maar die heeft blijkbaar geen hoge troef. Ik trouwens ook niet. (3) Slag Maken? Heb ik dan een hoge die rond kan? ... En zo gaat het verder. Net zolang tot er een keuze is gemaakt en de kaart met de op dat moment beste kans op winst gevonden en neergelegd is. In het geval van dit voorbeeld misschien de Ruiten Vrouw... de strategie 'Troef Lokken' gaat op zoek naar de Schoppen Boer?

Mensen met een heel goed geheugen zijn beter in het optimaal toepassen van de gekozen strategie. Ze weten beter welke kaarten hoog zijn en welke roem er nog inzit. Hierin is de computer moeilijk te verslaan, zijn geheugen is perfect, en in Klaverjas Trainer wordt daar zoveel mogelijk gebruik van gemaakt. Elke speler heeft een eigen 'geheugen' wat na elke gespeelde kaart wordt bijgewerkt. Ook een computer speler heeft natuurlijk geen toegang tot de kaarten van de andere spelers, maar zijn eigen geheugen weet feilloos welke kaarten er gespeeld zijn en door wie. De gevonden observaties zijn te lezen in het eerste venster van de Trainer.

Eén stap voorwaarts, twee stappen terug

Lang voordat ik in de informatica onderwezen was begreep ik dat je als programmeur continue bezig bent met het herhalen van dezelfde stappen: ontwerpen, bouwen, testen, corrigeren, opschonen en vastleggen. Die laatste twee stappen mag je volstrekt niet overslaan of (te lang) uitstellen. Dat is een bekende valkuil, een 'beginnersfout' zeg maar. Wanneer je daar iets mist krijg je al snel een stuk code waar niemand meer uit wijs kan, uiteindelijk ook de programmeur zelf niet meer. En een programma wat niet verder kan worden ontwikkeld is een 'dood' programma...
Het opschonen van sourcecode bestaat ook niet enkel uit het verwijderen van overbodig geworden regels of het verbeteren van de leesbaarheid door het aanpassen van de naamgeving en/of het toevoegen van commentaarregels. Veel komt tegenwoordig neer op het geschikt maken voor hergebruik. Hoe breder een bepaalde routine of functie binnen (en buiten) je programma kan worden gebruikt hoe beter. Twee functies die deels hetzelfde doen moeten daarvoor worden herschreven tot kleinere functies die allebij dezelfde nieuwe functie(s) aanroepen. De code wordt daardoor leesbaarder en makkelijker te onderhouden.
Maar goed, dit is géén studie boek ;-) en, terugkomend op de spellogica, bij de laatste opschoonactie van vorig jaar bedacht ik me dat de functies die de gekozen taktiek toepassen herschreven konden worden op een manier waarbij ze allemaal gebruik maken van een verzameling 'filters'. Alleen de volgorde waarin die filters elkaar opvolgen en de conclusies die daaraan worden ontleent verschillen dan nog.

Een voorbeeld: de Trainer module komt op basis van de factoren "ik ben gegaan" en "ik kom uit" tot het besluit dat de volgende strategieën (functies) in deze volgorde het beste resultaat zullen geven:

• TROEF TREKKEN
  Controleert of L/R nog troef heeft, en of ik (of mijn maat) de hoogste troef of troeven bezit. Zo ja, dan wordt de kaart aangewezen die daarbinnen de meeste kans op roem geeft. Zoniet, dan wordt de volgende taktiek getest.
• TROEF UITLOKKEN
  Controleert of L/R nog troef heeft, en of ik een lage kaart bezit die waarschijnlijk (of zeker) moet worden ingetroeft en geen tegen-roem kan maken. Zo ja, dan wordt de kaart aangewezen die (qua punten en nog te behalen slagen) het makkelijkst gemist kan worden. Zoniet, dan kijken we verder.
• SLAG MAKEN
  Controleert of wij (ikzelf of, bij mijn weten, mijn maat) een hoge kaart hebben die redelijkerwijs rond kan zonder door L/R te worden ingetroeft. Als er daar zelfs meer van zijn, dan wordt de kaart aangewezen die de meeste kans op roem geeft. Zijn die er niet, dan probeeer ik iets anders.
• TROEF OFFER
  Als de hoogste troef mogelijk bij L/R zit en ik voldoende (lage) troeven heb, kan ik besluiten er daarvan één op te offeren. Als ik daarmee tenminste geen (kans op) roem weggeef. En kan ik dat niet, dan laat ik ook deze taktiek achter me.
• SEIN SPELEN
  Als ik weet dat er bij L/R geen troef meer zit en ik ook geen 'slag kan maken', dan kom ik uiteindelijk hier terecht. Wanneer mijn maat geseind heeft met een kleur die ik ook heb zal ik daar nu naar handelen. Als het een PIT sein was, dan zal ik eerst mijn troeven uitspelen en pas daarna de kaart van de geseinde kleur met de hoogste kans op roem. Als het een 'vuil' sein was (de andere twee kleuren zijn 'afgeseind') dan worden de laatste troeven voor later bewaard. En als ik helemaal niets aan mijn maat heb - er is niet geseind of ik heb dat niet - dan blijft er nog maar één "taktiek" over.
• VEILIG UIT
  De computer zoekt nu de kaart die de minste (kans op) schade berokkend. Aangezien deze 'taktiek' in elke situatie als laatste komt moeten hier een flink aantal mogelijkheden worden bekeken. Zo worden er eerst de troeven uitgefilterd, dan gesorteerd op roemkans, de laatst gekozen kleur, en kleuren die door maat zijn afgeseind en gesorteerd op waarde. Als er dan nog steeds twee of meer kaarten over zijn wordt daar tenslotte 'iene miene mutte' mee gedaan.

Filters

Eerdere versies van Klaverjas Trainer gebruikten voor elke strategie een eigen functie, maar nu zijn de meeste van die functies (niet allemaal) herscheven en gebruiken ze generieke filters om tot een advies te komen. Deze filters worden aangeroepen op de volgende manier:
Sommige filters hebben meer variabelen nodig dan deze twee, vandaar de puntjes aan het eind. De return waarde (boolean) wordt gebruikt wanneer een filter noodzakelijk is voor een bepaalde taktiek. De variabele 'iCardsLeft' houdt bij uit hoeveel kaarten er nog gekozen kan worden. Zodra die op 1 staat zullen de overige filters niets meer doen. Nadat de filters allemaal zijn aangeroepen kan er aan de verschillende 'bUsed' waardes worden afgelezen welke filters daadwerkelijk een beperking van het aantal kaarten tot gevolg hadden. Stel dat ik vijf kaarten heb die ik mag opleggen en dat het eerste filter er drie uithaalt omdat het troeven zijn; dan is dat filter dus gebruikt en kan er bij het advies worden verklaart: "..is geen troef". Als ik geen troeven heb heeft het filter vanzelfsprekend geen toegevoegde waarde, maar als AL mijn kaarten troeven zijn, dan kan dit filter óók niets doen; er moet tenslotte IETS worden opgelegd. Door alleen van de werkelijk gebruikte filters een opmerking in het advies mee te nemen krijg je dus iets als: "De Kla-10 is geen troef, is hoog, kan rond en geeft de beste kans op roem.". Dit advies is samengesteld uit statements van 4 filters: fKleur(troef), fHoger(0), fKanRond() en fRoemKans(); de andere filters zijn wel aangeroepen maar hadden geen invloed op het resultaat, en dus ook niet op het advies.
Het implementeren van de (nu 15) filters is een lastig proces en zal nog een aantal maanden gaan duren. Maar dat wil gelukkig niet zeggen dat er in die tijd geen nieuwe features kunnen bijkomen. Dus wanneer je iets mist of als je een leuk idee hebt.. laat het gerust weten.

Reageren? Graag!
Schrijf een Krabbel!