Teoría de juegos combinatorios - Combinatorial game theory

Este artículo trata sobre la teoría de los juegos combinatorios. Para conocer la teoría que incluye juegos de azar y juegos de conocimiento imperfecto, consulte Teoría de juegos .
Matemáticos jugando Konane en un taller de teoría de juegos combinatoria

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. CGT no ha estudiado tradicionalmente los juegos de azar o aquellos que utilizan información imperfecta o incompleta, privilegiando los juegos que ofrecen una información perfecta en la que ambos jugadores siempre conocen el estado del juego y el conjunto de jugadas disponibles. 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. 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áciles de resolver". Algunos juegos combinatorios también pueden tener un área de juego ilimitada , como el ajedrez infinito . En 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 Game of Life 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.

CGT tiene un énfasis diferente a la teoría de juegos "tradicional" o "económica", que fue desarrollada inicialmente para estudiar juegos con estructura combinatoria simple, pero con elementos de azar (aunque también considera movimientos secuenciales, ver juego de forma extensa ). Esencialmente, CGT 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 CGT también es de interés en inteligencia artificial , particularmente para planificación y programación automatizadas . En CGT ha habido menos énfasis en refinar los algoritmos de búsqueda práctica (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 las medidas de la complejidad del juego o las pruebas de la existencia de una solución óptima sin especificando necesariamente un algoritmo, como el argumento de robo de estrategia ).

Una noción importante en CGT es la del juego resuelto . Por ejemplo, tic-tac-toe 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 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. La aplicación de CGT a una posición intenta 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" combinatorios de interés para la población en general como una forma de entretenimiento y competencia. Sin embargo, varios juegos pertenecen a ambas categorías. Nim , por ejemplo, es un juego fundamental en la fundación de CGT 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 inteligencia artificial a los estudiantes de ciencias de la computación .

Historia

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 presentaron conjuntamente la teoría de un juego partidista , en el que se relajó 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 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 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.

Ejemplos de

El texto introductorio Winning Ways 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 partidista permite la construcción de juegos cuyos valores son números racionales diádicos . En el nivel infinito, le permite a uno 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 de juego adicionales que no son números en el sentido tradicional, por ejemplo, estrella .
  • Toads and Frogs : 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.
  • Dominante : varios juegos interesantes, como los juegos calientes , aparecen como posiciones en Dominante, 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 de temperatura (ver referencias). Armados con esto, pudieron construir posiciones plausibles de finales de Go desde las que podían dar a los jugadores expertos de Go una opción de lados 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 120 , 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).

Visión general

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

20x20square.png20x20square.png
20x20square.png

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; por lo tanto, 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 de estrellas, el único movimiento válido conduce al juego de cero, lo que significa que el turno de quien llegue durante el juego de estrellas 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 asciende, ya que entonces puede alternar interminablemente entre dos o más cuadrados. Un juego que no posee tales movimientos se llama loopfree .

Abreviaturas de juegos

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

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

∗ + ∗ = 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.

Hasta

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

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 es "candente"; 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, dominar no es imparcial, porque un jugador coloca dominós horizontales y el otro coloca los verticales. Asimismo, Checkers 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 más pequeño; los juegos definidos de esta manera se conocen como nimbers . El teorema de Sprague-Grundy establece que todo juego imparcial equivale a un ágil.

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

Ver también

Notas

Referencias

enlaces externos