Ampliación de los juegos de Conway a $n$ jugadores

Question

¿Ha intentado alguien ampliar la definición de los Juegos de Conway a $n$ ¿jugadores? Y si no, ¿cuál sería la definición de $-G$ en dicha teoría?

Motivación

La mayoría de las definiciones de juego de la ONAG parecen tener una extensión natural a $n$ jugadores. Por ejemplo: Que $G = \{G_1|G_2|\ldots|G_n\}$ ser un juego con $n$ jugadores donde el jugador $p$ tiene opciones $G_p$ . $n$ -La adición de jugadores también es fácil de ampliar: $G+H = \{G_1 + H, H_1 + G|\ldots|G_n + H, H_n+G\}$ . La verdadera dificultad parece ser una definición razonable de $-G$ y alguna forma canónica para $G$ . He intentado una definición de $-G$ .

(En lo que sigue, daré por sentado que la suma de juegos es conmutativa y asociativa, ya que la prueba es esencialmente la misma que en el caso de 2 jugadores. Nuestros juegos son finitos en todos los casos).

Negativo $G$

Dejemos que $\sigma^n$ sea una permutación de $(1,2,\ldots,n)$ y $\sigma_p^n$ sea el $p$ th $(1 \leq p \leq n)$ entrada de $\sigma^n$ . Nos limitaremos a escribir $\sigma$ o $\sigma_p$ cuando $n$ se entiende. Tomaremos $G + H$ como en el caso anterior. Definir $\stackrel{\sigma}{-}G := \{\stackrel{\sigma}{-}G_{\sigma_1}|...|\stackrel{\sigma}{-}G_{\sigma_n}\}$ . ( $\overset{\sigma}{-}G$ se denominan inversos parciales de $G$ o permutaciones de $G$ ).

$$ -G = \sum_{\sigma^n/e} \stackrel{\sigma}{-}G $$

Donde sumamos sobre todas las permutaciones excepto la identidad ( $e=(1,2,\ldots,n)$ ) permutación. Ejemplo: $$ -G = -\{G_1|G_2|G_3\} = \stackrel{132}{-}G +\stackrel{213}{-}G+\stackrel{231}{-}G+\stackrel{312}{-}G+\stackrel{321}{-}G = $$ $$ \{\stackrel{132}{-}G_1|\stackrel{132}{-}G_3|\stackrel{132}{-}G_2\} + \ldots+ \{\stackrel{321}{-}G_3|\stackrel{321}{-}G_2|\stackrel{321}{-}G_1\} $$

La idea es que si tenemos el árbol de juego de G con las flechas etiquetadas por los jugadores, entonces $-G$ es la suma de cualquier otra permutación de etiquetas. Algunos ejemplos más:

$$ -0_3=-\{||\}=\stackrel{132}{-}0+\ldots+\stackrel{321}{-}0=0 $$ $$ -H=-\{0||\}=\stackrel{132}{-}\{0||\}+\ldots+\stackrel{321}{-}\{0||\}= $$ $$ \{0||\}+\{|0|\}+\{||0\}+\{|0|\}+\{||0\} $$

Por supuesto, tendríamos que comprobar que $G+(-G)=0$ y $-(-G)=G$ para que esto sea el $-G$ . Sospecho que podríamos hacerlo si equivocamos todas las partidas que son pérdidas del primer jugador al juego cero . (Con la convención sólo hay un perdedor y los jugadores juegan de forma óptima: véase la Convención de la Mejor Jugada más adelante). Tenga en cuenta que $H+(-H)$ del último ejemplo es una pérdida de primer jugador.

Por otra parte, tenemos $G=\stackrel{e}{-}G \implies \sum_{\sigma^n} \stackrel{\sigma}{-}G = 0 \iff G + (-G) = 0$ .

¡Pero conozco el orden de los movimientos!

También hay un estricto versión de $-G$ que llamaremos $\ominus G$ que podemos definir si conocemos el orden en que se mueven los jugadores. Supongamos que los jugadores $(1,2,\ldots,n)$ moverse en algún orden $(1+p,2+p,...,n+p)$ donde tomamos $(p \mod n)$ . Entonces $\ominus G = \sum_{\sigma^{n}/e} \overset{\sigma}{-}G$ pero aquí $\sigma$ se extiende sobre el turnos de $(1+p,2+p,\ldots,n+p)$ (excluyendo el cambio de identidad, $e$ ) en lugar de las permutaciones, de modo que nuestra suma sólo contiene $n-1$ términos en lugar de $n!-1$ términos. (Podemos llamar al $\overset{\sigma}{-}G$ En este caso, estricto inversiones parciales o desplazamientos de $G$ .)

Robo de estrategias

He encontrado el argumento de robo de estrategia para $G + (-G) = 0$ de los juegos de 2 jugadores no funciona del todo. Considere el siguiente juego:

Los puntos indican una continuación muy larga, pero finita. WLOG, deja que $Red$ jugar primero, entonces, si los otros jugadores reflejan adecuadamente $Red$ la partida terminará después de una secuencia muy larga (pero finita) de movimientos como una pérdida para $Red$ . Sin embargo, $Red$ y $Blue$ pueden conspirar para terminar el juego después de sólo $8$ movimientos (con el orden de juego $(\ldots ,Red,Blue,Green,Red,\ldots)$ ) jugando sólo en $G$ ( $=\stackrel{e}{-}G$ ); $Green$ se verá obligado a utilizar su única $2$ movimientos disponibles. Entonces, ¿este juego no es el $0$ ¿juego?

De hecho, es el $0$ juego como $Blue$ y $Green$ puede conspirar contra $Red$ para terminar el juego incluso antes, en un mero $6$ movimientos (!), jugando sólo en el $\stackrel{RBG}{-}G$ componente. Esta convención de la mejor jugada forzará una pérdida del primer jugador (la pérdida más pronta que se puede forzar, véase más adelante). Tenga en cuenta que, tomando $G$ de este ejemplo, $G+(\ominus G)$ también es una pérdida para el primer jugador.

Convención Best-Play

Supongamos que los jugadores de algún juego $G$ son $\mathbb{P} = \{p_1,\ldots,p_n\}$ . Consideramos que la mejor jugada es la pérdida que puede ser forzada en el menor número de movimientos por los jugadores $\mathbb{P}/p_k$ cooperando contra $p_k$ , $ \forall p_k \in \mathbb{P}$ . Si $\mathbb{P}/p_m$ obliga a tal pérdida entonces diremos que $p_m$ pierde $G$ y llamamos $\mathbb{P}/p_m$ el ganador coalición . Lo que realmente queremos decir con $G = 0$ es que $G$ es una pérdida del primer jugador bajo esta convención de mejor jugada.

Todavía no ha llegado el momento...

Desafortunadamente, bajo nuestras convenciones, nuestra inversa falla en $G = \{0|0|\}$ . O bien hay que revisar nuestras convenciones o tendremos que redefinir $-G$ . La respuesta de Mark S. a continuación asume una convención diferente y obtiene una inversa factible, pero tal vez demasiados juegos son equivalentes a la $0$ juego bajo tal convención. He considerado la equivalencia $G \equiv 0$ si $G = \stackrel{\sigma}{-}G$ , $\forall \sigma$ pero sigue pareciendo mucho menos interesante que $G \equiv 0$ si $G$ es una pérdida de primer jugador en el marco del Best Play.

En un intento de derivar $-G$ calculé a mano los (posibles) inversos de algunos juegos simples bajo la restricción de que el inverso de un $n$ -Juego de profundidad $d$ debe ser una suma de $n!-1$ profundidad- $d$ juegos (y la suma de $G$ y $-G$ son una pérdida para el primer jugador). Aquí hay unas cuantas inversiones para juegos de profundidad-1 de 3 jugadores que sugieren un patrón simple para una profundidad-1 similar $n$ -Juegos de jugadores:

Por $nG$ nos referimos a $\sum_{1}^{n}G$ . Si la suma y la resta del juego funcionan como esperamos, la segunda ecuación anterior se derivaría fácilmente de la primera con sólo mover los términos. Para calcular inversiones más complejas, también asumo que las inversiones se distribuyen sobre la suma del juego y luego compruebo a mano que el resultado es una pérdida del primer jugador. También aprendí otro truco para el que no tengo explicación de por qué funciona, pero que intentaré demostrar.

Intentemos averiguar $-\{|\{0||0\}|\}$ utilizando sólo la tabla de inversiones anterior. En primer lugar, observamos que esto es sólo un árbol de juego parcial de $-(\{|0|\}+\{0||0\})$ . Podemos calcularlo directamente:

Ahora añadimos los términos dentro de los paréntesis y reordenamos los términos en el lado derecho:

En este punto sólo supongo que un subárbol del LHS sería una suma de subárboles del RHS. Como se señaló anteriormente, no tengo ni idea de por qué esto sería cierto, pero, al menos en este caso, me lleva a una inversa de trabajo:

Aquí, la raíz del árbol está en la línea de puntos y he puesto los subárboles que me dan la inversa que estoy buscando por encima de la línea de puntos. Vale la pena señalar que lo que queda por debajo de la línea de puntos no es una ecuación correcta, ya que es una pérdida para Green.

Esto puede o no ser un método útil para derivar inversiones más difíciles. Comprobar estas ecuaciones a mano es bastante tedioso, incluso para estos juegos de baja profundidad, y puede ser más útil conseguir un programa para forzar algunos de estos y ver si hay algún patrón reconocible - puedo o no intentar esto pronto. Aunque invitaría a cualquier otra persona con interés en ello a intentarlo.

Answer 1

Definiciones

Suma de juegos

La OP dice "Se podría esperar que [definición de suma]". Creo que deberíamos tomar eso como la definición de suma disyuntiva. Creo que es una extensión muy natural de la definición de 2 jugadores, y coincide con la definición de A. Cincotti 's " N -jugadores de juegos partizan ".

Igual a cero

Para la definición de igualdad, en medio de la pregunta, el PO incluye una información muy importante: "Sospecho que podríamos hacerlo si equivocamos todas las partidas que son pérdidas del primer jugador a la partida cero".

Preocupación

Aunque no se trata de una definición completa de la igualdad de los juegos, me gustaría señalar que esto hace que esta propuesta de definición de la igualdad sea considerablemente más gruesa que las definiciones tradicionalmente utilizadas en CGT . Resulta que es una especie de teorema casual que en juego normal todos los juegos de 2 jugadores que tienen pérdidas para el primer jugador son equivalentes (en el sentido habitual de preservar los resultados para todos sumas ), pero incluso en 2 jugadores misère play En este caso, se viola el espíritu de la definición propuesta en el PO. Por ejemplo, el Nim posiciones $0$ y $G=2+2+1$ son ambas victorias de misère para el siguiente jugador (para $G$ la jugada ganadora es tomar el montón de tamaño $1$ ). Pero como $G+G$ es una victoria misère para el jugador anterior (espejo hasta el final) y $0+G$ no es, decimos $G\ne0$ .

Posibles significados

En cualquier caso, podemos romper con la convención y declarar por decreto que $G+\left(-G\right)=0$ siempre y cuando $G+\left(-G\right)$ es una "pérdida del primer jugador". Pero entonces tenemos otro problema: ¿qué significa aquí ser una "pérdida de primer jugador"?

$0$ es 1. "un juego que el primer jugador pierde independientemente de cómo jueguen los demás", 2. "un juego que el primer jugador pierde porque algún otro jugador tiene una estrategia ganadora", 3. "un juego que el primer jugador pierde si todos los demás jugadores conspiran para que eso ocurra", y 4. "un juego que el primer jugador pierde si alguna pequeña coalición conspira para que eso ocurra". Para todas estas posibilidades, también está la cuestión de A. "bajo al menos un orden de juego" frente a B. "bajo todos los órdenes de juego" frente a C. "en el contexto de un orden de juego concreto". La discusión del ejemplo hacia el final de la pregunta sugiere que 3B o 4B era la intención principal de la OP, aunque también parecen contentos de considerar 3C o 4C (dada la discusión de $\ominus$ ). El debate sobre las coaliciones en La respuesta de Salt deja claro que el 4 no es una opción, por lo que parece que la intención era el 3B (o el 3C, según el contexto).

Definición

Para aclarar esta ambigüedad, dejaré que " $=0$ " signifique "un juego que el primer jugador siempre perderá (bajo cualquier orden de juego) si los otros jugadores están coludidos con ese objetivo". Y que una notación como " $\equiv0$ " significan "un juego que el primer jugador siempre perderá (bajo un orden de juego determinado por el contexto) si los otros jugadores están coludidos con ese objetivo".

Negativos

Definiremos $-G$ y $\ominus G$ como en la pregunta original. Brevemente, $-G$ es la suma de todas las copias de $G$ con diferentes órdenes de juego, y $\ominus G$ es la suma de todas las copias de $G$ con las permutaciones cíclicas del orden de juego.

---

Los negativos son inversos

Teorema 1

$G+\left(\ominus G\right)\equiv0$

Prueba:

Dado un determinado orden de juego para n jugadores, todos los jugadores que no sean el primero pueden reflejar las jugadas en sus correspondientes componentes, de modo que después de $n$ se mueve, tenemos $G'+\left(\ominus G'\right)$ para alguna opción $G'$ . Por inducción estructural, esto es suficiente para demostrar la afirmación.

Lema:

Una suma finita de juegos que son $\equiv0$ también son $\equiv0$ .

Prueba

En primer lugar, consideremos una suma de dos juegos: queremos demostrar que si $G\equiv0$ y $H\equiv0$ entonces $G+H\equiv0$ . Por cada movimiento del primer jugador, la coalición de todos los demás puede responder en el mismo componente para reducir las cosas a, WLOG, $G+H'$ donde $H'\equiv0$ . Por inducción, esto es suficiente para dos componentes. Entonces, por inducción sobre el número de componentes, tenemos que cualquier suma finita como ${\displaystyle \sum_{i=1}^{m}G_{i}\equiv0}$ si $G_{i}\equiv0$ para todos $i$ .

Teorema 2

$G+\left(-G\right)=0$

Prueba

El $n!$ Las permutaciones de los jugadores están todas representadas en la suma $G+\left(-G\right)$ y para cualquier elección de orden de juego, se dividen en $\left(n-1\right)!$ copias de algo de la forma $G'+\ominus G'$ para una adecuada $G'$ s. Por ejemplo, con $4$ jugadores y un orden de turno como $\left(1234\right)$ la suma podría ser sugerida por $\left(G^{1234}+G^{2341}+G^{3412}+G^{4123}\right)+\left(G^{1324}+\cdots\right)+\left(G^{1432}+\cdots\right)+\left(G^{1243}+\cdots\right)+\left(G^{1342}+\cdots\right)+\left(G^{1423}+\cdots\right)$ . Por el Teorema 1 y el lema, esto debe ser $\equiv0$ . Como este argumento funciona para cualquier orden de juego, tenemos $G+\left(-G\right)=0$ .

---

Propiedades de $=$

Ni el PO ni la respuesta de Salt contienen una definición de $=$ en general. Pero en la respuesta de Salt, parece que asumen 1. $=$ es transitivo, y 2. $X=0\Rightarrow G+X=G$ .

El $-G$

Como se indica en la respuesta de Salt, podemos utilizar esas propiedades para demostrar algebraicamente que $-\left(-G\right)=G$ : Tenga en cuenta que $G+-G+-\left(-G\right)=G$ desde $-G+-\left(-G\right)=0$ y $G+-G+-\left(-G\right)=-\left(-G\right)$ desde $G+-G=0$ . Por transitividad, tenemos $G=-\left(-G\right)$ .

Además, el OP mencionó " el $-G$ " de una manera que parecía asumir implícitamente la unicidad, como en $G+G_{1}=G+G_{2}=0\Rightarrow G_{1}=G_{2}$ . Esto se puede comprobar con un álgebra muy similar, simplemente considerando $G_{1}+G+G_{2}$ para demostrar que $G_{1}=G_{2}$ .

Comentarios

Desde $X\equiv0$ es cierto para muchos juegos, " $X\equiv0\Rightarrow G+X\equiv G$ " haría un lote de juegos iguales bajo $\equiv$ . Por ejemplo, si $X$ es cualquier juego en el que el primer jugador nunca tiene un movimiento, entonces $X\equiv0$ para que $G+X\equiv G$ para todos $G$ aunque $X$ hace algo así como dar al séptimo jugador un millón de movimientos gratis para que gane $G+X$ para $G$ de tamaño razonablemente pequeño. Para $=$ en lugar de $\equiv$ la situación sería menos extrema, pero todavía más gruesa que una definición estándar, como se ha señalado anteriormente.

Answer 2

Teorema: $\sum_{\sigma^n}\overset{\sigma}{-}G = 0$ , donde $G$ es un $n$ -Juego de jugadores.

Prueba de ello: Sea $H=\sum_{\sigma^n}\overset{\sigma}{-}G$ y que $A$ piojos, $B$ ob, y $E$ odos los demás sean jugadores de $H$ . Supongamos que $A$ se mueve primero y, por contradicción, no pierde. WLOG, deja que $B$ ser el jugador que pierde $H$ . Entonces $A+E$ (la coalición de $A$ , donde $A$ elige $E$ ) debe ganar antes de que $B+E$ . Dejemos que $\underset{A+E}{H}$ sea el juego tal y como lo juega $A+E$ . Si $B+E \in \underset{B+E}{H}$ espejos $A+E \in \underset{A+E}{H}$ mientras que $B \in \underset{A+E}{H}$ espejos $A \in \underset{B+E}{H}$ entonces los juegos tal y como se juegan son exactamente los mismos hasta la permutación, pero $A$ se queda sin opciones antes de $B$ como $A$ juega primero, contradiciendo nuestra suposición de que $A+E$ fue el coalición ganadora. (La mejor secuencia para este reflejo podría ser dejar que $A+E \in \underset{A+E}{H}$ mover hasta que sea $B$ El turno de la mujer $\in \underset{A+E}{H}$ . Entonces dejemos que $A \in \underset{B+E}{H}$ mover. Ahora $B$ , $B+E$ , $A$ , $A+E$ pueden alternar los movimientos de forma normal). Por lo tanto, $A$ El primer jugador que mueve, pierde y nuestro teorema se cumple.

Observamos que este reflejo es posible tanto si $\sigma$ rangos sobre los turnos (suponiendo un orden de juego para (A,B,E), que se puede hacer WLOG) o permutaciones de $(A,B,E)$ . Así que tenemos $G + (\ominus G) = 0$ y $G + (-G) = 0 $ . (También, $G+(\ominus G) = 0 \implies G + (-G) = 0$ .)

Armados con este teorema podemos ahora simplificar canónicamente las cargas de $G$ . Por ejemplo, consideremos el número típico de términos en el cálculo de $-(-G)$ . Pero como sabemos que $G + (-G) = -G + (-(-G))$ tenemos una justificación para definir la equivalencia $G = -(-G)$ . Del mismo modo, para $\ominus(\ominus G)$ .