StartseiteMathlog

Computer schlägt Go-Profi – mit Vorgabe

Von / 20. August 2008 / 5 Kommentare
Mehr

Das Brettspiel Go ist wesentlich komplexer als Schach und deshalb können Computer dort dem Menschen noch keine Konkurrenz machen. Die besten Programme spielen allenfalls auf Amateur-Niveau. So sorgte am 5.8. die Meldung, daß der holländische Supercomputer Huygens gegen Kim Myung Hwan (den Sieger des letzten US-Open) gewonnen hat, für einiges Aufsehen.

Verwendet wurde das Programm “MoGoTitan”.

Die Nachricht relativiert sich aber etwas, wenn man weiß, daß Hwan dem Computer ein Handicap gewährte, nämlich vor Beginn der Partie neun Steine auf wichtigen Zentralfeldern zu platzieren.

Ich spiele kein Go und kann deshalb nicht einschätzen, wie viel dieses Handicap tatsächlich ausmacht. Auch die Kommentatoren bei Stefan Löffler sind nicht ganz einig.

Aus der SARA-Mitteilung: “Huygens, ein IBM Power 575 Hydro-Cluster-System, ist der neue niederländische nationale Supercomputer. Das System hat eine Spitzengeschwindigkeit von 60 Billionen Berechnungen pro Sekunde (Teraflop/s), 3328 Power6 Prozessorkerne mit 4,7 GHz, eine Gesamtspeicherkapazität von mehr als 15 TB und nahezu 1000 TB Festplattenkapazität. Das gesamte System befindet sich seit 1. August dieses Jahres in Betrieb. Mithilfe der engagierten Mitarbeiter von SARA konnte die Go-Anwendung innerhalb kürzester Zeit auf dem neuen System einsatzfähig gemacht werden.”

Über mathematische Details erfährt man leider nur, daß Monte-Carlo-Suchverfahren eine Rolle spielen.

Bei Gobase kann man die Partie nachspielen.

(Der Kampf fand während des Go-Kongresses in Portland statt. Das Foto unten ist von einem anderen Go-Kongreß, paßt aber trotzdem.)

i-30cdc8ab6846f5edb0aa8cd11fecf584-leksand.jpg

Quelle: https://schachblaetter.de/1450/16-08-2008/

Stichworte: , , , ,
Mehr

Kommentare (5)

  1. #1 Thilo Kuessner
    9. März 2009

    Stephane Lamy schreibt zum selben Thema auf
    https://images.math.cnrs.fr/Un-ordinateur-medaille-Fields.html

    “[…]
    Die zentrale Idee des Programms ist grob wie folgt. Um in einer bestimmten Stellung einen Zug zu bewerten, spielt das Programm diesen Zug, beendet danach die Partie durch eine völlig zufällige Abfolge von schwarzen und weißen Zügen und merkt sich das Ergebnis. Das Programm wiederholt dies viele Male (sagen wir eine Million zufälliger Partien mit diesem ersten Zug) und die Bewertung des getesteten Zugs ist der Durchschnitt der Ergebnisse. Das Programm spielt dann den Zug, der die beste Note erhielt. Auf den ersten Blick erscheint es mir absolut erstaunlich, dass ein solcher Algorithmus (selbst mit ein paar Regeln heuristischer Vorauswahl für eine Liste “plausibler” Züge) erfolgreich sein kann. Und dennoch, es funktioniert!
    In den Artikeln nennen die Experten dieses Vorgehen: Monte-Carlo-Methode.
    […]”

  2. #2 BLANKENSHIPMiranda31
    13. Mai 2010

    Have no enough cash to buy some real estate? Do not worry, just because it’s real to take the http://www.lowest-rate-loans.com to work out such problems. Hence get a commercial loan to buy all you need.
    Link gelöscht

  3. #3 Christian A.
    14. Mai 2010

    Das Ziel beim Go ist es ja, Gebiet abzugrenzen. Dies Gebiet wird am Spielschluss durch eine ununterbrochene Folge eigener Steine angezeigt (Es gibt im Allgemeinen aber viele getrennte Gebiete pro Spieler). Am Anfang und im Mittelteil ist das Gebiet aber nicht wichtig; wichtig sind vielmehr sehr abstrakte Größen, die als “Einfluß der Steine” zusammengefasst werden. Darunter fällt zum Beispiel auch die Effizienz der eigenen Steine (wieviele Steine habe ich gesetzt, um einen bestimmten Einfluß zu erreichen usw.). Auf dieser Ebene scheitern Computer im Allgemeinen noch sehr, es gibt aber schon lange Ansätze einem Computer auch Positionsbeurteilung beizubringen, z.B. mit Hilfe von neuronalen Netzen (*).

    Zum Handicap: Das Handicap besteht aus Steinen, die auf vorbestimmten Plätzen ausgelegt werden. Es ist ein sehr feines System; pro zehn Punkte Unterschied im mittleren Spiel zweier Spieler wird ein zusätzlicher Stein ausgelegt. 9 Steine ist eine Menge Holz. Ich kann mir vorstellen, dass ein Computer aus den 9 Steinen einen überproportionalen Vorteil zieht, weil er früher Endspielzüge machen kann. Im Endspiel kommt es eher darauf an, mit konkreten Steinen und Zügen zu rechnen, da sind Computer durch ihre brute-force Methoden auch heute schon ziemlich gut, denke ich.

    (*) Im Prinzip ist das ähnlich wie das, was der Rechner gemacht hat: Man gibt sehr viele Spiele in das System ein, und der Computer macht so etwas wie eine Mittelung der End-Ergebnisse über ähnliche Positionen (Beispielsweise: Temporal Difference Learning Go, Sejnowski et. al. 1994). Allerdings wird die Positionsbeurteilung vorher gelernt, nicht on-the-fly im Spiel durchgeführt.

  4. #4 Ketzu
    16. Mai 2010

    In Turnieren habe ich es kennen gelernt, das pro Rangstufe Unterschied ein zusätzlicher Stein an Vorgabe gewährt wird (also ab 2 Stufen Unterschied wird eine Vorgabe gewährt, da nur 1 Stein Vorgabe Unsinn wäre). Allerdings kenne ich das auch nur so bis ~5 Steinen Vorgabe.
    Gegen einen 6 Dan Profi (wenn ich das gerade richtig gesehen habe), entspräche das in etwas einem Rang eines mittleren Amateur Dans, was für ein Go-Programm äußerst gut ist.

    Verschiedene Programme versuchen die Monte-Carlo Alogrithmen mit Daten zu lokalen Stellungen, Joseki, Fuseki und was es sonst noch an Zugfolgen gibt zu kombinieren um bessere Ergebnisse zu erzielen. So werden die Spiele nach einem angenommenen Zug eben nicht komplett zufällig zu ende gespielt, sondern eben nach solchen evaluierten Zugfolgen wenn möglich. Das klingt so weit sehr viel versprechend, aber man sieht, das man selbst damit noch nicht viel weiter als mittleres Amateurlevel gekommen ist, im Vergleich zu Schach ist da doch ziemlich erstaunlich, wenn man bedenkt das jedes halbwegs ordentliche Schachprogramm schon wirklich gut spielen kann. 🙂

  5. #5 Rolf
    31. Oktober 2010

    Als Go Spieler will ich nur mal zwei wichtige Links beisteuern:
    Auf https://www.computer-go.info/h-c/index.html findet man eine Historie von Mensch Maschine Spielen die die Entwicklung des Computer Go recht gut zeigt. Gerade in den letzten Jahren gab es schon grosse Fortschritte. Allerdings ist ein 9 oder 7 Steine Handicap sehr groß (führt auf jeden Fall in den Amateur Bereich, das heisst ein Profi wird im allgemeinen gegen jeden anderen Profi mit dieser Vorgabe gewinnen) Und dann natürlich https://www.dgob.de die Seite des Go-Bunds mit allen relevanten Links.