Probieren Sie das Brettspiel Hex!

Man kann davon ebenso süchtig werden wie von den besten Computerspielen, aber es fordert Ihre kombinatorischen Fähigkeiten weit mehr. Cameron Browne, ein Programmierer aus Brisbane (Australien), hat in einem neueren Buch das Spiel mitsamt Anleitungen zum Gewinnen erstmals umfassend dargestellt: ein Leckerbissen für jeden Liebhaber mathematischer Spielereien.

Hex ist ein Zwei-Personen-Spiel, das auf einem rhombusförmigen, in sechseckige Felder eingeteilten Brett gespielt wird. Das Standardbrett hat 11x11 Felder. Nennen wir die Spieler Rot und Blau. Jedem Spieler "gehören" zwei einander gegenüberliegende Ränder des Brettes; die vier Eckfelder gehören beiden Spielern. Außerdem hat jeder Spieler einen Vorrat an Spielsteinen seiner Farbe.

Die Spielregeln sind denkbar einfach: Die Spieler ziehen abwechselnd, indem sie jeweils einen eigenen Spielstein auf ein freies Feld legen. Sieger ist, wer als Erster seine beiden Ränder durch eine Kette aus Spielsteinen miteinander verbunden hat. Die Kette kann beliebig viele Abzweigungen und Schleifen haben; es kommt nur darauf an, dass sie einen zusammenhängenden Weg von einem zum gegenüberliegenden Rand enthält. Das hört sich einfach an, aber der Schein trügt: Hex ist voller Überraschungen und Fallstricke.

Erfinder des Spiels war Piet Hein (1905-1996), ein dänischer Mathematiker, der auch als Dichter bekannt geworden ist. Er nannte sein Spiel "Polygon", und es erschien zuerst in der Ausgabe vom 26. Dezember 1942 der dänischen Zeitung "Politiken". Unabhängig von Hein erfand es 1947 John Nash aufs Neue. Damals war er noch Student an der Universität Princeton; wenig später fand er seine bahnbrechenden Resultate zur Spieltheorie, für die er 1994 mit dem

Nobelpreis in Wirtschaftswissenschaften geehrt wurde. In Princeton nannte man das Spiel einfach "Nash" oder auch "John". Martin Gardner beschrieb das Spiel 1957 in seiner Kolumne in "Scientific American", und über Nacht verfielen ganze mathematische Institute in aller Welt dem Hex-Fieber.

Jedes Hex-Spiel hat nur endlich viele Züge: Es endet spätestens dann, wenn alle Felder besetzt sind, also nach 121 Zügen auf dem 11x11-Brett. Eine zusammenhängende Kette eines Spielers blockiert jede Kette des anderen Spielers. Ein Unentschieden kann es nicht geben. Ein Spieler kann seinen Gegner nämlich letztlich nur dadurch an der Konstruktion einer siegreichen Kette hindern, dass er selbst eine solche Kette konstruiert.

Man kann sogar beweisen, dass der erste Spieler bei optimalem Spiel gewinnen kann. Der Beweis beruht auf dem Prinzip des Strategiediebstahls. Nehmen wir an, Rot zieht zuerst, und es gäbe eine Gewinnstrategie für Blau, den zweiten Spieler. Wenn das so wäre, könnte aber Rot die Gewinnstrategie selber anwenden, um Blau zu schlagen. Dazu genügt es, dass Rot seinen ersten Stein schlicht vergisst, sowie er ihn gesetzt hat. Er tut so, als habe Blau das Spiel eröffnet, und er selbst sei der nachziehende und nicht der anziehende Spieler. Welchen Zug nun Blau auch macht, Rot setzt seinen Stein auf das Feld, das die (angeblich existierende) Strategie für den Nachziehenden vorschreibt. Und wenn das nun gerade das Feld ist, das er in seinem "vergessenen" Eröffnungszug belegt hat? Das macht nichts; dann liegt ja schon ein roter Stein auf dem zu besetzenden Feld. Rot macht also irgendeinen anderen Zug, und dieser wird der neue "vergessene" Zug.

Wenn Rot so fortfährt, kann er nach der Annahme den Sieg erzwingen. Aber nun befinden wir uns in einer merkwürdigen Situation. Rot beginnt das Spiel, stiehlt, wie beschrieben, Blau seine angebliche Gewinnstrategie für den zweiten Spieler und gewinnt damit, einerlei wie Blau spielt. Die einzige Möglichkeit, diesen Widerspruch aufzulösen, besteht darin, dass es keine Gewinnstrategie für den nachziehenden Spieler gibt. Da aber das Spiel endlich ist und es kein Unentschieden gibt, muss es eine Gewinnstrategie für den anziehenden Spieler geben.

Auf den ersten Blick ist das Spiel damit langweilig: Man weiß von vornherein, wer gewinnen wird, wenn beide Spieler der Gewinnstrategie folgen. Nur geht diese Strategie aus dem Beweis nicht hervor und ist auch nicht einfach zu finden. Nur bis zum Format 7x7 ist sie bekannt. Schon auf einem 8x8-Brett weiß der Anziehende zwar, dass er mit Sicherheit gewinnt, wenn er perfekt spielt, hat aber keine Ahnung, wie er dabei zu Wege gehen müsste.

Gleichwohl bleibt ein großer Vorteil für den anziehenden Spieler. Um diesen auszugleichen, vereinbaren manche Spieler eine weitere Regel: Wenn der Anziehende seinen ersten Zug gemacht hat, darf der zweite Spieler den gesetzten Stein gegen einen eigenen austauschen, statt auf ein freies Feld zu setzen. Der erste Spieler bietet damit dem zweiten an, nach dem ersten Zug die Rollen zu tauschen, und tut daher gut daran, seinen ersten Stein so zu setzen, dass er ihm weder Vorteile noch Nachteile verschafft; andernfalls könnte sein Gegner einen Vorsprung nutzen.

Eine ausführliche Besprechung von Hex würde diese Kolumne für fünf Jahre füllen. Ich will mich daher auf zwei wesentliche Aussagen konzentrieren. Die erste ist jedem offensichtlich, der das Spiel ein paar Mal gespielt hat: Auch unbesetzte Felder können eine strategische Bedeutung haben. Teil A im Bild oben zeigt eine "Brücke". Die Pfeiler sind zwei von Blau besetzte Felder; dazwischen liegen zwei freie, gemeinsame Nachbarfelder. Damit sind die blauen Pfeiler so gut wie verbunden; denn sobald Rot eines der Felder besetzt, kann Blau das andere besetzen. Hex-Spieler versuchen oftmals Ketten aus solchen Brücken über das Brett zu bauen.

Eine Brücke ist nicht unbesiegbar. Wenn es Rot gelingt, eines der Zwischenfelder zu besetzen und dabei gleichzeitig mit einem Gewinnzug zu drohen, ist die Brücke durchbrochen. Aber das ist meist ein schwieriges Unterfangen; besser ist es, den Gegner möglichst wirksam am Brückenbau zu hindern.

Die zweite Aussage: Die Kette eines Spielers ist nur so stark wie ihr schwächstes Glied. Wenn Ihr Gegner einen Teil Ihrer heranwachsenden Kette mit guten Erfolgsaussichten angreift, dann sollten Sie ihr schwächstes Glied verstärken oder Ihrerseits seine Kette angreifen. Um Ihre Absichten zu verbergen, ist es oft ratsam, sich aus einiger Entfernung an seine schwachen Punkte heranzuschleichen.

Eine höhere Kunst ist die Beherrschung von Leitern. Sie entstehen, wenn ein Spieler die letzte Lücke zu seinem Rand zu schließen versucht. Teil B im Bild oben zeigt den Beginn der Leiter mit Blau am Zug. Blau muss auf Feld p setzen, sonst kann Rot das Spiel gewinnen. Aus dem gleichen Grund muss Rot dann Feld q besetzen. Wenn Blau weiter versucht, eine Verbindung zu seinem Rand herzustellen (und das muss er über mehrere Züge, wenn er nicht verlieren will), dann muss Rot weiter blockieren, und es entstehen zwei parallele Ketten aus roten und blauen Steinen entlang des Randes. Blau hat nicht rechtzeitig bemerkt, dass Rot gewinnen wird, wenn das so weitergeht. Es ist wichtig, gegnerische Leitern zu blockieren, ehe sie überhaupt in Gang kommen. Blau hätte das Leiterrennen gewonnen, wenn er früher im Spiel einen seiner Spielsteine in die Nähe des Randes gesetzt hätte.

Neben solchen Fragen werden in dem Buch "Hex Strategies" auch unzählige Varianten des Spieles besprochen. Das Spiel "Y" wird auf einem dreieckigen Brett gespielt; es gewinnt der Spieler, dessen Kette zuerst alle drei Seiten des Dreiecks miteinander verbindet. Wie bei Hex kennt man auch hier nur für sehr kleine Bretter eine Gewinnstrategie.

Oder man spielt Hex auf einer Landkarte der USA. Als Felder dienen die Staaten; der eine Spieler hat die Nord- und die Südgrenze miteinander zu verbinden und der andere die beiden Ozeane. Wenn der Nord-Süd-Spieler den ersten Zug hat, kann er gewinnen, indem er im ersten Zug Kalifornien besetzt.

Hex lässt sich sogar auf einer Kugel spielen, deren Oberfläche in Fünf- und Sechsecke eingeteilt ist. Der Spieler, dem es gelingt, ein leeres oder vom Gegner besetztes Feld einzukreisen, hat gewonnen.

Zum Schluss habe ich noch zwei Hex-Probleme für Sie, mit denen Sie sich in Ihrer Freizeit beschäftigen können. Das erste ist Heins Originalartikel über das Spiel entnommen. Die Aufgabe besteht darin, das Feld zu finden, auf das Rot spielen muss, um den Sieg zu erzwingen. Wenn Ihnen das zu einfach ist, probieren Sie doch die Stellung in D, die der Programmierer Bert Enderton aus Pittsburgh für das 6x6-Brett erfunden hat. Wieder ist das Feld zu finden, auf das Rot setzen muss, um zu gewinnen.

Aus: Spektrum der Wissenschaft 9 / 2002, Seite 118
© Spektrum der Wissenschaft Verlagsgesellschaft mbH