TUD Computer Poker Challenge - SS 08

News

Die Noten hängen nun am Aushang des Fachgebiets (neben Raum S202/E306) aus.

Die Resultate des Abschlussturnieres liegen nur vor.

Der wiki ist nun online.

Die Ausarbeitungen und Folien sind nun als einzelne pdfs verfügbar. Die "Proceedings" sind hier verfügbar.

Beschreibung

• Seminar aus Knowledge Engineering in Spielen (2 SWS)
• Praktikum aus Künstliche Intelligenz (4 SWS)

Nach Maßgabe freier Plätze kann auf Anfrage auch eine der beiden Veranstaltungen für sich belegt werden, Priorität haben jedoch Studenten, die beides absolvieren.

Inhalt

Das Ziel der Challenge ist der Entwurf und die Implementierung eines intelligenten Spielers für (Multiplayer Limit) Texas Hold'em Poker. Die Teilnehmer an der Challenge implementieren alleine oder in Kleingruppen (max. 2-3 Teilnehmer) einen Spieler, die Spieler werden sich dann abschließend in einem Turnier aller Teilnehmer messen. Eventuell (bei befriedigenden Ergebnissen) werden wir auch eine Teilnahme an der Computer Poker Challenge, die im Juli von der AAAI-08, der amerikanischen Gesellschaft für Künstliche Intelligenz, im Rahmen ihrer jährlichen Tagung veranstaltet wird, in Erwägung ziehen.

Organisation

Die Veranstaltung beginnt mit einer Vorbesprechung am Freitag, dem 7. 3. 2008, ab 13 Uhr in Raum S202/E302. In der Vorbesprechung werden

• die Teilnahmeplätze endgültig vergeben
• wir den Ablauf des Praktikums durchbesprechen
• die Vortragsthemen für das Seminar vergeben

Die Vortragsthemen werden in Kürze verfügbar sein. Es werden dabei ausschließlich Themen behandelt, die für Computer Poker relevant sind. In Summe werden nicht mehr als 10 Themen vergeben werden.

Seminar

Das Block-Seminar findet am 31. 3. 2008 ganztägig ab 9 Uhr in Raum A313 statt. Hier werden die Teilnehmer Vorträge über das gewählte Thema halten. Jeder Vortrag soll nicht länger als 30 min (20 min pro Person plus ca. 10 min Diskussion des Themas der Gruppe) dauern, sodaß noch ausreichend Zeit für Diskussionen bleibt. Ziel ist es, den anderen Teilnehmern einen Überblick über das eigene Themengebiet zu geben, sodaß alle Teilnehmer rasch einen Überblick über weiterführende Literatur für die Arbeit an dem eigenen Bot erhalten.

Ausarbeitung: Die Ausarbeitung sollte die für das folgende Praktikum relevanten Aspekte der im Vortrag vorgestellten Arbeiten umfassend darstellen, sodaß sich auch andere Gruppen bei Bedarf rasch in die Thematik einarbeiten können. Der Umfang der Ausarbeitungen ist nebensächlich, wesentlich ist der Inhalt. Eine grobe Richtlinie sind 7-10 Seiten, wobei im allgemeinen kürzere Darstellungen, die die wesentlichen Aspekte auf den Punkt bringen, besser sind als längere, die dem Leser wenig Anhaltspunkte auf das Wesentliche geben. Aber auch größere Abweichungen nach oben oder unten sind durchaus zulässig, solange sie inhaltlich gerechtfertigt sind.

Im April und Mai wird dann von allen Gruppen an Ihren Lösungen gearbeitet. In dieser Zeit wird es regelmäßige Treffen zum Erfahrungsaustausch geben (voraussichtlich Mittwoch, 16:00-17:30, Raum A126, wobei die Häufigkeit und Dauer dieser Treffen variieren wird). Die Abgaben sind Ende Mai fällig, sodaß wir dann noch gegebenfalls eine Teilnahme an der AAAI-08 Computer Poker Challenge (Deadline 1. Juni) in Betracht ziehen können.

Praktikum

Vortrag: Am 17. Juni, 16:15 Uhr und am 25. Juni, 15:15 Uhr finden die beiden Treffen für die Abschlußvorträge in Raum A126 statt.

Ausarbeitung: Die Ausarbeitungen sollten bis zum 16.06.2008 für die Vorträge am 17. Juni und bis zum 18.06.2008 für die Vorträge am 25. Juni bei uns vorliegen. Sie sollten ca. 5-10 Seiten pro Gruppe umfassen. Das Vorgehen im Praktikum, sowie die verwendeten Algorithmen sollten dokumentiert werden. Ebenfalls erwünscht sind Bezüge auf das vorangegangene Seminar.

Hinweis: Die Ausarbeitungen sollten im gleichen Format wie die Seminarausarbeitungen angefertigt werden (Jair-Style). Wir bitten auch darauf zu achten, dass die Form eines papers (Abstract, Introduction, Sections, Conclusions, References) gewahrt bleibt. Da in vielen Seminarausarbeitungen nicht auf Rechtschreibung geachtet wurde, bitten wir darum, dass jede Gruppe eine Rechtschreibprüfung ihres Dokuments durchführt.

Zeitplan

Hier nochmals die wichtigsten Termine zusammengefasst:

7. März

Generelle Vorbesprechung und Vergabe der Seminar-Themen

31. März

ganztägiges Blockseminar

April / Mai

Arbeit an den Poker-Bots, regelmäßige Treffen, voraussichtlich Mittwoch nachmittag, 15:15

25. Mai

Abgabe der Bots

28. Mai

Resultate des internen Turniers

1. Juni

Deadline für Einreichungen an der AAAI-08 Computer Poker Challenge

16. bzw. 18. Juni

Abgabe der Ausarbeitungen des Praktikums

17. und 25. Juni

Abschlußvorträge über die implementierte Lösung

Teilnahme und Anmeldung

Die Plätze für die Teilnahme sind begrenzt und werden von uns vergeben. Kriterien für die Auswahl sind (die Reihenfolge sagt nichts über die Gewichtung):

• Starkes Interesse an Texas Hold'em Poker
• Vorkenntnisse in Maschinellem Lernen und Künstlicher Intelligenz
• Programmiererfahrung in Computer-Spielen
• Studienleistungen
• Anmeldezeitpunkt

Bei Interesse schicken melden Sie sich bitte unter ke@informatik.tu-darmstadt.de an. Legen Sie Ihrer Anmeldung bitte ein kurzes Statement bei, warum Sie an der Teilnahme besonders interessiert sind (ein Absatz genügt).

Die endgültige Vergabe der Plätze erfolgt in der Vorbesprechung.

Beurteilung

Die Lösungen können in Gruppenarbeit (1-3 Teilnehmer pro Gruppe) erstellt werden. Beurteilt wird Ihr Engagement für die Challenge, die Mitarbeit in den Seminarvorträgen und Praktikumstreffen, Ihre Vorträge (Seminar und Abschluß- Vortrag, sowie natürlich die Qualität Ihres Lösungsweges.

Gutes Abschneiden im Wettbewerb wird ebenfalls notenrelevant sein, jedoch sicher nicht das einzige Kriterium sein. Insbesondere gilt die Umkehrung nicht, d.h. schlechtes Abschneiden bedingt nicht notwendigerweise eine schlechte Note (hier fliessen auch Dinge wie die Orginalität und Kreativität der Lösung mit ein).

Es ist geplant, eine gemeinsame Note für beide Veranstaltungen (Seminar und Praktikum) zu vergeben, jedoch behalten wir uns vor, ggf. auch von diesem Prinzip abzuweichen.

Gruppen

1. Oliver Uwira und Hendrik Schaffer
2. Thomas Görge, Lars Meyer und Timo Bozsolik
3. Marian Wieczorek und Michael Wächter
4. Björn Heidenreich und Andreas Eismann
5. Michael Herrmann und Arno Mittelbach
6. Bastian Christoph und Benjamin Herbert
7. Claudio Weck und Stefan Lück
8. Immanuel Schweizer, Alexander Marinc und Kamill Panitzek

Themen

Einführung in die menschlichen Strategien (Oliver Uwira und Hendrik Schaffer) (Folien)

Übersichtsartikel (Björn Heidenreich und Andreas Eismann) (Folien Heidenreich, Folien Eismann)

• Michael Johansson's M.Sc. thesis. Robust Strategies and Counter-Strategies: Building a Champion Level Computer Poker Player.
  
• Darse Billings, Lourdes Pena, Jonathan Schaeffer, and Duane Szafron. The challenge of poker. Artificial Intelligence, 134(1-2):201-240, January 2002. Special Issue on Games, Computers and Artificial Intelligence.
  

Klassische Artikel (Immanuel Schweizer und Kamill Panitzek) (Folien)

• Nicholas V. Findler. Studies in machine cognition using the game of poker. Communications of the ACM, 20(4):230-245, April 1977.
• Nicholas V. Findler. Computer poker. Scientific American, pages 112-119, 1978
• D. A. Waterman. A generalization learning technique for automating the learning of heuristics. Artificial Intelligence, 1:121-170, 1970.
• Stephen F. Smith. Flexible learning of problem solving heuristics through adaptive search. In Proceedings of the 8th International Joint Conference on Artificial Intelligence (IJCAI-83), pages 421-425, Los Altos, CA, 1983. Morgan Kaufmann.

Approximieren des spieltheoretischen Optimums 1 (Claudio Weck und Stefan Lück) (Folien)

• Daphne Koller, Avi Pfeffer: Representations and Solutions for Game-Theoretic Problems. Artificial Intelligence 94(1-2): 167-215 (1997)
• Peter Bro Miltersen and Troels Bjerre Sorensen. A Near-Optimal Strategy for a Heads-Up No-Limit Texas Hold'em Poker Tournament. AAMAS '07: Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems. ACM, 2007.

Approximieren des spieltheoretischen Optimums 2 (Alexander Marinc) (Folien)

• M. Zinkevich, M. Bowling, M. Johanson and C. Piccione. Regret Minimization in Games with Incomplete Information. Advances in Neural Information Processing Systems (NIPS 2007) , 2007.
• William Dudziak. Using Fictitious Play to Find Pseudo-optimal Solutions for Full-scale Poker. In Proceedings of the 2006 International Conference on Artificial Intelligence (ICAI-2006), pages 374-380, 2006.

Abstraktion (Marian Wieczorek) (Folien)

• Darse Billings, Neil Burch, A. Davidson, Robert Holte, Jonathan Schaeffer, Terence Schauenberg and Duane Szafron. Approximating Game-Theoretic Optimal Strategies for Full-scale Poker. International Joint Conference on Artificial Intelligence (IJCAI), pp. 661-668, 2007.
• Andrew Gilpin and Tuomas Sandholm. A Competitive Texas Hold'em Poker Player via Automated Abstraction and Real-Time Equilibrium Computation. AAAI, AAAI Press, 2006.
  

Opponent Modeling (Timo Bozsolik, Lars Meyer und Thomas Görge) (Folien Meyer und Görge, Folien Bozsolik)

• Bret Hoehn, Finnegan Southey, Robert C. Holte and Valeriy Bulitko. Effective Short-Term Opponent Exploitation in Simplified Poker. Proceedings AAAI'05, pp. 783-788.
• Darse Billings, Denis Papp, Jonathan Schaeffer, and Duane Szafron. Opponent modeling in poker. In Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98), pages 493-498, Madison, WI, 1998. AAAI Press.
• Aaron Davidson, Darse Billings, Jonathan Schaeffer, and Duane Szafron. Improved opponent modelling in poker. In Proceedings of the International Conference on Artificial Intelligence (ICAI-2000), pages 1467-1473, Las Vegas, Nevada, 2000.
• Darse Billings, Aaron Davidson, Terence Schauenberg, Neil Burch, Michael Bowling, Robert C. Holte, Jonathan Schaeffer and Duane Szafron. Game-Tree Search with Adaptation in Stochastic Imperfect-Information Games. Computers and Games, Lecture Notes in Computer Science, Vol. 3846, pp. 21-34, Springer, 2004.
  

Das erste Paper (zum Thema Stein/Schere/Papier) ist bei uns im Büro (S202/E306) auszuleihen, da es online nicht verfügbar sind

• Billings, D. (2000). Thoughts on RoShamBo. ICGA Journal, Vol. 23, No. 1, pp. 3-8.
• Daniel Egnor (2000). Iocaine Powder. ICGA Journal, Vol. 23, No. 1.

Hier noch 2 Links zum Thema:

• The Second International RoShamBo Programming Competition
• Results

Evolutionäre Algorithmen (Arno Mittelbach und Michael Herrmann) (Folien)

• Jason Noble. Finding robust Texas Hold'em poker strategies using pareto coevolution and deterministic crowding. In Proceedings of the 2002 International Conference on Machine Learning and Applications (ICMLA-02), CSREA Press, 2002.
• Jason Noble and R. A. Watson. Pareto co-evolution: Using performance against coevolved opponents in a game as dimensions for pareto selection. In L. Spector, E. Goodman, A. Wu, W.B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon, and E. Burke, editors, Proceedings of the Genetic and evolutionary Computation Conference (GECCO-01), pages 493-500, 2001.
• Luigi Barone, Lyndon While. Evolving Computer Opponents to Play a Game of Simplified Poker. Proceedings of the 8th University of Western Australia Computer Science Research Conference.
• Luigi Barone and Lyndon While. An adaptive learning model for simplified Poker using evolutionary algorithms. In Proceedings of the 1st Congress on Evolutionary Computation (CEC-99), pages 153-160, Washington, DC, 1999. IEEE Press.
• Graham Kendall and Mark Willdig. An investigation of an adaptive Poker player. In Proceedings of the 14th Australian Joint Conference on Artificial Intelligence (AI-01), pages 189-200, Adelaide, Australia, 2001. Springer-Verlag.

Reinforcement Learning (Bastian Christoph) (Folien)

• Fredrik A. Dahl. A reinforcement learning algorithm applied to simplified two-player texas hold'em poker. In L. De Raedt and P. Flach, editors, Proceedings of the 12th European Conference on Machine Learning (ECML-01), pages 85-96, Freiburg, Germany, September 2001. Springer-Verlag.
• Fredrik A. Dahl. The lagging anchor algorithm: Reinforcement learning in two-player zero-sum games with imperfect information. Machine Learning, 49(1):5-37, October 2002.

SVMs und Kategorisierung der Spieler (Benjamin Herbert) (Folien)

• T. Blank, Soh Leen-Kiat and S. Scott. Creating an SVM to Play Strong Poker. Proceedings of the International Conference on Machine Learning and Applications (ICMLA’2004), Louisville, KY, December 16-18, pp. 150-155.
  
• Ulf Johansson, Cecilia Sonstrod and Lars Niklasson. Explaining Winning Poker--A Data Mining Approach. 5th International Conference on Machine Learning and Applications (ICMLA'06), pp. 129-134, 2006.
  

Monte-Carlo Tree Search (Michael Wächter) (Folien)

• L. Kocsis, C. Szepesvari. Bandit Based Monte Carlo Planning. Proceedings ECML-07, Springer Verlag, 2007.
• R. Coulom. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search, Proceedings Computers and Games (CG-06), Springer-Verlag, 2006.

Veranstalter

Die Challenge wird betreut von

• Johannes Fürnkranz
• Ulf Lorenz
• Frederik Janssen
• Sang-Hyeun Park
• Eneldo Loza
• Jan-Nikolas Sulzmann