Teoría de juegos combinatorios

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.​ 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.​ 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.

Matemáticos jugando a Konane en un taller de teoría de juegos combinatorios.

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 10¹²⁰, 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

$\{(\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.

$\{(\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 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 en realidad se puede abreviar como 0. En el juego cero, ningún jugador tiene movimientos válidos; así, el jugador cuyo turno es cuando aparece el juego cero pierde automáticamente.

El tipo de juego en el diagrama anterior también tiene un nombre simple; se llama el juego de las estrellas, que también se puede abreviar ∗. En el juego estrella, el único movimiento válido conduce al juego cero, lo que significa que el turno de quien llegue durante el juego estrella gana automáticamente.

Un tipo adicional de juego, que no se encuentra en Domineering, es un juego descabellado, en el que un movimiento válido de izquierda o derecha es un juego que luego puede llevar de regreso al primer juego. Las damas, por ejemplo, se vuelven locas cuando una de las piezas es promocionada, ya que entonces puede alternar interminablemente entre dos o más casillas. Un juego que no posee tales movimientos se llama loopfree.

Abreviaturas del juego

Números

Los números representan el número de movimientos libres 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 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 los juegos de números se comporta como los números enteros, por ejemplo, 3 + −2 = 1.

Estrella

Estrella, escrita como ∗ o {0 | 0}, es una victoria para el 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.

∗ + ∗ = 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; y todos los otros juegos en los que los primeros jugador gana (independientemente de qué lado del jugador está en) se dice que son difusos con o confundirse con 0; simbólicamente, escribimos ∗ || 0.

Arriba

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

−↑ = ↓ (abajo)

Up es estrictamente positivo (↑> 0), pero es infinitesimal. Up se define en Winning Ways for your Mathematical Plays.

Abajo

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

−↓ = ↑ (arriba)

Down es estrictamente negativo (↓ <0), pero es infinitesimal. Down se define en Winning Ways for your Mathematical Plays.

Juegos "calientes"

Considere el juego {1 | −1}. Ambos movimientos en este juego son una ventaja para el jugador que los realiza; por lo que se dice que el juego está "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. Está escrito como ± 1. Puede sumarse a números o multiplicarse por positivos, de la manera esperada; por ejemplo, 4 ± 1 = {5 | 3}.

Nimbers

Un juego imparcial es aquel en el que, en todas las posiciones del juego, los mismos movimientos están disponibles para ambos jugadores. Por ejemplo, Nim es imparcial, ya que cualquier conjunto de objetos que un jugador puede eliminar puede ser eliminado por el otro. Sin embargo, el dominó no es imparcial, porque un jugador coloca dominós horizontales y el otro coloca los verticales. Asimismo, las damas no es imparcial, ya que los jugadores poseen piezas de diferentes colores. Para cualquier número ordinal, se puede definir un juego imparcial generalizando Nim en el que, en cada movimiento, cualquier jugador puede reemplazar el número con cualquier número ordinal menor; los juegos definidos de esta manera se conocen como nimbers. El teorema de Sprague-Grundy afirma que todo juego imparcial equivale a un nimber.

Los nimbers "más pequeños", los más simples y los menos según el orden habitual de los ordinales, son 0 y ∗.

Véase también

• Poda alfa-beta
• Inducción hacia atrás
• Juego de conexión
• Base de datos de tablas de finales
• Árbol Expectiminimax
• Juegos en forma extensiva
• Clasificación de juegos
• Complejidad en los juegos
• Juego de Grundy
• Sistema multiagente
• Juego posicional
• Resolución del ajedrez
• Acuñación de Sylver
• Juego de Wythoff
• Juego topológico
• Zugzwang

Bibliografía

• Albert, Michael H.; Nowakowski, Richard J.; Wolfe, David (2007). Lessons in Play: An Introduction to Combinatorial Game Theory. A K Peters Ltd. ISBN 978-1-56881-277-9. 
• Beck, József (2008). Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press. ISBN 978-0-521-46100-9. 
• Berlekamp, E.; Conway, J. H.; Guy, R. (1982). Winning Ways for your Mathematical Plays: Games in general. Academic Press. ISBN 0-12-091101-9.  2nd ed., A K Peters Ltd (2001–2004), ISBN 1-56881-130-6, ISBN 1-56881-142-X
• Berlekamp, E.; Conway, J. H.; Guy, R. (1982). Winning Ways for your Mathematical Plays: Games in particular. Academic Press. ISBN 0-12-091102-7. (requiere registro).  2nd ed., A K Peters Ltd (2001–2004), ISBN 1-56881-143-8, ISBN 1-56881-144-6.
• Berlekamp, Elwyn; Wolfe, David (1997). Mathematical Go: Chilling Gets the Last Point. A K Peters Ltd. ISBN 1-56881-032-6. (requiere registro). 
• Bewersdorff, Jörg (2004). Luck, Logic and White Lies: The Mathematics of Games. A K Peters Ltd. ISBN 1-56881-210-8.  See especially sections 21–26.
• Conway, John Horton (1976). On Numbers and Games. Academic Press. ISBN 0-12-186350-6.  2nd ed., A K Peters Ltd (2001), ISBN 1-56881-127-6.
• Robert A. Hearn; Erik D. Demaine (2009). Games, Puzzles, and Computation. A K Peters, Ltd. ISBN 978-1-56881-322-6. 

Enlaces externos

En inglés:

• Lista de enlaces de teoría de juegos combinatorios en la página de David Eppstein
• Una introducción a los juegos y números de Conway
• Sumario de términos de teoría de juegos combinatorios
• Combinatorial Game Theory Workshop, Banff International Research Station, June 2005

• Datos: Q1320931
• Multimedia: Game theory / Q1320931