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 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 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, privilegiando los juegos que ofrecen información perfectaen el 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 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 CGT, los movimientos en estos y otros juegos se representan como un árbol de juego .
Los juegos combinatorios también incluyen acertijos 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, por lo que 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.
CGT tiene un énfasis diferente al de la teoría de juegos "tradicional" o "económica", que inicialmente se desarrolló para estudiar juegos con estructura combinatoria simple, pero con elementos de azar (aunque también considera movimientos secuenciales, ver juego de forma extensiva ). Esencialmente, CGT ha contribuido con 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. [3] El tipo de juegos estudiado por CGT también es de interés en inteligencia artificial , particularmente para la planificación y programación automatizada . En CGT ha habido menos énfasis en refinar los algoritmos de búsqueda prácticos (como la poda alfa-betaheurí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 medidas de la complejidad del juego o 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 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 . [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 los finales de Go. Aplicar CGT a un puestointenta 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.
