chess_engine_using_python

Motor de xadrez usando Python

Este repositório contém implementação de mecanismo de xadrez usando Minimax , poda Alpha-Beta e algoritmo de pesquisa Quiescência . O notebook Jupyter dentro de um Docker Container é usado para codificação. Todos os Jupyter Notebook também estão disponíveis na forma de imagem docker.

Confira o documento do projeto para ver uma análise detalhada.

Módulo Externo Usado

• Xadrez Python

Como executar usando o docker

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

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

Algoritmos do mecanismo de xadrez

Mínmax

Teoria

O núcleo do xadrez jogando xadrez em minmax. Minmax geralmente associa a peça preta com MAX, e a peça branca com MIN, e sempre avalia do ponto de vista das brancas.

O algoritmo Minmax é um algoritmo de busca adversária na teoria dos jogos. Ele utiliza árvore de jogo e inclui MIN e MAX para dois jogadores. Ambos os jogadores tentam anular a ação do outro. Max tenta maximizar o resultado enquanto MIN tenta minimizar o resultado. Ambos os jogadores jogam alternadamente, partindo do pressuposto de que ambos estão jogando de forma otimizada. Jogo ideal significa que ambos os jogadores estão jogando de acordo com a regra, ou seja, MIN está minimizando o resultado e MAX está maximizando o resultado.

O algoritmo minmax utiliza a abordagem Depth First Search para encontrar o resultado. Além disso, ele também utiliza retrocesso e recursão. O algoritmo percorrerá até o nó terminal e então retrocederá enquanto compara todos os valores filhos. Ele selecionará o valor mínimo ou máximo, com base em quem é o turno. Em seguida, ele propagará o valor de volta ao pai. Ele usa função de avaliação estática para determinar o valor em cada nó folha. Aproveita a vantagem do jogo de soma zero.

Implementação

Motor de xadrez usando Minmax

Complexidade de tempo

Minmax usa Depth First Search (DFS) na árvore do jogo, portanto, a complexidade de tempo do algoritmo minmax é O(b**m) , onde b é o fator de ramificação da árvore do jogo e m é a profundidade máxima da árvore.

Complexidade Espacial

A complexidade espacial do algoritmo minmax também é semelhante ao DFS, que é O(bm) , onde b é o fator de ramificação da árvore do jogo e m é a profundidade máxima da árvore.

Completude

O algoritmo Minmax está completo. Definitivamente encontrará uma solução, se existir, na árvore de pesquisa finita.

Otimização

O algoritmo Minmax é ideal se ambos os oponentes estiverem jogando de maneira otimizada.

---

Poda Alfa-Beta

Teoria

O algoritmo minmax pode ser otimizado podando alguns ramos. Galhos podados são os que não vão afetar o resultado. Isso melhorará a complexidade do tempo. Esta versão minmax é conhecida como minmax com poda alfa-beta. Também é chamado de algoritmo alfa-beta.
Na Poda Alfa-Beta, existem dois valores, Alfa e Beta. Abaixo estão alguns pontos a serem considerados sobre alfa e beta:

Algum ponto sobre Alpha (α)

• Alpha é o valor mais alto encontrado ao longo do caminho MAX.
• O valor inicial de alfa é infinito negativo porque o valor alfa continuará aumentando ou permanecerá o mesmo a cada movimento. Se escolhermos algum valor diferente do infinito negativo, então pode ocorrer o cenário em que todos os valores de alfa podem ser menores que o valor escolhido. Então, temos que escolher o menor valor possível, que é menos infinito.
• Alpha só é atualizado pelo jogador MAX.

Alguns pontos sobre Beta(β)

• Beta é o valor mais baixo encontrado ao longo do caminho MIN.
• O valor inicial do beta é infinito positivo porque o valor do beta continuará diminuindo ou permanecerá o mesmo a cada movimento. Se escolhermos algum valor diferente do infinito positivo, pode ocorrer um cenário em que todos os valores de beta podem ser maiores que o valor escolhido. Então, temos que escolher o valor máximo possível, e isso é infinito positivo.
• O valor beta é atualizado apenas pelo jogador MIN.

Durante o retrocesso, apenas o valor do nó é passado para o pai, não os valores alfa e beta.

A condição para poda alfa-beta:

 α >= β

Mover pedido

A eficácia do algoritmo alfa-beta depende muito da ordem de travessia. Desempenha um papel crucial na complexidade do tempo e do espaço.

Pior pedido

Em alguns casos, nenhum nó ou subárvore é removido da Árvore de Jogo. Neste caso, o melhor movimento ocorre na subárvore direita da Árvore do Jogo. Isso resultará em maior complexidade de tempo.

Pedido Ideal

Neste caso, o número máximo de nós e subárvores é podado. Os melhores movimentos ocorrem na subárvore esquerda. Isso reduzirá a complexidade do tempo e do espaço.

Implementação

Mecanismo de xadrez usando poda alfa-beta

Complexidade de tempo

Algoritmo Alpha Beta, também usa Depth First Search (DFS) na Game Tree.

• Em caso de pior pedido: O(b^m)
• Em caso de ordenação ideal: O(b^m/2)

Complexidade Espacial

• Em caso de pior pedido: O(bm)
• Em caso de ordenação ideal: O(b(m/2))

Completude

O algoritmo Alfa-Beta está completo. Definitivamente encontrará uma solução, se existir, na árvore de pesquisa finita.

Otimização

O algoritmo Alfa-Beta é ideal se ambos os oponentes estiverem jogando de maneira otimizada.

---

Pesquisa de Quiescência

Quiescência Search é uma modificação além da poda alfa-beta com min-max. Quiescência significa silêncio. Esta pesquisa avalia apenas movimentos silenciosos. Ou seja, após uma certa profundidade, ele utiliza apenas movimentos de captura para calcular os próximos movimentos. Uma busca quiescente pode evitar o efeito horizonte.
O efeito horizonte ocorre quando procuramos apenas até uma certa profundidade, mas pode acontecer que, se olharmos mais um nível de profundidade, o movimento poderá marcar menos pontos. Uma pesquisa de quiescência usa apenas movimentos de captura para evitar isso. A pesquisa de quiescência também reduz o fator de ramificação em diferentes níveis, resultando em um algoritmo rápido.

Complexidade de tempo

Algoritmo de pesquisa de quiescência, também usa pesquisa de profundidade (DFS) na árvore de jogos.

• Em caso de pior pedido: O(b^m)
• Em caso de ordenação ideal: O(b^m/2)

Complexidade Espacial

• Em caso de pior pedido: O(bm)
• Em caso de ordenação ideal: O(b(m/2))

Completude

O algoritmo de pesquisa de quiescência está completo. Definitivamente encontrará uma solução, se existir, na árvore de pesquisa finita.

Otimização

O algoritmo Quiescence Search é ideal se ambos os oponentes estiverem jogando de maneira otimizada.

---

Principal vantagem

• Os nós explorados por movimento são reduzidos em 10 vezes no Alpha Beta em comparação com o Minmax.
• O tempo necessário para encontrar o melhor movimento também é reduzido em 10 vezes no Alpha Beta em comparação com o Minmax.
• A pesquisa de quiescência tem um bom desempenho em maior profundidade.
• A pesquisa de quiescência é o algoritmo mais rápido de todos os três.
• A pesquisa de quiescência avalia menos nós.
• A pesquisa de quiescência pode resultar em movimentos repetidos, se não for tratada adequadamente.