Teoría de los juegos combinatorios: definición, reglas y ejemplos

La teoría de los juegos combinatorios (CGT, por sus siglas en inglés) es una rama de la matemática aplicada y de la informática teórica dedicada al estudio de juegos abstractos en los que no interviene el azar y los jugadores alternan movimientos. Se diferencia de la teoría de los juegos "tradicional" o "económica" en sus objetivos y técnicas: la CGT se centra en caracterizar posiciones, calcular valores de juego y entender cómo se combinan juegos sencillos para formar juegos más complejos.

Un juego se considera combinatorio si satisface una serie de condiciones fundamentales. Entre ellas están:

Al menos dos jugadores (generalmente exactamente dos) que alternan movimientos.
Secuencialidad: los jugadores realizan movimientos por turnos; no hay jugadas simultáneas.
Información perfecta: no hay elementos ocultos ni información privada (a diferencia del póker). Ver condiciones.
Determinismo: no interviene la suerte ni tiradas aleatorias; el resultado de un movimiento está determinado por la posición y la jugada elegida. La suerte no forma parte del juego.
Conjunto finito (o razonablemente tractable) de movimientos posibles desde cualquier posición.
Finitud/terminación: el juego termina después de un número finito de movimientos.
Terminación por falta de movimiento: el juego finaliza cuando un jugador ya no puede mover (y se aplica la convención de victoria/derrota correspondiente).

La CGT suele concentrarse especialmente en juegos de dos jugadores, finitos y con la convención de victoria "normal" (el jugador que no puede mover pierde), aunque también se estudian variantes (por ejemplo, la misère, donde la última jugada puede invertir la condición de victoria). Muchos resultados y técnicas cambian según la convención elegida.

Clasificación básica de juegos:

• Impartiales: las opciones disponibles dependen únicamente de la posición y no del jugador que mueve. Un ejemplo clásico es el Nim. Para estos juegos existe una teoría muy desarrollada (teorema de Sprague–Grundy) que asocia a cada posición un grundy o nimber: una posición imparcial es equivalente a un montón de Nim de tamaño igual a ese número.
• Partidistas (o partidales): las opciones dependen del jugador (por ejemplo, Hackenbush o Domineering). Aquí aparecen valores más ricos que los nimbers: números (positivos/negativos), infinitesimales, y juegos no numéricos como el símbolo * (star) y otros nimbers.

Representación y valores de juego: las posiciones se representan naturalmente mediante árboles de juego: cada vértice es una posición y los arcos son movimientos posibles. Las hojas son posiciones terminales. A muchas posiciones se les puede asignar un valor matemático que resume su fuerza estratégica. Entre los conceptos centrales están:

• Clases de resultado: posiciones N (Next player wins), P (Previous player wins) y, en juegos partidistas, también L y R para victorias garantizadas de izquierda o derecha.
• Suma de juegos: la combinación disyuntiva de dos juegos donde, en cada turno, un jugador mueve en uno solo de ellos. La suma es fundamental: evaluar juegos compuestos (por ejemplo, varias pilas de Nim) se reduce a conocer los valores de los componentes y cómo se combinan.
• Teorema de Sprague–Grundy: para juegos imparciales bajo la convención normal, cada posición es equivalente a un único nimber (un montón de Nim de cierto tamaño) y la suma de juegos corresponde al nim-sum (xor) de esos números.
• Valores partizan: en juegos partizan aparecen los llamados números surrealistas (números de Conway) y otros valores como *, 1/2, infinitesimales y hot games (juegos “calientes” con ventaja de mover pronto). Las obras de Conway introducen un lenguaje algebraico para manipular estos valores.

Ejemplo sencillo (Nim): en Nim clásico hay varias pilas de fichas; en cada movimiento un jugador quita una cantidad positiva de fichas de una sola pila. Las posiciones se resuelven calculando el xor binario (nim-sum) de los tamaños de las pilas: si el nim-sum es 0 la posición es P (segundo jugador gana con juego perfecto), si es distinto de 0 la posición es N (primer jugador puede forzar la victoria). La suma de juegos se ejemplifica precisamente al sumar pilas de Nim.

Convenciones y variantes: la mayoría de resultados mencionados aplican a la convención normal (quien no puede mover pierde). En la misère la última jugada puede hacer que cambien las reglas de victoria y muchas fórmulas sencillas (como la del Nim) requieren ajustes; el análisis de misère es más complicado en general.

Aspectos algorítmicos y complejidad: aunque para muchos juegos imparciales concretos existe un método eficiente (mediante cálculo de grundy), el análisis de juegos combinatorios puede ser computacionalmente costoso. Determinar el ganador en la versión general de muchos juegos es un problema difícil desde el punto de vista de la complejidad computacional (en numerosos casos PSPACE-completo). Por ello la CGT combina técnicas algorítmicas, teoría estructural y combinatoria.

Aplicaciones y ejemplos notables: además del Nim, la CGT estudia juegos como Kayles, Dawson's Kayles, Take-and-Break, Domineering, Hackenbush y ciertos finales de Go desde la perspectiva de valores combinatorios. Las ideas de la CGT también se usan en inteligencia artificial (bases de datos de finales, heurísticas), en diseño de juegos y en problemas combinatorios que se modelan como juegos.

Historia y referencias: la teoría moderna fue formalizada por autores como Elwyn Berlekamp, John Conway y Richard Guy, quienes colaboraron intensamente desde la década de 1960. Su obra conjunta Winning Ways for Your Mathematical Plays y la obra de Conway On Numbers and Games son textos fundacionales que introducen conceptos como los números surrealistas, los nimbers y la algebra de los juegos.

En resumen, la teoría de los juegos combinatorios proporciona un marco poderoso para comprender y resolver juegos finitos perfectos sin azar: combina representación estructural (árboles de juego), algebra de valores, teoremas como Sprague–Grundy y técnicas algorítmicas para analizar posiciones y sumas de juegos. Es un campo en continua expansión con conexiones profundas a la lógica, la teoría de números, la computación y la práctica del juego.

Definiciones

En la teoría, hay dos jugadores llamados izquierda y derecha. Un juego es algo que permite a la izquierda y a la derecha hacer movimientos a otros juegos. Por ejemplo, en el juego del ajedrez, hay una configuración inicial habitual. Sin embargo, también se puede pensar en una partida de ajedrez después del primer movimiento como un juego diferente, con una configuración diferente. Por lo tanto, cada posición también se denomina partida.

Las partidas tienen la notación {L|R}. L {estilo de visualización L} $L$ son las partidas a las que se puede mover el jugador de la izquierda. R {\displaystyle R} $R$ son las partidas a las que puede moverse el jugador de la derecha. Si conoce la notación del ajedrez, la configuración habitual del ajedrez es el juego

{ a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } {\displaystyle \ {a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \} $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

Los puntos "..." significan que hay muchos movimientos, por lo que no se muestran todos.

El ajedrez es muy complejo. Es mejor pensar en juegos más fáciles. El Nim, por ejemplo, es mucho más sencillo de pensar. El Nim se juega así:

Hay cero o más montones de fichas.
En un turno, un jugador puede coger tantas fichas de un montón como quiera.
El jugador que no pueda hacer un movimiento pierde.

La partida más fácil de Nim comienza sin fichas. En este caso, ninguno de los dos jugadores puede moverse. Esto se muestra como {|}. Ambos lados están vacíos, porque ninguno de los dos jugadores puede moverse. El primer jugador que se vaya no puede mover, y por lo tanto perderá. En CGT, la gente suele escribir {|} como el símbolo 0 (cero).

El siguiente juego más fácil tiene una sola pila, con una sola ficha. Si el jugador de la izquierda va primero, ese jugador debe tomar la ficha, dejando a la derecha sin movimientos ({|}, o 0). Si, por el contrario, la derecha mueve primero, no habrá más movimientos para la izquierda. Así que tanto la izquierda como la derecha pueden hacer un movimiento a 0. Eso se muestra como {{|}|{|}}, o {0|0}. El primer jugador que mueva ganará. Las partidas iguales a {0|0} son muy importantes. Se escriben con el símbolo, * (estrella).

Preguntas y respuestas

P: ¿Qué es la Teoría Combinatoria de Juegos?

R: La Teoría Combinatoria de Juegos (CGT) es una rama de las matemáticas aplicadas y la informática teórica que estudia los juegos combinatorios, y es distinta de la teoría de juegos "tradicional" o "económica".

P: ¿Qué condiciones debe cumplir un juego para ser considerado un juego combinatorio?

R: Para que un juego se considere un juego combinatorio, debe tener al menos dos jugadores, debe ser secuencial (es decir, los jugadores alternan turnos), debe tener información perfecta (es decir, no hay información oculta), debe ser determinista (es decir, no azaroso), la suerte no puede formar parte del juego, debe haber una cantidad definida de movimientos posibles, el juego debe terminar eventualmente y el juego debe terminar cuando uno de los jugadores ya no pueda mover más.

P: ¿En qué tipo de juegos se centra la Teoría Combinatoria de Juegos?

R: La Teoría Combinatoria de Juegos se centra principalmente en juegos finitos de dos jugadores que tienen ganadores y perdedores (es decir, que no terminan en tablas).

P: ¿Cómo se representan este tipo de juegos?

R: Estos tipos de juegos pueden representarse mediante árboles en los que cada vértice representa el juego resultante de un movimiento concreto del situado directamente debajo de él en el árbol.

P: ¿Cuáles son algunos objetivos para los teóricos del CG?

R: Algunos objetivos para los teóricos del CG incluyen encontrar valores para este tipo de juegos, así como comprender el concepto de "adición de juegos", que implica que cada jugador haga sólo un movimiento en dos juegos diferentes dejando el otro sin cambios durante su turno.

P: ¿Quién fundó la CGT?

R: Se atribuye a Elwyn Berlekamp, John Conway y Richard Guy la fundación de la CGT en su obra publicada titulada Winning Ways for Your Mathematical Plays en la década de 1960.