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)
>>> n shift naar rechts over n bits (de waarde van de integer wordt hierdoor kleiner)
<< n shift 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

 



 

U kunt het commentaar van twee reviewers onderaan de pagina vinden. Wilt U hier commentaar aan toevoegen, dan kan dat via de Dit e-mailadres wordt beveiligd tegen spambots. JavaScript dient ingeschakeld te zijn om het te bekijken..

De computer en 'de vrije wil'.

Henk Palstra.

U zult met goed gevolg de basisschool doorlopen hebben en daar geleerd hebben dat wij deel uitmaken van een opgebouwde wereld?

De opgebouwde wereld kort samengevat:
Met het verschijnen van de filosofie enige eeuwen voor onze jaartelling, begon ook de verwoording van het besef dat de mens leeft in een opgebouwde wereld (Democritus 460-371 v. Chr.). Het bijbelboek Prediker, 'Alles is ijdelheid' of in een nieuwe vertaling 'Alles is lucht en leegte' van enige eeuwen later spreekt over de gevolgen van die opbouw van werkelijk alles *1.

Als u nu pas kennis hiervan neemt, kan het zijn dat dit wat ontluisterend overkomt. U moet echter bedenken dat na de basisschoolleeftijd de levenskijk, door invloed van hormonen, te mooi is. In de opgebouwde wereld zijn een optimistische en een pessimistische levenskijk van minder belang *2. Het is gewoon 'alles wat is, is opgebouwd'. De opbouw van de wereld wordt in de meeste levensbeschouwingen aanvaard.

In juni 2012 verscheen een boek van Lawrence Krauss: 'Universum uit het niets, waarom er iets is in plaats van niets'. Dit 'iets uit niets' kan mogelijk de eerste bouwstap van alles zijn. Kortom de mens leeft in een illusie.

In het dagelijks leven zijn wij er ons nauwelijks van bewust dat alles is opgebouwd. Als men echter te maken krijgt met vragen die ons bestaan raken, zoals 'bestaat de vrije wil', dan moeten wij, die deel uitmaken van die opbouw, er ons rekenschap van geven dat, wat in wezen illusie is, voor ons wel degelijk betekenis heeft *3.


 Met bovenstaande kennis kan nu de vraag gesteld worden: Kun je voor de computer een 'vrije wil' bouwen?

Het is prettig maar niet noodzakelijk dat de lezer voor het volgende op beginnersniveau bekend is met de computertaal BASIC *4.

In het boekje 'Over Micro-elektronica' van Hans de Witte *5, staat op blz. 20 de volgende zin: 'Microprocessoren kunnen de opgeslagen informatie foutloos en snel bewerken, zij het uitsluitend -opnieuw- op basis van een programma dat in het algemeen door mensen moet zijn gemaakt'. Het opmerkelijke in deze uitspraak is dat niet wordt uitgesloten dat een programma ook door een computer kan worden gemaakt. Men kan zich voorstellen dat in een programma in de computertaal BASIC een BASIC-regel wordt gegenereerd en in een stringvariable wordt opgeslagen. Nu is het probleem van BASIC dat deze string wel op het scherm of de printer kan worden afgedrukt, maar niet kan worden uitgevoerd. Met andere woorden de aanwezige BASIC-interpreter is niet bereikbaar. Het is echter mogelijk de BASIC-interpreter uit te breiden met een commando 'voer wat in de stringexpressie staat uit', kortweg DO <stringexpressie> *6. Een BASIC-interpreter kan gezien worden als een subroutine die een BASIC-commando, -statement, -regel of een BASIC-programma als argument meekrijgt. Er is niets op tegen dat deze subroutine van uit diezelfde subroutine wordt aangeroepen. Dat wordt ook wel recursieve aanroep genoemd. In het kader van de opgebouwde wereld, moet 'DO' gezien worden als een belangrijke bouwstap. Dat deze vorm van recursie bij BASIC mogelijk is komt doordat BASIC de stringvariable kent. In een string laat zich met gemak een BASIC-statement of -regel opslaan.

Het wordt nu ook duidelijk dat het begrip taal uit twee delen bestaat:

  1. De commando's en statements, die aaneengeregen kunnen worden tot een programma.
  2. De interpreter(-subroutine), die opnieuw in twee delen gesplitst kan worden, eventueel enz.,enz., totdat het hardware-niveau bereikt wordt.

Maar omgekeerd kan met het DO-statement taal gecreëerd worden met als interpreter een BASIC-programma.

'DO' heeft iets van het 'RUN'-statement, het commando of statement opgeslagen in de string wordt uitgevoerd, 'de gedachte wordt daad'.

Het was een groot gemis dat een los BASIC-statement of -regel alleen via het toetsenbord uitgevoerd kon worden .

Door 'DO' wordt de formele taal verlaten en wordt op een intuïtieve manier verder gegaan. Het is zaak dat hier zorgvuldig mee wordt omgegaan. Bij robottoepassingen bestaat het gevaar dat de robot zijn maker te lijf gaat.

De computer kan zonder 'DO' uitsluitend taken uitvoeren. Echter met 'DO' is het mogelijk dat de computer zelfstandig beslissingen gaat nemen. Om hier van vrije wil te spreken zal iets te ver gaan, wel zal het gedrag van de computer onvoorspelbaar zijn. Bij de mens zien we een grote overeenkomst met het DO-statement, ook hier wordt 'de vrije wil' betwijfeld. Maar ook bij de mens is het in ieder geval zeker dat het gedrag onvoorspelbaar*7 is.

Noten:

*1 Het oude testament in Leidse vertaling met inleidingen en toelichtingen. Uitgave Brill 1906 Leiden.

*2 De optimist: "Hoe ver zullen wij het nog brengen." De pessimist: "Hoe ver zal het nog met ons komen."

*3 Doch de sferen der waarheid zijn nu eenmaal minder permeabel, dan die der illusie. Citaat uit WILLEN, WETEN, SPREKEN van L.E.J.Brouwer. (Euclides 1933 blz. 190).

*4 BASIC is een laagdrempelige programmeertaal die snel te leren is, en meer flexibel is dan talen die een GOTO-statement missen.

*5 Staatsuitgeverij 1980, ISBN 90 12 62871 X

*6 De computertaal LISP bevat 'EVAL' dat dezelfde werking heeft als 'DO'. LISP wordt veel gebruikt voor kunstmatige intelligentie.

*7 De onvoorspelbaarheid bij de computer zowel als bij de mens wordt verklaard door de chaostheorie. (Ook de weersverwachting valt onder de chaostheorie.)


(HP 10 juni 2013)

Commentaar

Peter Uilenreef merkt op:

  • Het begrip "opgebouwde wereld" wordt nog steeds niet helemaal duidelijk. [Ondanks discussies hierover op de bijeenkomsten (GV).] Filosofisch doet het denken aan materialisme / naturalisme / fysicalisme; duidelijk geen Cartesiaans dualisme met "geest" als zelfstandige entiteit / essentie.
  • Het is interessant om te lezen dat Henk het begrip en mechanisme van de recursieve aanroep en het adapteren van de eigen code (bekend uit Lisp) in Basic al vroeg heeft onderkend en geïmplementeerd.
  • Of het aanpassen van het eigen "programma" aan ervaringen (onder andere door ontvangen input) leidt tot "vrije wil" is voor mij nog een punt van discussie.


(PU 10 juni 2013)

Gerard Vriens voegt daaraan toe:

Ik vond (en vind) het een uitstekend idee om de filosofische implicaties van deze programmeerconstructie (en soortgelijke constructies, zoals EVAL in LISP en eval in Python) in een apart artikel verder uit te diepen; maar in dat opzicht schiet het artikel wat tekort bij mijn verwachtingen.

  • De "technische" informatie over het DO-statement is grotendeels letterlijk overgenomen uit een eerder artikel van Henk in Kennisgeving (1996 nr.2, pp.4-5). Natuurlijk staat het een auteur vrij om uit eigen werk te citeren; maar daardoor wordt een kans gemist om de materie nog wat helderder te formuleren, met name ook voor niet-programmeurs. Dat had het toegankelijker kunnen maken voor leken op het gebied van de informatica die mogelijk wèl in "het probleem van de vrije wil" geïnteresseerd zijn. Ik vermoed dat die toch ook tot de doelgroep van de auteur behoren.
  • Maar ook de filosofische kant wordt naar mijn mening niet goed belicht. De essentie van filosofie is toch "het denken", bij voorkeur op een niveau dat wat dieper gaat dan wat losse associaties. In dit artikel wordt echter veel essentiële informatie bekend verondersteld; redeneringsstappen worden niet duidelijk gezet, technische details weggelaten, en gehanteerde begrippen (zoals "opgebouwde wereld") niet echt uitgelegd. De woorden "dus", "want" en "daarom" komen geen enkele maal in het artikel voor!
  • En vooral is het niet echt duidelijk welk punt de schrijver nu precies over vrije wil wil maken. Hij lijkt geen enkel echt standpunt te willen innemen. Niet over wat vrije wil nu precies is; niet over de vraag of mensen vrije wil hebben; en niet over de vraag of computers het kunnen hebben (al dan niet met behulp van het DO-statement). Heeft vrije wil iets te maken met onvoorspelbaarheid, en zo ja, wat? Het blijft allemaal wat in het luchtledige zweven...


(GV 10 juni 2013)