Fonction de grundy exemple

Par conséquent, nous pouvons jouer correctement la somme de n`importe quel nombre de jeux en connaissant la fonction Grundy de chaque jeu individuel. Le grand jeu est appelé la somme disjuctive ou jeu combiné des jeux plus petits. Formellement, les nimbers sont définis de manière inductive comme suit: ∗ 0 {displaystyle * 0} est {} {displaystyle {}}, ∗ 1 = {∗ 0} {displaystyle * 1 = {* 0 }}, ∗ 2 = {∗ 0, ∗ 1} {displaystyle * 2 = {* 0, * 1 }} et pour tous n ≥ 0 {displaystyle ngeq 0}, ∗ (n + 1) = ∗ n ∪ {∗ n} {dis style * (n + 1) = * ncup {* n }}. Rappelez-vous que la fonction Sprague-Grundy renvoie le MEX d`un ensemble. En tant qu`étape intermédiaire pour prouver le théorème principal, nous montrons que pour chaque position G {displaystyle G} et chaque P {displaystyle {mathcal {P}}}-position A {displaystyle A}, l`équivalence G ≈ A + G {displaystyle Gapprox A + G} contient. Ainsi, par exemple, ∗ 0 {displaystyle * 0} est une position P {displaystyle {mathcal {P}}}, tandis que ∗ 1 {displaystyle * 1} est une position N {displaystyle {mathcal {N}}}. Maintenant, supposons que nous avons donné deux jeux G1 et G2. Nous le faisons en donnant une stratégie explicite pour le joueur précédent. Définissons donc la notion de positions équivalentes dans les jeux. Mais la somme de deux positions N peut être soit un P-soit une position N.

Commençons par définir une fonction sur des ensembles d`entiers non numériques appelés l`exclusion minimale (MEX). En outre, ≈ {displaystyle approx} est une relation d`équivalence car l`égalité est une relation d`équivalence sur les classes de résultats. Dans le prochain post, nous allons discuter des solutions de jeux impartiaux en utilisant des nombres Grundy ou nimbers. Notez que toute configuration d`un jeu impartial peut donc être écrite comme une seule position, parce que les mouvements seront les mêmes, peu importe à quel tour il s`agit. Le jeu se termine quand il n`y a que des piles de tailles 1 et 2 à gauche, qui ne peuvent pas être divisés plus loin. Et, comme montré avant, toute position plus elle-même est une position P. Par l`hypothèse d`induction, toutes les options sont équivalentes aux nimbers, par exemple G i ≈ ∗ n i {displaystyle _ _ {i} approx * n_ {i}}. Considérez une position G = {G 1, G 2,…, G k} {displaystyle G = {G_{1}, _ {2}, ldots, _ {k} }}. Les nombres Grundy ou les nimbers déterminent comment n`importe quel jeu impartial (non seulement le jeu de NIM) peut être résolu une fois que nous avons calculé les nombres Grundy associés à ce jeu en utilisant le théorème de Sprague-Grundy.

Il s`avère que la réponse est non. La fonction renvoie le plus petit entier non négatif qui n`est pas dans l`ensemble des valeurs de Sprague-Grundy des disciples de v. Notez que γ ⊕ ω a un 1 dans son KTH bit, et a 0s dans tous les bits à gauche du KTH bit. Nous pouvons classer chaque position dans le jeu selon qu`il s`agisse d`une première ou d`une victoire de deuxième joueur, si les deux joueurs jouent de manière optimale à partir de cette position. Dans le jeu combiné, est un adepte de exactement quand il ya un tel que et pour tous tels que,. Comme il ya certains qui a un 1 à son bit KTH. Un jeu impartial peut être représenté par un graphe acyclique dirigé, dans lequel chaque sommet correspond à une position, et chaque arête dirigée représente un déplacement légal d`une position à une autre. En résumé, nous avons G ≈ G ′ {displaystyle Gapprox G`} et G ′ ≈ ∗ m {displaystyle G` approx * m}. Ainsi, dans ce cas, A + G + H {displaystyle A + G + H} doit être une position N {displaystyle {mathcal {N}}}, tout comme G + H {displaystyle G + H}. Ainsi, x + z et ∗ n + z ont toujours le même résultat par le fait 2, ce qui signifie qu`ils sont équivalents. Grundy en 1939. La connaissance des positions P et N d`un jeu fournit la stratégie gagnante pour elle: si c`est notre tour et le jeu est dans une position N, nous devrions passer dans une position P.

This entry was posted in Uncategorized. Bookmark the permalink.