door Kees Vlak, Artificiële Intelligentie interessegroep (AI ig)
Inleiding
De laatste tijd is er in de Interessegroep Artificiële Intelligentie van de HCC belangstelling voor checkers. Checkers is een variant van het welbekende dammen, die veel in engelstalige landen wordt gespeeld.
Een voordeel van checkers boven andere spellen als schaken en bridge is, dat de spelregels vrij eenvoudig zijn en dat het dus relatief eenvoudig is om deze tot een programma te verwerken.
Een van de programma's die het resultaat is van deze interesse voor checkers, wordt hier besproken. Om te beginnen in het kort de spelregels.
Spelregels
Omdat de meeste mensen dammen wel kennen, hier even in het kort de belangrijkste verschillen tussen dammen en checkers.
Om te beginnen is het bord bij checkers 8×8 en dus is er in de beginstelling maar plaats voor 12 stukken per kleur in plaats van 20 bij dammen.
Verder kunnen gewone stukken alleen naar voren, ook bij het slaan.
Als een stuk aan de overkant komt, promoveert het tot king. Een king kan ook achteruit, maar in tegenstelling tot een dam kan de king maar een veld tegelijk zetten. Bij het slaan komt hij onmiddellijk achter het geslagen stuk te staan. Een king kan dus precies hetzelfde als een gewoon stuk, maar dan zowel voor- als achteruit.
Er geldt geen meerslagregel, maar als het mogelijk is om na het slaan van een stuk nog een volgend stuk te slaan dan is dit ook verplicht. Er moet doorgeslagen worden tot er geen stuk meer geslagen kan worden.
Bitboard
Het is natuurlijk mogelijk om een programma te schrijven dat per stuk op het bord kijkt naar welke velden het stuk kan zetten en slaan, maar het kan sneller.
Een aantal programmeertalen heeft namelijk de mogelijkheid om bewerkingen op de bits van een getal (variabele) uit te voeren. Voorbeelden van dergelijke talen zijn C en Java. In die laatste taal is het hier beschreven programma geschreven.
Een voorbeeld is de and (in Java &). Als we twee byte-variabelen a en b hebben met de bits gevuld zoals hieronder dan krijgen we het volgende resultaat.
01010101 a
00110011 b
00010001 a & b
Op het checkers-bord zijn er 32 zwarte velden waarop stukken kunnen staan en toevallig is in Java een integer-variabele 32 bits lang. We kunnen de bezetting van de velden daardoor weergeven als een integer waarin een bit de waarde 1 heeft als er een stuk op het betreffende veld staat en een 0 als het veld vrij is.
De mapping van de velden op de bits is zoals hieronder weergegeven. De gangbare nummering van de velden is van 1 linksboven (de zwarte kant) tot 32 rechtsonder. In het algemeen worden de bits genummerd van 0 aan de rechterkant (de bit met de laagste waarde) tot 31 aan de linkerkant (de hoogste waarde).
Veld 1, bit 0
|
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
|
Veld 32, bit 31
De hierboven weergegeven integer bevat de zwarte stukken in de beginpositie. We zien dus
00000000000000000000111111111111 binair
00000FFF hex
4095 decimaal
Het programma gebruikt 3 integer-variabelen om een stelling weer te geven:
- de witte stukken (zowel gewone als kings)
- de zwarte stukken (zowel gewone als kings)
- de kings (zowel wit als zwart)
Willen we dus bijvoorbeeld weten wat de witte kings zijn, dan doen we:
white & kings
Bit-operaties
Bij het maken van een checkers-programma met bitboards hebben we de volgende bit-operaties nodig:
&and |or ~not (0 wordt 1 en 1 wordt 0) >>> nshift naar rechts over n bits (de waarde van de integer wordt hierdoor kleiner) << nshift naar links over n bits
Ze kunnen bijvoorbeeld gebruikt worden voor het bepalen van de lege velden: alles waar geen wit of zwart stuk op staat.
empty = ~ (white | black);
Dan kunnen we bepalen welke witte stukken een zet kunnen doen: schuif eerst alle witte bits 4 naar rechts (op het bord 1 rij naar voren), kijk of ze samenvallen met een leeg veld en schuif ze dan weer 4 terug naar hun oorspronkelijke plaats.
move = ((white >>> 4) & empty) << 4;
Deze shift over 4 bits is voor een stuk vanuit elke positie mogelijk, maar in het algemeen kan een stuk 2 kanten op zetten. In het bord hieronder zijn de velden weergegeven van waaruit zetten mogelijk zijn, die overeenkomen met een shift over 5 bits.
0 0 0 0
0 1 1 1
0 0 0 0
0 1 1 1
0 0 0 0
0 1 1 1
0 0 0 0
0 1 1 1
11100000111000001110000011100000 binair
E0E0E0E0 hex
-522133280 decimaal
Het getal is een negatief getal omdat het meest linkse bit van een integer het sign-bit is. Laten we deze variabele white5Legal noemen:
int white5Legal = -522133280;
Analoog aan de shift 4 hiervoor, krijgen we dus voor de velden van waaruit een zet gedaan kan worden die overeenkomt met een shift over 5:
move = (((white5Legal & white) >>> 5) & empty) << 5;
En er zijn ook velden van waaruit een zet gedaan kan worden die overeenkomt met een shift over 3 bits.
0 0 0 0
0 0 0 0
1 1 1 0
0 0 0 0
1 1 1 0
0 0 0 0
1 1 1 0
0 0 0 0
int white3Legal = 117901056;move = (((white3Legal & white) >>> 3) & empty) << 3;
Dit zijn de 3 mogelijkheden voor wit om te zetten. Voor zwart werkt het analoog, maar met de operators >>> en << verwisseld en met andere velden van waaruit de shift over 3 en over 5 bits mogelijk is.
Zoals gezegd kan de king precies hetzelfde als een gewoon stuk, maar dan ook achteruit. Dat betekent dat voor de kings zowel de witte als de zwarte zetten bekeken moeten worden.
Slaan
Bij het slaan is het iets ingewikkelder. Daar hebben we 2 shifts nodig:
- de eerste shift gaat naar de volgende rij; daar moet gekeken worden of er een stuk van de tegenstander staat
- de volgende shift gaat van daaruit verder in dezelfde richting en in de resultaatvelden wordt gekeken of die leeg zijn
In het volgende bord staan de velden van waaruit wit kan slaan door eerst een shift over 4 en vervolgens een shift over 5 bits te doen.
0 0 0 0
0 0 0 0
0 1 1 1
0 0 0 0
0 1 1 1
0 0 0 0
0 1 1 1
0 0 0 0
Als we deze variabele white45LegalJump noemen, dan krijgen we
jump = (((((white45LegalJump & white) >>> 4) & black) >>> 5) & empty) << 9;
Door op het laatst weer over 9 bits terug te schuiven, krijgen we de velden van waaruit naar links geslagen kan worden.
In totaal zijn er 4 mogelijkheden om te slaan. Hierbij is altijd een van de shifts er een over 4 bits. Voor de king, die ook de andere kant op mag, dus 8 mogelijkheden.
Het spelen
Als de menselijke speler aan zet is, kan deze de bedachte zet invoeren. Omdat veel mensen de notatie van de zetten nogal lastig vinden, laat het programma de mogelijke zetten zien, samen met de stelling die na de zet resulteert. Deze zetten en stellingen zijn voorzien van een nummer, dat de gebruiker in kan tikken.
Als het programma aan zet is, probeert het een aantal plies diep alle mogelijke zetten uit. Een ply is een zet van wit of zwart. Meestal rekent dit programma 8 plies diep, dat is dus 4 zetten van wit en 4 zetten van zwart.
Dit gaat als volgt: er is een array van stellingen, waarbij het elementnummer in de array overeenkomt met de ply. Voor een stelling worden alle mogelijke zetten afgelopen en voor elke zet worden de 3 variabelen die de stelling representeren (black, white en kings) gekopieerd naar het array-element met het nummer dat 1 hoger is.
Daar wordt hetzelfde herhaald: alle zetten aflopen en in het volgende array-element ook weer alle zetten aflopen. Dit gaat zo door tot we de diepste ply (in dit geval 8) bereiken. Op de diepste ply wordt de stelling geëvalueerd.
De evaluatie is heel simpel, het tellen van het aantal witte stukken en van het aantal zwarte stukken. De kings worden dubbel geteld, ze kunnen immers in principe 2 keer zoveel als gewone stukken. Deze telling voor de zwarte stukken wordt van de telling voor wit afgetrokken en dit is het resultaat voor de stelling.
Van alle mogelijke zetten wordt het beste resultaat genomen. Als bijvoorbeeld wit op ply 8 aan zet is, is dat het hoogste resultaat. Dit beste resultaat wordt doorgegeven naar de hogere ply. Op ply 7 is dan zwart aan zet. Voor zwart is het laagste resultaat van alle zetten het beste. Dit wordt doorgegeven naar ply 6 enzovoort. De beste zet op de hoogste ply wordt uitgevoerd. De in deze alinea beschreven werkwijze heet het minimax-algoritme.
Meerslag
Bij het slaan hierboven is nog geen aandacht besteed aan wat er gebeurt als er in een slagzet meer dan 1 stuk geslagen kan worden. Eventueel kan er na het slaan van een stuk de keus zijn uit verschillende richtingen om door te slaan.
Door diverse mensen die zich in de Interessegroep Artificiële Intelligentie met een checkers-programma hebben beziggehouden, werd dit onderdeel als vrij lastig ervaren. In het onderhavige programma werd het opgelost door bij de stelling van elke ply een array van 12 andere stellingen te definiëren. Het aantal van 12 is gekozen omdat de tegenstander hoogstens 12 stukken heeft, al zal er in de praktijk waarschijnlijk geen partij zal voorkomen waarin er 12 stukken geslagen kunnen worden in een enkele zet.
Als er zich een slagzet voordoet, wordt de stelling die ontstaat na het slaan van het eerste stuk, gekopieerd naar het volgende element van deze array van 12. Van daaruit worden alle mogelijke volgende slagzetten afgelopen door steeds de stelling na het slaan te kopieren naar het volgende array-element. Dit gaat door totdat er in een bepaalde vertakking geen volgende slagzetten meer mogelijk zijn, waarna het doorrekenen van de stellingen weer verder gaat met de volgende ply.
Promotie
Bij het spelen met de eerste programma-versie bleek dat het programma het promoveren tot king vaak heel lang uitstelde. De evaluatie leverde hetzelfde resultaat op, of de promotie onmiddellijk gebeurt of 4 zetten later. Dit terwijl wij als mensen weten dat je de king juist kan gebruiken om het de tegenstander lastig te maken en meer stukken te veroveren.
Dit is opgelost door niet alleen op de diepste ply het saldo van de stukken uit te rekenen, maar ook op de hogere plies. De evaluatie op de diepste ply telt nog steeds het zwaarste, maar de evaluatie op de hogere ply telt ook mee. Dit wordt bereikt door de evaluatie bij het doorgeven naar de hogere ply met 2 te vermenigvuldigen en de evaluatie op de hogere ply er bij op te tellen.
Op deze manier wordt beloond dat het programma snel promoveert in plaats van de promotie uit te stellen.
Mogelijke verbeteringen
Het programma is relatief eenvoudig, gewoon 8 plies diep alle mogelijke zetten bekijken en zien wie de meeste stukken heeft. Ondanks dat biedt het programma toch aardig tegenstand aan een niet al te sterke speler.
Er zijn nog tal van verbeteringen mogelijk:
- Zo blijkt bij kritische bestudering van het programma dat nog enkele versnellingen mogelijk zijn. Dit zal al gauw een ply winst opleveren, dus van 8 naar 9 plies vrijwel zonder dat je merkt dat het programma nadenkt.
- Er kan een openingsboek worden toegevoegd van goede manieren om de partij te beginnen.
- Evenzo een eindspeldatabase, zodat het programma altijd de beste voortzetting kiest als er nog maar een beperkt aantal stukken op het bord staat. Op dit moment blijkt regelmatig dat het programma stellingen met 1, 2 of 3 stukken meer niet weet te winnen omdat de 8 plies niet voldoende zijn om de winstvoortzetting te vinden.
- Nu kijkt het programma naar alle mogelijke zetten. Als het aantal zetten waarnaar gekeken wordt, beperkt wordt tot bijvoorbeeld 2 of 3 in plaats van nu gemiddeld 6 of 7, kan aanzienlijk dieper gerekend worden dan de huidige 8 plies.
Dit zijn maar enkele van de mogelijke verbeteringen. Van de programma's die binnen de Interessegroep Artificiële Intelligentie geschreven zijn, blijkt het hierboven beschreven programma tot nu toe het sterkste te zijn. Tegen de tijd dat er wat meer tegenstand komt, wordt het tijd om een of meer van de genoemde verbeteringen aan te brengen.
Kees Vlak, mei 2014
KV(/GV) 06-11-2014
