Accueil/Jeux/Jeux de Nim/Wythoff Grundy

Jeu de Wythoff
Fonction de Grundy - Périodicité


Règles, description

Les deux joueurs déplacent à tour de rôle un pion sur se quadrillage. le gagnant est le premier à atteindre l'origine : la case (0, 0).
Les déplacements permis à partir de la case (x, y) sont vers l'ensemble Im(x, y) des cases (x-a, y), (x, y-b) ou (x-c, y-c) avec les conditions 0<a<x, 0<b<y et 0<c<x et c<y.

(Page du jeu de Wythoff)

Le graphe correspondant est sans circuit et il existe une fonction de Grundy g unique.
g(0, 0) = 0 et pour x et y non tous les deux nuls, g(x, y) est le plus petit entier qui n'est pas dans g(Im(x, y)).

Les valeurs nulles g(x, y) = 0 correspondent aux positions gagnantes du jeu, c'est-à-dire les cases où placer le pion chaque fois que l'on joue, pour gagner, (du moins lorsque l'adversaire n'a pu nous en empêcher, s'il en a eu la possibilité en début de partie).

Grundy g(x,y) g(x,y)-x+2y x+y-g(x,y)


Calculs

Sauf pour certains couples particuliers comme (0, y),(x, 0) ou encore pour ceux où la fonction de Grundy s'annule, on ne connaît pas de formule permettant un calcul direct. La seule possibilité est donc le calcul par récurrence de la fonction de Grundy, ici un programme en javascript se charge des calculs.

Tant que x et y restent petits, g(x, y) se calcule aisément. Le programme de cette page a pu effectuer les calculs pour x et y inférieurs à N=200, mais évitez de lui en demander trop !

Le programme permet d'obtenir les valeurs g(x, y) modulo un entier m supérieur ou égal à 2. Il permet aussi de mettre en évidence, en les écrivant en rouge, les valeurs supérieures à un entier K donné.
Indiquez les valeurs de m et de K avant de lancer le calcul ou au contraire laissez les cases vides, ci-dessous.
Pour obtenir la table de g(x,y)-s+2*y ou de x+y-g(x,y) au lieu de g(x,y), cocher la case correspondante.

Valeurs maximales de x et de y, X Y =
g(x, y) est calculé modulo m =
Valeur coloriée à partir de K =
Grundy g(x)
Périodique g(x,y)-x+2y
Périodique x+y-g(x,y)

Propriétés

Symétrie g(x, y) = g(y, x).
Alignements des positions gagnantes sur deux droites.
Chaque ligne ou colonne du tableau est une permutation de N. En particulier, pour x=0 on a g(0, y) = y et pour y=0, g(x, 0)=x.
g(x, y) est compris (au sens large) entre x-2y et x+y. (Howard Landman)
Pour y fixé et x variable, la suite des g(x,y) -x + 2*y est périodique après un certain rang. Les périodes sont successivement, pour y = 0 : [0], pour y = 1 : [3, 3, 0], pour y = 2 : [6, 3, 3], pour y = 3 : [8, 9, 4, 2, 9, 4] ...
De même sont périodiques,lorsque x est variable et y constant, les suites de la forme a.(g(x,y)-x+b).
Les suites périodiques sans doute les plus naturelles sont sans doute g(x,y) -x + 2*y et x+y-g(x,y).

Liens vers d'autres pages du site


Documents - compléments - Liens


A Simple FSM-Based Proof of the Additive Periodicity of the Sprague--Grundy Function of Wythoff's Game  by Howard Landman, 383-386 - More Games of No Chance - Edited by Richard J. Nowakowski MSRI Publications -- Volume 42
Alternate Proof of the Additive Periodicity of the Sprague-Grundy Function of Wythoff's Game (Video 56 k)   by Howard Landman. (Image de qualité médiocre).
Liens sur les jeux de Nim   
Numericana.com Wythoff et Grundy sur le site de Gérard Michon  






















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014