LOG IN Leitseite

[2000]

 


log-in_small.gif (418 Byte)


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.