# 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 CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

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