Research Projects

GamesCrafters: Undergraduate Game Theory Research and Development


Dan Garcia

The GamesCrafters research and development group was formed in 2001 as a "watering hole" to gather and engage top undergraduates as they explore the fertile area of computational game theory. At the core of the project is GAMESMAN, an open-source AI architecture developed for solving, playing, and analyzing two-person abstract strategy games (e.g., Tic-Tac-Toe or Chess). Given the description of a game as input, our system generates a command-line interface and Tcl/Tk graphical application that will solve it (in the strong sense [5-7]), and then play it perfectly. Programmers can easily prototype a new game with multiple rule variants, learn the strategy via color-coded value moves (win = go = green, tie = caution = yellow, lose = stop = red), and perform extended analysis. The group is accessible to undergraduates at all levels. Those not yet ready to dive into code can create graphics, find bugs, or research the history of games for our website. Programmers can easily prototype a new game with multiple rule variants, design a fun interface, and perform extended analysis. Advanced students are encouraged to tinker with the software core, and optimize the solvers, databases, hash functions, networking, user experience, etc. Since this is not a class, but directed group study, students can re-register as often as they like; most stay for two or three semesters. This allows for a real community to be formed, with veterans providing continuity and mentoring as project leads, as well as allowing for more ambitious multi-term projects. Our alumni have told us how valuable this experience has been for them, providing them with a nurturing environment to mature as researchers, developers, and leaders. Over the past six years, over two hundred undergraduates have implemented more than sixty-five games and several advanced software engineering projects. Here are but a few of the recent projects:

Our future research direction is "hunting big game"--implementing, solving, and analyzing large games whose perfect strategy is yet unknown. Authors include (in decreasing seniority): Alan Roytman, Eudean Sun, Filip Furmanek, David Chan, David Eitan Poll, Patricia Fong, Jerry Hong, Kevin Liu, Ofer Sadgat, Albert Shau, Daniel Wei, Omar Akkawi, Louis Chan, Anthony Chen, James Ide, Valerie Ishida, Yiding Jia, Taejun Lee, William Li, Teng Chi Lim, Moonway Lin, Hong Hanh Nguyen, Dounan Shi, Michael So, Harry Su, Brian Taylor, and Alan Young

D. Garcia, "GAMESMAN: A Finite, Two-Person, Perfect-Information Game Generator," master's thesis, UC Berkeley, May 1995.
R. Nowakowski, ed., "More Games of No Chance," Math. Sci. Res. Publ. 42, Cambridge University Press, Cambridge, 2002.
R. Nowakowski, ed., "Games of No Chance," Math. Sci. Res. Publ. 29, Cambridge University Press, Cambridge, 1996.
E. Berlekamp, J. Conway, and R. Guy, Winning Ways for your Mathematical Plays, Academic Press, New York, 1982, second edition, A. K. Peters, Natick (MA), 2001.
Wikipedia: Solved Board Games:
V. Allis, "Searching for Solutions in Games and Artificial Intelligence," PhD thesis, Department of Computer Science, University of Limburg, 1994.
H. J. van den Herik, J. W.H.M. Uiterwijk, and J. van Rijswijck, "Games Solved: Now and in the Future," Artificial Intelligence, Vol. 134, pp. 277-311, 2002.