La teoría de juegos combinatorios (CGT) es una rama de las matemáticas y la informática teórica que normalmente estudia juegos secuenciales con información perfecta. El estudio se ha limitado en gran medida a los juegos de dos jugadores que tienen una posición en la que los jugadores se turnan para cambiar de formas o movimientos definidos para lograr una condición ganadora definida. La CGT no ha estudiado tradicionalmente los juegos de azar o aquellos que utilizan información imperfecta o incompleta, favoreciendo los juegos que ofrecen información perfecta, en los cuales ambos jugadores conocen siempre el estado del juego y el conjunto de movimientos disponibles.Lessons in Play, p. 3 Sin embargo, a medida que avanzan las técnicas matemáticas, los tipos de juegos que pueden analizarse matemáticamente se expanden, por lo que los límites del campo cambian constantemente.Thomas S. Fergusson's analysis of poker is an example of CGT expanding into games that include elements of chance. Research into Three Player NIM is an example of study expanding beyond two player games. Conway, Guy and Berlekamp's analysis of partisan games is perhaps the most famous expansion of the scope of CGT, taking the field beyond the study of impartial games. Los académicos generalmente definirán lo que quieren decir con un "juego" al comienzo de un artículo, y estas definiciones a menudo varían, ya que son específicas del juego que se analiza y no pretenden representar el alcance completo del campo.

Los juegos combinatorios incluyen juegos bien conocidos como ajedrez, damas y go, que se consideran no triviales, y tic-tac-toe, que se considera trivial en el sentido de ser "fácil de resolver". Algunos juegos combinatorios también pueden tener un área de juego ilimitada, como el ajedrez infinito. En la CGT, los movimientos en estos y otros juegos se representan como un árbol de juego.

Los juegos combinatorios también incluyen rompecabezas combinatorios para un jugador, como Sudoku, y autómatas sin jugador, como el Juego de la vida de Conway, (aunque en la definición más estricta, se puede decir que los "juegos" requieren más de un participante, de ahí las designaciones de "rompecabezas" y "autómatas")

La teoría de juegos en general incluye juegos de azar, juegos de conocimiento imperfecto y juegos en los que los jugadores pueden moverse simultáneamente, y tienden a representar situaciones de toma de decisiones de la vida real.

La CGT tiene un énfasis diferente a la teoría de juegos "tradicional" o "económica", que inicialmente fue desarrollada para estudiar juegos con estructura combinatoria simple, pero con elementos de azar (aunque también considera movimientos secuenciales, ver juego de forma extensiva). Básicamente, la CGT ha aportado nuevos métodos para analizar árboles de juegos, por ejemplo, utilizando números surreales, que son una subclase de todos los juegos de información perfecta para dos jugadores. El tipo de juegos estudiados por la CGT también es de interés en inteligencia artificial, particularmente para planificación y programación automatizadas. En la CGT se ha hecho menos hincapié en perfeccionar los algoritmos de búsqueda prácticos (como la poda alfa-beta heurística incluida en la mayoría de los libros de texto de inteligencia artificial), pero más énfasis en los resultados teóricos descriptivos (como las medidas de la complejidad del juego o las pruebas de la existencia de una solución óptima sin especificar necesariamente un algoritmo, como el argumento de robo de estrategia).

Una noción importante en la CGT es la del juego resuelto. Por ejemplo, el tic-tac-toe se considera un juego resuelto, ya que se puede demostrar que cualquier juego terminará en empate si ambos jugadores juegan de manera óptima. Es difícil obtener resultados similares para juegos con ricas estructuras combinatorias. Por ejemplo, en 2007 se anunció que las damas se habían resuelto débilmente —el juego óptimo de ambos lados también conduce a un empate— pero este resultado fue una prueba asistida por computadora. Otros juegos del mundo real son en su mayoría demasiado complicados para permitir un análisis completo en la actualidad, aunque la teoría ha tenido algunos éxitos recientes en el análisis de finales de go. Aplicar la CGT a una posición significa intentar determinar la secuencia óptima de movimientos para ambos jugadores hasta que finaliza el juego y, al hacerlo, descubre el movimiento óptimo en cualquier posición. En la práctica, este proceso es tortuosamente difícil a menos que el juego sea muy simple.

Puede ser útil distinguir entre "juegos matemáticos" combinatorios de interés principalmente para que los matemáticos y científicos reflexionen y resuelvan, y "juegos de juego" combinatorios de interés para la población en general como una forma de entretenimiento y competencia. Sin embargo, varios juegos se incluyen en ambas categorías. Nim, por ejemplo, es un juego fundamental en la formación de la CGT y uno de los primeros juegos computarizados. El tic-tac-toe todavía se utiliza para enseñar principios básicos del diseño de juegos de inteligencia artificial a estudiantes de informática.

Historia La CGT surgió en relación con la teoría de los juegos imparciales, en la que cualquier juego disponible para un jugador debe estar disponible para el otro también. Uno de esos juegos es Nim, que se puede resolver por completo. Nim es un juego imparcial para dos jugadores y sujeto a la condición de juego normal, lo que significa que un jugador que no puede moverse pierde. En la década de 1930, el teorema de Sprague-Grundy mostró que todos los juegos imparciales son equivalentes a montones en Nim, mostrando así que las grandes unificaciones son posibles en juegos considerados a nivel combinatorio, en los que las estrategias detalladas importan, no solo los pagos.

En la década de 1960, Elwyn R. Berlekamp, John H. Conway y Richard K. Guy introdujeron conjuntamente la teoría de un juego partisano, en el que se relaja el requisito de que una jugada disponible para un jugador esté disponible para ambos. Sus resultados fueron publicados en su libro Winning Ways for your Mathematical Plays en 1982. Sin embargo, el primer trabajo publicado sobre el tema fue el libro de Conway de 1976 On Numbers and Games, también conocido como ONAG, que introdujo el concepto de números surreales y la generalización de juegos. On Numbers and Games también fue fruto de la colaboración entre Berlekamp, Conway y Guy.

Los juegos combinatorios generalmente, por convención, se ponen en una forma en la que un jugador gana cuando al otro no le quedan movimientos. Es fácil convertir cualquier juego finito con solo dos resultados posibles en uno equivalente cuando se aplique esta convención. Uno de los conceptos más importantes en la teoría de los juegos combinatorios es el de la suma de dos juegos, que es un juego en el que cada jugador puede elegir moverse en un juego o en el otro en cualquier momento del juego, y un jugador gana cuando su oponente no tiene movimiento en ninguno de los juegos. Esta forma de combinar juegos conduce a una estructura matemática rica y poderosa.

Conway declaró en ONAG que la inspiración para la teoría de los juegos partisanos se basó en su observación del juego en los finales de go, que a menudo se pueden descomponer en sumas de finales más simples aislados entre sí en diferentes partes del tablero.

Ejemplos El texto introductorio Winning Ways for your Mathematical Plays presentó una gran cantidad de juegos, pero los siguientes se utilizaron como ejemplos motivadores para la teoría introductoria:

Blue – Red Hackenbush: en el nivel finito, este juego combinatorio partisano permite la construcción de juegos cuyos valores son números racionales diádicos. En el nivel infinito, permite construir todos los valores reales, así como muchos infinitos que caen dentro de la clase de números surreales. Blue – Red – Green Hackenbush: permite valores de juego adicionales que no son números en el sentido tradicional, por ejemplo, estrella. Sapos y Ranas: permite varios valores de juego. A diferencia de la mayoría de los otros juegos, una posición se representa fácilmente mediante una pequeña cadena de caracteres. Domineering: varios juegos interesantes, como los juegos calientes, aparecen como posiciones en Domineering, porque a veces hay un incentivo para moverse y otras no. Esto permite discutir la temperatura de un juego. Nim: un juego imparcial. Esto permite la construcción de nimbers. (También se puede ver como un caso especial solo verde de Hackenbush azul-rojo-verde).

El juego clásico go influyó en la teoría de los juegos combinatorios iniciales, y Berlekamp y Wolfe desarrollaron posteriormente una teoría de finales y temperatura de juegos (ver referencias). Armados con esto, fueron capaces de construir posiciones plausibles de finales de go desde las que podían dar a los jugadores expertos de go una opción de bandos y luego derrotarlos de cualquier manera.

Otro juego estudiado en el contexto de la teoría de juegos combinatorios es el ajedrez. En 1953, Alan Turing escribió sobre el juego: "Si uno puede explicar sin ambigüedades en inglés, con la ayuda de símbolos matemáticos si es necesario, cómo se debe hacer un cálculo, entonces siempre es posible programar cualquier computadora digital para hacer ese cálculo, siempre que la capacidad de almacenamiento sea adecuada". En un artículo de 1950, Claude Shannon estimó que el límite inferior de la complejidad del árbol de juego del ajedrez era 10120, y hoy en día esto se conoce como el número de Shannon. El ajedrez sigue sin resolverse, aunque un estudio extenso, incluido el trabajo que involucra el uso de supercomputadoras, ha creado bases de tablas de finales de ajedrez, que muestran el resultado de un juego perfecto para todas las partidas finales con siete piezas o menos. El ajedrez infinito tiene una complejidad combinatoria aún mayor que el ajedrez (a menos que solo se estudien partidas finales limitadas o posiciones compuestas con una pequeña cantidad de piezas).

Descripción general Un juego, en sus términos más simples, es una lista de posibles "movimientos" que pueden hacer dos jugadores, llamados izquierda y derecha. La posición de juego resultante de cualquier movimiento puede considerarse como otro juego. Esta idea de ver los juegos en términos de sus posibles movimientos a otros juegos conduce a una definición matemática recursiva de juegos que es estándar en la teoría de juegos combinatorios. En esta definición, cada juego tiene la notación {L | R}. L es el conjunto de posiciones de juego a las que puede moverse el jugador izquierdo, y R es el conjunto de posiciones de juego a las que puede moverse el jugador derecho; cada posición en L y R se define como un juego que usa la misma notación.

Usando Dominante como ejemplo, etiquete cada una de las dieciséis casillas del tablero de cuatro por cuatro con A1 para el cuadrado superior izquierdo, C2 para el tercer casillero desde la izquierda en la segunda fila desde arriba, y así sucesivamente. Usamos, por ejemplo, (D3, D4) para representar la posición del juego en la que se ha colocado un dominó vertical en la esquina inferior derecha. Entonces, la posición inicial se puede describir en notación combinatoria de teoría de juegos como

En el juego Cross-Cram estándar, los jugadores alternan turnos, pero esta alternancia se maneja implícitamente mediante las definiciones de la teoría de juegos combinatorios en lugar de estar codificada dentro de los estados del juego.