Het spel Chomp wordt gespeeld op een m bij n
rooster met vierkante vakjes.
Er zijn dus m rijen en n kolommen.
(Het stelt een reep chocola met blokjes voor.)
Het vakje linksboven, met coordinaten (0,0), is giftig. De spelers
nemen om de beurt een niet-lege "hap". Diegene die het giftige vakje eet,
heeft verloren.
Een hap (oftewel "zet")
grijpt aan op een vakje (i,j), en verwijdert alle vakjes
waarvoor geldt dat
de eerste coordinaat groter dan of gelijk aan i is,
EN de tweede coordinaat groter dan of gelijk aan j is.
(Dit is dus een rechthoekig stuk reep, rechtsonder uitgehapt.)
Een voorbeeldje, met m = 3 en n = 4,
waarbij V het vergiftigde blokje is,
en X een gewoon blokje:
V X X X
X X X X
X X X X
Stel dat de beginspeler (1,1) kiest. Dan resteert:
V X X X
X
X
De tweede speler kiest nu bijvoorbeeld (0,3). Dan resteert:
V X X
X
X
Etcetera.
Eenvoudig is in te zien dat er een winnende strategie is voor
de beginspeler. Er zijn namelijk maximaal mn zetten, en er is geen
remise. Stel dat het kiezen van het vakje (m-1,n-1)
rechtsonder tot zekere winst leidt voor de beginspeler: dan zijn we klaar.
Zo niet, dan heeft de tegenspeler blijkbaar een verpletterend
antwoord, zeg (a,b), waarmee hij/zij wint.
Nu, dan is meteen aan het begin (a,b) ook al winnend
voor de beginspeler!
Dit argument heet wel strategy stealing.
Het is overigens een niet constructief bewijs, en hoe
die winnende strategie er in het algemeen uit ziet is tot op heden
onbekend.
Voor een vierkante reep (met m = n) is er een eenvoudige winnende strategie. Begin namelijk met (1,1). (Zie het derde voorbeeld hierboven.) Spiegel vervolgens de happen van de tegenstander. (In het voorbeeld: beantwoord (0,2) met (2,0).)
En nu de opgave.
Opmerkingen:
In te leveren: geprint verslag (in LaTeX gemaakt; de C++-code als Appendix, zie verder hier voor opmerkingen over het verslag), plus code per email aan kosters@liacs.nl en tcocx@liacs.nl .
Deadline:
dag - woensdag 12 februari 2003;
avond - maandag 17 februari 2003.
Enkele weblinks over Chomp (er zijn er meer):
Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.
10 januari 2003 - http://www.liacs.nl/home/kosters/AI/chomp.html