Complejidad Algorítmica

Integrantes

• Elvia Artega - u201616507

• Diego Pereira - u201723546

• Diego Livia - u201612753

1. Introducción

Mucho se ha dicho respecto al alcance de los juegos virtuales en pleno siglo XXI. Desde William Higinbotham con su impresionante aporte a la industria de los juegos hasta Ralph Baer con sus experiencias y premios. Es por ello que nuestro entendimiento en este campo ha variado tanto, pues con el pasar del tiempo ha ido mejorando cada aspecto, desde la calidad de las imágenes hasta las estrategias que puede utilizar un humano para ganarle a una máquina en sentidos tan impredecibles que a nadie sorprenderá. Es así que, el presente trabajo de investigación está orientado al estudio de la lógica del juego llamado Quoridor desde un enfoque descriptivo y explicativo donde ejemplificamos de manera objetiva y puntual en que dichas especulaciones operan, sobre todo a la hora de validar conocimientos, actitudes y estrategias y así relacionarlas con nuestra vida diaria.

El Quoridor es un juego abstracto de estrategia en el que pueden participar de dos a más jugadores. Se utiliza un tablero similar el ajedrez, en la que cada jugador tendrá que llevar su ficha respectiva al otro extremo del tablero. El oponente podrá hacer uso de bloques de madera para obstruir el paso, de esta manera obliga a los demás jugadores a desviarse y retrasar así su llegada. La única restricción es no poder encerrar a la ficha riva con el uso de estos bloques. Gana el jugador que lleve su ficha al otro extremo del tablero.

Al terminar la investigación, se realizará la codificación y exportación en un ejecutable del juego "Quoridor" utilizando el lenguaje de programación Python. Además de utilizar las técnicas o métodos aprendidos en el curso de "Complejidad Algorítmica"

2. Estado del arte

En el presente apartado se hace una revisión exhaustiva de investigaciones que plantean algoritmos capaces de poder jugar el juego abstracto de estrategia Quoridor. Un algoritmo recursivo que es utilizado a menudo para encontrar un movimiento óptimo para diversos juegos de mesa es el Minimax. Según Iker Eizagirre, en su investigación Quoridor, a board game AI (2018), afirma que dicho algoritmo es eficiente hasta cierto punto, debido a que conforme el juego transcurre surgen nuevas posibilidades de movimiento, lo cual hace que el árbol de posibilidades de movimiento sea demasiado grande para realizar una búsqueda Minimax hasta las hojas finales. Es en este punto donde surge una posible solución a este problema, lo cual sería limitando la profundidad de la búsqueda Minimax mediante la Poda alfa-beta, lo cual es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego, creando un rango potencial, el cual se limita por un valor mínimo donde no se permite movimientos que produzcan un potencial menor que el mínimo. Según P.J.C. Mertens en A Quoridor-playing Agent (2006), primero para poder desarrollar un algoritmo que pueda desempeñar un nivel razonable en Quoridor se debe plantear primero la complejidad del juego, para que de esta manera se pueda seleccionar el algoritmo óptimo para su futura implementación. Como bien es sabido el algoritmo Minimax, es comúnmente usado. Mertens plantea al igual que Eizagirre que dicho algoritmo es útil hasta cierto punto ya que el árbol de posibilidades tiende a crecer de manera exponencial. Por lo que, una manera en la que Mertens soluciono esto fue limitando la profundidad de la búsqueda Minimax. Además de utilizar funciones de evaluación para determinar el valor de una posición, el valor devuelto por la función vendría a ser la suma de los valores ponderados obtenidos por varias funciones de evaluación. Merten concluye mencionando que las extensiones del algoritmo Minimax, no conducen a un algoritmo capaz de jugar Quoridor de manera competente. Ya que explica y prueba que el desempeño alcanzado es un nivel amateur. Una de las razones sería la poca profundidad que utilizo en la búsqueda Minimax. Por lo que un Deep Search podría haber dado lugar a mejores movimientos y por ende a mejores resultados. En conclusión, para desarrollar un algoritmo que juegue Quoridor de manera competente, se necesita que la complejidad del algoritmo sea razonable ya que de esto dependerá la velocidad de respuesta del mismo. Además, cuanto más profundo y rápido pueda buscar nuestro algoritmo, el resultado será más preciso y desarrollado en una cantidad razonable de tiempo.

3. Metodología

Para el desarrollo del Proyecto de Complejidad algorítmica implementaremos una metodología que usaremos durante todo el proceso. Esta mostrará el paso a paso de las acciones que usaremos para poder lograr el objetivo del proyecto. A continuación, se explicarán las 3 Fases iniciales que aplicaremos en el proyecto.

3.1. Análisis

Para lograr el objetivo del proyecto tenemos que analizar las mecánicas del juego de mesa Quoridor. Esto con el fin de poder conocer más a fondo las características que tengamos que implementar para cada jugador. Nuestra meta para esta primera instancia es implementar los movimientos de los bots, o sea los jugadores, dentro del mapa. Para esto estudiamos las condiciones que tiene los jugadores dentro del juego para poder avanzar con éxito y así poder ganar el juego.

3.2. Diseño

El juego consiste en un mapa de cuadros de dimensiones de 9x9 con 20 paredes y cuatro jugadores. Esto nos indica los elementos que deberemos tener en consideración al momento de implementar las opciones que tendrá cada Bot al momento de realizar un movimiento. El diseño que tendrá el juego será implementado mediante una matriz. Esta última indicará los obstáculos que se presentarán dentro del juego para cada Bot. Esto nos servirá para poder realizar los movimientos inteligentes de cada player. Si es que un bot llega a la fila opuesta a su fila de inicio ganará el juego , es decir que si se encuentra 8 filas más que su posición inicial se considera automáticamente que llegó a la fila opuesta

3.3. Implementación

Para la creación y edición del documento del proyecto se estará usando el sistema de composición de texto LaTex y siendo editado en la herramienta OverLeaf. Como desarrolladores implementaremos nuestros algoritmos y el desarrollo del juego en el lenguaje Python. Luego se definirá un mismo editor de código para que el trabajo sea lo más elocuente. Tal como mencionado anteriormente el Mara será implementado en una matriz con el fin de facilitar el algoritmo de los Bot. Para el desarrollo de este último se presentarán 3 diferentes tipos de algoritmos para poder realizar los movimientos de cada jugador. Para una facilidad de trabajo en equipo estaremos utilizando la plataforma de GitHub. En esta se creará un repositorio nos ayudará a poder tener distintas versiones del proyecto para poder corregir los errores que podríamos tener.

4. Conclusiones

El Proyecto nos presentó nuevos horizontes, el uso de algoritmos y el manejo de grafos como en juegos e incluso en otros proyectos no ayudarán a volverlos más moldeables y menos estáticos. Gracias al uso de los sistemas de búsqueda se pueden realizar proyectos tales como la configuración de la IA siguiendo un algoritmo, predicción de movimientos,etc. En conclusión, el algoritmo designado por nosotros es el A*, debido a ser más intuitivo, consume menos memoria y tiempo en el momento de ejecución con los otros algoritmos.

5. Bibliografía

Bezakova, I., Heliotis, J. E. Strout, S. P. (2013, Marzo). Board game strategies in introductory computer science. In Proceeding of the 44th ACM technical symposium on Computer science education (pp. 17-22). Recuperado de: https://cs.bemidjistate.edu/fneville/CS1BoardGames.pdf

Glendenning. L(2005, Mayo). Mastering Quoridor. Recuperado de: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.5204&rep=rep1&type=pdf Mertens.

P(2006, Junio) A Quoridor-playing Agent. Recuperado de: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.134.5605&rep=rep1&type=pdf

Respall, V. M. (2018, Junio). Quoridor Agent using Monte Carlo Tree Search (pp. 25-29).Recuperado de: https://upcommons.upc.edu/bitstream/handle/2117/127676/131875.pdf?sequence=1&isAllow

TechWithTim. (2020, 16 julio). A* Pathfinding Visualization Tutorial - Python A* Path Finding Tutorial [Vídeo]. YouTube. Recuperado de: https://www.youtube.com/watch?v=JtiK0DOeI4A&t=2382s&ab_channel=TechWithTim

https://pdfs.semanticscholar.org/acad/6962a9bb3eb3fde4272f476d6625eb0a8182.pdf

https://project.dke.maastrichtuniversity.nl/games/files/bsc/Mertens_BSc-paper.pdf

https://ikereizagirre.files.wordpress.com/2018/03/quoridor-a-board-game-ai.pdf