ComputerGo

Aus GoVB

(Unterschied zwischen Versionen)
Wechseln zu: Navigation, Suche
(Basicplayer)
(ToDos)
 
(23 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 4: Zeile 4:
  
 
== ToDos ==
 
== ToDos ==
* Ferstlegung Termin und Teilnehmer (http://doodle.com/rxhszz8r8k3tmbg2)
 
* Ausarbeitung der Gruppenaufteilung (zusammenarbeitende Gruppen ~ jeweils 2-3 Mitglieder)
 
** Gruppen aufteilen in Optimierung verschiedener Parameter (beispielsweise dynamisches Komi), Parallelisierung, zusätzliche Lösungsstrategien zu MCTS o.ä. (dafür nötig eine Grundimplementierung, also mit mCTS und Verständnis aller Teilnehmer wie MCTS arbeitet)
 
* Festlegen des OS für die Hardware
 
* !!!!!!!!!!!!!!!!! Basic-Player evaluieren + nochmal nachfragen ob es noch weitere gibt !!!!!!!!!!!!!!!!!!!!!!!!!!!!
 
* SVN Gastaccounts für teilnehmende Ifis anlegen
 
 
* Eventuelle Kooperation mit BS-Lehrstuhl (Parallelisierung) ---> Dr. Martin von Löwis
 
* Eventuelle Kooperation mit BS-Lehrstuhl (Parallelisierung) ---> Dr. Martin von Löwis
* Vortragsthemen für 3 Gruppen (a ~ 2 Personen) ausarbeiten, hierfür Auswahl der wichtigsten Themen und wichtigsten Paper (diese sollen am Anfang gehalten werden)
+
* komplett kompilieren
 +
* Baum (da real MCTS)
 +
* weiterrechnen während der Gegner dran ist
 +
* Performance Monitoring
 +
* Gabage Collection beim gegnerischen Zug
 +
* eigener MCTS-Thread
 +
* Exception 2D-3D
 +
 
 +
== 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 [http://computer-go.org/pipermail/computer-go/2010-May/000289.html] ) bringen transposition tables bei Go wenig bis gar nix. (eher noch mehr Probleme)
 +
* So nicht! [http://eyetvision.de/fuego-fail.sgf Fuego mit 100.000 Simulationen/Zug (7-8k) gegen Martin (6k)]
  
 
== Eckpunkte ==
 
== Eckpunkte ==
Zeile 17: Zeile 24:
 
=== Bot-Name ===
 
=== Bot-Name ===
  
* (Pingoin)
+
* '''Pingoin'''
 
* Golem!
 
* Golem!
* God/Got/Gott (muss man sich nur nocha usdenken wofür das angeblich stehen sollen)
+
* God/Got/Gott (muss man sich nur noch ausdenken wofür das angeblich stehen sollen)
 +
* PoGo (Potsdam Go :P)
 +
* Stoned
  
 
=== Teilnehmer ===
 
=== Teilnehmer ===
Zeile 25: Zeile 34:
 
* Mailinglist: http://lists.hpi.uni-potsdam.de/listinfo/go2010
 
* Mailinglist: http://lists.hpi.uni-potsdam.de/listinfo/go2010
 
* 6 - 10 Teilnehmer
 
* 6 - 10 Teilnehmer
* Interessenten:
+
** '''Marius Schneider'''
** Marius Schneider
+
** '''Tobias Pfeiffer'''
** Tobias Pfeiffer
+
** '''Martin Büttner'''
** Martin Büttner
+
** '''Martin Köppelmann'''
** Martin Köppelmann
+
** '''Lars Wassermann'''
** Lars Wassermann
+
** '''Henning Klein'''
** Maximilian Schneider?
+
** '''Markus Behrens'''
** Henning Klein
+
** Andre Kunze
+
** Thomas Bünger
+
** Simon Völcker
+
** Lena Herrscheid
+
** Jossekin Beilharz
+
  
 
=== mögliche Vertiefungsgebiete ===
 
=== mögliche Vertiefungsgebiete ===
Zeile 43: Zeile 46:
 
* Monte Carlo Tree Search & co.
 
* Monte Carlo Tree Search & co.
 
** dynamisches Komi
 
** dynamisches Komi
 +
** UCT/RAVE und Freunde
 
* Parallelisierung (Thread / Cluster)
 
* Parallelisierung (Thread / Cluster)
 
* Tsume Go
 
* Tsume Go
Zeile 56: Zeile 60:
 
* jede der Gruppen hält einen vertiefenden Vortrag über ein Thema (schon zu Beginn des Semester ---> Ausarbeitung vorher)
 
* 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)
 
* 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 (--> todos)
+
* Aufteilung in Gruppen und arbeiten an einzelnen themen  
 +
* Bot spielt dann auf KGS etc...
  
 
== Literatur ==
 
== Literatur ==
 
(Auszug aus den Veröffentlichungen der letzten Jahre)
 
(Auszug aus den Veröffentlichungen der letzten Jahre)
  
=== Monte Carlo Tree Search ===
+
==== Monte Carlo Tree Search (1.Vortrag) ====
 
* [http://www.lri.fr/~gelly/paper/SylvainGellyThesis.pdf PHD: A CONTRIBUTION TO REINFORCEMENT LEARNING; APPLICATION TO COMPUTER-GO (SYLVAIN GELLY)] '''MUST-READ''' Kapitel 4
 
* [http://www.lri.fr/~gelly/paper/SylvainGellyThesis.pdf PHD: A CONTRIBUTION TO REINFORCEMENT LEARNING; APPLICATION TO COMPUTER-GO (SYLVAIN GELLY)] '''MUST-READ''' Kapitel 4
* [http://www.lri.fr/~teytaud/eg.pdf Combining expert, offline, transient and online knowledge in Monte-Carlo exploration (Chaslot et.al)]
 
 
* [http://www.personeel.unimaas.nl/G-chaslot/papers/newMath.pdf PROGRESSIVE STRATEGIES FOR MONTE-CARLO TREE SEARCH (Chaslot et.al)]
 
* [http://www.personeel.unimaas.nl/G-chaslot/papers/newMath.pdf PROGRESSIVE STRATEGIES FOR MONTE-CARLO TREE SEARCH (Chaslot et.al)]
 
* [http://www.personeel.unimaas.nl/G-chaslot/papers/crossmcICGA.pdf CROSS-ENTROPY FOR MONTE-CARLO TREE SEARCH (Chaslot et.al)]
 
* [http://www.personeel.unimaas.nl/G-chaslot/papers/crossmcICGA.pdf CROSS-ENTROPY FOR MONTE-CARLO TREE SEARCH (Chaslot et.al)]
Zeile 71: Zeile 75:
 
* [http://www.inference.phy.cam.ac.uk/ph347/CPGS-Report_Hennig.pdf Monte Carlo Temperature Discovery Search for Combinatorial Games (Philipp Hennig)]
 
* [http://www.inference.phy.cam.ac.uk/ph347/CPGS-Report_Hennig.pdf Monte Carlo Temperature Discovery Search for Combinatorial Games (Philipp Hennig)]
 
* [http://remi.coulom.free.fr/CG2006/CG2006.pdf Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search (Rémi Coulom, Crazy Stones)]
 
* [http://remi.coulom.free.fr/CG2006/CG2006.pdf Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search (Rémi Coulom, Crazy Stones)]
 +
* [http://users.soe.ucsc.edu/~dph/mypubs/AMAFpaperWithRef.pdf All moves as first variations(David P. Helmbold and Aleatha Parker-Wood)]
 +
 +
==== Patterns und statische Evaluationsfunktionen (2.Vortrag) ====
 
* [http://remi.coulom.free.fr/Amsterdam2007/MMGoPatterns.pdf Computing Elo Ratings of Move Patterns in the Game of Go (Rémi Coulom, Crazy Stones)]
 
* [http://remi.coulom.free.fr/Amsterdam2007/MMGoPatterns.pdf Computing Elo Ratings of Move Patterns in the Game of Go (Rémi Coulom, Crazy Stones)]
* [http://pasky.or.cz/~pasky/go/compgo-r2.pdf Current Approaches in Computer Go (Slides) (Petr Baudis)]
+
* [http://www.lri.fr/~teytaud/eg.pdf Combining expert, offline, transient and online knowledge in Monte-Carlo exploration (Chaslot et.al)]
 +
* [http://lie.math.brocku.ca/twolf/papers/IEEE10.pdf A Dynamical Systems Approach for Static Evaluation in Go (Thomas Wolf)]
 +
* [https://webdisk.lclark.edu/drake/publications/GAMEON-07-drake.pdf MOVE ORDERING VS HEAVY PLAYOUTS (Peter Drake et.al)]
 +
* [http://www.science.uva.nl/research/ias/alumni/m.sc.theses/theses/EmilNijhuis.pdf Learning Patterns in the Game of Go (MSc Thesis Emil H.J. Nijhuis)]
  
==== Parallelisierung ====
+
==== Parallelisierung (3.Vortrag) ====
 
* [http://www.personeel.unimaas.nl/m-winands/documents/multithreadedMCTS2.pdf Parallel Monte-Carlo Tree Search (Chaslot et.al)]
 
* [http://www.personeel.unimaas.nl/m-winands/documents/multithreadedMCTS2.pdf Parallel Monte-Carlo Tree Search (Chaslot et.al)]
 
* [http://www.geocities.jp/hideki_katoh/publications/gpw08-private.pdf Parallel Monte-Carlo Tree Search with Simulation Servers (KATO, TAKEUCHI)]
 
* [http://www.geocities.jp/hideki_katoh/publications/gpw08-private.pdf Parallel Monte-Carlo Tree Search with Simulation Servers (KATO, TAKEUCHI)]
 
* [http://hal.archives-ouvertes.fr/docs/00/28/78/67/PDF/icin08.pdf THE PARALLELIZATION OF MONTE-CARLO PLANNING (S. Gelly et.al)]
 
* [http://hal.archives-ouvertes.fr/docs/00/28/78/67/PDF/icin08.pdf THE PARALLELIZATION OF MONTE-CARLO PLANNING (S. Gelly et.al)]
 +
* [http://webdocs.cs.ualberta.ca/~emarkus/publications/enzenberger-mueller-acg12.pdf A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm (Martin Müller et.al)]
  
=== Other ===
+
==== Other ====
 
* [http://www.unimaas.nl/games/files/phd/Van%20der%20Werf_thesis.pdf PHD: AI techniques for the game of Go (2004) (Erik van der Werf)]
 
* [http://www.unimaas.nl/games/files/phd/Van%20der%20Werf_thesis.pdf PHD: AI techniques for the game of Go (2004) (Erik van der Werf)]
 
* [http://books.nips.cc/papers/files/nips17/NIPS2004_0747.pdf Modelling Uncertainty in the Game of Go (David H. Stern et.al)]
 
* [http://books.nips.cc/papers/files/nips17/NIPS2004_0747.pdf Modelling Uncertainty in the Game of Go (David H. Stern et.al)]
Zeile 86: Zeile 97:
 
* [http://webdocs.cs.ualberta.ca/~mmueller/ps/yoshizoe.pdf Lambda Depth-first Proof Number Search and its Application to Go (Yoshizoe, Kishimoto, M. Müller)]
 
* [http://webdocs.cs.ualberta.ca/~mmueller/ps/yoshizoe.pdf Lambda Depth-first Proof Number Search and its Application to Go (Yoshizoe, Kishimoto, M. Müller)]
 
* [http://www.science.uva.nl/research/ias/alumni/m.sc.theses/theses/EmilNijhuis.pdf MSc Thesis: Learning Patterns in the Game of Go (Emil H.J. Nijhuis)]
 
* [http://www.science.uva.nl/research/ias/alumni/m.sc.theses/theses/EmilNijhuis.pdf MSc Thesis: Learning Patterns in the Game of Go (Emil H.J. Nijhuis)]
 +
* [http://pasky.or.cz/~pasky/go/compgo-r2.pdf Current Approaches in Computer Go (Slides) (Petr Baudis)]
  
 
== Basicplayer ==
 
== Basicplayer ==
Zeile 93: Zeile 105:
 
** [https://plug-and-go.dev.java.net/ plug-and-go]
 
** [https://plug-and-go.dev.java.net/ plug-and-go]
 
** [http://www.google.com/url?sa=D&q=http://cgos.boardspace.net/public/javabot.zip&usg=AFQjCNHAZJiQ-ak-3pwvZRokIF8ID2xhQQ Java-Bot by Don Dailey]
 
** [http://www.google.com/url?sa=D&q=http://cgos.boardspace.net/public/javabot.zip&usg=AFQjCNHAZJiQ-ak-3pwvZRokIF8ID2xhQQ Java-Bot by Don Dailey]
 +
** [http://gogui.sourceforge.net/doc/reference-dummy.html GoGui-Dummy]
 
** [http://legacy.lclark.edu/~drake/Orego.html Orego]
 
** [http://legacy.lclark.edu/~drake/Orego.html Orego]
 
* C++
 
* C++
Zeile 111: Zeile 124:
 
* [http://www.mail-archive.com/computer-go@computer-go.org/info.html Go-Mailingliste]
 
* [http://www.mail-archive.com/computer-go@computer-go.org/info.html Go-Mailingliste]
 
* [http://www.dgob.de/yabbse/index.php?board=27.0 DGoB-Forum Computer-Sektion]
 
* [http://www.dgob.de/yabbse/index.php?board=27.0 DGoB-Forum Computer-Sektion]
 +
* [http://www.citeulike.org/group/5884/library computer go library]
  
 
=== andere Player ===
 
=== andere Player ===

Aktuelle Version vom 17. Juni 2010, 09:12 Uhr

Inhaltsverzeichnis

[Bearbeiten] Computer-Go am HPI

Ideensammlung zum Computer-Go-Seminar des HPI

[Bearbeiten] 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
  • Exception 2D-3D

[Bearbeiten] 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)

[Bearbeiten] Eckpunkte

[Bearbeiten] Bot-Name

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

[Bearbeiten] Teilnehmer

[Bearbeiten] 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)

[Bearbeiten] 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...

[Bearbeiten] Literatur

(Auszug aus den Veröffentlichungen der letzten Jahre)

[Bearbeiten] Monte Carlo Tree Search (1.Vortrag)

[Bearbeiten] Patterns und statische Evaluationsfunktionen (2.Vortrag)

[Bearbeiten] Parallelisierung (3.Vortrag)

[Bearbeiten] Other

[Bearbeiten] Basicplayer

[Bearbeiten] Links

[Bearbeiten] online spielen

[Bearbeiten] Community

[Bearbeiten] andere Player

[Bearbeiten] something else

Meine Werkzeuge
Ansichten