Juego imparcial

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 actualmente, 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 va 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 ningún movimiento. Entonces 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 para ambos jugadores es visible para ambos jugadores.

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

Los juegos imparciales se pueden analizar mediante el teorema de Sprague-Grundy, que establece que todo 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 nim del juego, y luego sumarlos mediante la suma de nimber, para dar un valor de nimber para el juego.

Un juego que no es imparcial se denomina juego partidista, aunque algunos juegos partidistas aún pueden evaluarse utilizando nimbers como Domineering. El dominio no se clasificaría como un juego imparcial ya que los jugadores usan piezas de diferente actuación, un jugador con fichas de dominó verticales y otro con fichas 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 llegar a un estado final.
• Un ganador es elegido cuando un jugador ya no puede cambiar de posición o hacer cualquier operación.
• Debe haber un número finito de operaciones y posiciones para ambos jugadores. Por ejemplo, en Nim, los jugadores deben quitar un subconjunto de una pila que está actualmente en juego. Como hay un número finito de monedas en cualquier pila, un jugador sólo puede eliminar un número finito de monedas.
• Todas las operaciones deben ser capaces de ser realizadas por ambas partes. En todos los juegos Imparciales, los jugadores están haciendo acciones a alguna tabla de juego ya sea en la forma de pilas para Nim o filas y columnas Cram. Ambos jugadores están actuando en el tablero hasta que el tablero ya no puede cambiar de alguna manera.
• Ninguna acción en el juego puede depender de la oportunidad. Cualquier inclusión de la oportunidad significaría que no hay información perfecta sobre el juego, además acciones no podrían ser minmaxed descartar cualquier forma de estrategia inductiva.