La teoría de juegos combinatoria 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 maneras o movimientos definidos para lograr una condición ganadora definida. La teoría de juegos combinatoria no ha estudiado tradicionalmente los juegos de azar o aquellos que utilizan información imperfecta o incompleta, privilegiando los juegos que ofrecen información perfecta en los que ambos jugadores conocen siempre el estado del juego y el conjunto de jugadas disponibles. [1] Sin embargo, a medida que avanzan las técnicas matemáticas, los tipos de juego que pueden analizarse matemáticamente se expanden, por lo que los límites del campo cambian constantemente. [2] Los académicos generalmente definirán lo que quieren decir con "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 el ajedrez , las damas y el Go , que se consideran no triviales, y el tres en raya , que se considera trivial, en el sentido de que es "fácil de resolver". Algunos juegos combinatorios también pueden tener un área de juego ilimitada , como el ajedrez infinito . En la teoría de juegos combinatoria, los movimientos en estos y otros juegos se representan como un árbol de juegos .
Los juegos combinatorios también incluyen acertijos combinatorios para un solo jugador, como el 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". [3] )
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 teoría de juegos combinatoria tiene un énfasis diferente a la teoría de juegos "tradicional" o "económica", que se desarrolló inicialmente para estudiar juegos con estructura combinatoria simple, pero con elementos de azar (aunque también considera movimientos secuenciales, véase juego de forma extensiva ). Esencialmente, la teoría de juegos combinatoria ha aportado nuevos métodos para analizar árboles de juegos, por ejemplo utilizando números surrealistas , que son una subclase de todos los juegos de información perfecta para dos jugadores. [3] El tipo de juegos estudiados por la teoría de juegos combinatorios también es de interés en la inteligencia artificial , particularmente para la planificación y programación automatizadas . En la teoría de juegos combinatorios se ha puesto menos énfasis en refinar los algoritmos de búsqueda prácticos (como la heurística de poda alfa-beta incluida en la mayoría de los libros de texto de inteligencia artificial), pero más énfasis en resultados teóricos descriptivos (como medidas de complejidad del juego o pruebas de solución óptima). existencia sin necesariamente especificar un algoritmo, como el argumento del robo de estrategias ).
Una noción importante en la teoría de juegos combinatorios es la de juego resuelto . Por ejemplo, el tres en raya se considera un juego resuelto, ya que se puede demostrar que cualquier juego resultará 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 al empate), pero este resultado fue una prueba asistida por computadora . [4] Otros juegos del mundo real son en su mayoría demasiado complicados para permitir un análisis completo hoy en día, aunque la teoría ha tenido algunos éxitos recientes en el análisis de finales de Go. La aplicación de la teoría de juegos combinatoria a una posición intenta determinar la secuencia óptima de movimientos para ambos jugadores hasta que finaliza el juego y, al hacerlo, descubrir 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 resultar útil distinguir entre "juegos matemáticos" combinatorios de interés principalmente para que los matemáticos y científicos reflexionen y resuelvan, y "juegos" combinatorios de interés para la población general como forma de entretenimiento y competencia. [5] Sin embargo, varios juegos entran en ambas categorías. Nim , por ejemplo, es un juego fundamental en la base de la teoría de juegos combinatorios y uno de los primeros juegos computarizados. [6] El tres en raya todavía se utiliza para enseñar principios básicos del diseño de IA de juegos a estudiantes de informática . [7]
La teoría de juegos combinatoria surgió en relación con la teoría de los juegos imparciales , en la que cualquier juego disponible para un jugador debe estarlo también para el otro. Uno de esos juegos es Nim , que se puede resolver por completo. Nim es un juego imparcial para dos jugadores y sujeto a las condiciones de juego normales , lo que significa que el jugador que no puede moverse pierde. En la década de 1930, el teorema de Sprague-Grundy demostró que todos los juegos imparciales son equivalentes a montones en Nim, mostrando así que son posibles unificaciones importantes en juegos considerados a un nivel combinatorio, en el que las estrategias detalladas importan, no solo los resultados.
En la década de 1960, Elwyn R. Berlekamp , John H. Conway y Richard K. Guy introdujeron conjuntamente la teoría del 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 surrealistas y la generalización a 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 presentan en una forma en la que un jugador gana cuando al otro no le quedan movimientos. Es fácil convertir cualquier juego finito con sólo dos resultados posibles en uno equivalente donde 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 ningún movimiento en ninguno de los juegos. Esta forma de combinar juegos conduce a una estructura matemática rica y poderosa.
Conway afirmó en Sobre números y juegos que la inspiración para la teoría de los juegos partidistas 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.
El texto introductorio Winning Ways presentó una gran cantidad de juegos, pero los siguientes se utilizaron como ejemplos motivadores para la teoría introductoria:
El juego clásico Go influyó en las primeras teorías de juegos combinatorios, y Berlekamp y Wolfe posteriormente desarrollaron una teoría de finales y temperatura para él (ver referencias). Armados con esto, pudieron construir posiciones finales de Go plausibles desde las cuales podían dar a los jugadores expertos de Go la posibilidad de elegir bando 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." [8] En un artículo de 1950, Claude Shannon estimó que el límite inferior de la complejidad del árbol de juego del ajedrez era 10 120 , y hoy esto se conoce como el número de Shannon . [9] El ajedrez sigue sin resolverse, aunque un estudio extenso, incluido el trabajo que involucra el uso de supercomputadoras, ha creado bases de datos de finales de ajedrez , que muestran el resultado de un juego perfecto para todos los finales con siete piezas o menos. El ajedrez infinito tiene una complejidad combinatoria aún mayor que el ajedrez (a menos que sólo se estudien finales limitados o posiciones compuestas con un pequeño número de piezas).
Un juego, en sus términos más simples, es una lista de posibles "movimientos" que pueden realizar dos jugadores, llamados izquierda y derecha . La posición de juego resultante de cualquier jugada puede considerarse como otro juego. Esta idea de ver los juegos en términos de sus posibles movimientos hacia 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 usando la misma notación.
Usando Domineering 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 la tercera casilla 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 una ficha de dominó vertical en la esquina inferior derecha. Entonces, la posición inicial se puede describir en notación de teoría de juegos combinatoria 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 combinatoria en lugar de estar codificada dentro de los estados del juego.
El juego anterior describe un escenario en el que sólo queda un movimiento para cada jugador, y si cualquiera de los jugadores hace ese movimiento, ese jugador gana. (Se ha omitido del diagrama un cuadrado abierto irrelevante en C3). El {|} en la lista de movimientos de cada jugador (correspondiente al único cuadrado sobrante después del movimiento) se llama juego cero y , de hecho, puede abreviarse 0. En el juego cero, ningún jugador tiene movimientos válidos; por lo tanto, el jugador al que le toca cuando sale el juego cero pierde automáticamente.
El tipo de juego del diagrama anterior también tiene un nombre sencillo; se llama juego de las estrellas , que también puede abreviarse ∗. En el juego de estrellas, el único movimiento válido conduce al juego cero, lo que significa que quien le toque el turno durante el juego de estrellas gana automáticamente.
Un tipo adicional de juego, que no se encuentra en Domineering, es un juego loco , en el que un movimiento válido de izquierda o derecha es un juego que luego puede conducir de regreso al primer juego. Las damas , por ejemplo, se vuelven locas cuando una de las piezas avanza, ya que entonces puede circular sin cesar entre dos o más cuadrados. Un juego que no posee tales movimientos se llama loopfree .
Los números representan el número de movimientos gratis o la ventaja de movimiento de un jugador en particular. Por convención, los números positivos representan una ventaja para la izquierda, mientras que los números negativos representan una ventaja para la derecha. Se definen recursivamente siendo 0 el caso base.
El juego cero es una pérdida para el primer jugador.
La suma de juegos de números se comporta como los números enteros, por ejemplo 3 + −2 = 1.
Estrella , escrita como ∗ o {0|0}, es una victoria del primer jugador ya que cualquiera de los jugadores debe (si es el primero en moverse en el juego) pasar a un juego cero y, por lo tanto, ganar.
El juego ∗ no es ni positivo ni negativo; se dice que este y todos los demás juegos en los que gana el primer jugador (independientemente de en qué lado esté el jugador) están confusos o confusos con 0; simbólicamente escribimos ∗ || 0.
Arriba , escrito como ↑, es una posición en la teoría de juegos combinatoria. [10] En notación estándar, ↑ = {0|∗}.
Up es estrictamente positivo ( ↑ > 0), pero es infinitesimal . Up se define en Formas de Ganar para tus Jugadas Matemáticas .
Abajo , escrito como ↓, es una posición en la teoría de juegos combinatoria. [10] En notación estándar, ↓ = {∗|0}.
Down es estrictamente negativo (↓ < 0), pero es infinitesimal . Down se define en Formas de Ganar para tus Jugadas Matemáticas .
Considere el juego {1|−1}. Ambos movimientos en este juego son una ventaja para el jugador que los realiza; por eso se dice que el juego está "de moda"; es mayor que cualquier número menor que −1, menor que cualquier número mayor que 1 y difuso con cualquier número intermedio. Se escribe como ±1. Se puede sumar números o multiplicar por números positivos, de la forma esperada; por ejemplo, 4 ± 1 = {5|3}.
Un juego imparcial es aquel en el que, en cada posición del juego, ambos jugadores disponen de los mismos movimientos. Por ejemplo, Nim es imparcial, ya que cualquier conjunto de objetos que un jugador puede eliminar puede ser eliminado por el otro. Sin embargo, dominar no es imparcial, porque un jugador coloca fichas horizontales y el otro coloca fichas verticales. Asimismo, Damas no es imparcial, ya que los jugadores poseen piezas de diferentes colores. Para cualquier número ordinal , se puede definir un juego imparcial que generalice a Nim en el que, en cada movimiento, cualquiera de los jugadores puede reemplazar el número con cualquier número ordinal menor; los juegos definidos de esta manera se conocen como números . El teorema de Sprague-Grundy establece que todo juego imparcial equivale a un número.
Los números "más pequeños", los más simples y los menos según el orden habitual de los ordinales, son 0 y ∗.
