Juego imparcial

Concepto en la teoría de juegos

En la teoría de juegos combinatorios , un juego imparcial es un juego en el que los movimientos permitidos dependen solo de la posición y no de cuál de los dos jugadores se está moviendo en ese momento, y donde los pagos son simétricos. En otras palabras, la única diferencia entre el jugador 1 y el jugador 2 es que el jugador 1 comienza primero. El juego se juega hasta que se alcanza una posición terminal. Una posición terminal es aquella desde la que no es posible realizar movimientos. Luego, uno de los jugadores es declarado ganador y el otro perdedor. Además, los juegos imparciales se juegan con información perfecta y sin movimientos aleatorios, lo que significa que toda la información sobre el juego y las operaciones de ambos jugadores es visible para ambos jugadores.

Los juegos imparciales incluyen Nim , Sprouts , Kayles , Quarto , Cram , Chomp , Subtract a square , Notakto y juegos de poset . El Go y el ajedrez no son juegos imparciales, ya que cada jugador solo puede colocar o mover piezas de su propio color. Juegos como el póquer , los dados o el dominó no son juegos imparciales, ya que dependen del azar.

Los juegos imparciales pueden analizarse utilizando el teorema de Sprague-Grundy , que establece que cada juego imparcial bajo la convención de juego normal es equivalente a un nimber . La representación de este nimber puede cambiar de un juego a otro, pero cada estado posible de cualquier variación de un tablero de juego imparcial debería poder tener algún valor de nimber. Por ejemplo, se pueden calcular varios montones de nim en el juego nim y luego sumarlos utilizando la adición de nimber para obtener un valor de nimber para el juego.

Un juego que no es imparcial se llama juego partidista , aunque algunos juegos partidistas aún pueden evaluarse utilizando números como Dominante . ^[1] Dominante no se clasificaría como un juego imparcial ya que los jugadores usan piezas que actúan de manera diferente, un jugador con dominós verticales, otro con horizontales, rompiendo así la regla de que cada jugador debe poder actuar usando las mismas operaciones.

Requisitos

Todos los juegos imparciales deben cumplir las siguientes condiciones:

• Dos jugadores deben alternar turnos hasta alcanzar un estado final.
• Se elige un ganador cuando un jugador ya no puede cambiar de posición ni realizar ninguna operación.
• Debe haber un número finito de operaciones y posiciones para ambos jugadores. Por ejemplo, en Nim, los jugadores deben retirar un subconjunto de una pila que esté en juego en ese momento. Como hay un número finito de monedas en cualquier pila, un jugador solo puede retirar un número finito de monedas.
• Todas las operaciones deben poder ser realizadas por ambos lados. En todos los juegos imparciales, los jugadores realizan acciones en un tablero de juego, ya sea en forma de pilas para Nim o filas y columnas para Cram. Ambos jugadores actúan en el tablero hasta que este ya no pueda cambiar de ninguna manera.
• Ninguna acción del juego puede depender del azar. Cualquier inclusión del azar significaría que no hay información perfecta sobre el juego; además, las acciones no podrían minimizarse, lo que descarta cualquier estrategia inductiva. ^[2]

Referencias

1. Avances en juegos de computadora: 14.a Conferencia Internacional, ACG 2015, Leiden, Países Bajos, 1 al 3 de julio de 2015, artículos seleccionados revisados . Herik, Jaap van den, Plaat, Aske, Kosters, Walter. Cham. 24 de diciembre de 2015. ISBN 978-3319279923.OCLC 933627646  .{{cite book}}: CS1 maint: falta la ubicación del editor ( enlace ) CS1 maint: otros ( enlace )
2. Ferguson, Thomas S. (otoño de 2000). "Teoría de juegos" (PDF) .

Lectura adicional

• E. Berlekamp ; JH Conway ; R. Guy (1982). Maneras ganadoras para sus juegos matemáticos . Vol. 2 vols. Academic Press.; Berlekamp, ​​Elwyn R.; Conway, John Horton; Guy, Richard K. (1982). vol. 1 . Prensa académica. ISBN 0-12-091101-9.; Berlekamp, ​​Elwyn R. (1982). vol. 2 . Prensa académica. ISBN 0-12-091102-7.
• E. Berlekamp; JH Conway; R. Guy (2001–2004). Maneras ganadoras para sus jugadas matemáticas . Vol. 4 vols. (2.ª ed.). AK Peters Ltd.; Berlekamp, ​​Elwyn R.; Conway, John H.; Guy, Richard K. (16 de enero de 2001). vol. 1 . ISBN 1-56881-130-6.; vol. 2 . ISBN 1-56881-142-X.; Berlekamp, ​​Elwyn R.; Conway, John Horton; Guy, Richard K. (15 de junio de 2003). vol. 3 . ISBN 1-56881-143-8.; Berlekamp, ​​Elwyn R.; Conway, John Horton; Guy, Richard K. (15 de junio de 2004). vol. 4 . ISBN 1-56881-144-6.