Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

   

2009 Research Summary

GamesCrafters: Undergraduate Game Theory Research and Development

View Current Project Information

Dan Garcia

Intel

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

Figure 1
Figure 1: The Tcl/Tk XGamesman choose-a-game launching application used to start a graphical game

Figure 2
Figure 2: An alternative Tcl/Tk choose-a-game launching application used to start a graphical game

Figure 3
Figure 3: The Tcl/Tk GAMESMAN interface for the game Achi. The left bar currently displays the rules of the game, and each move in the main window is shown in a uniform cyan color.

Figure 4
Figure 4: The same Tcl/Tk GAMESMAN interface for Achi with value moves and visual value history selected. Value moves is described above, and the visual value history is a graph on the left bar that displays how close each player is from claiming victory at any point. The yellow strip down the center indicates a draw position, and the color of the nodes highlights the value of the position at that point. We can see that Dan (left blue player) was handed a winning (green) initial position, but stumbled and returned it to a draw position. However, three moves later, GamesCrafters (right red player) also stumbled and made a catastrophic move, allowing Dan to win in one move. Dan choked and returned it to a draw, only to have GamesCrafters also choke and give Dan a win-in-3 position which is shown in the main window. Can you see the winning combination?

Figure 5
Figure 5: A recursive, graphical representation of the Tic-Tac-Toe game tree for the first three moves. The outer rim is the value of the position (in this case, a tie), and each recursive sub-square is the value the move for that person. For example, the x move to the upper-right is a tie, because the upper-right hollow square (imagine the board being broken up into 3 by 3 hollow squares) is yellow. Recursively, within that upper-right square there are 8 other hollow subsquares (7 red = losing, 1 central yellow = tieing), and one black filled square (representing the illegal move of placing the o directly onto the x already on the board). o now can choose among any of those 8 moves, let's say it chooses to place its piece in the lower left of the board--this is a hollow red square, thus a losing move. This means x has at least one winning response, and we see from the diagram that it has two, one in the upper-left or lower-right.

[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.