# pyplAI
## Introducción
Esta biblioteca para *Python* es el resultado final de un Trabajo de Fin de Grado centrado en la implementación de algoritmos de *Monte Carlo Tree Search (MCTS)* y *minimax* para diferentes tipos de juegos de mesa, entre ellos, según clasifica la teoría de juegos, los juegos de información perfecta, como lo son el *ajedrez* o las *damas*, en los que en todo momento cualquier jugador puede ver toda la información del juego, como los posibles movimientos del rival, y juegos de información imperfecta, como lo son la mayoría de juegos de cartas como por ejemplo el *Uno* o la *brisca*, en el que los jugadores solo conocen información propia, como sus cartas, o información general del juego, como el estado de la mesa, pero desconocen la información del rival, como las cartas de los demás jugadores.
### Juegos de Información Perfecta
Para este tipo de juegos se han implementado los algoritmos de *MCTS con UCT* [[1]](#MCTS) y *minimax* con la técnica de *poda de alfa-beta* [[2]](#Minimax). Además, como ejemplos para ver el correcto uso de la biblioteca, se han creado diferentes juegos de mesa, entre ellos, el *Tic-Tac-Toe* (3 en raya), el *Ultimate Tic-Tac-Toe* [[3]](#UltimateTicTacToe) y las *damas*.
### Juegos de Información Imperfecta
Para este segundo tipo de juegos se han implementado dos algoritmos, el *Single Observer Information Set Monte Carlo Tree Search (SO-ISMCTS)* [[4]](#ISMCTS) y el *Multiple Observer Information Set Monte Carlo Tree Search (MO-ISMCTS)* [[4]](#ISMCTS). El primero de estos algoritmos genera un único árbol desde el punto de vista del jugador al que le toca jugar. Por otro lado, el segundo algoritmo crea un árbol para cada uno de los jugadores y agrupa las acciones que son indiferenciables desde el punto de vista de este jugador, es decir, si un jugador puede realizar varios movimientos que no aportarían información a los rivales, agrupa estos movimientos como si fuesen uno solo, creando un único nodo en el árbol de los jugadores rivales.
Un ejemplo serían los juegos en los que un jugador intercambia una de las cartas de su mano con cualquier carta de la baraja, cuando el jugador efectúa este intercambio los demás jugadores no reciben ningún tipo de información sobre el intercambio de cartas, por lo que su conocimiento sobre el estado del juego no cambia.
Para estos algoritmos también se han desarrollado varios juegos como ejemplos de uso de la biblioteca, aunque ambos algoritmos se pueden usar en todos los juegos de información imperfecta, se ha diferenciado entre juegos para el *SO-ISMCTS* y el *MO-ISMCTS*. Para el primer algoritmo se ha creado el juego de la *escoba*, el *Stratego* y el *blackJack*, y para el segundo se ha desarrollado el *holjjak* (juego de adivinar las canicas del rival) y el *phantom* (variante del 4 en raya en el que no se ven los movimientos del rival).
## Manual de Uso
El primer paso necesario para poder usar esta biblioteca es descargarla. Se puede descargar la biblioteca desde la consola usando el comando:
``` python
pip install pyplAI
```
Tras esto, ya se puede importar en el archivo de *Python* del juego al que queramos implementarla.
``` python
import pyplAI
```
### Clase sobre el Estado del Juego
Para poder usar esta biblioteca es imprescindible que haya una clase que guarde la información necesaria sobre el estado del juego. Aunque se puede dar a esta clase el nombre que se desee, en este manual se utilizará una clase llamada *Juego* a modo de ejemplo.
``` python
class Juego:
.
.
.
```
### Atributo Obligatorio *jugadorActual*
Debido a que los algoritmos necesitan saber cuál es el jugador al cual le toca jugar en cada uno de los turnos, es obligatorio añadir un atributo *jugadorActual* en la clase del juego. Además, es muy importante que este atributo tenga este mismo nombre.
``` python
class Juego:
def __init__(self):
self.jugadorActual = 1
.
.
.
```
Este atributo debe contener un valor numérico que representa el índice del jugador al que le toca jugar (empezando por 1). También, debe ir actualizándose conforme se avanza en el juego, por ejemplo, en el *3 en raya*, este atributo se debe iniciar con el valor 1, pero cuando el primer jugador realice su movimiento, se actualiza al valor 2, indicando que el segundo jugador es el que debe realizar su jugada.
Además del atributo para identificar el jugador actual del estado del juego, esta clase deberá implementar ciertos métodos para poder interactuar y obtener información sobre el estado del juego. Algunos métodos son comunes para todos los algoritmos, mientras que otros algoritmos requieren de métodos específicos. Cabe destacar que estos métodos pueden ser nombrados de forma distinta a como se mostrará a continuación, pero es totalmente necesario que reciban los parámetros de entrada y devuelvan la salida tal y como se especifica en este manual.
### Métodos Generales
Los siguientes 4 métodos serán obligatorios para todos los algoritmos que se implementan en esta biblioteca:
**• obtiene_movimientos(self):** Devolverá una lista con todos los movimientos posibles del jugador actual del estado del juego, es recomendable devolver estos movimientos en un orden aleatorio.
``` python
class Juego:
.
.
.
def obtiene_movimientos(self):
.
.
.
return movimientos
```
**• aplica_movimiento(self, movimiento):** Aplicará el movimiento dado al estado del juego y devolverá el estado resultante (*self*).
``` python
class Juego:
.
.
.
def aplica_movimiento(self, movimiento):
.
.
.
return self
```
**• es_estado_final(self):** Comprueba el estado actual del juego, devolviendo *True* o *False* dependiendo de si es un estado final o no.
``` python
class Juego:
.
.
.
def es_estado_final(self):
.
.
.
return True
o
return False
```
**• gana_jugador(self, jugador):** Comprueba si el jugador dado gana el juego en el estado actual de este, devolviendo *True* en caso de que sea ganador, o *False* en caso contrario. La variable *jugador* debe ser un número entero positivo, y se debe situar en el rango de 1, para el primer jugador del juego, hasta *n*, siendo *n* el número total de jugadores.
``` python
class Juego:
.
.
.
def gana_jugador(self, jugador):
.
.
.
return True
o
return False
```
### Métodos SO/MO-ISMCTS
Además de los 4 métodos anteriores, los algoritmos de *SO-ISMCTS* y *MO-ISMCTS* necesitan un método adicional para su uso, el cuál se explica a continuación:
**• determinación(self):** Devuelve una determinación aleatoria del estado del juego, desde el punto de vista del jugador actual.
``` python
class Juego:
.
.
.
def determinacion(self):
.
.
.
return determinacion
```
Por ejemplo, para un juego de cartas en el que cada jugador tiene una mano, hay una mesa con cartas visibles, una pila de descartes y un mazo de robo inicial, el jugador actual no tiene conocimiento sobre las cartas del rival ni las cartas del mazo de robo, pero si sabe cuáles son sus cartas, las de la mesa y las que han sido mandadas a la pila de descartes, por lo que tiene la información sobre cuáles son las cartas restantes, pero aún no sabe donde se encuentran.
Con esta información, este método debe dar un estado del juego en el que aleatoriamente se distribuyan las cartas que el jugador no tiene localizadas entre las zonas en las que no sabe que cartas hay, en este caso, las zonas serían las manos de los rivales y el mazo de robo.
### Métodos MO-ISMCTS
Además, para el funcionamiento del algoritmo *MO-ISMCTS* se necesitará otro método adicional:
**• es_movimiento_visible(movimiento):** Este método, dado un movimiento, devuelve *True* si es un movimiento visible para los rivales, o *False* en caso contrario.
``` python
class Juego:
.
.
.
def es_movimiento_visible(movimiento):
.
.
.
return True
o
return False
```
Por ejemplo, un movimiento visible para los rivales sería jugar una carta de tu mano sobre la mesa, por lo que, haría saber a los rivales el lugar exacto de esa carta, cosa que antes no sabían. Sin embargo, un movimiento no visible sería intercambiar una carta de tu mano con el mazo de robo sin revelar ninguna de las dos. Esta acción no mostraría nueva información a ningún rival, ya que no se muestran las cartas y los rivales seguirán sin saber que cartas hay en tu mano ni que cartas hay en el mazo.
### Métodos Minimax
En el caso del algoritmo de *minimax*, además de los 4 métodos generales, se necesita un método que devuelva una heurística sobre el estado del juego, es decir, que evalúe su estado para saber como de bueno es desde el punto de vista de un jugador dado:
**• heuristica(self, jugador):** Este método debe devolver un número entero que refleje una evaluación sobre como de bueno es el estado del juego para un jugador dado. Esta evaluación debe ser mayor cuanto mejor sea el estado del juego para este jugador.
``` python
class Juego:
.
.
.
def heuristica(self, jugador):
.
.
.
return evaluacion
```
Por ejemplo, para el juego de las *damas* una posible heurística sería contar el número de fichas del jugador y restarle el número de fichas del rival. Hay multitud de posibles heurísticas para cada uno de los juegos, y se debe tener un conocimiento sobre el juego para poder crear una buena heurística, ya que la heurística tendrá un gran peso a la hora de decidir cuál es el mejor movimiento.
Al igual que en el método *gana_jugador*, el argumento *jugador* debe ser un número entero positivo, desde el 1, para el primer jugador, hasta *n*, para el último jugador, siendo *n* el número total de jugadores.
### Constructor Algoritmo
Una vez tengamos todos estos métodos solamente debemos llamar a la biblioteca y al constructor del algoritmo que se desee utilizar. A esta llamada le pasaremos como argumentos los métodos necesarios para el uso de este algoritmo junto con algunas otras variables que detallaremos a continuación:
**• numeroJugadores:** Este argumento es obligatorio para todos los algoritmos, representará el número de jugadores que contiene el juego, siendo este un número entero mayor que cero.
**• tiempoEjecucion:** Este argumento es común para todos los algoritmos de Monte Carlo, ya que, estos algoritmos necesitan un tiempo límite de ejecución antes de devolver el mejor movimiento encontrado. Este argumento debe ser un número real mayor que cero y representa el tiempo de ejecución en segundos.
**• profundidadBusqueda:** Este argumento solo es necesario en la llamada al constructor del algoritmo de *minimax*, y sirve para limitar la profundidad en el árbol de búsqueda. Este argumento debe ser un número entero mayor que cero.
Sabiendo todo esto ya podemos ver como se deben hacer las llamadas a la biblioteca y los constructores para cada uno de los tipos de algoritmos. Es muy importante que se siga el orden mostrado en los argumentos de entrada. Además, recordar que *Juego* es la clase de ejemplo que contiene la información sobre el estado del juego, como el atributo *jugadorActual*, y los métodos explicados anteriormente.
**• MCTS:**
``` python
mcts = pyplAI.MCTS(
Juego.aplica_movimiento,
Juego.obtiene_movimientos,
Juego.es_estado_final,
Juego.gana_jugador,
numeroJugadores,
tiempoEjecucion)
```
**• Minimax:**
``` python
minimax = pyplAI.Minimax(
Juego.aplica_movimiento,
Juego.obtiene_movimientos,
Juego.es_estado_final,
Juego.gana_jugador,
Juego.heuristica,
numeroJugadores,
profundidadBusqueda)
```
**• SO-ISMCTS:**
``` python
so_ismcts = pyplAI.SOISMCTS(
Juego.aplica_movimiento,
Juego.obtiene_movimientos,
Juego.es_estado_final,
Juego.gana_jugador,
Juego.determinacion,
numeroJugadores,
tiempoEjecucion)
```
**• MO-ISMCTS:**
``` python
mo_ismcts = pyplAI.MOISMCTS(
Juego.aplica_movimiento,
Juego.obtiene_movimientos,
Juego.es_estado_final,
Juego.gana_jugador,
Juego.determinacion,
Juego.es_movimiento_visible,
numeroJugadores,
tiempoEjecucion)
```
**• Modo *verbose*:**
Si queremos ver algunos detalles cuando ejecutemos el algoritmo, se debe añadir un *True* como último argumento en la llamada al constructor. Este modo mostrará información útil del algoritmo por consola, como por ejemplo, tiempo de ejecución, número de nodos creados y visitados y demás características propias de cada uno de los algoritmos. Un ejemplo de como quedaría la creación del algoritmo de *MCTS* con este argumento extra sería el siguiente:
``` python
mcts = pyplAI.MCTS(
Juego.aplica_movimiento,
Juego.obtiene_movimientos,
Juego.es_estado_final,
Juego.gana_jugador,
numeroJugadores,
tiempoEjecucion,
True)
```
### Ejecución Algoritmo
Una vez tengamos el objeto del algoritmo que se quiere utilizar solamente se debe llamar a su método *ejecuta* y pasarle como argumento el objeto que contiene el estado actual del juego, esto devolverá el mejor movimiento encontrado durante el tiempo de computación dado, para los algoritmos de *Monte Carlo*, o la profundidad de búsqueda, en el caso del algoritmo *minimax*. A continuación, se mostrará el código de ejemplo en el que se usa el algoritmo de *MCTS* para obtener un movimiento y seguidamente aplicarlo al juego, obteniendo así un nuevo estado del juego:
``` python
def main():
juego = Juego()
movimiento = mcts.ejecuta(juego)
juego = aplica_movimiento(movimiento)
```
En caso de que el estado del juego no tenga ningún movimiento posible para aplicar los algoritmos devolverán *None*, y si solo hay un posible movimiento para aplicar, para ahorrar cálculos innecesarios, se devolverá el único movimiento posible.
Si se tienen dudas sobre como integrar la biblioteca a juegos propios se recomienda ver los juegos del repositorio de *GitHub* ([*pyplAI*](https://github.com/plss12/pyplAI)) como ejemplos de uso. Este repositorio contiene la biblioteca y todos los juegos nombrados en la introducción de este manual, incluyendo las implementaciones de los algoritmos correspondientes con cada uno de ellos.
## Contacto
En caso de tener alguna duda, idea o aportación sobre la biblioteca por favor contactar al siguiente correo: [pepoluis712@gmail.com](mailto:pepoluis712@gmail.com)
## Referencias
<a id="MCTS"></a>
[1] Cameron B. Browne, Edward Powley, Daniel Whitehouse, Simon M. Lucas, Peter I.Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samoth-rakis, and Simon Colton. A survey of monte carlo tree search methods. IEEETransactions on Computational Intelligence and AI in Games, 4(1):1–43, 2012. doi:10.1109/TCIAIG.2012.2186810. URL https://ieeexplore.ieee.org/document/6145622.
<a id="Minimax"></a>
[2] Patricio Mendoza. Alpha-beta pruning algorithm: The intelligence behind strategygames. page 9, 2022. URL https://www.researchgate.net/publication/360872512.
<a id="UltimateTicTacToe"></a>
[3] Eytan Lifshitz and David Tsurel. Ai approaches to ultimate tic-tac-toe. page 5, 2013. URL https://www.cs.huji.ac.il/w~ai/projects/2013/UlitmateTic-Tac-Toe/files/report.pdf.
<a id="ISMCTS"></a>
[4] Peter I. Cowling, Edward J. Powley, and Daniel Whitehouse. Information setmonte carlo tree search. IEEE Transactions on Computational Intelligence and AIin Games, 4(2):120–143, 2012. doi: 10.1109/TCIAIG.2012.2200894. URL https://ieeexplore.ieee.org/document/6203567.
Raw data
{
"_id": null,
"home_page": "https://github.com/plss12/pyplAI",
"name": "pyplAI",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "python,articial intelligence,AI,games,board games,minimax,alpha-beta,monte carlo,monte carlo tree search,UCT,game theory,information set,perfect information,imperfect information",
"author": "Pedro Luis Soto Santos",
"author_email": "pepoluis712@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/15/19/e419d88f0c41580dfcfac4eb9765d784af2e5f27760754772111e711e8ab/pyplAI-1.0.3.tar.gz",
"platform": null,
"description": "# pyplAI\r\n\r\n## Introducci\u00f3n\r\nEsta biblioteca para *Python* es el resultado final de un Trabajo de Fin de Grado centrado en la implementaci\u00f3n de algoritmos de *Monte Carlo Tree Search (MCTS)* y *minimax* para diferentes tipos de juegos de mesa, entre ellos, seg\u00fan clasifica la teor\u00eda de juegos, los juegos de informaci\u00f3n perfecta, como lo son el *ajedrez* o las *damas*, en los que en todo momento cualquier jugador puede ver toda la informaci\u00f3n del juego, como los posibles movimientos del rival, y juegos de informaci\u00f3n imperfecta, como lo son la mayor\u00eda de juegos de cartas como por ejemplo el *Uno* o la *brisca*, en el que los jugadores solo conocen informaci\u00f3n propia, como sus cartas, o informaci\u00f3n general del juego, como el estado de la mesa, pero desconocen la informaci\u00f3n del rival, como las cartas de los dem\u00e1s jugadores.\r\n\r\n### Juegos de Informaci\u00f3n Perfecta\r\n\r\nPara este tipo de juegos se han implementado los algoritmos de *MCTS con UCT* [[1]](#MCTS) y *minimax* con la t\u00e9cnica de *poda de alfa-beta* [[2]](#Minimax). Adem\u00e1s, como ejemplos para ver el correcto uso de la biblioteca, se han creado diferentes juegos de mesa, entre ellos, el *Tic-Tac-Toe* (3 en raya), el *Ultimate Tic-Tac-Toe* [[3]](#UltimateTicTacToe) y las *damas*.\r\n\r\n### Juegos de Informaci\u00f3n Imperfecta\r\n\r\nPara este segundo tipo de juegos se han implementado dos algoritmos, el *Single Observer Information Set Monte Carlo Tree Search (SO-ISMCTS)* [[4]](#ISMCTS) y el *Multiple Observer Information Set Monte Carlo Tree Search (MO-ISMCTS)* [[4]](#ISMCTS). El primero de estos algoritmos genera un \u00fanico \u00e1rbol desde el punto de vista del jugador al que le toca jugar. Por otro lado, el segundo algoritmo crea un \u00e1rbol para cada uno de los jugadores y agrupa las acciones que son indiferenciables desde el punto de vista de este jugador, es decir, si un jugador puede realizar varios movimientos que no aportar\u00edan informaci\u00f3n a los rivales, agrupa estos movimientos como si fuesen uno solo, creando un \u00fanico nodo en el \u00e1rbol de los jugadores rivales.\r\n\r\nUn ejemplo ser\u00edan los juegos en los que un jugador intercambia una de las cartas de su mano con cualquier carta de la baraja, cuando el jugador efect\u00faa este intercambio los dem\u00e1s jugadores no reciben ning\u00fan tipo de informaci\u00f3n sobre el intercambio de cartas, por lo que su conocimiento sobre el estado del juego no cambia. \r\n\r\nPara estos algoritmos tambi\u00e9n se han desarrollado varios juegos como ejemplos de uso de la biblioteca, aunque ambos algoritmos se pueden usar en todos los juegos de informaci\u00f3n imperfecta, se ha diferenciado entre juegos para el *SO-ISMCTS* y el *MO-ISMCTS*. Para el primer algoritmo se ha creado el juego de la *escoba*, el *Stratego* y el *blackJack*, y para el segundo se ha desarrollado el *holjjak* (juego de adivinar las canicas del rival) y el *phantom* (variante del 4 en raya en el que no se ven los movimientos del rival).\r\n\r\n## Manual de Uso\r\nEl primer paso necesario para poder usar esta biblioteca es descargarla. Se puede descargar la biblioteca desde la consola usando el comando: \r\n\r\n``` python\r\npip install pyplAI\r\n```\r\n\r\nTras esto, ya se puede importar en el archivo de *Python* del juego al que queramos implementarla.\r\n\r\n``` python\r\nimport pyplAI\r\n```\r\n\r\n### Clase sobre el Estado del Juego\r\nPara poder usar esta biblioteca es imprescindible que haya una clase que guarde la informaci\u00f3n necesaria sobre el estado del juego. Aunque se puede dar a esta clase el nombre que se desee, en este manual se utilizar\u00e1 una clase llamada *Juego* a modo de ejemplo.\r\n\r\n``` python\r\n class Juego:\r\n .\r\n .\r\n .\r\n```\r\n\r\n### Atributo Obligatorio *jugadorActual*\r\nDebido a que los algoritmos necesitan saber cu\u00e1l es el jugador al cual le toca jugar en cada uno de los turnos, es obligatorio a\u00f1adir un atributo *jugadorActual* en la clase del juego. Adem\u00e1s, es muy importante que este atributo tenga este mismo nombre.\r\n\r\n``` python\r\n class Juego:\r\n def __init__(self):\r\n self.jugadorActual = 1\r\n .\r\n .\r\n .\r\n```\r\n\r\nEste atributo debe contener un valor num\u00e9rico que representa el \u00edndice del jugador al que le toca jugar (empezando por 1). Tambi\u00e9n, debe ir actualiz\u00e1ndose conforme se avanza en el juego, por ejemplo, en el *3 en raya*, este atributo se debe iniciar con el valor 1, pero cuando el primer jugador realice su movimiento, se actualiza al valor 2, indicando que el segundo jugador es el que debe realizar su jugada.\r\n\r\nAdem\u00e1s del atributo para identificar el jugador actual del estado del juego, esta clase deber\u00e1 implementar ciertos m\u00e9todos para poder interactuar y obtener informaci\u00f3n sobre el estado del juego. Algunos m\u00e9todos son comunes para todos los algoritmos, mientras que otros algoritmos requieren de m\u00e9todos espec\u00edficos. Cabe destacar que estos m\u00e9todos pueden ser nombrados de forma distinta a como se mostrar\u00e1 a continuaci\u00f3n, pero es totalmente necesario que reciban los par\u00e1metros de entrada y devuelvan la salida tal y como se especifica en este manual.\r\n\r\n### M\u00e9todos Generales\r\n\r\nLos siguientes 4 m\u00e9todos ser\u00e1n obligatorios para todos los algoritmos que se implementan en esta biblioteca:\r\n\r\n**\u2022\tobtiene_movimientos(self):** Devolver\u00e1 una lista con todos los movimientos posibles del jugador actual del estado del juego, es recomendable devolver estos movimientos en un orden aleatorio.\r\n\r\n``` python\r\n class Juego:\r\n .\r\n .\r\n .\r\n def obtiene_movimientos(self):\r\n .\r\n .\r\n .\r\n return movimientos\r\n```\r\n\r\n**\u2022\taplica_movimiento(self, movimiento):** Aplicar\u00e1 el movimiento dado al estado del juego y devolver\u00e1 el estado resultante (*self*).\r\n\r\n``` python\r\n class Juego:\r\n .\r\n .\r\n .\r\n def aplica_movimiento(self, movimiento):\r\n .\r\n .\r\n .\r\n return self\r\n```\r\n\r\n**\u2022\tes_estado_final(self):** Comprueba el estado actual del juego, devolviendo *True* o *False* dependiendo de si es un estado final o no.\r\n\r\n``` python\r\n class Juego:\r\n .\r\n .\r\n .\r\n def es_estado_final(self):\r\n .\r\n .\r\n .\r\n return True\r\n o\r\n return False\r\n```\r\n\r\n**\u2022\tgana_jugador(self, jugador):** Comprueba si el jugador dado gana el juego en el estado actual de este, devolviendo *True* en caso de que sea ganador, o *False* en caso contrario. La variable *jugador* debe ser un n\u00famero entero positivo, y se debe situar en el rango de 1, para el primer jugador del juego, hasta *n*, siendo *n* el n\u00famero total de jugadores.\r\n\r\n``` python\r\n class Juego:\r\n .\r\n .\r\n .\r\n def gana_jugador(self, jugador):\r\n .\r\n .\r\n .\r\n return True\r\n o\r\n return False\r\n```\r\n\r\n### M\u00e9todos SO/MO-ISMCTS\r\n\r\nAdem\u00e1s de los 4 m\u00e9todos anteriores, los algoritmos de *SO-ISMCTS* y *MO-ISMCTS* necesitan un m\u00e9todo adicional para su uso, el cu\u00e1l se explica a continuaci\u00f3n:\r\n\r\n**\u2022\tdeterminaci\u00f3n(self):** Devuelve una determinaci\u00f3n aleatoria del estado del juego, desde el punto de vista del jugador actual.\r\n\r\n``` python\r\n class Juego:\r\n .\r\n .\r\n .\r\n def determinacion(self):\r\n .\r\n .\r\n .\r\n return determinacion\r\n```\r\n\r\nPor ejemplo, para un juego de cartas en el que cada jugador tiene una mano, hay una mesa con cartas visibles, una pila de descartes y un mazo de robo inicial, el jugador actual no tiene conocimiento sobre las cartas del rival ni las cartas del mazo de robo, pero si sabe cu\u00e1les son sus cartas, las de la mesa y las que han sido mandadas a la pila de descartes, por lo que tiene la informaci\u00f3n sobre cu\u00e1les son las cartas restantes, pero a\u00fan no sabe donde se encuentran. \r\n\r\nCon esta informaci\u00f3n, este m\u00e9todo debe dar un estado del juego en el que aleatoriamente se distribuyan las cartas que el jugador no tiene localizadas entre las zonas en las que no sabe que cartas hay, en este caso, las zonas ser\u00edan las manos de los rivales y el mazo de robo.\r\n\r\n### M\u00e9todos MO-ISMCTS\r\n\r\nAdem\u00e1s, para el funcionamiento del algoritmo *MO-ISMCTS* se necesitar\u00e1 otro m\u00e9todo adicional:\r\n\r\n**\u2022\tes_movimiento_visible(movimiento):** Este m\u00e9todo, dado un movimiento, devuelve *True* si es un movimiento visible para los rivales, o *False* en caso contrario.\r\n\r\n``` python\r\n class Juego:\r\n .\r\n .\r\n .\r\n def es_movimiento_visible(movimiento):\r\n .\r\n .\r\n .\r\n return True\r\n o\r\n return False\r\n```\r\n\r\nPor ejemplo, un movimiento visible para los rivales ser\u00eda jugar una carta de tu mano sobre la mesa, por lo que, har\u00eda saber a los rivales el lugar exacto de esa carta, cosa que antes no sab\u00edan. Sin embargo, un movimiento no visible ser\u00eda intercambiar una carta de tu mano con el mazo de robo sin revelar ninguna de las dos. Esta acci\u00f3n no mostrar\u00eda nueva informaci\u00f3n a ning\u00fan rival, ya que no se muestran las cartas y los rivales seguir\u00e1n sin saber que cartas hay en tu mano ni que cartas hay en el mazo.\r\n\r\n### M\u00e9todos Minimax\r\n\r\nEn el caso del algoritmo de *minimax*, adem\u00e1s de los 4 m\u00e9todos generales, se necesita un m\u00e9todo que devuelva una heur\u00edstica sobre el estado del juego, es decir, que eval\u00fae su estado para saber como de bueno es desde el punto de vista de un jugador dado:\r\n\r\n**\u2022\theuristica(self, jugador):** Este m\u00e9todo debe devolver un n\u00famero entero que refleje una evaluaci\u00f3n sobre como de bueno es el estado del juego para un jugador dado. Esta evaluaci\u00f3n debe ser mayor cuanto mejor sea el estado del juego para este jugador.\r\n\r\n``` python\r\n class Juego:\r\n .\r\n .\r\n .\r\n def heuristica(self, jugador):\r\n .\r\n .\r\n .\r\n return evaluacion\r\n```\r\n\r\nPor ejemplo, para el juego de las *damas* una posible heur\u00edstica ser\u00eda contar el n\u00famero de fichas del jugador y restarle el n\u00famero de fichas del rival. Hay multitud de posibles heur\u00edsticas para cada uno de los juegos, y se debe tener un conocimiento sobre el juego para poder crear una buena heur\u00edstica, ya que la heur\u00edstica tendr\u00e1 un gran peso a la hora de decidir cu\u00e1l es el mejor movimiento.\r\n\r\nAl igual que en el m\u00e9todo *gana_jugador*, el argumento *jugador* debe ser un n\u00famero entero positivo, desde el 1, para el primer jugador, hasta *n*, para el \u00faltimo jugador, siendo *n* el n\u00famero total de jugadores.\r\n\r\n### Constructor Algoritmo\r\n\r\nUna vez tengamos todos estos m\u00e9todos solamente debemos llamar a la biblioteca y al constructor del algoritmo que se desee utilizar. A esta llamada le pasaremos como argumentos los m\u00e9todos necesarios para el uso de este algoritmo junto con algunas otras variables que detallaremos a continuaci\u00f3n:\r\n\r\n**\u2022\tnumeroJugadores:** Este argumento es obligatorio para todos los algoritmos, representar\u00e1 el n\u00famero de jugadores que contiene el juego, siendo este un n\u00famero entero mayor que cero.\r\n\r\n**\u2022\ttiempoEjecucion:** Este argumento es com\u00fan para todos los algoritmos de Monte Carlo, ya que, estos algoritmos necesitan un tiempo l\u00edmite de ejecuci\u00f3n antes de devolver el mejor movimiento encontrado. Este argumento debe ser un n\u00famero real mayor que cero y representa el tiempo de ejecuci\u00f3n en segundos.\r\n\r\n**\u2022\tprofundidadBusqueda:** Este argumento solo es necesario en la llamada al constructor del algoritmo de *minimax*, y sirve para limitar la profundidad en el \u00e1rbol de b\u00fasqueda. Este argumento debe ser un n\u00famero entero mayor que cero.\r\n\r\nSabiendo todo esto ya podemos ver como se deben hacer las llamadas a la biblioteca y los constructores para cada uno de los tipos de algoritmos. Es muy importante que se siga el orden mostrado en los argumentos de entrada. Adem\u00e1s, recordar que *Juego* es la clase de ejemplo que contiene la informaci\u00f3n sobre el estado del juego, como el atributo *jugadorActual*, y los m\u00e9todos explicados anteriormente.\r\n\r\n**\u2022\tMCTS:**\r\n\r\n``` python\r\n mcts = pyplAI.MCTS(\r\n Juego.aplica_movimiento,\r\n Juego.obtiene_movimientos, \r\n Juego.es_estado_final, \r\n Juego.gana_jugador, \r\n numeroJugadores, \r\n tiempoEjecucion)\r\n```\r\n\r\n**\u2022\tMinimax:**\r\n\r\n``` python\r\n minimax = pyplAI.Minimax(\r\n Juego.aplica_movimiento,\r\n Juego.obtiene_movimientos, \r\n Juego.es_estado_final, \r\n Juego.gana_jugador, \r\n Juego.heuristica,\r\n numeroJugadores, \r\n profundidadBusqueda)\r\n```\r\n\r\n**\u2022\tSO-ISMCTS:**\r\n\r\n``` python\r\n so_ismcts = pyplAI.SOISMCTS(\r\n Juego.aplica_movimiento,\r\n Juego.obtiene_movimientos, \r\n Juego.es_estado_final, \r\n Juego.gana_jugador, \r\n Juego.determinacion,\r\n numeroJugadores, \r\n tiempoEjecucion)\r\n```\r\n\r\n**\u2022\tMO-ISMCTS:**\r\n\r\n``` python\r\n mo_ismcts = pyplAI.MOISMCTS(\r\n Juego.aplica_movimiento,\r\n Juego.obtiene_movimientos, \r\n Juego.es_estado_final, \r\n Juego.gana_jugador, \r\n Juego.determinacion,\r\n Juego.es_movimiento_visible,\r\n numeroJugadores, \r\n tiempoEjecucion)\r\n```\r\n\r\n**\u2022\tModo *verbose*:**\r\n\r\nSi queremos ver algunos detalles cuando ejecutemos el algoritmo, se debe a\u00f1adir un *True* como \u00faltimo argumento en la llamada al constructor. Este modo mostrar\u00e1 informaci\u00f3n \u00fatil del algoritmo por consola, como por ejemplo, tiempo de ejecuci\u00f3n, n\u00famero de nodos creados y visitados y dem\u00e1s caracter\u00edsticas propias de cada uno de los algoritmos. Un ejemplo de como quedar\u00eda la creaci\u00f3n del algoritmo de *MCTS* con este argumento extra ser\u00eda el siguiente:\r\n\r\n``` python\r\n mcts = pyplAI.MCTS(\r\n Juego.aplica_movimiento,\r\n Juego.obtiene_movimientos, \r\n Juego.es_estado_final, \r\n Juego.gana_jugador, \r\n numeroJugadores, \r\n tiempoEjecucion,\r\n True)\r\n```\r\n\r\n### Ejecuci\u00f3n Algoritmo\r\n\r\nUna vez tengamos el objeto del algoritmo que se quiere utilizar solamente se debe llamar a su m\u00e9todo *ejecuta* y pasarle como argumento el objeto que contiene el estado actual del juego, esto devolver\u00e1 el mejor movimiento encontrado durante el tiempo de computaci\u00f3n dado, para los algoritmos de *Monte Carlo*, o la profundidad de b\u00fasqueda, en el caso del algoritmo *minimax*. A continuaci\u00f3n, se mostrar\u00e1 el c\u00f3digo de ejemplo en el que se usa el algoritmo de *MCTS* para obtener un movimiento y seguidamente aplicarlo al juego, obteniendo as\u00ed un nuevo estado del juego:\r\n\r\n``` python\r\n def main():\r\n juego = Juego()\r\n movimiento = mcts.ejecuta(juego)\r\n juego = aplica_movimiento(movimiento)\r\n```\r\n\r\n\r\nEn caso de que el estado del juego no tenga ning\u00fan movimiento posible para aplicar los algoritmos devolver\u00e1n *None*, y si solo hay un posible movimiento para aplicar, para ahorrar c\u00e1lculos innecesarios, se devolver\u00e1 el \u00fanico movimiento posible.\r\n\r\nSi se tienen dudas sobre como integrar la biblioteca a juegos propios se recomienda ver los juegos del repositorio de *GitHub* ([*pyplAI*](https://github.com/plss12/pyplAI)) como ejemplos de uso. Este repositorio contiene la biblioteca y todos los juegos nombrados en la introducci\u00f3n de este manual, incluyendo las implementaciones de los algoritmos correspondientes con cada uno de ellos.\r\n\r\n## Contacto\r\n\r\nEn caso de tener alguna duda, idea o aportaci\u00f3n sobre la biblioteca por favor contactar al siguiente correo: [pepoluis712@gmail.com](mailto:pepoluis712@gmail.com)\r\n\r\n## Referencias\r\n\r\n<a id=\"MCTS\"></a>\r\n[1] Cameron B. Browne, Edward Powley, Daniel Whitehouse, Simon M. Lucas, Peter I.Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samoth-rakis, and Simon Colton. A survey of monte carlo tree search methods. IEEETransactions on Computational Intelligence and AI in Games, 4(1):1\u201343, 2012. doi:10.1109/TCIAIG.2012.2186810. URL https://ieeexplore.ieee.org/document/6145622.\r\n\r\n<a id=\"Minimax\"></a>\r\n[2] Patricio Mendoza. Alpha-beta pruning algorithm: The intelligence behind strategygames. page 9, 2022. URL https://www.researchgate.net/publication/360872512.\r\n\r\n<a id=\"UltimateTicTacToe\"></a>\r\n[3] Eytan Lifshitz and David Tsurel. Ai approaches to ultimate tic-tac-toe. page 5, 2013. URL https://www.cs.huji.ac.il/w~ai/projects/2013/UlitmateTic-Tac-Toe/files/report.pdf.\r\n\r\n<a id=\"ISMCTS\"></a>\r\n[4] Peter I. Cowling, Edward J. Powley, and Daniel Whitehouse. Information setmonte carlo tree search. IEEE Transactions on Computational Intelligence and AIin Games, 4(2):120\u2013143, 2012. doi: 10.1109/TCIAIG.2012.2200894. URL https://ieeexplore.ieee.org/document/6203567.\r\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Biblioteca para Python con algoritmos de resoluci\u00f3n de juegos de mesa (minimax, MCTS, SO-ISMCTS y MO-ISMCTS)",
"version": "1.0.3",
"project_urls": {
"Homepage": "https://github.com/plss12/pyplAI"
},
"split_keywords": [
"python",
"articial intelligence",
"ai",
"games",
"board games",
"minimax",
"alpha-beta",
"monte carlo",
"monte carlo tree search",
"uct",
"game theory",
"information set",
"perfect information",
"imperfect information"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "957b4c9d1611c05e377f31229e935f02e6f1baa275a0e2e0a7fc019467cdbb3b",
"md5": "a1850bbec4f7999357cbb648cfce8016",
"sha256": "fe6a7ae4fbe8ae0326aab1e2d120ff171e9e5608cc8e7023e9aec72ddf9610db"
},
"downloads": -1,
"filename": "pyplAI-1.0.3-py3-none-any.whl",
"has_sig": false,
"md5_digest": "a1850bbec4f7999357cbb648cfce8016",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 12048,
"upload_time": "2023-05-27T11:20:06",
"upload_time_iso_8601": "2023-05-27T11:20:06.280104Z",
"url": "https://files.pythonhosted.org/packages/95/7b/4c9d1611c05e377f31229e935f02e6f1baa275a0e2e0a7fc019467cdbb3b/pyplAI-1.0.3-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "1519e419d88f0c41580dfcfac4eb9765d784af2e5f27760754772111e711e8ab",
"md5": "a7a0efe3f928f859a088e4e32eb8c802",
"sha256": "ed3b5f69f10efc11e8f3230f481f9f132f59c6697c849fd735f8164ad12213f5"
},
"downloads": -1,
"filename": "pyplAI-1.0.3.tar.gz",
"has_sig": false,
"md5_digest": "a7a0efe3f928f859a088e4e32eb8c802",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 17615,
"upload_time": "2023-05-27T11:20:10",
"upload_time_iso_8601": "2023-05-27T11:20:10.075387Z",
"url": "https://files.pythonhosted.org/packages/15/19/e419d88f0c41580dfcfac4eb9765d784af2e5f27760754772111e711e8ab/pyplAI-1.0.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-05-27 11:20:10",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "plss12",
"github_project": "pyplAI",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "pyplai"
}
JSON
