Mathematics – Combinatorics
Scientific paper
2012-01-02
Mathematics
Combinatorics
26 pages, 5 figures
Scientific paper
Given an impartial combinatorial game G, we create a class of related games (CIS-G) by specifying a finite set of positions in G and forbidding players from moving to those positions (leaving all other game rules unchanged). Such modifications amount to taking cofinite induced subgraphs (CIS) of the original game graph. Some recent numerical/heuristic work has suggested that the underlying structure and behavior of such "CIS-games" can shed new light on, and bears interesting relationships with, the original games from which they are derived. In this paper we present an analytical treatment of the cofinite induced subgraphs associated with the game of (three-heap) Nim. This constitutes one of the simplest nontrivial cases of a CIS game. Our main finding is that although the structure of the winning strategies in games of CIS-Nim can differ greatly from that of Nim, CIS-Nim games inherit a type of period-two scale invariance from the original game of Nim.
Friedman Eric J.
Garrabrant Scott M.
Landsberg Adam Scott
No associations
LandOfFree
Cofinite Induced Subgraphs of Impartial Combinatorial Games: An Analysis of CIS-Nim does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Cofinite Induced Subgraphs of Impartial Combinatorial Games: An Analysis of CIS-Nim, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cofinite Induced Subgraphs of Impartial Combinatorial Games: An Analysis of CIS-Nim will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-55190