Laatste wijziging:

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 over dit onderwerp (AI - Artificiële Intelligentie) zoveel mogelijk te leren. Mijn eerste stap was het verzamelen van de op internet beschikbare informatie hierover. Maar dat viel me erg tegen. Ik kon er toen eigenlijk niets nuttigs over vinden en ik ben maar gewoon ergens begonnen. Eigenlijk is me dat best goed bevallen. Het maakte (en maakt) het schrijven van dit spel erg 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.

Maar hoe speelt een mens?

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 of intuïtief 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. De 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.

Stap voorwaarts? Stapje terug!

Al ver voordat ik in de bijbehorende theorie werd onderwezen begreep ik dat je als programmeur bezig bent met het steeds herhalen van een aantal 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, hoewel er ook wel gevorderde programmeurs in trappen. En het gevolg? Een stuk code waar niemand meer uit wijs kan, en uiteindelijk ook de programmeur zelf niet. Weer een programma wat dus nooit verder zal worden ontwikkeld. Tja, heel droevig eigenlijk ;-)
Het opschonen van sourcecode bestaat niet alleen uit het verwijderen van overbodig geworden regels of het verbeteren van de leesbaarheid door het aanpassen van de naamgeving of het toevoegen van commentaarregels. Veel komt neer op het geschikt maken voor hergebruik. Hoe breder een bepaalde routine of functie binnen je programma kan worden gebruikt hoe beter. Twee functies die deels hetzelfde blijken te doen ga je dan bijvoorbeeld herschrijven tot functies die ergens allebij dezelfde (nieuwe) functie aanroepen. Je code wordt daardoor leesbaarder en makkelijker te debuggen.
Maar vooruit, dit is géén studie boek ;-) en, terugkomend op de spellogica, tijdens één zo'n opschoonactie 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) en 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 die 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 worden eerst mijn eventuele troeven aangewezen 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 zal die kaart nu direct favoriet zijn en worden de troeven voor later bewaard. Maar als ik helemaal niets heb aan mijn maat - er is niet geseind of ik heb dat niet - dan blijft er nog maar één laatste "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, 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 meesten van die functies herscheven en gebruiken ze filters om tot een advies te komen. Filters worden aangeroepen op de volgende manier:

in C : bool fDitFilter(bool *bUsed, int *iCardsLeft, ..) {

in VB: Function fDitFilter(byref bUsed as Boolean, byref iCardsLeft as Integer, ..) As Boolean

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!