chess_engine_using_python

Motor de ajedrez usando Python

Este repositorio contiene la implementación del motor de ajedrez utilizando Minimax , poda Alfa-Beta y algoritmo de búsqueda de inactividad . El cuaderno Jupyter dentro de un contenedor Docker se utiliza para codificar. Todos los Jupyter Notebook también están disponibles en forma de imagen acoplable.

Consulte el documento del proyecto para ver un análisis detallado.

Módulo externo utilizado

• Ajedrez Pitón

Cómo ejecutar usando la ventana acoplable

docker pull codewithnk/chess-engine-using-python:latest

docker run -p 8888:8888 -v $( pwd ) codewithnk/chess-engine-using-python:latest

Algoritmos del motor de ajedrez

Mínmax

Teoría

El núcleo del ajedrez es jugar al ajedrez en minmax. Minmax suele asociar la pieza negra con MAX y la pieza blanca con MIN, y siempre evalúa desde el punto de vista blanco.

El algoritmo Minmax es un algoritmo de búsqueda adversario en teoría de juegos. Utiliza un árbol de juegos e incluye MIN y MAX para dos jugadores. Ambos jugadores intentan anular la acción del otro. Max intenta maximizar el resultado mientras que MIN intenta minimizarlo. Ambos jugadores juegan alternativamente, bajo el supuesto de que ambos juegan de manera óptima. Juego óptimo significa que ambos jugadores juegan según la regla, es decir, MIN minimiza el resultado y MAX maximiza el resultado.

El algoritmo minmax utiliza el enfoque de búsqueda en profundidad para encontrar el resultado. Además, también utiliza retroceso y recursividad. El algoritmo atravesará hasta el nodo terminal y luego retrocederá mientras compara todos los valores secundarios. Seleccionará el valor mínimo o máximo, según a quién le toque. Luego propagará el valor a su padre. Utiliza una función de evaluación estática para determinar el valor en cada nodo hoja. Aprovecha el juego de suma cero.

Implementación

Motor de ajedrez usando Minmax

Complejidad del tiempo

Minmax utiliza Depth First Search (DFS) en Game Tree, por lo que la complejidad temporal del algoritmo minmax es O(b**m) , donde b es el factor de ramificación del árbol de juegos y m es la profundidad máxima del árbol.

Complejidad espacial

La complejidad espacial del algoritmo minmax también es similar a DFS, que es O(bm) , donde b es el factor de ramificación del árbol del juego y m es la profundidad máxima del árbol.

Lo completo

El algoritmo Minmax está completo. Definitivamente encontrará una solución, si existe, en el árbol de búsqueda finito.

Optimidad

El algoritmo Minmax es óptimo si ambos oponentes juegan de manera óptima.

---

Poda Alfa-Beta

Teoría

El algoritmo minmax se puede optimizar podando algunas ramas. Las ramas podadas son las que no van a afectar el resultado. Mejorará la complejidad del tiempo. Esta versión minmax se conoce como minmax con poda alfa-beta. También se le llama algoritmo alfa-beta.
En la poda Alfa-Beta, hay dos valores, Alfa y Beta. A continuación se detallan algunos puntos a considerar sobre alfa y beta:

Algún punto sobre Alpha(α)

• Alfa es el valor más alto que se encuentra a lo largo de la ruta MAX.
• El valor inicial de alfa es infinito negativo porque el valor alfa seguirá aumentando o permanecerá igual con cada movimiento. Si elegimos algún valor distinto del infinito negativo, entonces puede ocurrir el escenario en el que todos los valores de alfa pueden ser menores que el valor elegido. Entonces, tenemos que elegir el valor más bajo posible, y ese es infinito negativo.
• Alpha solo lo actualiza el reproductor MAX.

Algunos puntos sobre Beta(β)

• Beta es el valor más bajo que se encuentra a lo largo de la ruta MIN.
• El valor inicial de beta es infinito positivo porque el valor beta seguirá disminuyendo o permanecerá igual con cada movimiento. Si elegimos algún valor distinto del infinito positivo, entonces puede ocurrir un escenario en el que todos los valores de beta puedan ser mayores que el valor elegido. Entonces, tenemos que elegir el valor máximo posible, y ese es infinito positivo.
• El valor Beta solo lo actualiza el jugador MIN.

Mientras que el retroceso solo se pasa el valor del nodo al padre, no el valor alfa y beta.

La condición para la poda alfa-beta:

 α >= β

Mover pedidos

La eficacia del algoritmo alfa-beta depende en gran medida del orden de recorrido. Desempeña un papel crucial en la complejidad del tiempo y el espacio.

Peor pedido

En algunos casos, no se elimina ningún nodo o subárbol del Game Tree. En este caso, el mejor movimiento ocurre en el subárbol derecho del árbol de juego. Esto dará como resultado una mayor complejidad del tiempo.

Pedidos ideales

En este caso, se poda el número máximo de nodos y subárboles. Los mejores movimientos ocurren en el subárbol izquierdo. Reducirá la complejidad del tiempo y el espacio.

Implementación

Motor de ajedrez que utiliza poda alfa-beta

Complejidad del tiempo

El algoritmo Alpha Beta también utiliza la búsqueda en profundidad (DFS) en el árbol de juegos.

• En caso de peor pedido: O(b^m)
• En caso de orden ideal: O(b^m/2)

Complejidad espacial

• En caso de peor pedido: O(bm)
• En caso de orden ideal: O(b(m/2))

Lo completo

El algoritmo Alfa-Beta está completo. Definitivamente encontrará una solución, si existe, en el árbol de búsqueda finito.

Optimidad

El algoritmo Alfa-Beta es óptimo si ambos oponentes juegan de manera óptima.

---

Búsqueda de inactividad

Quiescencia Search es una modificación además de la poda alfa-beta con min-max. Quiescencia significa silencio. Esta búsqueda sólo evalúa movimientos silenciosos. En otras palabras, después de cierta profundidad, solo usa movimientos de captura para calcular los siguientes movimientos. Una búsqueda de quietud puede evitar el efecto horizonte.
El efecto horizonte se produce cuando sólo buscamos hasta una determinada profundidad, pero puede suceder que si miramos un nivel más de profundidad, entonces movernos pueda sumar menos puntos. Una búsqueda de inactividad sólo utiliza movimientos de captura para evitar esto. La búsqueda de inactividad también reduce el factor de ramificación en diferentes niveles, lo que da como resultado un algoritmo rápido.

Complejidad del tiempo

El algoritmo de búsqueda de inactividad también utiliza la búsqueda en profundidad (DFS) en el árbol de juegos.

• En caso de peor pedido: O(b^m)
• En caso de orden ideal: O(b^m/2)

Complejidad espacial

• En caso de peor pedido: O(bm)
• En caso de orden ideal: O(b(m/2))

Lo completo

El algoritmo de búsqueda de inactividad está completo. Definitivamente encontrará una solución, si existe, en el árbol de búsqueda finito.

Optimidad

El algoritmo de búsqueda de quietud es óptimo si ambos oponentes juegan de manera óptima.

---

Conclusión clave

• Los nodos explorados por movimiento se reducen 10 veces en Alpha Beta en comparación con Minmax.
• El tiempo necesario para encontrar el mejor movimiento también se reduce 10 veces en Alpha Beta en comparación con Minmax.
• La búsqueda de inactividad funciona bien a mayor profundidad.
• La búsqueda de inactividad es el algoritmo más rápido de los tres.
• La búsqueda de inactividad evalúa menos nodos.
• La búsqueda inactiva puede dar como resultado movimientos repetidos si no se maneja adecuadamente.