PSU CS442/542: Combinatorial Games
Spring 2013
Course Syllabus
When: 1640-1830 (4:40-6:30PM) Tuesdays and
Thursdays, April 1 — June 13 2013
Where: UTS 304
Who: Bart Massey <bart@cs.pdx.edu>
Office Hours: By e-mail appointment
CRN: 64678 (442), 64679 (542)
This course concentrates on adversary search using combinatorial search techniques to achieve high-quality tactics in competitive situations. Other successful methods of tackling combinatorial games will also be examined.
There is no course text. However, there are a variety of readings as well as a MiniChess tutorial .
There are some ?course notes available.
Homework
- . Build a random MiniChess player
- . Build a MiniChess player
- . Build a competent MiniChess player
- . Build a MiniChess player with memory
- . Course Project
Course Schedule
| Date | Topics | Readings | HW |
|---|---|---|---|
| 4/2 |
Games Computers Play Introduction to MiniChess |
[esai]; [mc] intro, 1-4 | HW 1 |
| 4/4 | Search In Games Minimax Search in MiniChess |
[mc] 6-8 | |
| 4/9 | In-class programming and implementation day | HW 2 | |
| 4/11 | AB | [abmn], [abav] | |
| 4/16 | TTables | [ghi] | HW 3 |
| 4/18 | Advanced Search | [mtdf] | |
| 4/23 | Work Session: CS Linux Lab | ||
| 4/25 | Guest Lecture: Joe Hurd, Retrograde Analysis | [crga],[mrga] | |
| 4/30 | Openings | [book] | HW 4 |
| 5/2 | Software Engineering and Debugging | ||
| 5/7 | Evaluation, TTables | Course Project | |
| 5/9 | Network Client Programming | ||
| 5/14 | Probability and Hidden Information | [scev],[mavn] | |
| 5/16 | Machine Learning | [lgst],[glem] | |
| 5/21 | TBA | ||
| 5/23 | TBA | ||
| 5/28 | Theory vs Practice | ||
| 5/30 | Adversary Search vs The Real World | ||
| 6/4 | Status Reports | ||
| 6/6 | Playtime, Final Thoughts |
About The Course
The catalog says
This course covers the theory and practice of finding optimal and satisfying solutions to one-player and two-player combinatorial games, including such popular games as Sokoban, Othello, checkers, chess, backgammon, bridge, and CCGs. Simple applications in decision theory and economics may also be discussed. Emphasis on implementation of state-of-the-art solution techniques. Prerequisites include CS 350 (Algorithms) or equivalent experience, plus fluency in some reasonable programming language. Previous AI experience is not required, but may prove helpful.
This course should be a huge amount of fun. Please let me know if you have questions I can answer, or just want to chat about some fascinating material.
Prerequisites:
A good working knowledge of algorithms, data structures, and computational complexity.
The ability to write medium-sized programs in a reasonable programming language.
Basic reasoning skills, and the ability to quickly read and understand complex material.
Sincere interest in the subject area.
If you are unwilling to devote substantial out-of-class time and really get into this topic, you will likely be disappointed in both the course and your performance. Come prepared to work hard and play hard!
Previous Offerings
This course has been offered a number of times previously:
In addition, I taught this material this Winter as a short course at the Fachhochschule Würzburg-Schweinfurt in 2006, 2009 and 2010.
Course Load
This course is intended to dig very quickly and deeply into this cutting-edge topic. As such, students not prepared to devote substantial out-of-class time to programming, learning, and exploring are unlikely to achieve a passing grade.
The course will move very quickly, and if you get behind, you will never catch up. No incompletes will be given (except in the most catastrophic of personal circumstances). Homework turned in after an assignment has been graded or after the last scheduled acceptance date will be silently discarded.
E-mail and Web
This web page is http://wiki.cs.pdx.edu/cs542. There are several e-mail addresses associated with the course.
The e-mail address <cs542-discuss@ai.cs.pdx.edu> is the course mailing list (using mailman). Subscribe to this by visiting http://wiki.cs.pdx.edu/cgi-bin/mailman/listinfo/cs542-discuss/, and use it for class discussions and most questions.
<cs542-hw@ai.cs.pdx.edu> will send e-mail to me: use this for homework submissions, and for private questions.
Readings
Required Text
There will not be a required text. Almost any artificial intelligence text gives the basics of game tree search; you'll probably want to find one and read it.
Required Readings
- [scev]
- Andrew Appel and Guy Jacobson. The World's Fastest Scrabble Program. Communications of the ACM 31(5) pp. 572-578, May 1988.
- [bgre]
- Michael Buro. Efficient Approximation Of Backgammon Race Equities. ICCA Journal 22(3) (1999), pp. 133-142.
- [glem]
- Michael Buro. From Simple Features To Sophisticated Evaluation Functions. Proceedings Of The First International Conference on Computers and Games (CG '98), Tsukuba, Japan. Published in LNCS vol. 1558, Springer-Verlag.
- [lgst]
- Michael Buro. Improving Heuristic Mini-Max Search By Supervised Learning. NECI Technical Report #106 (NEC 2000).
- [pcut]
- Michael Buro. ProbCut: An Effective Selective Extension of the αβ Algorithm. ICCA Journal vol. 18, 1995.
- [book]
- Michael Buro. Toward Opening Book Learning. Proceedings of the IJCAI-97 Workshop on Using Games as an Experimental Testbed for AI Research.
- [ghi]
- Murray Campbell. The graph-history interaction problem. Proceedings of the 1985 ACM annual conference on the range of computing: mid-80's perspective. October 1985.
- [mrga]
- Ralph Gasser. Applying Retrograde Analysis to Nine Men's Morris. In Heuristic Programming in Artificial Intelligence; The Second Computer Olympiad, D.N.L. Levy and D.F. Beal (ed.), 1991.
- [esai]
- Matt Ginsberg. Essentials of Artificial Intelligence, chapters 3 and 4. Morgan Kaufman, 1993. ISBN 1-55860-221-6.
- [part]
- Matt Ginsberg. Partition Search. Proc. 1997 National Conference on Artificial Intelligence (AAAI '97).
- [nets]
- Kevin Gurney. Computers and Symbols versus Nets and Neurons. Pre-publication draft, UCL Press.
- [pchs]
- A.X. Jiang, Michael Buro. First experimental results of ProbCut applied to Chess. Advances in Computer Games Conference 10, 2003.
- [crga]
- Robert Lake, Jonathan Schaeffer, and Paul Lu. Solving Large Retrograde Analysis Problems Using a Network of Workstations. Advances in Computer Chess VII, Maastricht, Netherlands, 1994.
- [mc]
- Bart Massey et al. All About Minichess. Web document, on site, 2009.
- [abav]
- Judea Pearl. The solution for the branching factor of the alpha-beta pruning algorithm and its optimality. Communications of the ACM (25)8, August 1982.
- [mtdf]
- Aske Plaat. Best-First Fixed-Depth Minimax Algorithms. J. Art. Int. 187:1-2 (November 1996) pp. 255-293.
- [sch1]
- Arthur L. Samuel. Some studies in Machine Learning using the game of Checkers. IBM Journal 3(3) (1959), pp. 210-.
- [sch2]
- Arthur L. Samuel. Some studies in Machine Learning using the game of Checkers. II - Recent progress. IBM Journal 11(6) (November 1967), pp. 601-617.
- [mavn]
- Brian Sheppard. Mastering Scrabble. IEEE Intelligent Systems 14:6 (November/December 1999) pp. 15-16.
- [abmn]
- James R. Slagle and John K. Dixon. Experiments with some programs that search game trees. Journal of the ACM (16)2, April 1969.
- [pgam]
- J.D. Williams. The Compleat Strategist. McGraw-Hill 1954.
Links
Check out the First and Second International Rock-Scissors-Paper Programming Competition.
Iocaine Powder is the 1999 Rock-Scissors-Paper computer champ.
MTD(f) is a top-flight modern adversary search algorithm.
Thanks to Rolla Selbak for recommending this useful summary of minimax, negamax, alpha-beta, and zero-window search.
Thanks to Zan Gligorov for recommending this summary site on machine learning methods in combinatorial and other games.
This is a very nice reference to a lot of the ideas in this course as they pertain to chess, written for a similar course in the U.K.
This is a lovely collection of links on the theory of combinatorial games (where the author defines "combinatorial" as roughly "two-player zero-sum alternating").
Thanks to Jamey Sharp for recommending this good collection of ideas in chess programming. (MTD(f) subsumes some of what is there: read carefully.)
Thanks to Steve Coward for these really good links to people's demo chess programs with lots of strong information.
Coursework
The coursework will consist primarily of a course-long individual programming project, implementing a player for an adversary game and evaluating adversary performance. You may cooperate with other students in your work, as long as you credit those students. However, you are expected to produce your own work product, independent of others.
Those experimenting with departmental computers must follow the "safety guidelines".
No quizzes or examinations are currently planned, but I reserve the option to schedule them at a later date.
Academic Honesty
If I catch you plagiarizing any material, there is a limited amount that I can do about it, but I will be really unhappy, and will give you a zero on the relevant work. Plagiarism is using anyone else's works, writings, or ideas without explicitly giving them credit. If you get code, ideas, or text from a fellow student, put their name on it so that we both know what happened.
In this course, you will be expected to do a lot in a short time, in a sometimes competitive environment. This is not an excuse to do things that are unethical, immoral, or illegal.
We will occasionally play our programs off against each other, most notably at the end of the course. This will never harm your grade. Your program may be able to win these contests by "cheating". If so, you will receive due credit for this, as long as you explicitly acknowledge and explain your methods up front. If you fail to do so, and your program is caught deliberately cheating, it will lose the tournament it participates in, and you will receive a 0 for the related assignment.