Is Nim a (strong) positional game?

53 Views Asked by At

A positional game is a kind of a combinatorial game described by:

  • $X$ a finite set of elements. (Often $X$ is called the board and its elements are called positions.)
  • $F$ a family of subsets of $X$. (These subsets are usually called the winning-sets.)
  • A criterion for winning the game.

For $n$-pile Nim, wouldn't $X$ be the union of disjoint posets, e.g. $\{(1,2,...,k_1), (1,2,...,k_2),..., (1,2,...,k_n)\}$? Then a move consists of choosing a point in one of the posets and removing that point and everything above it in said poset.

Then $F$ would be $\{\{{(1,2,...,j),(),()}\}, \{{(),(1,2,...,j),()}\}, \{{(),(),(1,2,...,j)}\}\}$

And the winning criterion is being the first one to "receive" a position in $F$?

This seems right to me, but it appears that player two can have a winning strategy, which contradicts the notion of Nim being strong positional.

1

There are 1 best solutions below

0
On BEST ANSWER

No. For a positional game, the legal moves are to take any element of $X$ which hasn't already been taken. In this setting of Nim, taking an element of one of the posets can mean that several other elements of $X$ stop being legal moves.

Also, I don't think your $F$ makes sense. $F$ should be the sets such that if you can take all of one set in $F$, you win the game. That's not what you have (your $F$ would mean that the winner is the first to take the last $j$ elements of one of the posets).