Seminar: Knowledge Engineering und Lernen in Spielen - SS 04

Benotung: Die Noten für das Seminar sind vergeben und können ab 26.7. jeweils vormittags im Sekretariat erfragt werden (E304). Allerdings habe ich festgestellt, daß ich von den meisten von Ihnen keine Matrikelnummer habe, die ich aber für einen Aushang der Noten brauche! Bitte diese umgehend an Frau Ploch schicken!

Inhalt

Im Rahmen dieses Seminars werden wir wissensbasierte Ansätze für intelligente Computer-Spieler betrachten. Schwerpunkt wird dabei auf Lern-Ansätzen sein, jedoch stehen auch andere Themen zur Auswahl.

Studenten erhalten 2-3 zusammenhängende Fachartikel zur Bearbeitung, deren wesentliche Aspekte dann in einem ca. 45-minütigen Kurz-Vortrag (30 min Vortrag, 15 min Diskussion) präsentiert werden sollen. Es steht (nach Rücksprache) auch frei, anstatt der Fachartikel eine praktische Erprobung eines bekannten oder eigenes Ansatzes zu erarbeiten und zu präsentieren. Studenten können auch selbständig einen Themenvorschlag einbringen. Eine umfangreiche Bibliographie über dieses Gebiet finden Sie hier.

Ort und Zeit:

Geänderte Zeiten für die Seminartermine mit drei Vorträgen (8.6., 15.6. 29.6.):
jeweils Dienstag, 15:55 - 18:15, Raum S2/02|A102.

Mai	4.5.	11.5.	18.5.	25.5.
Juni	1.6.	8.6.	15.6.	22.6.	29.6.

Lehrveranstaltung 20.410.4 im TUD Vorlesungsvorzeichnis

Vorträge:

Es wird erwartet, daß Sie die Vorträge mit Slides begleiten. Falls Sie keinen Laptop haben, bitte mir die Slides rechtzeitig zu senden, damit ich Sie auf meinem Laptop einspielen bzw. testen kann. Die Vorträge und/oder Slides können wahlweise auf Deutsch oder Englisch gehalten werden.

4.5.

Poker (Daniel Schreiber)
TD-Gammon (Aristotelis Hadjakos)

11.5.

TD-learning in chess-like games (Thu Trang Pham Thi)
Paradise (Michael Achenbach)

18.5.

Opening Book (Widjaja)
Perfect Games (Johannes Clos)

25.5.

Selective Search Heuristics (Carsten Cibura)
Learning Search Control (Simone Daum)

1.6.

Search Anomalies (Ludwig)
Search and Knowledge (Janssen)

8.6.

Human Learning (Steger)
Early Chess Programs (Lugsch)
Deep Blue (Baier)

15.6.

22.6.

Opponent Modeling in Search (Laabs)

29.6.

Samuel's Checkers program (Nam)
Chinook (Wasser)
Bridge (Gotovac)

Literatur:

Überblick

Johannes Fürnkranz. Machine Learning in Game Playing: A Survey. In J. Fürnkranz and M. Kubat (eds.), Machines that Learn to Play Games, pp.11-59, Nova Science Publishers, 2001.

Early Chess Programs

Alan Turing: Chess. In Bowden (editor) Faster Than Thought, pp. 286--295. 1953.
Allen Newell, Cliff Shaw, Herbert Simon: Chess Playing Programs and the Problem of Complexity. IBM Journal of Research and Development 2 (1958)
Richard D. Greenblatt, Donald E. Eastlake III, Stephen D. Crocker. The Greenblatt Chess Program Fall Joint Computer Conference, pp. 801-810, 1967.

Deep Blue

Murray Campbell, A. Joseph Hoane Jr., Feng-hsiung Hsu: Deep Blue. Volume 134, Number 1-2, January 2002, pp. 57-83.
Gerald Tesauro: Comparison Training of Chess Evaluation Functions. In Fürnkranz & Kubat: Machines That Learn To Play Games, Nova Science Publishers 2001.
Murray Campbell: Knowledge Discovery in Deep Blue. Communications of the ACM 42(11): 65-67, 1999.

Perfect Play

H. Jaap van den Herik, Jos W. H. M. Uiterwijk, Jack van Rijswijck: Games Solved: Now and in the future. Artificial Intelligence 134:277-311, 2002.
M. R. Clarke, A quantitative Study of King and Pawn against King. Advances in Computer Chess 1, 1976.
Chess Endgame Databases FAQ
Robert Lake, Jonathan Schaeffer and Paul Lu.Solving Large Retrograde Analysis Problems Using a Network of Workstations, Advances in Computer Chess 7, H.J. van den Herik, I.S. Herschberg and J.W.H.M. Uiterwijk (editors), University of Limburg, Maastricht, Netherlands, pp. 135-162, 1994.

Opening Book Learning

Michael Buro. Toward opening book learning. In H. J. van den Herik and H. Iida, editors, Games in AI Research, pages 47-54. Universiteit Maastricht, 2000.
Robert M. Hyatt. Book learning --- a methodology to tune an opening book automatically. International Computer Chess Association Journal, 22(1):3-12, March 1999.
Murray Campbell: Knowledge Discovery in Deep Blue. Communications of the ACM 42(11): 65-67, 1999.

Paradise

D. E. Wilkins: Using Patterns and Plans in Chess. Artificial Intelligence 14(3):165-203, 1980
D. E. Wilkins: Using Knowledge to Control Tree Search Searching: Artificial Intelligence 18(1):1-51

Samuel's Checkers Program

Arthur L. Samuel. Some studies in machine learning using the game of checkers. IBM Journal of Research and Development, 3(3):211-229, 1959.
Arthur L. Samuel. Some studies in machine learning using the game of<> checkers. ii - recent progress. IBM Journal of Research and Development, 11(6):601-617, 1967.

Chinook

Chinook Web-site
Jonathan Schaeffer, Joseph Culberson, Norman Treloar, Brent Knight, Paul Lu and Duane Szafron, A World Championship Caliber Checkers Program, Artificial Intelligence, Volume 53, Number 2-3, pages 273-290, 1992.
Jonathan Schaeffer, Robert Lake, Paul Lu and Martin Bryant,Chinook: The Man-Machine World Checkers Champion, AI Magazine, Volume 17, Number 1, pages 21-29, 1996.
Robert Lake, Jonathan Schaeffer and Paul Lu.Solving Large Retrograde Analysis Problems Using a Network of Workstations, Advances in Computer Chess 7, H.J. van den Herik, I.S. Herschberg and J.W.H.M. Uiterwijk (editors), University of Limburg, Maastricht, Netherlands, pp. 135-162, 1994.

Backgammon / TD-Gammon

Gerald Tesauro. Temporal difference learning and TD-Gammon. Communications of the ACM, 38(3):58-68, March 1995.
Gerald Tesauro. Practical issues in temporal difference learning. Machine Learning, 8:257-278, 1992.

TD-Learning in Chess-like Games

Jonathan Baxter, Andrew Tridgell, Lex Weaver: Learning to Play Chess Using Temporal Differences. Machine Learning 40(3): 243-263 (2000)
Donald F. Beal, Martin C. Smith: Temporal difference learning applied to game playing and the results of application to Shogi. Theoretical Computer Science 252(1-2): 105-119 (2001)

Selective Search Heuristics

Ernst A. Heinz: Scalable Search in Computer Chess, Chapters 0-3. Vieweg, 1999. (0: Computer-Chess Primer, 1: Adaptive Null-Move Pruning, 2: Extended Futility Pruning, 3: AEL Pruning)

Learning Search Control

Yngvi Björnsson and T. A. Marsland. Learning Extension Parameters in Game-Tree Search. Information Sciences, vol 154 (2003), pp.85-118.
Greer, K.R.C., Ojha, P.C. and Bell, D.A., A Pattern-Oriented Approach to Move Ordering: The Chessmaps Heuristic, International ComputerChess Association Journal, 22, 1, pp13-21, 1999.

Anomalies of game tree search

Sadikov, A., Bratko, I., Kononenko, I. (2003) Search versus Knowledge: An Empirical Study of Minimax on KRK, In: H.J. van den Herik, H. Iida and E. Heinz (eds.) Advances in Computer Games: Many Games, Many Challenges, Kluwer Academic Publishers, ISBN 1-4020-7709-2, pp. 33-44
Beal, D.F. and Smith, M.C. (1994). Random Evaluations in Chess. ICCA Journal, Vol. 17, No. 1, pp. 3
Dana S. Nau: An Investigation of the Causes of Pathology in Games. Artificial Intelligence 19(3): 257-278 (1982)

Search and Knowledge

Hans J. Berliner, Gordon Goetsch, Murray S. Campbell, Carl Ebeling. Measuring the performance potential of chess programs. Artificial Intelligence Volume 43 , Issue 1 (April 1990) Special issue on computer chess, pages 7 - 20.
Andreas Junghanns, Jonathan Schaeffer: Search Versus Knowledge in Game-Playing Programs Revisited. IJCAI (1) 1997: 692-697
Ernst A. Heinz. DarkThought Goes Deep. ICCA Journal, Vol. 21(4), pp. 228-244, Dec. 1998.

Game-theoretical learning

Amy Greenwald: Modern Game Theory: Deduction vs. Induction. NYU TR1998-756, February 24, 1998
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.

Poker

Web-Site
Darse Billings, Aaron Davidson, Jonathan Schaeffer, and Duane Szafron, The Challenge of Poker. Artificial Intelligence Journal, vol 134(1-2), pp 201-240, 2002.
Darse Billings, Neil Burch, Aaron Davidson, Robert Holte, Jonathan Schaeffer, Terence Schauenberg, and Duane Szafron, Approximating Game-Theoretic Optimal Strategies for Full-scale Poker. Proceedings of IJCAI-03, (Eighteenth International Joint Conference on Artificial Intelligence), 2003.

Othello / Logistello

M. Buro, Improving Heuristic Mini-Max Search by Supervised Learning, Artificial Intelligence, Vol. 134 (1-2) (2002) pp. 85-99.
M. Buro, Statistical Feature Combination for the Evaluation of Game Positions , JAIR 3(1995), 373-382

Bridge

Ginsberg, M.L. (2001) GIB: Imperfect Information in a Computationally Challenging Game, Journal of AI Research, Volume 14, pages 303-358.
Stephen J. J. Smith, Dana S. Nau, Thomas A. Throop: Computer Bridge - A Big Win for AI Planning. AI Magazine 19(2): 93-106 (1998)

Scrabble

Brian Sheppard: World-championship-caliber Scrabble. pp. 241-275, Artificial Intelligence 134, 2002.
Appel and Jacobson: The World's Fastest Scrabble Program, Communications of the ACM, 1988, 31(5):572-585.
Steven A. Gordon: A Faster Scrabble Move Generation Algorithm. Softw., Pract. Exper. 24(2): 219-232 (1994)

Symbolic Learning in Go

J. Ramon, and H. Blockeel, A survey of the application of machine learning to the game of go, Proceedings of the First International Conference on Baduk (Sang-Dae Hahn, ed.), pp. 1-10, 2001
J. Ramon, T. Francis, and H. Blockeel, Learning a Tsume-Go heuristic with Tilde, Computers and Games, CG2000, Revised Papers (Marsland, T. A. and Frank, I., eds.), vol 2063, Lecture Notes in Computer Science, pp. 151-169, 2001
Takuya Kojima and Atsushi Yoshikawa. Knowledge acquisition from game records. Proceedings of the ICML-99 on Machine Learning in Game Playing, Bled, 1999.

Neural Network Learning in Go

Fredrik A. Dahl. Honte, a go-playing program using neural nets. In Fürnkranz & Kubat: Machines That Learn To Play Games, Nova Science Publishers 2001. chapter 10, pages 205-223.
Markus Enzenberger: Evaluation in Go by a Neural Network Using Soft Segmentation. 10th Advances in Computer Games Conference, Graz, 2003.
Norman Richards, David Moriarty, and Risto Miikkulainen (1998). Evolving Neural Networks to Play Go. Applied Intelligence, 8:85-96.

Move Strategies in Go

K.-H. Chen: Computer Go: Knowledge, Search, and Move Decision. International Computer Games Journal 24(4), 2001.
K.-H. Chen: Some Practical Techniques for Global Search in Go. International Computer Games Journal 23(2), 2000.
B. Bouzy: The Move-Decision Strategy of INDIGO. International Computer Games Journal 26(1):14-27, 2003.

Opponent Modeling in Search

H.H.L.M. Donkers, H.J. van den Herik, and J.W.H.M. Uiterwijk (2003), Opponent Models in Bao: Conditions of a Successfull Application, Advances in Computer Games 10 (eds. H.J van den Herik, H. Iida, and E. Heinz), Kluwer Academic Press, Dordrecht, The Netherlands, pp. 307-323.
David Carmel and Shaul Markovitch. Learning models of opponent's strategy in game playing. In S. L. Epstein and R. A. Levinson (eds.) Proceedings of the AAAI Fall Symposium on Intelligent Games: Planning and Learning, number FS-93-02, Menlo Park, CA, 1993. The AAAI Press.
H.H.L.M. Donkers, J.W.H.M. Uiterwijk, and H.J. van den Herik, (2002). Learning Opponent-Type Probabilities for PrOM SearchM. Procedings of the Fourteenth Belgium-Netherlands Conference (ed. Hendrik Blockeel and Marc Denecker), October 21-22, 2002 Leuven. pp. 91-98.