Wythoff games, continued fractions, cedar trees and Fibonacci searches
type: Item
instance of: scholarly article
title: Wythoff games, continued fractions, cedar trees and Fibonacci searches
zbMATH Open document ID: 0557.90107
DOI: 10.1016/0304-3975(84)90066-5
author: Aviezri S. Fraenkel
published in: Theoretical Computer Science
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 91A05
Mathematics Subject Classification ID: 11A55
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 91A20
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 3889317
zbMATH Keywords: computation of winning strategies
zbMATH Keywords: misere play
zbMATH Keywords: cedar tree
zbMATH Keywords: generalized Wythoff game
zbMATH Keywords: algorithm
reviewed by: Irinel Dragan
MaRDI profile type: Publication
full work available at URL: 0304-3975(84)90066-5
OpenAlex ID: W2026086747
cites work: Ten Years of Hoare's Logic: A Survey—Part I
cites work: Q3898009
cites work: Q3899466
cites work: Q3914409
cites work: Q3939218
cites work: Programming Language Constructs for Which It Is Impossible To Obtain Good Hoare Axiom Systems
cites work: Effective Axiomatizations of Hoare Logics
cites work: Soundness and Completeness of an Axiom System for Program Verification
cites work: Q3854596
cites work: The IO- and OI-hierarchies
cites work: A sound and relatively* complete Hoare-logic for a language with higher type procedures
cites work: First-order dynamic logic
cites work: An axiomatic basis for computer programming
cites work: Q5626277
cites work: Pascal. User manual and report. 2nd ed
cites work: On correct procedure parameter transmission in higher programming languages
cites work: On termination problems for finitely interpreted ALGOL-like programs
cites work: The formal termination problem for programs with finite ALGOL 68-modes
cites work: Q3883459
cites work: Sound and complete Hoare-like calculi based on copy rules
cites work: Q3040481
cites work: On the notion of expressiveness and the rule of adaptation
cites work: Q5559220
cites work: Generic commands--a tool for partial correctness formalisms
description: scientific article; zbMATH DE number 3889317