Defining a finite impartial game.

Question

I've been wondering how to abstractly describe a finite impartial game, and if there exists a standard way to do so, similar to how one would define a metric space $(M,d)$.

I've read this related question: Definition of game in game theory

However I'm not sure if this is a good solution, specially since I have no idea how to define the set of strategies and the payout function from only the rules of the game.

The game in question is played on a square board, where players may place pieces on squares depending on the number of placed pieces adjacent to said square. Is there any way to define a game from the board shape and the rules for placing pieces on squares, under normal play?

Answer 1

An impartial game is just an acyclic directed graph, so you can use that definition from graph theory. Namely, an impartial game consists of

• A finite* set, $S$, of game states.

• A set, $M\subseteq S\times S$, of allowed moves. If $(s,t)\in M$, it means that you are allowed to move from $s$ to $t$.

This must satisfy the following property, ensuring the game has no cycles, so must end:

• For all $n\in \mathbb N$, there does not exist a sequence $(s_1,s_2,\dots,s_n)\in S^n$ where $(s_i,s_{i+1})\in M$ for each $i\in \{1,\dots,n-1\}$ and $(s_n,s_1)\in M$.

In your case, $S$ would be the set of subsets of your board, representing the places on the board occupied by pieces. You would say that $(s,t)\in M$ if $t$ has exactly one more element than $s$, and the unique element of $t\setminus s$ satisfies whatever local conditions you want to impose.

* You can remove the finite condition, but then you have to replace the "no cycles" condition with a "no infinite move sequences" condition. It seems finite is sufficient for your purposes.

Answer 2

The economic sort of "game theory" as used in that link is not really related to the combinatorial "game theory" that studies impartial games and the like. The latter type of game has no chance and (at least in the classical versions) no payouts, only a winner and a loser. Normally to define a combinatorial game, we define the board and the rules of play, in essentially the way you would normally specify the rules of a game. I'm not sure what you mean by "abstractly" or why you refer to a metric space.