Assemblertips für den Spectrum (15)

Teil 15: Mathematische Taktik für das Hölzchenspiel

In dieser Folge der Assemblertips befassen wir uns ausnahmsweise mit einem Spiel, nämlich mit dem Hölzchen- oder Nimmspiel. Achten Sie bitte beim Abtippen des Basiclistings darauf, jedes unterstrichene A als Grafikbuchstaben einzugeben. Während des Programmlaufs wird an dieser Stelle jeweils ein ö erscheinen. Das Programm ist in Optik und Akustik recht schlicht gehalten. Wer Lust hat, wird sicher Möglichkeiten finden, das Drumherum des Spiels noch etwas ansprechender zu gestalten, z. B. eine kleine Melodie einzufügen USW.
Was sucht dieses Programm nun bei den Assemblertips? Mir geht es hier um die Strategie, die den Gewinn des Spiels garantiert. Bevor Sie weiterlesen, sollten Sie einige Male gegen den Rechner antreten. Wer den Trick nicht kennt, wird wahrscheinlich kaum einmal gewinnen.

Wie geht man vor, Um bei irgendeinem Spiel in einer bestimmten Situation eine möglichst gute Fortsetzung zu finden? Im allgemeinen ist es erforderlich, verschiedene, eventuell alle möglichen Züge zu erwägen und zu beurteilen. Dazu sind die denkbaren Antworten des Gegners zu beachten, die vorstellbaren eigenen Reaktionen darauf usw. Je weiter, je "tiefer" man denkt, desto besser kann man spielen - desto mehr Zeit ist aber auch für einen Zug nötig. Schachprogramme arbeiten übrigens auf etwa diese Weise, wobei es aber eine geschickte Vorauswahl erlaubt, nicht jeweils alle möglichen Züge betrachten zu müssen, sondern eine Beschränkung auf weniger gestattet.

Die extrem kurze Antwortzeit des Computers läßt vermuten, daß er beim Hölzchenspiel ganz anders-vorgeht als gerade beschrieben. Tatsächlich gibt es eine rein mathematische Methode, um einen optimalen Zug zu finden.
Betrachten wir zunächst die Spielvariante, bei welcher derjenige gewinnt, der das letzte Holz ergattert. Man bildet die Exklusiv-Oder-Summe (XOR-Summe) der Binärdarstellungen der Hölzchenzahlen der einzelnen Haufen. Ist diese Summe null (wir wollen dann von einer Nullstellung sprechen), gibt es in der vorliegenden Situation keinen Zug,. der den Gewinn sichert. Sofern der Gegner optimal spielt, wird er siegen: Daher nimmt man am besten nur ein Holz von irgendeinem Haufen, um das Spielende möglichst hinauszuzögern, so daß noch Hoffnung auf Fehler des Gegners besteht.

Ist die XOR-Summe ungleich null, muß man sie auf null bringen. Das ist immer mittels eines zulässigen Zuges möglich, also durch Entfernen von Hölzern von nur einem Haufen. (In der Binärdarstellung der Hölzchenzahl auf diesem Haufen muß dasjenige Bit gesetzt sein, welches dem höchsten gesetzten Bit in der XOR-Summe entspricht. Eine solche Anzahl tritt notwendigerweise auf, weil sonst diese XOR-Summe nicht hätte entstehen können.)

Warum führt diese Taktik zum Sieg? Die Erklärung ist ganz einfach: Aus einer Nullstellung kann man nicht durch Verändern der Hölzerzahl eines einzigen Haufens wieder in eine Nullstellung gelangen. Die Siegstellung, in der die Hölzer aller Haufen abgeräumt sind, ist selbst eine Nullstellung. Wenn man sich also von Nullstellung zu Nullstellung hangelt, hat der Gegner keine Chance, diese Folge zu durchbrechen.

Was ist aber zu tun, wenn man eine Partie spielt, bei welcher derjenige verliert, der das letzte Holz erhält? In diesem Fall ist genauso vorzugehen wie in der ersten Variante, allerdings nur so lange, bis nur noch ein Haufen existiert, auf dem mindestens zwei Hölzchen liegen. In diese Lage gelangt man zwangsläufig, sofern es einem irgendwann gelungen ist, eine Nullstellungsfolge einzuleiten, denn diese Situation spiegelt eine Nicht-Nullstellung wider.

Nun entfernt man von diesem Haufen entweder alle Hölzer oder alle bis auf eins, gerade so, daß eine ungerade Anzahl von Einser-Haufen übrig bleibt. Dann ist das Spiel praktisch gelaufen; der Gegner muß das letzte Holz nehmen.

Damit besitzen wir eine einfache Strategie. Wenn Sie diese beherrschen und gegen jemanden antreten, der sie nicht kennt, werden Sie den Gegner sicher mit ständigen Gewinnen beeindrucken können. Natürlich gibt es solche Techniken nur für die allerwenigsten Spiele, und im Grunde sind diese ja ohne Reiz. Fairerweise sollten alle Teilnehmer um die Gewinnstrategien wissen.