Nimbers are inevitable

Julien Lemoine and Simon Viennot
Additional contact information
Julien Lemoine: LIFL - Laboratoire d'Informatique Fondamentale de Lille - Université de Lille, Sciences et Technologies - Inria - Institut National de Recherche en Informatique et en Automatique - Université de Lille, Sciences Humaines et Sociales - CNRS - Centre National de la Recherche Scientifique, SMAC - Systèmes Multi-Agents et Comportements - CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 - Centrale Lille - Université de Lille - CNRS - Centre National de la Recherche Scientifique
Simon Viennot: LIFL - Laboratoire d'Informatique Fondamentale de Lille - Université de Lille, Sciences et Technologies - Inria - Institut National de Recherche en Informatique et en Automatique - Université de Lille, Sciences Humaines et Sociales - CNRS - Centre National de la Recherche Scientifique, SMAC - Systèmes Multi-Agents et Comportements - CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 - Centrale Lille - Université de Lille - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

Abstract: This article concerns the resolution of impartial combinatorial games, in particular games that can be split in sums of independent positions. We prove that in order to compute the outcome of a sum of independent positions, it is always more efficient to compute separately the nimber of at least one of the independent positions, rather than to develop directly the game tree of the sum. The concept of the nimber is therefore inevitable to accelerate the computation of impartial games, even when we only try to determine the winning or losing outcome of a starting position. We also describe algorithms to use nimbers efficiently and to conclude, we give a review of the results obtained on two impartial games: Sprouts and Cram.

Date: 2012
References: Add references at CitEc
Citations:

Published in Theoretical Computer Science, 2012, 462, pp.70-79. ⟨10.1016/j.tcs.2012.09.002⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-00825749

DOI: 10.1016/j.tcs.2012.09.002

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().