CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

The star-operator and invariant subtraction games

Urban Larsson (Institutionen för matematiska vetenskaper, matematik)
Theoretical Computer Science (0304-3975). Vol. 422 (2012), p. 52-58.
[Artikel, refereegranskad vetenskaplig]

An invariant subtraction game is a 2-player impartial game defined by a set of invariant moves (k-tuples of non-negative integers),m. Given a position (another k-tuple) x = (x(1),...,x(k)), each option is of the form (x(1) - m(1)...x(k)-m(k)), where m = (m(1)...m(k)) is an element of M, and where x(i) - m(i) >= 0, for all i. Two players alternate in moving and the player who moves last wins. The set of non-zero P-positions of the game A defines the moves in the dual game M-star. For example, in the game of (2-pile Nim)(star) a move consists in removing the same positive number of tokens from both piles. Our main results concern a double application of star, the operation M -> (M-star)(star). We establish a fundamental 'convergence' result for this operation. Then, we give necessary and sufficient conditions for the relation M = (M-star)(star) to hold, as is the case for example with M = k-pile Nim.

Nyckelord: Dual game, Game convergence, Game reflexivity, Impartial game, Invariant, subtraction game, star-operator

Denna post skapades 2012-04-02.
CPL Pubid: 156375


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)



Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:

Impartial Games and Recursive Functions