LOG
IN: 19 (1999) Heft 2
Computer-Knobelei
StrategiespielNimQuad
Das Spiel NimQuad, auch Epsteins
Spiel genannt, wird mit 1 Haufen (von n Spielsteinen) gespielt. Es gibt in jeder
Position genau zwei Züge: Entweder wird die jeweils größte in n enthaltene Quadratzahl
addiert oder sie wird subtrahiert (Zug a bzw. s). Eine Partie können wie folgt
ablaufen:
Anfangsposition:
92
1 Anna zieht a, Ergebnis: 173
2 Bodo zieht a, Ergebnis: 342
3 Anna zieht a, Ergebnis: 666
4 Bodo zieht a, Ergebnis: 1291
5 Anna zieht a, Ergebnis: 2516
6 Bodo zieht s, Ergebnis: 16
7 Anna zieht a, Ergebnis: 0
Im 6. Zug hat Bodo offenbar einen Fehler gemacht; hätte er gewinnen
können?
Eine Spielposition p heißt Verlustposition, wenn p=0 ist, oder wenn jeder Zug dem Gegner
eine Gewinnposition überläßt; sie heißt Gewinnposition, wenn sich durch einen
geschickten Zug eine Verlustposition erreichen läßt (in der sich nun der
Spielgegner befindet).
Alle Quadratzahlen sind offenbar Gewinnpositionen. Beginnen wir mit
n=2, so bestehen die zulässigen Züge aus der Addition oder der Subtraktion von 1. Der am
Zug Befindliche wird die 1 nicht wegnehmen, da er sonst dem Gegner eine Quadratzahl
(Gewinnposition) hinterläßt; er addiert daher 1, was 3 ergibt. Aus dem gleichen Grund
addiert der Gegner nicht 1, sondern subtrahiert 1: Die Partie endet unschlüssig (d.h.
ohne Schluß). Die Positionen 2 und 3 nennen wir Remispositionen. Sie sind dadurch
gekennzeichnet, daß es stets einen Zug in wieder eine Remisposition, aber keinen Zug in
eine Verlustposition gibt.
Die beiden kleinsten Verlustpositionen sind 5 und 20; 6, 7 und 8 sind
Remispositionen. Jede Position <20000 läßt sich auf den Zyklus {2,3} reduzieren
außer einem weiteren Zyklus, in dem die Zahl 37 vorkommt.
Zuschriften an:
Rüdeger Baumann
Italienischer Garten 15
29221 Celle
E-Mail: baumann-celle@t-online.de
Literatur
Berlekamp, E.R.; Conway, J.H.; Guy, R.K.: Gewinnen Strategien für mathematische
Spiele. Band 3: Fallstudien. Braunschweig: Vieweg, 1986.
|