Nim is a game played with piles of chips, where a move consists of removing some chips from one pile, the winner being the last one to move. We are studying a generalisation where the piles of chips are placed on the edges or vertices of a graph and a move consists of taking some chips and moving to a neighbouring vertex. Incidentally, if only one chip is allowed in each pile then it resembles one version of the game Geography. We are studying the complexity of finding an optimal strategy for variants of this game.

Preliminary Presentation (ppt)
Final Presentation (ppt)

 

Other REUs for Summer 2004

Algorithms for Dynamic Point Location with Good Practical Performance
A Bezier-Based Approach to Unstructured Moving Meshes
Evaluation of Algorithms for the List Update Problem
Exploring PLS-Completeness of Simple Stochastic Game (or Stable Circuit Problem)
Fast and Compact Data Structures
The Game of NimG (Nim on Graphs)
Random Graph Models of Large Real-World Networks
Solving Partial Differential Equations Numerically
Traceable Anonymity

Back to the REU page