Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

   

Research Projects

GamesCrafters: Undergraduate Game Theory Research and Development

*** THIS PROJECT IS NO LONGER ACTIVE ***

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:

  • Maximization: An iterative, parallelizable, retrograde solver, which can use optimized level files of actual positions visited to optimize the search
  • Gamesman++: From-scratch core rewrite in C++
  • ODeepaBlue: A parallelization architecture that utilizes cluster computing and the Map-Reduce functional programming paradigm
  • GUI high-resolution resizeable skins, delta remoteness, visual value history, game tree traversal, solving progress bar, true game size, redo, and load and save games
  • Network play with eHarmony pairing and network database server
  • Bit-perfect and zero memory database access
  • Open positions and analysis database, with game graph visualizations
  • Generic game libraries and GUI language
  • Game histories and taxonomies researched, and an auto-updated web site with current analysis results
  • Solver and player utilizing "win by" (rather than remoteness) for games where a win can be quantified
  • Extensive documentation for all APIs
  • New games implemented in C to be strongly solved: Quarto!, Bagh Chal, Rubik's Checkers, Cambio, Topitop, Hex, and others
  • Existing games maximized: Tic-Tac-Toe, Bagh Chal, Mancala, Quick/Tile Chess, and 6-/9-Men's Morris
  • Goldification: GUI upgrade to Change!, Ice Blocks, Wuzhi, Mancala, Mu Torore, Nim, Queensland, Tac Tix, and others
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

[1]
D. Garcia, "GAMESMAN: A Finite, Two-Person, Perfect-Information Game Generator," master's thesis, UC Berkeley, May 1995.
[2]
R. Nowakowski, ed., "More Games of No Chance," Math. Sci. Res. Publ. 42, Cambridge University Press, Cambridge, 2002.
[3]
R. Nowakowski, ed., "Games of No Chance," Math. Sci. Res. Publ. 29, Cambridge University Press, Cambridge, 1996.
[4]
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.
[5]
Wikipedia: Solved Board Games: http://en.wikipedia.org/wiki/Solved_board_games
[6]
V. Allis, "Searching for Solutions in Games and Artificial Intelligence," PhD thesis, Department of Computer Science, University of Limburg, 1994.
[7]
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.