Winning or Losing in the Game of Nim on Graphs
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
This Demonstration presents a random oriented graph that has at least one terminal vertex. Such graphs can represent the terminal game Nim. To play Nim, players alternate in choosing a sequence of connected vertices until a terminal vertex is reached by one of the players; then the other player wins.
[more]
Contributed by: Igor Mandric (May 2011)
(Moldova State University)
Open content licensed under CC BY-NC-SA
Snapshots
Details
A terminal game with players is defined by:
• a partition of the nonempty set into nonempty sets ;
• a function (i.e. for every , there is a subset of ) such that ;
• a function (i.e. for every element , there is a vector ); is called the payoff function and each player tries to maximize it.
An arbitrary oriented graph with at least one terminal vertex can represent a Nim-like game that is a particular case of a terminal game on graphs with , , and equal to the set of terminal vertices. It can be verified that can be partitioned into subsets and (i.e. and ) with the properties:
• ,
• .
The vertices in the set are called the "gain" vertices, and those in are called the "loss" vertices, because the player who chooses a vertex from offers only losing vertices to the opponent (from ), and the player who chooses a vertex from offers only winning vertices (from ). Obviously is the graph's kernel. Define to be the set of terminal vertices.
The algorithm is:
1. Set .
2. For every vertex from , we know if belongs to or to
Let , and
Then, and .
3. Let .
only when .
Reference
[1] B. Kummer, Spiele auf Graphen, Berlin 1979.
Permanent Citation