Je leest:

Hex en Kamertje verhuren

Hex en Kamertje verhuren

Auteurs: en | 1 december 2001

Kamertje verhuren en Hex zijn al geruime tijd populaire spellen, in het bijzonder onder de wiskundestudenten. Op internet zijn er diverse pagina’s aan gewijd en je kunt beide spellen online spelen (zie links onderaan dit artikel). Onlangs verscheen er over elk spel een nieuw boek dat ingaat op de wiskundige aspecten. Ronald van Luijk en Sander van Rijnswou geven een kritische beschouwing van beide werken.

Voor wie tijdens de lange winteravonden genoeg heeft van monopolie en ganzenborden zijn er talloze alternatieven waarbij verlies niet aan het kanselement toegeschreven kan worden. Zo wordt menig uur doorgebracht met het traditionele schaken, dammen, het steeds populairder wordende Japanse Go of het eenvoudigere vier-op-een-rij. Over elk van de eerste drie zijn al vele boeken geschreven. Voor het laatste is enkele jaren geleden zelfs een winnende strategie voor de eerste speler gevonden.

Minder bekend zijn de spellen Hex en Kamertje verhuren. Beide hebben regels zo eenvoudig dat je ze aan een kind kunt uitleggen en beide zijn veel complexer dan je op het eerste gezicht wellicht zou vermoeden. Wat ze nog meer gemeen hebben is dat over beide recentelijk een boek is uitgekomen.

Hex wordt gespeeld op een ruitvormig bord opgebouwd uit n × n regelmatige zeshoeken. Twee tegenoverliggende zijden van het bord zijn zwart gekleurd, de andere twee wit. De twee spelers plaatsen om beurten een steen van hun eigen kleur op het aanvankelijk lege bord. Een speler heeft gewonnen als hij de tegenoverliggende zijden van zijn kleur weet te verbinden met een ononderbroken keten van zijn stenen, zie figuur 1.

Figuur 1. Hex op een 11 × 11-bord, een veel gebruikte grootte. Wit heeft dit spel gewonnen.

Het spel is bedacht door de Deense dichter en wiskundige Piet Hein. Hij beschreef het spel in de Deense krant Politiken van 26 december 1942. Er is een elegant bewijs dat het spel niet kan eindigen in remise. Om de geïnteresseerde speler niet het plezier te ontnemen daar zelf over na te kunnen denken, zullen we het bewijs achterwege laten. Met behulp van een strategy stealing argument impliceert dit dat de eerste speler, zeg wit, kan winnen.

Stel namelijk dat niet de eerste, maar de tweede speler een winnende strategie heeft. Door deze strategie te kopiëren krijgen we ook een winnende strategie voor de eerste speler. Wit doet de eerste zet volledig willekeurig. Hierna reageert wit op de zetten van zwart alsof de eerst geplaatste steen er niet is. Hierdoor wordt wit effectief de tweede speler en kan hij dus reageren volgens de winnende strategie van de tweede speler. Wanneer hij volgens deze strategie zou moeten spelen op het vakje van de willekeurig geplaatste steen, speelt hij de volgende steen op een willekeurig leeg zeshoekje op het bord. Aangezien een extra witte steen op het bord niet in het nadeel kan werken voor wit resulteert dit in een winnende strategie voor de eerste speler.

Hoewel de eerste speler bewezen eenwinnende strategie heeft, is deze strategie voor borden van lengte 8 of meer niet bekend. Er zijn nog andere interessante resultaten bewezen over het spel. Zo zijn de vakjes in de twee scherphoekige hoeken van het bord verliezende eerste zetten. Op een parallellogramvormig m x n-bord met m is ongelijk aan n kan de spelerwinnen die de dichtst bij elkaar liggende zijden moet verbinden. Hiervoor is zelfs een strategie bekend, gebaseerd op een bepaalde betegeling van het bord. Het is dus fataal een zwakkere speler een voorsprong te geven door het bord aan een kant een rij korter te maken.

Making the right connections

Wie Hex voor het eerst speelt heeft al snel in de gaten dat het patroon in figuur 2 erg nuttig is. In welke van de twee lege zeshoeken zwart ook speelt, wit kan in de andere spelen en is dus verzekerd van een verbinding tussen deze twee stenen. Dit patroon wordt een brug genoemd en is het begin van een uitgebreide beschrijving van strategieën in het boek Hex Strategy, Making the Right Connections, geschreven door Cameron Browne.

Figuur 2. Een brug: wit is verzekerd van een verbinding tussen de twee stenen.

In het eerste hoofdstuk van het ruim 370 bladzijden dikke boek worden niet alleen de regels uitgelegd, maar ook de geschiedenis van het spel. Verder wordt Hex vergeleken met enkele andere spelen en wordt een zeer grondige literatuurstudie gegeven. De schrijver is erin geslaagd een toegankelijk boek te schrijven dat nieuwe spelers in Hex zal interesseren, maar dat ook ervaren spelers tot nieuwe inzichten kan brengen. Een van de verdiensten van dit boek is dat de schrijver alles wat hij heeft kunnen vinden over Hex in één boek heeft verzameld. Hierdoor zal de lezer zijn eigen bevindingen in het spel bevestigd zien tot op het punt in het boek waar hij nieuwe strategieën ontdekt. Daarnaast bevat het boek vele voorbeelden en uitdagende puzzels (met oplossingen). Zo s het geschikt voor spelers op elk niveau.

Beoogde doelen van het boek zijn het opzetten van jargon voor Hex-spelers en -onderzoekers en het geven van werkbare definities, onder andere om strategieën en algoritmes precies te kunnen beschrijven. Of zijn terminologie standaard zal worden zal de tijd leren, maar aan de vereiste wiskundige precisie ontbreekt het hier en daar helaas. Dat enkele specifieke bordsituaties verkeerd zijn geanalyseerd heeft de schrijver niet weten te voorkomen, maar heeft geen consequenties voor de rest van het boek. Een serieuzer probleem betreft een van de veelgebruikte concepten in het boek, namelijk het begrip verbondenheid. Aangezien het doel van Hex is twee tegenoverliggende zijden van het bord te verbinden, is dit een begrip dat in de analyse van bordsituaties natuurlijk naar voren komt. De precieze definitie is als volgt.

Ketens en verbondenheid

Een keten is een maximale verzameling direct verbonden stenen van een kleur. Hier zijn twee stenen A en B van dezelfde kleur ‘direct verbonden’ als er een reeks tussenliggende stenen van die kleur is waarvan elke grenst aan de volgende, de eerste aan A en de laatste aan B. Twee verschillende ketens zijn dus per definitie niet verbonden, maar we noemen ze 0-verbonden als ze in een reeks zetten verbonden kunnen worden, ongeacht wat de tegenstander speelt, en zelfs als die aan de beurt is of zou zijn. Twee stenen met een brug ertussen vormen het eenvoudigste voorbeeld. De reeks zetten mag gebruik maken van reeds gevormde ketens. De twee uiterste stenen in figuur 3, bestaande uit twee bruggen, zijn dus ook 0-verbonden.

Figuur 3. Een 0-pad.

Een 0-pad bestaat uit een begin- en een eindketen, een verzameling andere ketens en een verzameling lege vakjes zodanig dat de beginen eindketen 0-verbonden zijn en wat de tegenstander ook speelt, er is een reeks zetten die de begin- en eindketen verbindt en die slechts gebruikmaakt van de ketens en lege vakjes uit de gegeven verzamelingen. Twee ketens zijn n-verbonden als ze door het plaatsen van n extra stenen op het bord 0-verbonden kunnen worden. Een n-padbestaat uit een begin- en een eindketen, een verzameling andere ketens en een verzameling lege vakjes, zodanig dat door het plaatsen van n stenen op vakjes uit de verzameling lege vakjes er een 0-pad ontstaat (na het eventuele samenvoegen van ketens).

Deze definities zijn preciezer dan die Browne geeft in zijn boek. Letterlijk vertaald schrijft hij: “Het concept van verbondenheid staat centraal in Hex. Twee stenen of ketens zijn n verbonden wanneer zij, geïsoleerd beschouwd, innzetten kunnen worden samengebracht tot een onverslaanbare verbinding.” Merk op dat twee n-verbonden ketens ook (n + 1)-verbonden zijn, wat de verbondenheid van een verbinding ambigu maakt. Of Browne zich dit realiseert is echter de vraag. Wanneer hij praat over een n-pad, noemt hij n de verbondenheid van de begin- en eindketen van het pad. Als hij het heeft over de verbondenheid, of soms zelfs de ware verbondenheid van twee ketens, kunnen we dit redelijkerwijs niet anders interpreteren dan het kleinste getal n waarvoor de twee ketens n-verbonden zijn.

Figuur 4.Andere voorbeelden van 0-paden bestaande uit de combinatie van twee 1-paden.

Zoals gezegd is het begrip verbondenheid nuttig in de analyse van een bordsituatie. Wanneer we de zijden van het bord ook beschouwen als ketens en er een 0-pad bestaat tussen de twee zijden van een speler, dan kan deze speler gegarandeerd winnen. Wanneer de speler aan de beurt is kan hij zelfs winnen wanneer er een 1-pad bestaat tussen zijn twee zijden. Het is daarom handig de verbondenheid van paden te kunnen berekenen en paden te kunnen construeren met lage verbondenheid.

Dit laatste kan bijvoorbeeld door het combineren van paden. Wanneer twee ketens verbonden zijn door twee disjuncte 1-paden, kunnen we die combineren tot een 0-pad. Als de tegenstander namelijk een van de twee paden aanvalt, speel je de zet die het andere 1-pad nodig heeft om een gegarandeerde verbinding tussen de ketens te creëren. Het simpelste voorbeeld hiervan isweer de brug,waarin beide 1-paden bestaan uit de twee stenen en een van de twee tussenliggende zeshoeken. Andere voorbeelden van 0-paden bestaande uit de combinatie van twee 1-paden zijn weergegeven in figuur 4.

Figuur 5.Enkele voorbeelden van n-paden, waarin n gelijk is aan respectievelijk 1, 0, 1 en 2.

Verwarring

Daarnaast kunnen uiteraard een n-pad van A naar B en een disjunct m-pad van B naar C gecombineerd worden tot een (m+ n)-pad van A naar C. Het boek beschrijft nog enkele manieren om paden te bouwen en met behulp van deze constructies geeft het een algoritme om paden te vinden met lage verbondenheid. Er is echter geen enkele reden om aan te nemen dat het pad met de laagste verbondenheid op deze manier is op te bouwen, dus het algoritme zal niets meer doen dan het geven van een redelijke bovengrens van de verbondenheid. Ondanks dat beweert de schrijver over andere Hex programma’s: “Some current Hex playing programs use adjacent and bridge steps only [. . .] these measurements do not describe the true connectivity across the board,” en over zijn eigen algoritme: “The following sections outline an algorithm that gives a precise measure of each player’s connectivity.” Het is een leuke uitdaging een bordsituatie te verzinnen waar het algoritme de mist in gaat.

Wij hebben hierover met Cameron Browne gecorrespondeerd, en hij geeft toe dat zijn methode alleen een bovengrens vindt in plaats van de geclaimde precieze verbondenheid. Uit dezelfde correspondentie blijkt dat de schrijver gedurende het hele boek bij het begrip n-paden niet denkt aan het algemene geval, maar slechts aan de deelverzameling van de speciaal gestructureerde n-paden die ook als zodanig worden herkend door zijn algoritme.Met deze interpretatie zou het bovenstaande citaat nogal triviaal worden. Bovendien valt door deze fout een van de weinige bewijzen, die gegeven worden in de appendices, als een kaartenhuis in elkaar. Het betreft de uitspraak dat de twee spelers niet beide tegelijkertijd een 0-pad tussen hun twee zijden kunnen hebben.

De verwarring verklaart ook uitspraken als dat elke twee ketens in een 0-pad gegarandeerd verbonden zouden kunnen worden. In het algemeen is dit verre van waar, maar het vormt in het boek toch de basis van de (nu wankel gebleken) constructie van een veilige groep. Het gebruik van dit belangrijke begrip lijkt overigens gebaseerd te zijn op een andere definitie dan die uit het boek. Het is overigens niet uitgesloten dat de twee equivalent zijn in het geval dat alleen de verzameling van speciale 0-paden worden beschouwd. Al met al zal elke Hex-speler plezier beleven en leren van de strategieën in dit boek. Ze zijn voornamelijk gebaseerd op de intuïtie van ervaren spelers. Uit wiskundig en algoritmisch oogpunt is het echter alleen interessant wanneer de lezer zich ten doel stelt te proberen de definities duidelijker te maken in het geval de uitspraak al duidelijk is, er tegenvoorbeelden voor te bedenken.

Kamertje verhuren

Wiskundig sterker is het boek Dots and Boxes van Elwyn Berlekamp. Het gaat over het spel dat in Nederland bekend is onder de naam ‘Kamertje verhuren’. Het spel wordt gespeeld op een stuk ruitjespapier. Twee spelers doen om de beurt een zet, die bestaat uit het verbinden van twee punten naast of boven elkaar. Als een speler een vakje helemaal insluit, dan is het voor hem en mag hij er zijn initiaal in zetten. Daarna moet hij nog een zet doen. Als het bord helemaal vol is dan heeft degene met de meeste vakjes gewonnen.

Wie het spel een paar keer gespeeld heeft realiseert zich vaak niet de diepte van de strategieën die mogelijk zijn in dit spel. Dit boek geeft een overzicht in 130 pagina’s van wat er allemaal mogelijk is, en dat is heel wat. Het begint met de beginnersstrategie: “neem zoveel mogelijk vakjes en geef er zo min mogelijkweg,” en eindigt met speltheoretische beschouwingen waar een hoop oefening voor nodig is om ze je eigen te maken.

Figuur 6.Kamertje verhuren Bron: www.overlaat.nl/spelletje/kamertje/kamertje.htm

Winning ways for your mathematical plays

Berlekamp kan zijn theorieën duidelijk naar voren brengen. De hoofdstukken worden afgesloten met een lijst dots-and-boxes stellingen waarvoor de winnende zet te vinden is met behulp van het zojuist geleerde. De eerste paar hoofdstukken zijn bijna helemaal overgenomen uit Winning Ways for your mathematical plays. Er zijn vooral veel oefeningen aan toegevoegd. Ze lezen gemakkelijk weg, en daarna ben je praktisch onverslaanbaar geworden (totdat iemand ook de volgende paar hoofdstukken gedaan heeft natuurlijk). De tweede helft van het boek is aanmerkelijk wiskundiger van opzet. Er wordt een overzicht gegeven van de ontwikkelingen in het onderzoek naar dit spel sinds Winning Ways. Het is aan te raden voor een bredere speltheoretische context dit laatste boek eerst te lezen. Berlekamp heeft met dit boek een interessante aanvulling geschreven op zijn reeks boeken over speltheorie. Dit boek is goed te vergelijken met zijn andere boeken, zoals Mathematical Go. Zowel de spelletjesenthousiast als de in speltheorie geïnteresseerde zal met dit boek een paar leuke dagen beleven.

De twee boeken over hex strategieen die hier besproken zijn.

Besproken literatuur

Elwyn R. Berlekamp, The Dots-and-Boxes Game: Sophisticated Child’s Play, A.K. Peters Ltd., ISBN 1568811292, prijs 44 Euro; Cameron Browne, Hex Strategy: Making the Right Connections, A.K. Peters Ltd., ISBN 1568811179, prijs 18 Euro.

Dit artikel is een publicatie van Nieuw Archief voor Wiskunde (KWG).
© Nieuw Archief voor Wiskunde (KWG), alle rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 01 december 2001

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.