This is a deprecated page.
Please see my Undergraduate Game Theory Research Group GamesCrafters for the current state of the project.
GAMESMEN
UC Berkeley Undergraduate Game Theory Research Group
led by Dan Garcia
Spring 2002

"Every game ever invented by mankind, is a
way of making things hard for the fun of it!"
 John Ciardi
Welcome to Dan Garcia's Spring 2002 Undergraduate Game
Theory research page. The overall goal of this project is to involve
freshmen and sophomores in an enjoyable research project, learn
about game theory, hash tables, efficient representations and
user interfaces through a software project in C. Each team of
students chooses a game to add to Gamesman
and throughout the semester they implement the internal C and
Tcl/Tk programming interface.
Spring 2002 Gamesmen and Alumni
Back Row: Peter Tretheway, Erwin Vedar, Farzad Eskafi,
Dave Le, Isaac Greenbride, Dan Garcia, James Chung, Alex Perelman,
Atilla Gyulassy, Sunil Ramesh
Front Row: Thomas Yiu, Edwin Mach, Alex Kozlowski, Mike
Savitsky, Kevin Ha, Babak Hamadini
Missing: Todd Segal, David Shultz, Greg Krimer, Chi Huynh,
David Chen, Ling Xiao
Instructor 
Dan
Garcia 
Independent
Students 
CHEAT
(CHess Endgame Awesome Teacher) 
Todd Segal 
Game Databases, Loopy Code
Coordinator 
Sunil Ramesh 
CS3
Final Project
"Shall we play a game?" 
David Schultz 
Greg Krimer 
Gamesmen 
Fox and Geese 
Sergey Kirshner 
James Chung 
Critical Mass 
Peterson Tretheway 
Quick
Cross 
Thomas Yiu 
The L Game 
Alex Kozlowski 
Mike Savitsky 
Chung
Toi 
Farzad Eskafi 
Erwin Vedar 
3x3
Rubik's Infinity 
Chi Huynh 
Edwin Mach 
Joust 
Isaac Greenbride 
Dave Le
Mike Jurka 
Three Spot 
Attila Gyulassy 
Kevin Ha 
ShiftTacToe 
David Chen 
Ling Xiao 
Lite3 
Babak Hamadani 
Alex Perelman 
Fall 2001 Gamesmen
Back Row: Thomas Yiu, Isaac Greenbride, Dan Garcia,
Farzad Eskafi, Chi Huynh, Erwin Vedar, Edwin Mach, Mike Savitsky,
James Chung, Alex Kozlowski
Carried: Dave Le
Missing: Peter Tretheway, Todd Segal, David Shultz, Greg
Krimer
How to create your own game
module in 10 easy steps

0  Read about and install
Gamesman

 Goal: Read about and install Gamesman on their computer
 Resources:
 Gamesman
WWW page
 Bring with you to the meeting
 Any questions you have about Gamesman or the install
 At the meeting we learned
 Basics of game theory
 Many different games from which to choose for the final project
1  Choose your game &
think of different rules

 Goal: To choose your game and think of different rules
that would be possible for it
 Resources (Game Theory Bible  the ultimate reference!)
 Elwyn Berlekemp, John H. Conway, and Richard K. Guy. Winning
Ways for Your Mathematical Plays, Volume 1,2. Academic Press
Inc., 1982. (red and blue books)
 Resources (Game Theory Books)
 Franco Agostino and Nicola Alberto DeCarlo. Intelligence
Games. Simon and Schuster, 1985.
 Andrea Angiolino. Super Sharp Pencil & Paper Games.
Sterling Publishing Co, Inc., 1995.
 John D. Beasley. The Mathematics of Games. Oxford
University Press, 1989.
 R. C. Bell. Board and Table Games from Many Civilizations.
Oxford University Press, 1979.
 R. C. Bell. The Boardgame Book. Exeter Books, 1983.
 Robbie Bell and MIchael Cornelius. Board Games Round the
World: A Resourse Book for Mathematical Investigations. Cambridge
University Press, 1988.
 Gyles Brandreth. The World's Best Indoor Games. Pantheon
Books, 1981.
 Matthew J. Costello. The Greatest Games of All Time.
John Wiley & Sons, 1991.
 Jon Freeman. The Playboy Winner's Guide to Board Games.
Playboy Press, 1979.
 Frederic V. Grunfeld. Games of the World : how to make
them, how to play them, how they came to be. UNICEF, 1975.
 KarlHeinz Koch. Pencil & Paper Games. Sterling
Publishing Co., Inc., 1992.
 Pentagram. Pentagames. Simon and Schuster, Inc., 1990.
 David Pritchard. Brain Games. Penguin Books Ltd.,
1982.
 Eric Solomon. Games with Pencil and Paper. Dover,
1993.
 At the meeting: we learned about TicTacToe
 Twoway hash function for positions
 Position is represented as an integer
 Each of the 9 slots is one of three values, Blank (0), O(1)
or X(2)
 Thus, the position is considered a 9digit ternary number,
from 0 to 3^{9}1
 Twoway hash function for moves
 Move is represented as an integer
 A number from 0 to 8 for the particular move depending on
the slot chosen
 How Position = DoMove(Position, Move) is implemented
 return(Position + WhoseTurn(Position) * 3^{Move})
 WhoseTurn(Position) returns 1 if it's O's turn and
2 if it's X's turn
 This works because the position must have a blank in the
Move slot, we're just adding that particular digit to
the Position number
2  Create hash function for
your game

 Goal: To come up with the hash functions for positions
and moves for your game
 Resources:
 Dan's scheme and C libraries (coming soon)
 At the meeting we...
 Analyzed the hash functions for several games
 Alex and Mike's LGame
 Farzad and Erwin's Chung Toi
 Isaac and Dave's Joust
 Discussed the four types of optimized hash functions (chapter
6 of Dan's
Gamesman thesis)
 Given C(n,k) is combination of n choose
k items
 Given Sum(from,to,expression) is a summation of
expression with variables bound in from to
to.
 Given Pi(from,to,expression) is a product of expression
with variables bound in from to to.
 Rearranger
 Game in which O pieces are rearranged in slots
slots.
 n = Rearranger(slots, O)
 = C(slots,O)
 RearrangerOX (also known as RearrangerPartisan)
 Game in which O Opieces and X Xpieces
are rearranged in slots slots.
 n = RearrangerOX(slots, O, X)
 = C(slots,O+X) * C(O+X,O)
 Dartboard
 Game in which players take turns putting pieces (up to a
maximum of MaxPieces) on the slots but don't move them.
 n = Dartboard(slots, MaxPieces)
 = Sum(i=0,i=MaxPieces,C(slots,i))
 = 2^slots (when MaxPieces = slots)
 DartboardOX (also known as DartboardPartisan)
 Game in which players take turns putting their own X or O
pieces (up to a maximum of MaxPieces) on the slots but don't
move them.
 n = DartboardOX(slots, MaxPieces)
 = Sum(i=0,i=MaxPieces,C(slots,i)*C(i,i/2))
 Discussed how to encode & decode a number with digits
of different bases to represent different independent components
of our game
 General idea
 What if you had bottles which could contain different integer
amounts of liquid, and you wanted to count all the possible ways
the bottles could be semifilled with integer amounts of water?
 Example: you have three bottles which can hold 2, 4 and 3
units of liquid. The first can hold 0 or 1 unit (remember, it
has to be semifilled, being filled isn't allowed), the second
can hold 0, 1, 2 or 3 units, and the last can hold 0, 1 or 2
units.
 Since they are all independent variables, the number of ways
they can be filled is 2 * 4 * 3 = 24 ways.
 We'll number them from 0 to 23:
2 4 3 : N
0 0 0 : 0
0 0 1 : 1
0 0 2 : 2
0 1 0 : 3
0 1 1 : 4
0 1 2 : 5
0 2 0 : 6
0 2 1 : 7
0 2 2 : 8
0 3 0 : 9
0 3 1 : 10
0 3 2 : 11
1 0 0 : 12
1 0 1 : 13
1 0 2 : 14
1 1 0 : 15
1 1 1 : 16
1 1 2 : 17
1 2 0 : 18
1 2 1 : 19
1 2 2 : 20
1 3 0 : 21
1 3 1 : 22
1 3 2 : 23
 We can think of representing a particular filling as a set
of rational numbers  the numerator represents what is currently
in each bottle and the denominator represents what the bottle
can hold.
 So, for example, if they are all as full as possible, they'd
contain: (1/2, 3/4, 2/3) units
 We want to be able to go from the particular fillings to
a number (hash) and from a particular number to the fillings
(unhash)
 If the current digits, or numerators are n_{0},
n_{1}, ... n_{k}
 ...and the bases, or denomenators are are d_{0},
d_{1}, ... d_{k}
 The hash function is
 N = n_{0} + d_{0}n_{1} + d_{0}d_{1}n_{2}
+ ... + d_{0}d_{1}*...*d_{k1}n_{k}
 N = Sum(i=0,i=k,Pi(j=0,j=i1,d_{j})n_{i})
 Example hash function:
 Given (2,4,3) bases and values (1,3,2) [also represented
as (1/2,3/4,2/3)] last one above, what is N?
 N = 2 + 3*3 + 1*4*3 = 23
 The unhash function is
 n_{0} = N % d_{0}
 n_{1} = (N / d_{0}) % d_{1}
 n_{2} = (N / d_{0}d_{1}) % d_{2}
 ...
 n_{k} = (N / Pi(i=0,k1,d_{i}) % d_{k}
 Example hash function:
 Bases are 2,4,3, N = 23, whare are n_{0}, n_{1},
n_{2}?
 n_{0} = 23 % 3 = 2
 n_{1} = (23 / 3) % 4 = 3
 n_{2} = (23 % 3 * 4) % 2 = 1
 Thus the digits are (1,3,2), the last one in the table above!
3  Start coding your textbased
game (in C)

 Goal: To start coding your textbased game (ignore
the graphics component for now)
 You should start coding your hash functions and the main
interface subroutines (here are the primary ones):
 InitializeDatabases()
 POSITION DoMove(thePosition, theMove)
 GetInitialPosition(initialPosition)
 PrintComputersMove(computersMove,computersName)
 VALUE Primitive(position)
 PrintPosition(position,playerName,usersTurn)
 MOVELIST *GenerateMoves(position)
 PrintMove(theMove)
 Roughly, here is how you should proceed
 Find a shortened name (< 6 letters) for your game
 Example: ttt for TicTacToe, chung for
Chung Toi, etc.
 Look at which of the 4 games already implemented most closely
approximates your own
 For most of you, this will be TicTacToe
 Copy these files (ttt.c and ttt.h if you're
basing it on TicTacToe)
 Edit the Makefile to include your game (make an
entry for your game  take the example from ttt)
 Ignore delete all the code dealing with symmetry!
 If your game is loopy, make sure you set BOOLEAN kLoopy
= TRUE;
 Edit the rest of the C code to implement your game
 Read Chapter 5 of Dan's
Gamesman thesis
 Bring any questions you have about your implementation to
the meeting
 Resources:
 Gamesman
source code examples: m1210.c, mdodgem.c, mttt.c,
mtactix.c
 Chapter 5 of Dan's
Gamesman thesis
 Dan's scheme and C libraries (coming soon)
 At the meeting...
 We'll address your implementation questions
 We talked about the four big pieces of this project:
 Coding the textbased version
 Coding the graphical version
 Performing analysis of your game
 Documenting everything  code, www pages, analysis.
 We talked about how each game is going to represent moves
and positions in a textbased manner. Example for TicTacToe:
 Moves = number from 1 to 9
 Position as shown below ( = blank)
( 1 2 3 ) : X X O
LEGEND: ( 4 5 6 ) TOTAL: :  O 
( 7 8 9 ) :  O X (Dan should Tie in 3)
4  Finish coding your textbased
game (in C)

 Goal:
 To finish the implementation of your textbased game in C
 Resources:
 Gamesman
source code: m1210.c, mdodgem.c, mttt.c,
mtactix.c
 At the meeting...
 We'll demo all your programs!
5  Design your graphics interface

 Goal: To begin coding your game's graphic interface.
Think of how you'll...
 draw your pieces
 interact with your pieces
 display all of the moves at once (through valuemoves)
 Resources:
 At the meeting...
 We'll analyze your designs
 We'll teach you how the Tcl/Tk code works
6  Start coding your graphics
game (in Tcl/Tk)

 Goal: To start coding your graphics game in Tcl/Tk
 Install Tcl/Tk on
your Unix system if it isn't there already
 Start from the basics: Tcl interactions first, then draw
the pieces
 Resources:
 Tcl/Tk site to install
it to your system
 Then, view a demo of all the widgets as follows (pay particular
attention to the canvas widget!)
unix% cd /usr/sww/lib/demos
unix% wish f widget
 Gamesman
Tcl/Tk source code
 Xmttt  Tcl/Tk TicTacToe module
 gamesman.tcl  Tcl/Tk library code
 At the meeting...
 We'll answer any questions you have
7  Continue coding your graphics
game (in Tcl/Tk)

 Goal: To continue coding your graphics game in Tcl/Tk
 You should be finished by next week
 Resources:
 At the meeting...
 We'll answer any questions you have
8  Finish coding your graphics
game (in Tcl/Tk)

 Goal: To finish coding your project
 Resources:
 At the meeting...
 We'll look at & play your games!!
9  Merge, WWW documentation,
writeup, analysis

 Goal: To merge your code with Gamesman, and finish
up your writeup
 Your writeup should be put on your WWW site in HTML format
 Resources:
 At the meeting...
 We'll discuss your analysis and writeup
WWW Maven: Dan
Garcia (ddgarcia@cs.berkeley.edu)
Send me feedback