Teoría de juegos combinatorios

La teoría de juegos combinatorios es una rama de las matemáticas y la informática teórica que estudia típicamente los 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 que los jugadores cambian por turnos de formas definidas o movimientos para lograr una condición ganadora definida. La teoría de juegos combinatorios tradicionalmente no ha estudiado los juegos de azar o aquellos que utilizan información imperfecta o incompleta, favoreciendo los juegos que ofrecen información perfecta en los que ambos jugadores siempre conocen el estado del juego y el conjunto de movimientos disponibles. ^[1] Sin embargo, a medida que avanzan las técnicas matemáticas, los tipos de juegos que se pueden analizar 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 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 están destinadas a representar el alcance completo del campo.

Los juegos combinatorios incluyen juegos tan 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 ser "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 combinatorios, los movimientos en estos y otros juegos se representan como un árbol de juego .

Los juegos combinatorios también incluyen rompecabezas 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 combinatorios tiene un énfasis diferente al de la teoría de juegos "tradicional" o "económica", que fue desarrollada inicialmente para estudiar juegos con una 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 combinatorios 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 de 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 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 existencia de solución óptima sin especificar necesariamente un algoritmo, como el argumento del robo de estrategia ).

Un concepto importante en la teoría de juegos combinatorios es el de juego resuelto . Por ejemplo, el tres en raya se considera un juego resuelto, ya que se puede demostrar que cualquier juego resultará en tablas si ambos jugadores juegan de manera óptima. Obtener resultados similares para juegos con estructuras combinatorias ricas es difícil. 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 tablas), 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 en la actualidad, 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 combinatorios a una posición intenta determinar la secuencia óptima de movimientos para ambos jugadores hasta que finalice 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 los "juegos matemáticos" combinatorios, cuyo interés principal es que los matemáticos y científicos reflexionen y resuelvan, y los "juegos" combinatorios, cuyo interés se dirige a la población en general como forma de entretenimiento y competición. ^[5] Sin embargo, hay varios juegos que entran en ambas categorías. Nim , por ejemplo, es un juego instrumental en la fundación de la teoría de juegos combinatorios, y uno de los primeros juegos informáticos. ^[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 combinatorios surgió en relación con la teoría de juegos imparciales , en la que cualquier juego disponible para un jugador debe estar disponible 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 está 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 son posibles las unificaciones importantes en juegos considerados a nivel combinatorio, en los que importan las estrategias detalladas, 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 del juego partidista , en la que se relaja el requisito de que una jugada disponible para un jugador esté disponible para ambos. Sus resultados se publicaron 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 los juegos. On Numbers and Games también fue fruto de la colaboración entre Berlekamp, ​​Conway y Guy.

Los juegos combinatorios se suelen plantear, por convención, de forma que un jugador gana cuando al otro no le quedan más movimientos. Es fácil convertir cualquier juego finito con sólo dos resultados posibles en uno equivalente en el que se aplique esta convención. Uno de los conceptos más importantes de 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 mover en uno u otro juego en cualquier momento del juego, y un jugador gana cuando a su oponente no le quedan más movimientos en ninguno de los dos. 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 pueden descomponerse en sumas de finales más simples aislados unos de otros 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:

• Hackenbush Azul-Rojo - En el nivel finito, este juego combinatorio partidista permite construir 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 surrealistas .
• Hackenbush Azul-Rojo-Verde: 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 demás juegos, una posición se representa fácilmente mediante una cadena corta de caracteres.
• Dominancia : varios juegos interesantes, como los juegos calientes , aparecen como posiciones en Dominancia, porque a veces hay un incentivo para moverse y a veces no. Esto permite discutir la temperatura de un juego .
• Nim : un juego imparcial que permite la construcción de los nimbers . (También puede considerarse como un caso especial de Hackenbush azul-rojo-verde, solo para los verdes).

El juego clásico Go influyó en la teoría de juegos combinatorios temprana, y Berlekamp y Wolfe posteriormente desarrollaron una teoría de finales y de temperaturas para él (ver referencias). Armados con esto, pudieron construir posiciones de finales de Go plausibles a partir de las cuales podían dar a los jugadores expertos de Go la opción de elegir entre dos 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 de manera bastante inequívoca en inglés, con la ayuda de símbolos matemáticos si es necesario, cómo se debe realizar un cálculo, entonces siempre es posible programar cualquier computadora digital para que haga 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 juegos del ajedrez era 10 ¹²⁰ , y hoy en día esto se conoce como el número de Shannon . ^[9] El ajedrez sigue sin resolverse, aunque un estudio extenso, incluido el trabajo que implica el uso de supercomputadoras, ha creado bases de datos de tablas de finales de ajedrez , que muestran el resultado del juego perfecto para todos los finales de siete piezas o menos. El ajedrez infinito tiene una complejidad combinatoria incluso mayor que el ajedrez (a menos que solo 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 dos jugadores, llamados izquierdo y derecho , pueden hacer. La posición de juego resultante de cualquier movimiento puede considerarse 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 los 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 de la izquierda, y R es el conjunto de posiciones de juego a las que puede moverse el jugador de la derecha; cada posición en L y R se define como un juego que utiliza 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 la casilla superior izquierda, 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. Luego, la posición inicial se puede describir en la notación de la teoría de juegos combinatorios como

${\displaystyle \{(\mathrm {A} 1,\mathrm {A} 2),(\mathrm {B} 1,\mathrm {B} 2),\dots |(\mathrm {A} 1,\mathrm {B} 1),(\mathrm {A} 2,\mathrm {B} 2),\dots \}.}$

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.

${\displaystyle \{(\mathrm {A} 1,\mathrm {A} 2)|(\mathrm {A} 1,\mathrm {B} 1)\}=\{\{|\}|\{|\}\}.}$

El juego anterior describe un escenario en el que solo queda un movimiento para cada jugador y, si cualquiera de los jugadores realiza ese movimiento, ese jugador gana. (Se ha omitido del diagrama una casilla vacía irrelevante en C3). El {|} en la lista de movimientos de cada jugador (que corresponde a la casilla única que queda después del movimiento) se denomina juego cero y, en realidad, se puede abreviar como 0. En el juego cero, ningún jugador tiene movimientos válidos; por lo tanto, el jugador cuyo turno es cuando aparece el juego cero pierde automáticamente.

El tipo de juego del diagrama anterior también tiene un nombre sencillo: se llama juego de estrellas , que también se puede abreviar como ∗. En el juego de estrellas, el único movimiento válido conduce al juego cero, lo que significa que quien tenga el turno durante el juego de estrellas gana automáticamente.

Un tipo adicional de juego, que no se encuentra en Domineering, es un juego con bucles , en el que un movimiento válido hacia la izquierda o hacia la derecha es un juego que puede llevar de nuevo al primer juego. Las damas , por ejemplo, se vuelven un juego con bucles cuando una de las piezas se promociona, ya que entonces puede alternar infinitamente entre dos o más casillas. Un juego que no posee tales movimientos se llama sin bucles .

También hay juegos transfinitos , que tienen infinitas posiciones, es decir, izquierda y derecha tienen listas de movimientos que son infinitas en lugar de finitas.

Los números representan la cantidad de movimientos libres o la ventaja de movimientos 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 de forma recursiva, siendo 0 el caso base.

0 = {|}

1 = {0|}, 2 = {1|}, 3 = {2|}

−1 = {|0}, −2 = {|−1}, −3 = {|−2}

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.

Cualquier número de juego está en la clase de los números surrealistas .

Estrella , escrita como ∗ o {0|0}, es una victoria del primer jugador ya que cualquiera de los jugadores debe (si es el primero en mover en el juego) moverse a un juego cero y, por lo tanto, ganar.

∗ + ∗ = 0, porque el primer jugador debe convertir una copia de ∗ en 0, y luego el otro jugador tendrá que convertir la otra copia de ∗ en 0 también; en este punto, el primer jugador perdería, ya que 0 + 0 no admite movimientos.

El juego ∗ no es ni positivo ni negativo; se dice que este y todos los demás juegos en los que el primer jugador gana (sin importar de qué lado esté el jugador) son difusos o confundidos con 0 ; simbólicamente, escribimos ∗ || 0.

Arriba , escrito como ↑, es una posición en la teoría de juegos combinatorios. ^[10] En notación estándar, ↑ = {0|∗}.

−↑ = ↓ ( abajo )

Up es estrictamente positivo (↑ > 0), pero es infinitesimal . Up se define en Formas ganadoras para tus jugadas matemáticas .

Abajo , escrito como ↓, es una posición en la teoría de juegos combinatorios. ^[10] En notación estándar, ↓ = {∗|0}.

−↓ = ↑ ( arriba )

Abajo es estrictamente negativo (↓ < 0), pero es infinitesimal . Abajo se define en Formas ganadoras para tus jugadas matemáticas .

Consideremos el juego {1|−1}. Ambos movimientos en este juego son una ventaja para el jugador que los realiza; por lo tanto, se dice que el juego es "caliente"; 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 a números, o multiplicar por números positivos, de la manera esperada; por ejemplo, 4 ± 1 = {5|3}.

Un juego imparcial es aquel en el que, en cada posición del juego, ambos jugadores pueden hacer los mismos movimientos. Por ejemplo, Nim es imparcial, ya que cualquier conjunto de objetos que pueda ser eliminado por un jugador puede ser eliminado por el otro. Sin embargo, el dominio no es imparcial, porque un jugador coloca fichas de dominó horizontales y el otro coloca fichas verticales. Del mismo modo, las damas no son imparciales, ya que los jugadores poseen piezas de diferentes colores. Para cualquier número ordinal , se puede definir un juego imparcial que generalice Nim en el que, en cada movimiento, cualquiera de los jugadores puede reemplazar el número con cualquier número ordinal más pequeño; los juegos definidos de esta manera se conocen como nimbers . El teorema de Sprague-Grundy establece que cada juego imparcial bajo la convención de juego normal es equivalente a un nimber.

Los números "más pequeños" – los más simples y menores bajo el ordenamiento usual de los ordinales – son 0 y ∗.

• Poda alfa-beta , un algoritmo optimizado para buscar en el árbol del juego
• Inducción regresiva , razonamiento hacia atrás a partir de una situación final.
• Refrigeración y calefacción (teoría de juegos combinatorios) , diversas transformaciones de juegos que los hacen más aptos para la teoría.
• Juego de conexión , un tipo de juego en el que los jugadores intentan establecer conexiones.
• Tabla de finales , una base de datos que explica cómo jugar los finales
• Árbol Expectiminimax , una adaptación de un árbol de juego minimax para juegos con un elemento de azar
• Juego en formato extensivo , un árbol de juego enriquecido con pagos e información disponible para los jugadores.
• Clasificación de juegos , un artículo que analiza las formas de clasificar los juegos.
• Complejidad del juego , un artículo que describe formas de medir la complejidad de los juegos.
• El juego de Grundy , un juego matemático en el que se dividen montones de objetos.
• Sistema multiagente , un tipo de sistema informático para abordar problemas complejos.
• Juego posicional , un tipo de juego en el que los jugadores reclaman posiciones no reclamadas previamente.
• Resolviendo ajedrez
• Moneda de plata , un juego matemático de elección de números enteros positivos que no sean la suma de múltiplos no negativos de números enteros elegidos previamente
• Juego de Wythoff , un juego matemático que consiste en tomar objetos de una o dos pilas.
• Juego topológico , un tipo de juego matemático que se juega en un espacio topológico.
• Zugzwang , estar obligado a jugar cuando esto es desventajoso

• Albert, Michael H .; Nowakowski, Richard J.; Wolfe, David (2007). Lecciones de juego: una introducción a la teoría de juegos combinatorios . AK Peters Ltd. ISBN 978-1-56881-277-9.
• Beck, József (2008). Juegos combinatorios: teoría del tres en raya . Cambridge University Press. ISBN 978-0-521-46100-9.
• Berlekamp, ​​E. ; Conway, JH ; Guy, R. (1982). Formas ganadoras para sus juegos matemáticos : juegos en general . Academic Press. ISBN 0-12-091101-9.2ª ed., AK Peters Ltd (2001-2004), ISBN 1-56881-130-6 , ISBN 1-56881-142-X  
• Berlekamp, ​​E.; Conway, JH; Guy, R. (1982). Formas ganadoras para sus jugadas matemáticas: juegos en particular . Academic Press. ISBN 0-12-091102-7.2ª ed., AK Peters Ltd (2001-2004), ISBN 1-56881-143-8 , ISBN 1-56881-144-6 .  
• Berlekamp, ​​Elwyn ; Wolfe, David (1997). Go matemático: el enfriamiento lleva al punto final . AK Peters Ltd. ISBN 1-56881-032-6.
• Bewersdorff, Jörg (2021). Suerte, lógica y mentiras piadosas: las matemáticas de los juegos (2.ª ed.). AK Peters/CRC Press. doi :10.1201/9781003092872. ISBN 978-1-003-09287-2.Véanse especialmente las secciones 21 a 26.
• Conway, John Horton (1976). Sobre números y juegos . Academic Press. ISBN 0-12-186350-6.2ª ed., AK Peters Ltd (2001), ISBN 1-56881-127-6 . 
• Robert A. Hearn y Erik D. Demaine (2009). Juegos, rompecabezas y computación . AK Peters, Ltd. ISBN 978-1-56881-322-6.

• Lista de enlaces de teoría de juegos combinatorios en la página de inicio de David Eppstein
• Introducción a los juegos y números de Conway por Dierk Schleicher y Michael Stoll
• Resumen de términos de la teoría de juegos combinacionales por Bill Spight
• Taller sobre teoría de juegos combinatorios, Estación de investigación internacional de Banff, junio de 2005