Teoría de juegos combinatorios

Teoría de juegos combinatorios 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 cambian por turnos de formas definidas o movimientos para lograr una condición ganadora definida. La teoría de juegos combinatorios 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 que el estado del juego y el conjunto de movimientos disponibles es siempre conocido por ambos jugadores. 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. Los académicos generalmente definirán lo que quieren decir con un "juego" al comienzo de un documento, 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 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 combinatorios, los movimientos en estos y otros juegos se representan como un árbol de juegos.

Los juegos combinatorios también incluyen acertijos combinatorios para un 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, los "juegos" pueden ser se dice que requiere 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 teoría de juegos combinatorios tiene un énfasis diferente al "tradicional" o "económico" teoría de juegos, que inicialmente se desarrolló para estudiar juegos con estructura combinatoria simple, pero con elementos de azar (aunque también considera movimientos secuenciales, ver juego en 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 para dos jugadores. El tipo de juegos estudiados por la teoría de juegos combinatorios también es de interés en inteligencia artificial, particularmente para la planificación y programación automatizadas. En la teoría de juegos combinatorios ha habido 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 los resultados teóricos descriptivos (como medidas de la complejidad del juego o pruebas de solución óptima). existencia sin especificar necesariamente un algoritmo, como el argumento del robo de estrategia).

Una noción importante en la teoría de juegos combinatorios 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 los finales de Go. La aplicación de la teoría del juego combinatorio 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 ser útil distinguir entre "juegos matemáticos" de interés principalmente para matemáticos y científicos para reflexionar y resolver, y "juegos" de interés para la población en general como una forma de entretenimiento y competencia. 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. Tic-tac-toe todavía se usa para enseñar los principios básicos del diseño de juegos de IA a los estudiantes de informática.

Historia

La teoría de los juegos combinatorios surgió en relación con la teoría de los juegos imparciales, en los que cualquier jugada disponible para un jugador también debe estar disponible 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 las condiciones normales de juego, 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, lo que demuestra que son posibles 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 de un juego partidista, en el 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 conocida 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.

Por lo general, los juegos combinatorios, por convención, adoptan 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 donde se aplica 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 u otro en cualquier punto del juego, y un jugador gana. cuando su oponente no tiene movimiento en ninguno de los dos 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 de entre sí en diferentes partes del tablero.

Ejemplos

El texto introductorio Winning Ways introdujo una gran cantidad de juegos, pero los siguientes se usaron como ejemplos motivadores para la teoría introductoria:

• Blue-Red Hackenbush - A nivel finito, este juego combinatorio partisano permite construcciones de juegos cuyos valores son números racionales dyadic. En el nivel infinito, permite construir todos los valores reales, así como muchos infinitos que caen dentro de la clase de números surrealistas.
• Blue–Red–Green Hackenbush - Permite valores adicionales de juego que no son números en el sentido tradicional, por ejemplo, estrella.
• Toads y ranas - Permite varios valores de juego. A diferencia de la mayoría de otros juegos, una posición es fácilmente representada por una corta cadena de caracteres.
• Domineering - Varios juegos interesantes, como juegos calientes, aparecen como posiciones en Domineering, porque a veces hay un incentivo para moverse, y a veces no. Esto permite discutir la temperatura de un juego.
• Nim - Un juego imparcial. Esto permite la construcción de los nimbers. (También se puede ver como un caso único y verde de Blue-Red-Green Hackenbush.)

El juego clásico Go influyó en las primeras teorías de juegos combinatorios, y Berlekamp y Wolfe desarrollaron posteriormente una teoría de final de juego y temperatura para él (ver referencias). Armados con esto, pudieron construir plausibles posiciones finales de Go desde las cuales podrían dar a los jugadores expertos de Go una opción de 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 haga 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 extenso estudio, incluido el trabajo que implica el uso de supercomputadoras, ha creado tablas 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 solo se estudien finales limitados o posiciones compuestas con un pequeño número de piezas).

Resumen

Un juego, en sus términos más simples, es una lista de posibles "movimientos" que pueden hacer dos jugadores, llamados izquierdo y derecho. 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 hacia 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 se puede mover el jugador de la izquierda, y R es el conjunto de posiciones de juego a las que se puede mover el jugador de la derecha; cada posición en L y R se define como un juego usando la misma notación.

Usando Domineering como ejemplo, etiquete cada uno de los dieciséis cuadros del tablero de cuatro por cuatro con A1 para el cuadrado superior izquierdo, C2 para el tercer cuadro desde la izquierda en la segunda fila desde arriba, y así sucesivamente.. Usamos, p. (D3, D4) para representar la posición de 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 combinatorios como

{}()A1,A2),()B1,B2),...... Silencio()A1,B1),()A2,B2),...... }.{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 por las definiciones de la teoría del juego combinatorio en lugar de codificarse dentro de los estados del juego.

{}()A1,A2)Silencio()A1,B1)}={}{}Silencio}Silencio{}Silencio}}.{displaystyle { {mathrm {A} 1,mathrm {A} 2) Tortura(mathrm {A} 1,mathrm {B}}={{{\}\}}}}

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 (que corresponde al único cuadrado sobrante después del movimiento) se denomina juego cero y, de hecho, se puede abreviar 0. En el juego cero, ningún jugador tiene movimientos válidos; por lo tanto, el jugador cuyo turno es cuando sale el juego cero pierde automáticamente.

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

Un tipo adicional de juego, que no se encuentra en Domineering, es un juego loopy, en el que un movimiento válido de izquierda o derecha es un juego que luego puede conducir de nuevo al primer juego. Las damas, por ejemplo, se vuelven locas cuando una de las piezas asciende, ya que entonces puede alternar sin cesar entre dos o más cuadrados. Un juego que no posee tales movimientos se llama loopfree.

Abreviaturas del juego

Números

Los números representan el número de movimientos gratuitos 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.

0 = { minúsculas}

1 = {0 vidas}, 2 = {1 vidas}, 3 = {2 sufrimiento}

−1 = { minusválidos}, −2 = { minusválidos−1}, −3 = { perpetua−2}

El juego cero es una pérdida para el primer jugador.

Los juegos de suma de números se comportan como los enteros, por ejemplo 3 + −2 = 1.

Estrella

Estrella, escrito 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) moverse a un juego cero y, por lo tanto, ganar.

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

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

Arriba

Arriba, 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.

"Caliente" juegos

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 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. Puede sumarse a números, o multiplicarse por números positivos, en la forma esperada; por ejemplo, 4 ± 1 = {5|3}.

Numbers

Un juego imparcial es aquel en el que, en cada posición 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 eliminarlo el otro. Sin embargo, dominar no es imparcial, porque un jugador coloca fichas de dominó horizontales y el otro coloca fichas verticales. Del mismo modo, Checkers 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, cualquier jugador puede reemplazar el número con cualquier número ordinal más pequeño; los juegos así definidos se conocen como nimbers. El teorema de Sprague-Grundy establece que todo juego imparcial es equivalente a un nimber.

The "smallest#34; numbers – the simplest and least under the usual ordering of the ordinals – are 0 and ∗.