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.
