My final project for Game Theory (Math 5750) is a web page that can create custom sums of combinatorial games based on some built-in game types. The webpage also includes a computer player that will never make a mistake.

The webpage has a few built-in gametypes such as:

• Nim
• Grundy's Game
• Subtraction Game (1,2)
• Even Except All or All and Odd
• Lasker's Nim

The user can select which built-in game/games to add to the sum of games. A random number of chips, between 10 and 20, will be chosen for the pile. Any number of games may be added.

When the game starts the player will play against the computer. The computer will always choose an ideal move if one is availiable. Because of this, and the basics of combinatorial games, a single wrong move by the user will result in loosing the game.

Implementation Details

The value of each individual pile is calculated based on the specified game type. The system uses the same basic method to calcute the sprague grundy value as we used in class. Any position that has no followers (possible moves) has a value of zero. Positions that have followers will retrieve the value of each of the follower positions. The value of that position is the minimum excludant of the values of the follower positions. (Ex: a function that has followers with the values (0,5,1,3,6) will have a value of 2)

To improve performance, the values for positions are saved once they are discovered. This prevents the need for an exponential running time to calculate the sprague-grundy value of a specified position for a specified game

The system uses the Sprague-Grundy Theorem to determine the total value of the sum of combinatorial games. The sprague-grundy theorem says that the combined value of several piles can be determined by taking the nim-sum of the values of each individual pile. The nim sum is the functional equivalent of the exclusive-or operator used in digital logic.

If a game has piles of x1,x2,x3 then the Sprague-Grundy value (as defined by the Sprague-Grundy theorem) G(x1,x2,x3) = G(x1)⊕G(x2)⊕G(x3)

If the value obtained for the combined game is X, and X is not equal to 0, then X⊕G(xi) is compared to the value of each follower in the ith pile. If the value of the follower is equal to X⊕G(xi) then that follower is an ideal move which will make the combined value of the game equal to 0.

The computer player will check for an ideal move in each pile. It will then randomly choose from the ideal moves that were found. If there is no ideal move (X=0) then the computer will just choose a random move.

If at any point there are no availiable moves then the game is over and the user is notified whether he won or lost (depending on who made the last move).