Version vom 17. Juni 2010, 09:03 Uhr

Computer-Go am HPI

Ideensammlung zum Computer-Go-Seminar des HPI

ToDos

• Eventuelle Kooperation mit BS-Lehrstuhl (Parallelisierung) ---> Dr. Martin von Löwis
• komplett kompilieren
• Baum (da real MCTS)
• weiterrechnen während der Gegner dran ist
• Performance Monitoring
• Gabage Collection beim gegnerischen Zug
• eigener MCTS-Thread

Ideenecke

(hier kann man kurze Ideen die man zum Seminar hat erstmal für alle lesbar zwischenspeichern)

• Auf den Systemen dann mindestens GnuGo installieren und die Schnittstelle implementieren um unseren Bot gegen GnuGo spielen zu lassen (GnuGo benutzt wohl kein MCTS sondern Alpha/Beta Suche und wird darum wohl gerne zum evaluieren von MCTS Bots genommen, da GnuGo ja unter Umständen auch bedeutend schneller spielt als menschliche Spieler)
• Nur ein Gedanke: JAPARA für Zufallszahlen... research needed
• Laut der Mailinglist ( siehe [1] ) bringen transposition tables bei Go wenig bis gar nix. (eher noch mehr Probleme)
• So nicht! Fuego mit 100.000 Simulationen/Zug (7-8k) gegen Martin (6k)

Eckpunkte

Bot-Name

• Pingoin
• Golem!
• God/Got/Gott (muss man sich nur noch ausdenken wofür das angeblich stehen sollen)
• PoGo (Potsdam Go :P)
• Stoned

Teilnehmer

• Mailinglist: http://lists.hpi.uni-potsdam.de/listinfo/go2010
• 6 - 10 Teilnehmer
  • Marius Schneider
  • Tobias Pfeiffer
  • Martin Büttner
  • Martin Köppelmann
  • Lars Wassermann
  • Henning Klein
  • Andre Kunze
  • Markus Behrens

mögliche Vertiefungsgebiete

• Monte Carlo Tree Search & co.
  • dynamisches Komi
  • UCT/RAVE und Freunde
• Parallelisierung (Thread / Cluster)
• Tsume Go
• direction of play
• statische Evaluationsfunktionen
• Kombination von verschiedenen Ansätzen (MCTS, direction of play, statische Evaluation...)
• Parameter Tuning
• Evaluieren des Players (menschliche / computer- Gegner)

Aufbau (Ideen)

• zuerst einführender Vortrag von Manju
• jede der Gruppen hält einen vertiefenden Vortrag über ein Thema (schon zu Beginn des Semester ---> Ausarbeitung vorher)
• Danach wird das Basisprinzip implementiert (MCTS), dies muss von allen umfassend verstanden werden (auch wenn nciht alle implementierne können)
• Aufteilung in Gruppen und arbeiten an einzelnen themen
• Bot spielt dann auf KGS etc...

Literatur

(Auszug aus den Veröffentlichungen der letzten Jahre)

Monte Carlo Tree Search (1.Vortrag)

• PHD: A CONTRIBUTION TO REINFORCEMENT LEARNING; APPLICATION TO COMPUTER-GO (SYLVAIN GELLY) MUST-READ Kapitel 4
• PROGRESSIVE STRATEGIES FOR MONTE-CARLO TREE SEARCH (Chaslot et.al)
• CROSS-ENTROPY FOR MONTE-CARLO TREE SEARCH (Chaslot et.al)
• Combining Final Score with Winning Percentage by Sigmoid Function in Monte-Carlo Simulations (SHIBAHARA, KOTANI)
• On the Laziness of Monte-Carlo Game Tree Search in Non-tight Situations (Ingo Althofer)
• Transpositions and Move Groups in Monte Carlo Tree Search (Benjamin E. Childs et.al)
• Monte Carlo Temperature Discovery Search for Combinatorial Games (Philipp Hennig)
• Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search (Rémi Coulom, Crazy Stones)
• All moves as first variations(David P. Helmbold and Aleatha Parker-Wood)

Patterns und statische Evaluationsfunktionen (2.Vortrag)

• Computing Elo Ratings of Move Patterns in the Game of Go (Rémi Coulom, Crazy Stones)
• Combining expert, offline, transient and online knowledge in Monte-Carlo exploration (Chaslot et.al)
• A Dynamical Systems Approach for Static Evaluation in Go (Thomas Wolf)
• MOVE ORDERING VS HEAVY PLAYOUTS (Peter Drake et.al)
• Learning Patterns in the Game of Go (MSc Thesis Emil H.J. Nijhuis)

Parallelisierung (3.Vortrag)

• Parallel Monte-Carlo Tree Search (Chaslot et.al)
• Parallel Monte-Carlo Tree Search with Simulation Servers (KATO, TAKEUCHI)
• THE PARALLELIZATION OF MONTE-CARLO PLANNING (S. Gelly et.al)
• A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm (Martin Müller et.al)

Other

• PHD: AI techniques for the game of Go (2004) (Erik van der Werf)
• Modelling Uncertainty in the Game of Go (David H. Stern et.al)
• Learning Position Evaluation for Go with Internal Symmetry Networks (Neuronale Netze) (Alan Blair)
• Coevolving Partial Strategies for the Game of Go (Genetic algorithm) (lokale Kopie)
• Lambda Depth-first Proof Number Search and its Application to Go (Yoshizoe, Kishimoto, M. Müller)
• MSc Thesis: Learning Patterns in the Game of Go (Emil H.J. Nijhuis)
• Current Approaches in Computer Go (Slides) (Petr Baudis)

Basicplayer

• Java
  • plug-and-go
  • Java-Bot by Don Dailey
  • GoGui-Dummy
  • Orego
• C++
  • fuego
• Go
  • Gongo

Links

online spielen

• Computer Go Server
• Connecting a Go-playing program to KGS
• Computer Go Tournaments on KGS

Community

• Go-Mailingliste
• DGoB-Forum Computer-Sektion
• computer go library

andere Player

• kifoo (FU Berlin)
• mogo (Uni Paris)
• fuego (Kanada Alberta)
• gnugo
• crazy stones
• NeuroGo (University of California)
• GoTools (Thomas Wolf) (Tsume Go)
• PD Dr. rer. nat. Ulf Lorenz (Darmstadt) (kein Player)

something else

• why programmers should play go
• SGF-Format Spezifikation
• Shodan Go Bet