Generalized impartial games

A complete mathematical theory of NIM type games have been developed byBouton 1902],Sprague 1935/36] andGrundy 1939]. The NIM type games are a special class of combinatorial games, called the impartial games. “Impartial” means that, at any stage, the set of legal moves is independent of whose turn it is to move. The outcome of an impartial game is that the first player either wins or loses. The results ofBouton, Sprague andGrundy are now generalized to a wider class of games which allow tie-positions. This wider class of games are defined on digraphs. It is proved that the games defined on a given digraph are all impartial games (without tie-positions) iff the birthday function (also called the terminal distance function) exists on this digraph.