Teoría de juegos combinatorios para niños
La teoría de juegos combinatorios (a menudo llamada CGT) es una rama de las matemáticas y la informática teórica. Se dedica a estudiar juegos donde los jugadores se turnan y tienen toda la información disponible. Estos juegos suelen ser para dos jugadores y tienen una "posición" clara. Los jugadores se mueven de formas definidas para alcanzar una condición de victoria.
La CGT no suele estudiar juegos con azar o con información incompleta. Se enfoca en juegos donde ambos jugadores siempre saben todo sobre el estado del juego y los movimientos posibles. Sin embargo, a medida que las técnicas matemáticas avanzan, los tipos de juegos que se pueden analizar se expanden.
Contenido
¿Qué son los juegos combinatorios?
Los juegos combinatorios incluyen juegos muy conocidos como el ajedrez, las damas y el go. También incluyen juegos más sencillos como el tres en raya, que se considera "fácil de resolver". Algunos juegos combinatorios pueden tener un área de juego muy grande, como el ajedrez infinito. En la CGT, los movimientos de estos juegos se representan como un árbol de juego.
Juegos y rompecabezas combinatorios
Los juegos combinatorios también incluyen rompecabezas para un solo jugador, como el Sudoku. Además, estudian "autómatas" sin jugadores, como el Juego de la vida de Conway. Aunque, en su definición más estricta, los "juegos" necesitan más de un participante. Por eso, a los de un jugador se les llama "rompecabezas" y a los otros "autómatas".
Diferencia con la teoría de juegos general
La teoría de juegos en general es un campo más amplio. Incluye juegos con azar, juegos con información imperfecta y juegos donde los jugadores pueden moverse al mismo tiempo. Esta teoría suele representar situaciones de toma de decisiones de la vida real.
La CGT se enfoca de manera diferente a la teoría de juegos "tradicional" o "económica". La CGT ha aportado nuevos métodos para analizar los árboles de juego. Por ejemplo, usa los números surreales, que son un tipo especial de juegos para dos jugadores con información perfecta. Los juegos estudiados por la CGT también son importantes en la inteligencia artificial, especialmente para la planificación automática.
Juegos resueltos y su complejidad
Un concepto importante en la CGT es el de "juego resuelto". Por ejemplo, el tres en raya es un juego resuelto. Esto significa que se puede demostrar que cualquier partida terminará en empate si ambos jugadores juegan de la mejor manera posible.
Es difícil obtener resultados similares para juegos más complejos. Por ejemplo, en 2007 se anunció que las damas se habían resuelto. Se demostró que el juego óptimo de ambos lados también lleva a un empate. Este resultado se logró con la ayuda de computadoras.
Otros juegos del mundo real son demasiado complicados para un análisis completo hoy en día. Sin embargo, la teoría ha tenido éxito en analizar partes finales del juego de go. Aplicar la CGT a una posición significa intentar encontrar la mejor secuencia de movimientos para ambos jugadores hasta el final del juego. En la práctica, este proceso es muy difícil a menos que el juego sea muy simple.
Juegos matemáticos vs. juegos de entretenimiento
Es útil diferenciar entre "juegos matemáticos" combinatorios, que interesan a matemáticos y científicos, y "juegos de entretenimiento" combinatorios, que interesan al público en general. Sin embargo, varios juegos están en ambas categorías. El Nim, por ejemplo, es un juego fundamental en la formación de la CGT y fue uno de los primeros juegos en ser programados en una computadora. El tres en raya todavía se usa para enseñar principios básicos de diseño de juegos de inteligencia artificial a estudiantes de informática.
Historia de la teoría de juegos combinatorios
La CGT surgió de la teoría de los juegos imparciales. En estos juegos, cualquier movimiento disponible para un jugador también debe estar disponible para el otro. Un ejemplo es el Nim, que se puede resolver por completo. Nim es un juego imparcial para dos jugadores. Se rige por 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 como montones en Nim. Esto demostró que se pueden unificar muchos juegos a nivel combinatorio.
En la década de 1960, Elwyn R. Berlekamp, John H. Conway y Richard K. Guy introdujeron la teoría de los juegos partisanos. En estos juegos, no es necesario que un movimiento disponible para un jugador esté disponible para ambos. Sus descubrimientos 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, que introdujo el concepto de números surreales.
Los juegos combinatorios, por lo general, se presentan de una forma en la que un jugador gana cuando el otro no tiene movimientos. Es fácil convertir cualquier juego finito con solo dos resultados posibles a esta forma. Uno de los conceptos más importantes es la suma de dos juegos. Esto es un juego en el que cada jugador puede elegir moverse en un juego o en el otro en cualquier momento. Un jugador gana cuando su oponente no tiene movimientos en ninguno de los juegos. Esta forma de combinar juegos crea una estructura matemática muy rica.
Conway mencionó en On Numbers and Games que la idea de los juegos partisanos surgió al observar las partidas finales de go. Estas a menudo se pueden dividir en sumas de finales más simples y separados en diferentes partes del tablero.
Ejemplos de juegos estudiados
El libro Winning Ways for your Mathematical Plays presentó muchos juegos. Los siguientes se usaron como ejemplos para explicar la teoría:
- Hackenbush Azul-Rojo: Este juego combinatorio partisano permite crear juegos cuyos valores son números racionales.
- Hackenbush Azul-Rojo-Verde: Permite valores de juego adicionales que no son números en el sentido tradicional, como la estrella.
- Ranas y Sapos: Permite varios valores de juego. Una posición se representa fácilmente con una pequeña secuencia de caracteres.
- Domineering: Varios juegos interesantes, como los "juegos calientes", aparecen como posiciones en Domineering. Esto permite hablar sobre la "temperatura" de un juego.
- Nim: Un juego imparcial. Permite la creación de nimbers.
El juego clásico go influyó en la teoría de juegos combinatorios inicial. Berlekamp y Wolfe desarrollaron una teoría de finales y de la "temperatura" de los juegos. Con esto, pudieron crear posiciones de finales de go donde podían vencer a jugadores expertos.
Otro juego estudiado en la teoría de juegos combinatorios es el ajedrez. En 1953, Alan Turing escribió que si se puede explicar cómo hacer un cálculo, se puede programar una computadora para hacerlo. En 1950, Claude Shannon estimó que la complejidad del árbol de juego del ajedrez era de al menos 10120. Esto se conoce como el número de Shannon. El ajedrez sigue sin resolverse por completo. Sin embargo, se han creado bases de datos de finales de ajedrez con la ayuda de supercomputadoras. Estas muestran el resultado de un juego perfecto para todas las partidas finales con siete piezas o menos. El ajedrez infinito es aún más complejo que el ajedrez.
Conceptos básicos de la CGT
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 que resulta de cualquier movimiento puede verse como otro juego. Esta idea de ver los juegos en términos de sus posibles movimientos a otros juegos lleva a una definición matemática recursiva de los juegos. Esta definición 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. 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.
El juego cero
El {|} en la lista de movimientos de cada jugador se llama el juego cero, y se puede abreviar como 0. En el juego cero, ningún jugador tiene movimientos válidos. Así, el jugador al que le toca el turno cuando aparece el juego cero pierde automáticamente.
El juego estrella
Un tipo de juego simple se llama el juego de las estrellas, que también se puede abreviar ∗. En el juego estrella, el único movimiento válido lleva al juego cero. Esto significa que quien tenga el turno durante el juego estrella gana automáticamente.
- ∗ + ∗ = 0, porque el primer jugador debe convertir una copia de ∗ en 0. 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 permite movimientos.
El juego ∗ no es ni positivo ni negativo. Se dice que todos los demás juegos en los que el primer jugador gana (sin importar de qué lado esté) son "difusos con" o "se confunden con" 0. Simbólicamente, escribimos ∗ || 0.
Juegos "locos" y "sin bucles"
Un tipo adicional de juego es un juego loco. En este, un movimiento válido de izquierda o derecha es un juego que luego puede llevar de vuelta al primer juego. Las damas, por ejemplo, se vuelven locas cuando una de las piezas es promocionada. Esto se debe a que puede alternar sin fin entre dos o más casillas. Un juego que no tiene tales movimientos se llama sin bucles.
Abreviaturas comunes de juegos
Números
Los números representan la cantidad de movimientos libres o la ventaja de un jugador. Por convención, los números positivos significan una ventaja para el jugador izquierdo, y los negativos para el derecho. Se definen de forma recursiva, siendo 0 el punto de partida.
- 0 = {|}
- 1 = {0|}, 2 = {1|}, 3 = {2|}
- −1 = {|0}, −2 = {|−1}, −3 = {|−2}
El juego cero es una derrota para el primer jugador. La suma de los juegos de números se comporta como los números enteros, por ejemplo, 3 + −2 = 1.
Arriba y Abajo
Arriba, escrito como ↑, es una posición en la teoría de juegos combinatorios. En notación estándar, ↑ = {0 | ∗}.
- −↑ = ↓ (abajo)
Arriba es estrictamente positivo (↑> 0), pero es muy pequeño (infinitesimal).
Abajo, escrito como ↓, es una posición en la teoría de juegos combinatorios. En notación estándar, ↓ = {∗ | 0}.
- −↓ = ↑ (arriba)
Abajo es estrictamente negativo (↓ <0), pero también es muy pequeño (infinitesimal).
Juegos "calientes"
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á "caliente". Es mayor que cualquier número menor que -1, menor que cualquier número mayor que 1 y se confunde con cualquier número intermedio. Se escribe como ± 1. Se puede sumar a números o multiplicar 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. Sin embargo, el dominó no es imparcial, porque un jugador coloca dominós horizontales y el otro verticales. Las damas tampoco es imparcial, ya que los jugadores tienen piezas de diferentes colores.
Para cualquier número ordinal, se puede definir un juego imparcial generalizando Nim. 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 es equivalente a un nimber.
Los nimbers "más pequeños" son 0 y ∗.
Galería de imágenes
Véase también
En inglés: Combinatorial game theory Facts for Kids
