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.

People (aka "Gamesmen")

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

Shift-Tac-Toe
David Chen
Ling Xiao

Lite-3
Babak Hamadani
Alex Perelman

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
Shift-Tac-Toe	David Chen	Ling Xiao
Lite-3	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:
1. 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)
1. Franco Agostino and Nicola Alberto DeCarlo. Intelligence Games. Simon and Schuster, 1985.
2. Andrea Angiolino. Super Sharp Pencil & Paper Games. Sterling Publishing Co, Inc., 1995.
3. John D. Beasley. The Mathematics of Games. Oxford University Press, 1989.
4. R. C. Bell. Board and Table Games from Many Civilizations. Oxford University Press, 1979.
5. R. C. Bell. The Boardgame Book. Exeter Books, 1983.
6. Robbie Bell and MIchael Cornelius. Board Games Round the World: A Resourse Book for Mathematical Investigations. Cambridge University Press, 1988.
7. Gyles Brandreth. The World's Best Indoor Games. Pantheon Books, 1981.
8. Matthew J. Costello. The Greatest Games of All Time. John Wiley & Sons, 1991.
9. Jon Freeman. The Playboy Winner's Guide to Board Games. Playboy Press, 1979.
10. Frederic V. Grunfeld. Games of the World : how to make them, how to play them, how they came to be. UNICEF, 1975.
11. Karl-Heinz Koch. Pencil & Paper Games. Sterling Publishing Co., Inc., 1992.
12. Pentagram. Pentagames. Simon and Schuster, Inc., 1990.
13. David Pritchard. Brain Games. Penguin Books Ltd., 1982.
14. Eric Solomon. Games with Pencil and Paper. Dover, 1993.
At the meeting: we learned about TicTacToe
- Two-way 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 9-digit ternary number, from 0 to 3⁹-1
- Two-way 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
  1. Alex and Mike's L-Game
  2. Farzad and Erwin's Chung Toi
  3. 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.
  1. Rearranger
    - Game in which O pieces are rearranged in slots slots.
    - n = Rearranger(slots, O)
    - = C(slots,O)
  2. RearrangerOX (also known as RearrangerPartisan)
    - Game in which O O-pieces and X X-pieces are rearranged in slots slots.
    - n = RearrangerOX(slots, O, X)
    - = C(slots,O+X) * C(O+X,O)
  3. 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)
  4. 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 semi-filled 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 semi-filled, 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:

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₀, n₁, ... n_k
...and the bases, or denomenators are are d₀, d₁, ... d_k
The hash function is
- N = n₀ + d₀n₁ + d₀d₁n₂ + ... + d₀d₁*...*d_k-1n_k
- N = Sum(i=0,i=k,Pi(j=0,j=i-1,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₀ = N % d₀
- n₁ = (N / d₀) % d₁
- n₂ = (N / d₀d₁) % d₂
- ...
- n_k = (N / Pi(i=0,k-1,d_i) % d_k
- Example hash function:
  - Bases are 2,4,3, N = 23, whare are n₀, n₁, n₂?
  - n₀ = 23 % 3 = 2
  - n₁ = (23 / 3) % 4 = 3
  - n₂ = (23 % 3 * 4) % 2 = 1
  - Thus the digits are (1,3,2), the last one in the table above!

3 - Start coding your text-based game (in C)

Goal: To start coding your text-based 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
  1. Find a shortened name (< 6 letters) for your game
    - Example: ttt for Tic-Tac-Toe, chung for Chung Toi, etc.
  2. Look at which of the 4 games already implemented most closely approximates your own
    - For most of you, this will be Tic-Tac-Toe
  3. Copy these files (ttt.c and ttt.h if you're basing it on Tic-Tac-Toe)
  4. Edit the Makefile to include your game (make an entry for your game -- take the example from ttt)
  5. Ignore delete all the code dealing with symmetry!
  6. If your game is loopy, make sure you set BOOLEAN kLoopy = TRUE;
  7. 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 text-based 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 text-based manner. Example for Tic-Tac-Toe:
  - 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 text-based game (in C)

Goal:
- To finish the implementation of your text-based 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 value-moves)
Resources:
- Gamesman graphic interface examples
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 Tic-Tac-Toe 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:
- Gamesman Tcl/Tk source code
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:
- Gamesman Tcl/Tk source code
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:
- Gamesman WWW page
At the meeting...
- We'll discuss your analysis and writeup

WWW Maven: Dan Garcia (ddgarcia@cs.berkeley.edu)

Send me feedback

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

GAMESMEN UC Berkeley Undergraduate Game Theory Research Group led by Dan Garcia Spring 2002

People (aka "Gamesmen")

How to create your own game module in 10 easy steps

How to create your own game module in 10 easy steps

0 - Read about and install Gamesman

0 - Read about and install Gamesman

1 - Choose your game & think of different rules

1 - Choose your game & think of different rules

2 - Create hash function for your game

2 - Create hash function for your game

3 - Start coding your text-based game (in C)

3 - Start coding your text-based game (in C)

4 - Finish coding your text-based game (in C)

4 - Finish coding your text-based game (in C)

5 - Design your graphics interface

5 - Design your graphics interface

6 - Start coding your graphics game (in Tcl/Tk)

6 - Start coding your graphics game (in Tcl/Tk)

7 - Continue coding your graphics game (in Tcl/Tk)

7 - Continue coding your graphics game (in Tcl/Tk)

8 - Finish coding your graphics game (in Tcl/Tk)

8 - Finish coding your graphics game (in Tcl/Tk)

9 - Merge, WWW documentation, writeup, analysis

9 - Merge, WWW documentation, writeup, analysis

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

GAMESMEN
UC Berkeley Undergraduate Game Theory Research Group
led by Dan Garcia
Spring 2002