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.