Teorema de Sprague-Grundy

En la teoria de jocs combinatoris, la teorema de Sprague-Grundy establix que tot joc imparcial baixe la convenció de joc normal és equivalent a un joc d'un montó de Nim, o a una generalisació infinita de Nim. Per tant, pot representar-se com un número natural, el tamany del montó en el seu joc equivalent de Nim, com un número ordinal en la generalisació infinita, o alternativament com un nimber, el valor d'eixe joc d'un montó en un sistema algebraic que el seu L'operació d'adició combina varis montons per a formar un únic montícul equivalent en nim.

El valor Grundy o valor Nim de qualsevol joc imparcial és el nimber únic al que és equivalent el joc. En el cas d'un joc les posicions del qual estan indexades per número natural (com el propi nim, que està indexat pel tamany del seu montó), la seqüència de nimbers per a posicions successives del joc es denomina seqüència Nim del joc.

La teorema de Sprague-Grundy i la seua demostració encapsulan els principals resultats d'una teoria descoberta independentment per R.P. Sprague (1935) i P.M. Grundy (1939).

Definicions

A los efectos de la teorema Sprague-Grundy, un joc és un joc seqüencial de dos jugadors d'informació perfecta que satisfà la condició de finalisació (tots els jocs apleguen al seu fi: no hi ha llínees infinites de joc) i el estat de reproducció normal (un jugador qui no pot moure's pert).

En qualsevol punt del joc, la posició de un jugador és el conjunt de moviments que se li permet realisar. Com a eixemple, podem definir el joc zero com el joc de dos jugadors en el que cap jugador té moviments llegals. Referint-se als dos jugadors com (per a Alice) i  (per a Bob), denotaríem les seues posicions com , ya que el conjunt de moviments que pot realisar cada jugador està buit.

Un joc imparcial és aquell en el que en qualsevol moment del joc, a cada jugador se li permet exactament el mateix conjunt de moviments. Nim de joc normal és un eixemple de joc imparcial. En nim, hi ha un o més montons d'objectes, i dos jugadors (els cridarem Alice i Bob), es turnan per a elegir un montó i eliminar 1 o més objectes d'ell. El guanyador és el jugador que elimina l'objecte final del montó final. El joc és imparcial perque per a qualsevol configuració donada de tamanys de pila, els moviments que Alice pot fer en la seua tanda són exactament els mateixos moviments que Bob podria fer si fora la seua tanda. Pel contrari, un joc com les dames no és imparcial perque, suponent que Alice jugara roig i Bob jugara negre, per a qualsevol disposició de peces en el tauler, si fora la tanda d'Alice, solament se li permetria moure les peces roges, i si fora la tanda de Bob, solament se li permetria moure les peces negres.

Tinga en conte que, per tant, qualsevol configuració d'un joc imparcial pot escriure's com una posició única, perque els moviments seran els mateixos sense importar de quí siga la tanda. Per eixemple, la posició del joc zero es pot escriure simplement, perque si és la tanda d'Alice, ella no té moviments que fer, i si és la tanda de Bob, ell tampoc té moviments que fer. Un moviment pot associar-se en la posició en la que deixa al següent jugador.

Plantilla:AnchorEixemple de joc de Nim

• En el pas 6 del joc (quan tots els montons estan buits) la posició és $\{\}$, perque Bob no té moviments vàlits que fer. Nomenem esta posició $*0$.
• En el pas 5, Alice tenia exactament una opció: eliminar un objecte del montó C, deixant a Bob sense moviments. Ya que el seu moviment deixa a Bob en posició $*0$, la seua posició està escrita $\{*0\}$. Nomenem esta posició $*1$.

• En el pas 4, Bob tenia dos opcions: eliminar un de B o eliminar un de C. Tinga en conte, no obstant, que realment no importava de quin montó Bob va eliminar l'objecte: De qualsevol manera, Alice es quedaria en exactament un objecte en exactament una pila. Llavors, usant la nostra definició recursiva, Bob realment solament té un moviment: $*1$. Per tant, la posició de Bob és $\{*1\}$.
• En el pas 3, Alice tenia 3 opcions: llevar dos de C, llevar un de C o llevar un de B. Llevar dos de C deixa a Bob en posició $*1$. Llevar un de C deixa a Bob en dos montons, cada u de tamany un, és dir, posició $\{*1\}$, com es descriu en el pas 4. No obstant, llevar 1 de B deixaria a Bob en dos objectes en una sola pila. Els seus moviments serien llavors $*0$ i $*1$, per lo que el seu moviment resultaria en la posició $\{*0,*1\}$. La posició d'Alice és llavors el conjunt de tots els seus moviments: $\{*1,\{*1\},*2\}$.
• Seguint la mateixa llògica recursiva, en el pas 2, la posició de Bob és $\{\{*1,\{*1\},*2\},*2\}$.
• Finalment, en el pas 1, la posició d'Alice és

$\left\{\right\{*1,\{*1\},*2\},\{*2,\{*1,\{*1\},*2\}\},\{\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}\left\}\right\}$.

Nimbers

Els noms especials $*0$, $*1$, i $*2$ referenciados en el joc d'eixemple es diuen nimbers. En general, el nimber $*n$ correspon a la posició en un joc de Nim a on hi ha exactament $n$ objectes en exactament un montó. Formalment, els nimbers es definixen inductivamente de la següent manera: $*0$ is $\{\}$, $*1=\{*0\}$, $*2=\{*0,*1\}$ i para tot $n\ge 0$, $*(n+1)=*n\cup \{*n\}$.

Si be la paraula nimber prové del joc nim, nimbers pot usar-se per a descriure les posicions de qualsevol joc finito i imparcial i, de fet, la teorema de Sprague-Grundy establix que cada instància d'un joc finito i imparcial pot associar-se en un nimber únic.

Combinant jocs

Es poden combinar dos jocs sumant les seues posicions. Per eixemple, considere un atre joc de Nim en montons $A^{\prime }$, $B^{\prime }$, i $C^{\prime }$.

Plantilla:AnchorJugue d'eixemple 2

Podem combinar-ho en el nostre primer eixemple per a obtindre un joc combinat en sis montons: $A$, $B$, $C$, $A^{\prime }$, $B^{\prime }$, and $C^{\prime }$:

Plantilla:AnchorJugue combinat

Per a diferenciar entre els dos jocs, per al primer joc d'eixemple , etiquetarem la seua posició inicial $S$, coloreado de blava:

$S=\{\{*1,\{*1\},*2\},\{*2,\{*1,\{*1\},*2\}\},\{\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}\}\}$

Per al segon joc d'eixemple , etiquetarem la posició inicial $S^{\prime }$coloreado de roig:

$S^{\prime }=\{\{*1\}\}$.

Per a calcular la posició inicial del joc combinat, recuerdése que un jugador pot fer un moviment en el primer joc, deixant el segon sense tocar, o fer un moviment en el segon joc, deixant el primer joc sense tocar. Llavors, la posició inicial del joc combinat és:

$S+S^{\prime }=\{S+\{*1\}\}\cup \{S^{\prime }+\{*1,\{*1\},*2\},S^{\prime }+\{*2,\{*1,\{*1\},*2\}\},S^{\prime }+\{\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}\}\}$

La fòrmula explícita per a agregar posicions és: $S+S^{\prime }=\{S+s^{\prime }\mid s^{\prime }\in S^{\prime }\}\cup \{s+S^{\prime }\mid s\in S\}$, lo que significa que la suma és tant conmutativa com a associativa