Antwoord op: Kat & Muis

Er zijn drie mogelijke uitkomsten:

• ja, het spel is berekenbaar en wit kan altijd winnen;
• ja, het spel is berekenbaar en zwart kan altijd winnen;
• nee, het spel is niet berekenbaar.

We definiëren nu eerst W_wit(spelsituatie) en W_zwart(spelsituatie) die aangeven of een speler gewonnen heeft in een bepaalde spelsituatie:

• W_wit(spelsituatie) geldt dan en slechts dan als wit in "spelsituatie" gewonnen heeft (d.w.z. dat zwart volledig klem gezet is).
• W_zwart(spelsituatie) geldt dan en slechts dan als zwart in "spelsituatie" gewonnen heeft (d.w.z. dat zwart de overkant bereikt heeft).

We definiëren verder B_wit(speler aan zet, spelsituatie) en B_zwart(speler aan zet, spelsituatie) die aangeven of een speler altijd kan winnen in een spelsituatie waarin een bepaalde speler aan zet is:

• B_wit(wit, spelsituatie) geldt dan en slechts dan als W_zwart(spelsituatie) niet geldt en er een witte zet w in "spelsituatie" bestaat waarvoor B_wit(zwart, "spelsituatie na zet w") geldt.
• B_wit(zwart, spelsituatie) geldt dan en slechts dan als W_wit(spelsituatie) geldt of voor alle mogelijke zwarte zetten z in "spelsituatie", B_wit(wit, "spelsituatie na zet z") geldt.
• B_zwart(wit, spelsituatie) geldt dan en slechts dan als W_zwart(spelsituatie) geldt of voor alle mogelijke witte zetten w in "spelsituatie", B_zwart(zwart, "spelsituatie na zet w") geldt.
• B_zwart(zwart, spelsituatie) geldt dan en slechts dan als W_wit(spelsituatie) niet geldt en er een zwarte zet z in "spelsituatie" bestaat waarvoor B_zwart(wit, "spelsituatie na zet z") geldt.

Nu geldt:

• Het spel is berekenbaar en wit kan altijd winnen als B_wit(zwart, beginsituatie).
• Het spel is berekenbaar en zwart kan altijd winnen als B_zwart(zwart, beginsituatie).
• Het spel is niet berekenbaar als B_wit(zwart, beginsituatie) en B_zwart(zwart, beginsituatie) beide niet gelden.

Omdat er slechts vijf speelstukken zijn die elk op maximaal 32 velden kunnen staan, zijn er ten hoogste 32⁵=33554432 mogelijke spelsituaties. Een computerprogramma kan alle mogelijke spelverlopen dus in korte tijd doorrekenen en voor elke spelsituatie B_wit(speler aan zet, spelsituatie) en B_zwart(speler aan zet, spelsituatie) bepalen. Met behulp van een dergelijk programma is te bepalen dat B_wit(zwart, spelsituatie) geldt, en dat dus wit altijd kan winnen.

Terug naar de puzzel