Hispanopedia Wiki
Articulo de referencia

Árbol de juego

El diagrama muestra los dos primeros niveles, o pliés , del árbol de juego del tres en raya . Las rotaciones y reflexiones de las posiciones son equivalentes, por lo que el prim...

Hispanopedia WikiContenido en espanolLectura gratuita
El diagrama muestra los dos primeros niveles, o pliés , del árbol de juego del tres en raya . Las rotaciones y reflexiones 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 de respuesta si el primero jugó en el centro; de lo contrario, tiene cinco opciones. Y así sucesivamente.

En el contexto de la teoría de juegos combinatoria , un árbol de juego es un grafo que representa todos los estados posibles de un juego secuencial con información perfecta . Algunos ejemplos de estos juegos son el ajedrez , las damas , el Go y el tres en raya .

Un árbol de juego puede utilizarse para medir la complejidad de un juego , ya que representa todas las posibles formas en que puede desarrollarse. Debido a la gran extensión de los árboles de juego de juegos complejos como el ajedrez, los algoritmos diseñados para este tipo de juegos utilizan árboles de juego parciales, lo que facilita su cálculo en ordenadores modernos. Existen diversos métodos para resolver árboles de juego. 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 . En los casos en que no sea posible generar un árbol de juego completo, se pueden utilizar algoritmos aleatorios y algoritmos minmax , como MCTS .

Comprender el árbol del juego

Para comprender mejor el árbol de juego, se puede considerar como una técnica para analizar juegos adversariales, que determina las acciones que un jugador realiza para ganar. En teoría de juegos, un árbol de juego es un grafo dirigido cuyos nodos representan posiciones en un juego (por ejemplo, la disposición de las piezas en un juego de mesa) y cuyas aristas representan movimientos (por ejemplo, mover piezas de una posición a otra en el tablero). [ 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 desde cada posición; el árbol completo es el mismo que se obtiene a partir de la representación del juego en forma extensiva . Más específicamente, el juego completo es una norma para el juego en la teoría de juegos, que puede expresar claramente muchos aspectos importantes. Por ejemplo, la secuencia de acciones que pueden tomar los participantes, sus elecciones en cada punto de decisión, información sobre las acciones tomadas por otros participantes cuando cada participante toma una decisión, y los beneficios de todos los resultados posibles del juego. [ 2 ]

El número de nodos hoja en el árbol de juego completo representa el número de formas diferentes en que se puede jugar. Por ejemplo, el árbol de juego del tres en raya tiene 255.168 nodos hoja.

Los árboles de juego son importantes en inteligencia artificial porque una forma de elegir el mejor movimiento en un juego es buscar en el árbol de juego utilizando cualquiera de los numerosos algoritmos de búsqueda de árboles , combinados con reglas tipo minimax para podar el árbol . El árbol de juego para el tres en raya es fácilmente explorable, pero los árboles de juego completos para juegos más grandes como el ajedrez son demasiado grandes para explorarlos. En cambio, un programa de ajedrez busca en un árbol de juego parcial : normalmente tantas jugadas desde la posición actual como pueda buscar en el tiempo disponible. Excepto en el caso de árboles de juego "patológicos" [ 3 ] (que parecen ser bastante raros en la práctica), aumentar la profundidad de búsqueda (es decir, el número de jugadas exploradas) generalmente mejora la probabilidad de elegir el mejor movimiento.

Los juegos para dos personas también pueden representarse como árboles de conjunción . Para que el primer jugador gane, debe existir una jugada ganadora para cada una de las jugadas del segundo jugador. Esto se representa en el árbol de conjunción mediante la disyunción para representar las jugadas alternativas del primer jugador y la conjunción para representar todas las jugadas del segundo jugador.

Resolver árboles de juego

Versión del algoritmo determinista

Un árbol de juego arbitrario que ha sido coloreado por completo.

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 puedan seguir para garantizar el mejor resultado posible para ese jugador (generalmente una victoria o un empate). El algoritmo determinista (que generalmente se denomina inducción hacia atrás o análisis retrógrado ) se puede describir recursivamente de la siguiente manera.

  1. Colorea la última capa del árbol de juego de manera que todas las victorias del jugador 1 estén coloreadas de una forma (azul en el diagrama), todas las victorias del jugador 2 estén coloreadas de otra forma (rojo en el diagrama) y todos los empates estén coloreados de una tercera forma (gris en el diagrama).
  2. Observa la siguiente capa. Si existe un nodo con un color opuesto al del jugador actual, colorea también este nodo para ese jugador. Si todos los nodos inmediatamente inferiores tienen el mismo color, colorea también este nodo para ese jugador. De lo contrario, marca este nodo como empate.
  3. Repite el proceso para cada capa, avanzando 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 según el algoritmo descrito anteriormente.

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 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 diversas formas se utilizan como medidas de la complejidad del juego . [ 4 ]

Versión con algoritmos aleatorios

Los algoritmos aleatorios pueden utilizarse para resolver árboles de juego. Este tipo de implementación presenta dos ventajas principales: velocidad y practicidad. Mientras que una versión determinista para resolver árboles de juego se puede realizar en Ο ( n ) , el siguiente algoritmo aleatorio tiene un tiempo de ejecución esperado de θ ( n = 0,792 ) si cada nodo del árbol de juego tiene grado 2. Además, resulta práctico porque los algoritmos aleatorios son capaces de "frustrar al adversario", lo que significa que un oponente no puede vencer el sistema de árboles de juego conociendo el algoritmo utilizado para resolverlo, ya que el orden de resolución es aleatorio.

A continuación se muestra 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""" if u . leaf : return u . win else : random_children = ( gt_eval_rand ( child ) for child in random_order ( u . children )) if u . op == "OR" : return any ( random_children ) if u . op == "AND" : return all ( random_children )

El algoritmo utiliza la idea de " cortocircuito ": si el nodo raíz se considera un operador " OR ", entonces una vez que se encuentra un verdadero , la raíz se clasifica como verdadera ; por el contrario, si el nodo raíz se considera un operador " AND ", entonces una vez que se encuentra un falso , la raíz se clasifica como falsa .

[ 6 ]

Véase también

Referencias

  1. ↑ Zuckerman, Inon; Wilson, Brandon; Nau, Dana S. (2018). "Evitando la patología del árbol de juego en la búsqueda adversaria de 2 jugadores" . Inteligencia Computacional . 34 (2): 542– 561. doi : 10.1111/coin.12162 . ISSN 1467-8640 . S2CID 46926187 .  
  2. ↑ Huang, Zishuo; Yu, Hang; Chu, Xiangyang; Peng, Zhenwei (2018-05-01). "Un nuevo modelo de optimización basado en un árbol de juego para sistemas de conversión de energía múltiple" . Energy . 150 : 109–121 . Bibcode : 2018Ene...150..109H . 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. ↑ Victor Allis (1994). Búsqueda de soluciones en juegos e inteligencia artificial (PDF) . Tesis doctoral, Universidad de Limburgo, Maastricht, Países Bajos. ISBN 90-900748-8-0.
  5. ↑ Daniel Roche (2013). SI486D: Aleatoriedad en la computación, Unidad de árboles de juego . Academia Naval de los Estados Unidos, Departamento de Ciencias de la Computación. Archivado del original el 8 de mayo de 2021. Recuperado el 29 de abril de 2013 .
  6. ↑ Pekař, Libor; Matušů, Radek; Andrla, Jiří; Litschmannová, Martina (septiembre de 2020). "Revisión de la investigación sobre el juego de Kalah y la propuesta de un nuevo algoritmo heurístico-determinista comparado con soluciones de búsqueda en árbol y toma de decisiones humana" . Informatics . 7 (3): 34. doi : 10.3390/informatics7030034 . hdl : 10084/142398 .

Lecturas adicionales

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