Árbol de juego

Para ver el árbol de juegos tal como se usa en la teoría de juegos (no en la teoría de juegos combinatoria ), consulte Juego de forma extensiva .

En el contexto de la teoría de juegos combinatoria , que normalmente estudia juegos secuenciales con información perfecta , un árbol de juegos es un gráfico que representa todos los estados posibles del juego dentro de dicho juego. Tales juegos incluyen los conocidos como ajedrez , damas , Go y tic-tac-toe . Esto se puede usar para medir la complejidad de un juego , ya que representa todas las formas posibles en que un juego puede funcionar. Debido a los grandes árboles de juego de los juegos complejos.como el ajedrez, los algoritmos que están diseñados para jugar esta clase de juegos utilizarán árboles de juego parciales, lo que hace que el cálculo sea factible en las computadoras modernas. Existen varios métodos para resolver árboles de juegos. Si se puede generar un árbol de juego completo, se puede utilizar un algoritmo determinista , como la inducción hacia atrás o el análisis retrógrado . Los algoritmos aleatorios y los algoritmos Minimax , como MCTS, se pueden utilizar en los casos en que no sea factible un árbol de juego completo.

Entendiendo el árbol del juego

Para comprender mejor el árbol del juego, se puede pensar en él como una técnica para analizar juegos adversarios, que determinan las acciones que realiza el jugador para ganar el juego. En teoría de juegos, un árbol de juego es un gráfico dirigido cuyos nodos son posiciones en un juego (p. Ej., La disposición de las piezas en un juego de mesa) y cuyos bordes son movimientos (p. Ej., Mover piezas de una posición en un tablero a otra ). ^[1]

El árbol de juego completo para un juego es el árbol de juego que comienza en la posición inicial y contiene todos los movimientos posibles de cada posición; el árbol completo es el mismo árbol que se obtiene de la representación del juego de forma extensiva . Para ser más específicos, el juego completo es una norma para el juego en la teoría de juegos. Lo que puede expresar claramente muchos aspectos importantes. Por ejemplo, la secuencia de acciones que pueden tomar las partes interesadas, sus elecciones en cada punto de decisión, información sobre las acciones tomadas por otras partes interesadas cuando cada participante toma una decisión y los beneficios de todos los resultados posibles del juego. ^[2]

Las dos primeras capas del árbol del juego para tic-tac-toe.

El diagrama muestra los dos primeros niveles, o capas , en el árbol del juego de tic-tac-toe . Las rotaciones y reflejos de las posiciones son equivalentes, por lo que el primer jugador tiene tres opciones de movimiento: en el centro, en el borde o en la esquina. El segundo jugador tiene dos opciones para la respuesta si el primer jugador jugó en el centro, de lo contrario, cinco opciones. Etcétera.

El número de nodos de hojas en el árbol completo del juego es el número de posibles formas diferentes en que se puede jugar el juego. Por ejemplo, el árbol de juego de tic-tac-toe tiene 255,168 nodos de hoja.

Los árboles de juego son importantes en la inteligencia artificial porque una forma de elegir el mejor movimiento en un juego es buscar en el árbol del juego utilizando cualquiera de los numerosos algoritmos de búsqueda de árboles , combinados con reglas similares a minimax para podar el árbol . El árbol de juego de tic-tac-toe se puede buscar fácilmente, pero los árboles de juego completos para juegos más grandes como el ajedrez son demasiado grandes para buscar. En cambio, un programa de ajedrez busca en un árbol de juego parcial : normalmente tantas capas de la posición actual como pueda buscar en el tiempo disponible. Excepto en el caso de los árboles de caza "patológicos" ^[3] (que parece ser bastante raro en la práctica), aumentar la profundidad de búsqueda (es decir, el número de capas buscadas) generalmente mejora la posibilidad de elegir el mejor movimiento.

Los juegos de dos personas también se pueden representar como árboles y-o . Para que el primer jugador gane un juego, debe existir un movimiento ganador para todos los movimientos del segundo jugador. Esto se representa en el árbol y-o usando la disyunción para representar los movimientos alternativos del primer jugador y usando la conjunción para representar todos los movimientos del segundo jugador.

Resolver árboles de juegos

Versión de algoritmo determinista

Se ha sugerido que este artículo se fusione en un algoritmo determinista . ( Discutir ) Propuesta desde junio de 2021.

Un árbol de juego arbitrario que ha sido completamente coloreado.

Con un árbol de juego completo, es posible "resolver" el juego, es decir, encontrar una secuencia de movimientos que el primer o el segundo jugador pueda seguir y que garantice el mejor resultado posible para ese jugador (generalmente una victoria o un lazo). El algoritmo determinista (que generalmente se denomina inducción hacia atrás o análisis retrógrado ) se puede describir de forma recursiva de la siguiente manera.

1. Colorea la capa final del árbol del juego para que todas las victorias para el jugador 1 se coloreen de una manera (azul en el diagrama), todas las ganancias para el jugador 2 estén coloreadas de otra manera (rojo en el diagrama) y todos los empates se coloreen de una tercera manera. (Gris en el diagrama).
2. Mira la siguiente capa. Si existe un nodo de color opuesto al del jugador actual, colorea este nodo para ese jugador también. Si todos los nodos inmediatamente inferiores están coloreados para el mismo jugador, colorea este nodo para el mismo jugador también. De lo contrario, colorea este nodo con una corbata.
3. Repita para cada capa, moviéndose hacia arriba, hasta que todos los nodos estén coloreados. El color del nodo raíz determinará la naturaleza del juego.

El diagrama muestra un árbol de juego para un juego arbitrario, coloreado usando el algoritmo anterior.

Por lo general, es posible resolver un juego (en este sentido técnico de "resolver") utilizando solo un subconjunto del árbol del juego, ya que en muchos juegos no es necesario analizar un movimiento si hay otro movimiento que sea mejor para el mismo jugador ( por ejemplo , la poda alfa-beta se puede utilizar en muchos juegos deterministas).

Cualquier subárbol que pueda usarse para resolver el juego se conoce como árbol de decisión , y los tamaños de los árboles de decisión de varias formas se usan como medidas de complejidad del juego . ^[4]

Versión de algoritmos aleatorios

Se ha sugerido que este artículo se fusione en un algoritmo aleatorio . ( Discutir ) Propuesta desde junio de 2021.

Se pueden utilizar algoritmos aleatorios para resolver árboles de juegos. Hay dos ventajas principales en este tipo de implementación: rapidez y practicidad. Mientras que una versión determinista de la resolución de árboles de juego se puede hacer en Ο ( n ) , el siguiente algoritmo aleatorio tiene un tiempo de ejecución esperado de θ ( n ^0,792 ) si cada nodo en el árbol de juego tiene grado 2. Además, es práctico porque aleatorio los algoritmos son capaces de "frustrar a un enemigo", lo que significa que un oponente no puede vencer al sistema de árboles de juego si conoce el algoritmo utilizado para resolver el árbol de juego porque el orden de resolución es aleatorio.

La siguiente es una implementación del algoritmo de solución de árbol de juego aleatorio: ^[5]

def  gt_eval_rand ( u )  ->  bool :  "" "Devuelve True si este nodo se evalúa como una victoria, de lo contrario False" ""  si  u . hoja :  return  u . win  else :  random_children  =  ( gt_eval_rand ( niño )  para  niño  en  random_order ( u . niños ))  si  u . op  ==  "OR" :  devuelve  cualquier ( random_children ) si  u . op  ==  "Y" :  devuelve  todos ( random_children )

El algoritmo hace uso de la idea de " cortocircuito ": si el nodo raíz se considera un operador " O ", una vez que se encuentra un Verdadero , la raíz se clasifica como Verdadero ; a la inversa, si el nodo raíz se considera un operador " Y ", una vez que se encuentra un Falso , la raíz se clasifica como Falso .

^[6]

Ver también

• Poda alfa-beta
• Juego de forma extenso
• Número de Shannon
• Complejidad del juego

Referencias

1. Zuckerman, Inon; Wilson, Brandon; Nau, Dana S. (2018). "Evitar la patología del árbol de juego en la búsqueda adversaria de 2 jugadores" . Inteligencia computacional . 34 (2): 542–561. doi : 10.1111 / moneda.12162 . ISSN  1467-8640 . S2CID  46926187 .
2. Huang, Zishuo; Yu, Hang; Chu, Xiangyang; Peng, Zhenwei (1 de mayo de 2018). "Un novedoso modelo de optimización basado en árbol de juegos para sistemas de conversión multienergía" . Energía . 150 : 109-121. doi : 10.1016 / j.energy.2018.02.091 . ISSN 0360-5442 . 
3. Nau, Dana (1982). "Una investigación de las causas de la patología en los juegos". Inteligencia artificial . 19 (3): 257–278. doi : 10.1016 / 0004-3702 (82) 90002-9 .
4. Víctor Allis (1994). Búsqueda de soluciones en juegos e inteligencia artificial (PDF) . Doctor. Tesis, Universidad de Limburg, Maastricht, Holanda. ISBN  90-900748-8-0.
5. Daniel Roche (2013). SI486D: Aleatoriedad en Computación, Unidad de Árboles de Juegos . Academia Naval de los Estados Unidos, Departamento de Ciencias de la Computación.
6. Pekař, Libor; Matušů, Radek; Andrla, Jiří; Litschmannová, Martina (septiembre de 2020). "Revisión de la investigación del juego Kalah y la propuesta de un algoritmo heurístico-determinista novedoso en comparación con las soluciones de búsqueda de árboles y la toma de decisiones humanas" . Informática . 7 (3): 34. doi : 10.3390 / informatics7030034 .

Otras lecturas

• Hu, Te Chiang; Shing, Man-tak (2002). Algoritmos combinatorios . Publicaciones de Courier Dover. ISBN 0-486-41962-2. Consultado el 2 de abril de 2007 .
• Judea Pearl , Heurística , Addison-Wesley, 1984