Geen wolf en zeven geitjes

Hap

Een curieus nimspel is Hap, in 1974 bedacht door David Gale, een Amerikaanse econoom en wiskundige die ook het spel Gale op zijn naam heeft staan. Martin Gardner wijdde er een artikel aan in Scientific American, daar heette het uiteraard Chomp. Het spel heeft een merkwaardige wiskundige diepgang.

Om het eenvoudig te houden kan het best worden begonnen op een bord van bij voorbeeld vijf bij vier. Op elk veld wordt een witte damsteen gelegd behalve op het veld linksonder (veld a1), daar ligt de giftige zwarte damsteen.

Om beurten mogen de spelers nu een 'hap' stenen van het bord nemen. Daartoe kiest de speler een steen, en laat slechts de stenen liggen die links en onder de steen liggen. Anders gezegd: alle stenen rechts van en boven de steen worden verwijderd, evenals de steen zelf. Gardner legt het uit door te zeggen dat het speelveld een soort koekje is, waarin een rechthoekig gebitje van rechtsboven een willekeurig grote hap zet. Kortom, hieronder wordt een eerste mogelijke zet getoond.

De beoeling is nu, zo te happen dat de tegenstander ten slotte de zwarte damsteen moet nemen. Wie enige routine heeft met nimspelen, zal al snel begrijpen dat de symmetrie in het happen belangrijk is. Als aan het eind van het spel alleen op de randen nog stenen liggen, verliest de speler die aan zet is als rechts van en boven de zwarte steen een gelijk aantal stenen ligt. Zijn tegenstander hoeft slechts de happen die hij doet, na te bootsen. Dat is ook de reden dat Hap niet op een vierkant veld moet worden gespeeld: dan zet de eerste speler zijn hap eenvoudig in de steen schuin boven de giftige, zodat twee symmetrische rijen ontstaan.

Nadere analyse heeft ook aangetoond dat de eerste speler altijd kan winnen op een veld van slechts twee stenen breed of hoog. Sterker nog, Gale heeft ook al bewezen dat de eerste speler op elk veld, hoe groot ook, kan winnen. Stel namelijk, dat die eerste speler besluit alleen de steen rechtsboven in de hoek te nemen. Als dat een winnende zet is, heeft hij gewonnen. Als het een verliezende zet is, dus als de tweede speler daarop de winnende zet heeft, dan had de eerste speler die zelf meteen kunnen doen, en zo kunnen winnen. Het aardige is nu, dat deze redenering niets zegt over de winnende zet -- hij bestaat, maar welke zet het is, is nog steeds onduidelijk, behalve voor de bovengenoemde 'triviale' uitzonderingen.

Het spel duurt langer en geeft meer kans op fouten en dus op spanning op een groter bord. Maar op een veld van bij voorbeeld vijf bij acht moeten al alle damstenen worden gebruikt; in de hoek linksonder ligt dan een erwt, een cent of een dode muis -- desnoods helemaal niets.

Het ligt voor de hand het spel uit te breiden naar de derde dimensie, en op elk veld een stapel van drie of vier damstenen te zetten. Het gebit komt dan van schuinboven en hapt zich op die manier een weg naar de giftige steen: alle stenen met een grotere of gelijke x, y en z worden verwijderd.

Volgende spel: Molenspel