Lenguaje de descripción de juegos

El Lenguaje de Descripción de Juegos (GDL) es un lenguaje de programación lógica especializado diseñado por Michael Genesereth . Su objetivo es permitir el desarrollo de agentes de IA capaces de jugar a juegos de forma general . Forma parte del Proyecto de Juego General de la Universidad de Stanford . GDL es una herramienta para expresar las complejidades de las reglas y la dinámica de los juegos de forma comprensible para los sistemas de inteligencia artificial (IA) mediante una combinación de construcciones lógicas y principios declarativos .

En la práctica, el GDL se utiliza con frecuencia en competiciones de juegos generales y en proyectos de investigación. En estos contextos, el GDL se emplea para especificar las reglas de los juegos que deben jugar los agentes de IA. Los desarrolladores e investigadores de IA utilizan el GDL para crear algoritmos capaces de comprender e interactuar con los juegos según sus reglas. El uso del GDL permite el desarrollo de agentes de IA altamente adaptables, capaces de competir en diversos escenarios.

Propósito del GDL

Citado en un artículo de New Scientist , Genesereth señaló que, si bien Deep Blue puede jugar ajedrez a nivel de gran maestro , es incapaz de jugar damas porque es un jugador especializado. ^{[ 1 ]} Tanto el ajedrez como las damas se pueden describir en GDL. Esto permite crear jugadores de juegos generales que puedan jugar ambos juegos, y cualquier otro juego que se pueda describir usando GDL.

Especificación

Sintaxis

GDL es una variante de Datalog , y la sintaxis es prácticamente la misma. Generalmente se expresa en notación prefija . Las variables comienzan con ?. ^{[ 2 ]}

Palabras clave

A continuación se muestra la lista de palabras clave en GDL, junto con breves descripciones de sus funciones:

distinct: Este predicado se utiliza para exigir que dos términos sean sintácticamente diferentes.

does: El predicado significa que el jugador (o rol ) realiza el movimiento en el estado actual del juego .(does?r?m)?r?m

goal: El predicado se utiliza para definir el valor objetivo (normalmente un número natural entre 0 y 100) para el rol en el estado actual.(goal?r?n)?n?r

init: Este predicado se refiere a un hecho sobre el estado inicial del juego.

legal: El predicado significa que es un movimiento permisible para el rol en el estado actual.(legal?r?m)?m?r

next: Este predicado se refiere a un hecho sobre el siguiente estado del juego.

role: Este predicado se utiliza para añadir el nombre de un jugador.

terminal: Este predicado significa que el estado actual es un estado final del juego.

true: Este predicado se refiere a un hecho sobre el estado actual del juego.

Normas

La descripción de un juego en GDL proporciona reglas completas que definen a los jugadores, el estado inicial, los movimientos válidos, cómo se actualiza el estado del juego, cómo termina y cómo se determina un ganador.

Jugadores

Hechos que definen los roles en un juego. Por ejemplo, el juego de dos jugadores tres en raya podría definir a los jugadores en GDL con (role xplayer)y (role oplayer).

Estado inicial

Reglas que incluyen todos los datos sobre el estado inicial del juego. El siguiente ejemplo describe un tablero vacío de tres por tres de tres casillas, donde el jugador x realiza el primer movimiento:

( inicializar ( celda 1 1 en blanco )) ... ( inicializar ( celda 3 3 en blanco )) ( inicializar ( control xplayer ))

Movimientos legales

Reglas que describen cada movimiento que puede realizar un jugador, según las condiciones actuales del juego. Un jugador de tres en raya puede marcar una casilla si está vacía y es su turno de mover. En GDL:

( <= ( legal ?jugador ( marca ?m ?n )) ( verdadero ( celda ?m ?n en blanco )) ( verdadero ( control ?jugador )))

Actualización del estado del juego

Reglas que describen todos los hechos sobre el siguiente estado en relación con el estado actual y los movimientos realizados por los jugadores. Por ejemplo:

( <= ( siguiente ( celda ?m ?n x )) ( hace xplayer ( marca ?m ?n ))) ( <= ( siguiente ( celda ?m ?n o )) ( hace oplayer ( marca ?m ?n )))

Terminación

Reglas que describen las condiciones bajo las cuales termina el juego. En el tres en raya, el juego termina si alguno de los jugadores hace tres marcas en línea o si no quedan más espacios en blanco:

( <= terminal ( línea x )) ( <= terminal ( línea o )) ( <= terminal not boardopen )

Estados objetivo

Los valores que determinan qué jugador gana en un estado final. Un ejemplo es:

( <= ( objetivo xjugador 100 ) ( línea x )) ( <= ( objetivo opjugador 0 ) ( línea x ))

Extensiones

GDL-II

GDL puede describir juegos finitos con un número arbitrario de jugadores. Sin embargo, GDL no puede describir juegos que contengan un elemento de azar (por ejemplo, lanzar dados ) o juegos donde los jugadores tengan información incompleta sobre el estado actual del juego (por ejemplo, en muchos juegos de cartas , las cartas de los oponentes no son visibles). Una extensión de GDL conocida como Lenguaje de Descripción de Juegos para Juegos con Información Incompleta ( GDL-II ) extiende el lenguaje con dos palabras clave, seesy random, que permiten la descripción de elementos de azar e información incompleta. ^{[ 3 ]} La instrucción significa que el rol percibe en el siguiente estado del juego. La constante se refiere a un jugador predefinido que elige movimientos aleatoriamente.(sees?r?p)?r?prandom

El siguiente es un ejemplo de una descripción GDL-II del juego de cartas Texas hold 'em :

( <= ( ve ?jugador ?carta ) ( hace aleatorio ( repartir_boca_abajo ?jugador ?carta ))) ( <= ( ve ?r ?carta ) ( rol ?r ) ( hace aleatorio ( repartir_río ?carta )))

GDL-III

Michael Thielscher también creó una extensión adicional, GDL-III , un GDL general con información imperfecta e introspección , que admite la especificación de juegos epistémicos , aquellos caracterizados por reglas que dependen del conocimiento de los jugadores. ^{[ 4 ]}

Otros métodos de representación de juegos

En la teoría clásica de juegos , estos pueden formalizarse en formas extensivas y normales . En la teoría de juegos cooperativos , los juegos se representan mediante funciones características. Algunas subclases de juegos permiten representaciones especiales en tamaños más pequeños, también conocidas como juegos sucintos . Con el tiempo, se han desarrollado otros formalismos y lenguajes para representar diferentes tipos de juegos, debido en parte a las necesidades de la investigación interdisciplinaria . ^{[ 5 ]} Algunas de estas representaciones alternativas incluyen aspectos relacionados con el tiempo:

Aplicaciones

Un artículo de 2016 "describe un algoritmo multinivel que compila una descripción general de un juego en GDL en un razonador optimizado en un lenguaje de bajo nivel ". ^{[ 19 ]}

Un artículo de 2017 utiliza GDL para modelar el proceso de mediación para la resolución de una disputa entre dos partes y presentó un algoritmo que utiliza la información disponible para hacerlo de manera eficiente. ^{[ 20 ]}

Véase también

Referencias

↑ Biever, Celeste (29 de julio de 2006). "Producción de los mejores bots para juegos - tecnología - 29 de julio de 2006 - New Scientist Tech" . Archivado del original el 11 de agosto de 2007.
↑ Love, N; Genesereth, M; Hinrichs, T (2006). "Juego general: especificación del lenguaje de descripción de juegos. Informe técnico LG-2006-01" (PDF) . Universidad de Stanford . Universidad de Stanford, Stanford. Archivado del original (PDF) el 24 de febrero de 2021. Recuperado el 1 de julio de 2019 .
↑ Thielscher, M (2010). Fox, M; Poole, D (eds.). "Un lenguaje general de descripción de juegos para juegos con información incompleta" . Actas de la Vigésimo Cuarta Conferencia AAAI sobre Inteligencia Artificial, AAAI 2010. Atlanta: AAAI Press . Recuperado el 1 de julio de 2019 .
↑ Thielscher, Michael (2017). «GDL-III: Un lenguaje de descripción para juegos generales epistémicos» (PDF) . Actas de la Vigésimo Sexta Conferencia Internacional Conjunta sobre Inteligencia Artificial . IJCAI. ISBN 978-0-9992411-0-3Consultado el 1 de julio de 2019 .
↑ Tagiew, Rustam (3 de mayo de 2011). "Si se necesita más que un modelo analítico para predecir la interacción estratégica de agentes reales". arXiv : 1105.0558 [ cs.GT ].
↑ Rosenthal, Robert W. (diciembre de 1973). "Una clase de juegos que poseen equilibrios de Nash de estrategia pura". International Journal of Game Theory . 2 (1): 65– 67. doi : 10.1007/BF01737559 . S2CID 121904640 .
↑ Koller, Daphne ; Megiddo, Nimrod ; von Stengel, Bernhard (1994). «Algoritmos rápidos para encontrar estrategias aleatorias en árboles de juego». Actas del vigésimo sexto simposio anual de la ACM sobre Teoría de la Computación - STOC '94 . págs. 750–759 . doi : 10.1145/195058.195451 . ISBN 0-89791-663-8. S2CID 1893272 .
↑ Alur, Rajeev; Dill, David L. (abril de 1994). "Una teoría de autómatas temporizados" . Theoretical Computer Science . 126 (2): 183– 235. doi : 10.1016/0304-3975(94)90010-8 .
↑ Tomlin, CJ; Lygeros, J.; Shankar Sastry, S. (julio de 2000). "Un enfoque de teoría de juegos para el diseño de controladores para sistemas híbridos". Actas del IEEE . 88 (7): 949– 970. Bibcode : 2000IEEEP..88..949T . CiteSeerX 10.1.1.129.8347 . doi : 10.1109/5.871303 . S2CID 1844682 .
↑ Koller, Daphne; Pfeffer, Avi (1997). "Representaciones y soluciones para problemas de teoría de juegos" (PDF) . Inteligencia Artificial . 94 ( 1–2 ): 167–215 . doi : 10.1016/S0004-3702(97)00023-4 .
↑ Michael, Michael Kearns; Littman, Michael L. (2001). "Modelos gráficos para la teoría de juegos". En UAI : 253–260 . CiteSeerX 10.1.1.22.5705 .
↑ Kearns, Michael; Littman, Michael L.; Singh, Satinder (7 de marzo de 2011). "Modelos gráficos para la teoría de juegos". arXiv : 1301.2281 [ cs.GT ].
↑ Leyton-Brown, Kevin; Tennenholtz, Moshe (2003). "Juegos de efectos locales" . IJCAI'03: Actas de la 18.ª Conferencia Internacional Conjunta sobre Inteligencia Artificial : 772–777 .
↑ Clempner, Julio (2006). "Modelado de juegos de caminos más cortos con redes de Petri: una teoría basada en Lyapunov" . Revista Internacional de Matemáticas Aplicadas y Ciencias de la Computación . 16 (3): 387– 397. ISSN 1641-876X .
↑ Sannikov, Yuliy (septiembre de 2007). "Juegos con acciones imperfectamente observables en tiempo continuo" (PDF) . Econometrica . 75 (5): 1285– 1329. doi : 10.1111/j.1468-0262.2007.00795.x .
↑ Tagiew, Rustam (diciembre de 2008). «Juegos de Petri multiagente». Conferencia Internacional de 2008 sobre Inteligencia Computacional para el Modelado, Control y Automatización . págs. 130–135 . doi : 10.1109/CIMCA.2008.15 . ISBN 978-0-7695-3514-2. S2CID 16679934 .
↑ Tagiew, Rustam (2009). «Sobre modelos de redes de Petri multiagente para el cálculo de juegos finitos extensos». Nuevos desafíos en inteligencia colectiva computacional . Estudios en inteligencia computacional. Vol. 244. Springer. pp. 243–254 . doi : 10.1007/978-3-642-03958-4_21 . ISBN 978-3-642-03957-7.
↑ Bhat, Navin; Leyton-Brown, Kevin (11 de julio de 2012). "Cálculo de equilibrios de Nash de juegos de grafos de acción". arXiv : 1207.4128 [ cs.GT ].
↑ Kowalski, Jakub; Szykuła, Marek (2013). "Construcción de un compilador de lenguaje de descripción de juegos" . AI 2013: Avances en inteligencia artificial: 26.ª Conferencia Conjunta Australásica, Dunedin, Nueva Zelanda, 1-6 de diciembre de 2013. Actas . págs. 234–245 . Consultado el 1 de julio de 2019 .
^ de Jonge, Dave; Trescak, Tomás; Sierra, Carles; Simoff, Simeón; López de Mántaras, Ramón (2017). "Uso del lenguaje de descripción de juegos para la resolución mediada de disputas". IA y sociedad . 2017 (4). Springer: 767– 784. doi : 10.1007/s00146-017-0790-8 . S2CID 22738517 .

Enlaces externos

Especificación del lenguaje de descripción de juegos archivada el 12 de abril de 2013 en Wayback Machine .
Artículo revisado por pares que presenta GDL-II

[1] Biever, Celeste (29 de julio de 2006). "Producción de los mejores bots para juegos - tecnología - 29 de julio de 2006 - New Scientist Tech" . Archivado del original el 11 de agosto de 2007.

[LG-2006-01-2] Love, N; Genesereth, M; Hinrichs, T (2006). "Juego general: especificación del lenguaje de descripción de juegos. Informe técnico LG-2006-01" (PDF) . Universidad de Stanford . Universidad de Stanford, Stanford. Archivado del original (PDF) el 24 de febrero de 2021. Recuperado el 1 de julio de 2019 .

[Thielscher@AAAI_2010-3] Thielscher, M (2010). Fox, M; Poole, D (eds.). "Un lenguaje general de descripción de juegos para juegos con información incompleta" . Actas de la Vigésimo Cuarta Conferencia AAAI sobre Inteligencia Artificial, AAAI 2010. Atlanta: AAAI Press . Recuperado el 1 de julio de 2019 .

[Thielscher-IJCAI_2017-4] Thielscher, Michael (2017). «GDL-III: Un lenguaje de descripción para juegos generales epistémicos» (PDF) . Actas de la Vigésimo Sexta Conferencia Internacional Conjunta sobre Inteligencia Artificial . IJCAI. ISBN 978-0-9992411-0-3Consultado el 1 de julio de 2019 .

[5] Tagiew, Rustam (3 de mayo de 2011). "Si se necesita más que un modelo analítico para predecir la interacción estratégica de agentes reales". arXiv : 1105.0558 [ cs.GT ].

[6] Rosenthal, Robert W. (diciembre de 1973). "Una clase de juegos que poseen equilibrios de Nash de estrategia pura". International Journal of Game Theory . 2 (1): 65– 67. doi : 10.1007/BF01737559 . S2CID 121904640 .

[7] Koller, Daphne ; Megiddo, Nimrod ; von Stengel, Bernhard (1994). «Algoritmos rápidos para encontrar estrategias aleatorias en árboles de juego». Actas del vigésimo sexto simposio anual de la ACM sobre Teoría de la Computación - STOC '94 . págs. 750–759 . doi : 10.1145/195058.195451 . ISBN 0-89791-663-8. S2CID 1893272 .

[8] Alur, Rajeev; Dill, David L. (abril de 1994). "Una teoría de autómatas temporizados" . Theoretical Computer Science . 126 (2): 183– 235. doi : 10.1016/0304-3975(94)90010-8 .

[9] Tomlin, CJ; Lygeros, J.; Shankar Sastry, S. (julio de 2000). "Un enfoque de teoría de juegos para el diseño de controladores para sistemas híbridos". Actas del IEEE . 88 (7): 949– 970. Bibcode : 2000IEEEP..88..949T . CiteSeerX 10.1.1.129.8347 . doi : 10.1109/5.871303 . S2CID 1844682 .

[10] Koller, Daphne; Pfeffer, Avi (1997). "Representaciones y soluciones para problemas de teoría de juegos" (PDF) . Inteligencia Artificial . 94 ( 1–2 ): 167–215 . doi : 10.1016/S0004-3702(97)00023-4 .

[11] Michael, Michael Kearns; Littman, Michael L. (2001). "Modelos gráficos para la teoría de juegos". En UAI : 253–260 . CiteSeerX 10.1.1.22.5705 .

[12] Kearns, Michael; Littman, Michael L.; Singh, Satinder (7 de marzo de 2011). "Modelos gráficos para la teoría de juegos". arXiv : 1301.2281 [ cs.GT ].

[13] Leyton-Brown, Kevin; Tennenholtz, Moshe (2003). "Juegos de efectos locales" . IJCAI'03: Actas de la 18.ª Conferencia Internacional Conjunta sobre Inteligencia Artificial : 772–777 .

[14] Clempner, Julio (2006). "Modelado de juegos de caminos más cortos con redes de Petri: una teoría basada en Lyapunov" . Revista Internacional de Matemáticas Aplicadas y Ciencias de la Computación . 16 (3): 387– 397. ISSN 1641-876X .

[15] Sannikov, Yuliy (septiembre de 2007). "Juegos con acciones imperfectamente observables en tiempo continuo" (PDF) . Econometrica . 75 (5): 1285– 1329. doi : 10.1111/j.1468-0262.2007.00795.x .

[16] Tagiew, Rustam (diciembre de 2008). «Juegos de Petri multiagente». Conferencia Internacional de 2008 sobre Inteligencia Computacional para el Modelado, Control y Automatización . págs. 130–135 . doi : 10.1109/CIMCA.2008.15 . ISBN 978-0-7695-3514-2. S2CID 16679934 .

[17] Tagiew, Rustam (2009). «Sobre modelos de redes de Petri multiagente para el cálculo de juegos finitos extensos». Nuevos desafíos en inteligencia colectiva computacional . Estudios en inteligencia computacional. Vol. 244. Springer. pp. 243–254 . doi : 10.1007/978-3-642-03958-4_21 . ISBN 978-3-642-03957-7.

[18] Bhat, Navin; Leyton-Brown, Kevin (11 de julio de 2012). "Cálculo de equilibrios de Nash de juegos de grafos de acción". arXiv : 1207.4128 [ cs.GT ].

[GDL_Compiler-19] Kowalski, Jakub; Szykuła, Marek (2013). "Construcción de un compilador de lenguaje de descripción de juegos" . AI 2013: Avances en inteligencia artificial: 26.ª Conferencia Conjunta Australásica, Dunedin, Nueva Zelanda, 1-6 de diciembre de 2013. Actas . págs. 234–245 . Consultado el 1 de julio de 2019 .

[GDL-III-20] Jonge, Dave; Trescak, Tomás; Sierra, Carles; Simoff, Simeón; López de Mántaras, Ramón (2017). "Uso del lenguaje de descripción de juegos para la resolución mediada de disputas". IA y sociedad . 2017 (4). Springer: 767– 784. doi : 10.1007/s00146-017-0790-8 . S2CID 22738517 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 19 ]

[ 20 ]