Wythoff games, continued fractions, cedar trees and Fibonacci searches (Q761983): Difference between revisions

The generalized Wythoff game may be described as follows: Let A be a positive integer. Given two piles of tokens, two players move alternately. A player may remove any positive number of tokens from a single pile, or he may take from both piles, say k from one and h from the other, provided that \(| k-h| <A\). A normal play means that the player first unable to move is the loser and a misere play means that such a player is the winner. In a previous paper by the author [Am. Math. Mont. 89, 353-361 (1982; Zbl 0504.90087)] it has been shown how the winning strategies may be computed recursively, algebraically and arithmetically in a normal play. In this paper the three analogous strategies are shown and justified for misère play. In addition the concept of ceder tree attached to a Wythoff game is defined and used to compute the winning strategies. The algorithm is stated and its complexity has been computed.