Há algum tempo que me interesso por algoritmos de IA de xadrez de computador (e tive a chance de trabalhar em um em algum momento) como o Minimax , e como o componente principal desses algoritmos é a chamada função de avaliação para determinar o que é um boa configuração da placa e o que é ruim .
Em outros termos, dada uma configuração do seu tabuleiro de xadrez, como você determina que isso é a sua vantagem e com que grau de confiança?
Por exemplo:
- Se você possui o centro, isso é bastante favorável.
- Se você tem mais peças que seu oponente, isso é bastante favorável.
- Se você perdeu sua rainha, isso não é favorável.
- Se você tem um peão que está perto de ser promovido, isso é favorável.
- ...
Por isso, gostaria de pedir alguns conselhos sobre como criar uma boa função de avaliação, com base em algum conhecimento especializado sobre o jogo de xadrez em geral. E, se possível, um grau de favorabilidade (digamos, entre 1 sendo muito pouco favorável e 100 sendo extremamente favorável).
A idéia no final é ser capaz de criar um algoritmo que analise a árvore de possibilidades até uma certa profundidade e avalie qual é a configuração mais favorável para a próxima jogada (levando em consideração várias jogadas no futuro) com base no que é favorável ao jogador e não favorável ao oponente. Mas sem uma boa função de avaliação, o algoritmo não é nada.
fonte
Respostas:
Aqui está um bom ponto de partida. A comparação de materiais é fundamental (e fácil), então você pode ajustar isso para considerar aspectos posicionais, como classificações / arquivos abertos / diagonais, estrutura de peões, etc.
https://www.chessprogramming.org/Evaluation
fonte
Somando-se à resposta de @Eve Freeman, sugiro pesquisar como o melhor mecanismo de computador do mundo, Stockfish, avalia uma determinada posição. Como o código fonte está aberto, você pode fazer isso de graça. Acho que o arquivo com a função de avaliação que você está procurando é esse .
fonte
Sinto que estou um pouco atrasado com essa resposta, mas também estou no processo de fabricar um motor. O código fonte está em Python (que é bastante fácil de ler, mesmo que você não o conheça) e está disponível aqui se você deseja lê-lo. A lista de 'heurísticas' atualmente ativas (no momento da publicação):
Em um desses pontos, mencionei a 'fase' do jogo (por exemplo, abertura, meio-jogo, final de jogo) e, se você quiser incluir isso em seu mecanismo, provavelmente terá o mesmo problema que eu: não há linha clara que os separa. Minha função que decide em que fase está o jogo usa algumas coisas:
Esta resposta pode ter sido longa, tardia e fora de tópico, mas espero que tenha sido útil de qualquer maneira.
fonte
Surpreendentemente, acontece que um mecanismo Minimax funcionará razoavelmente bem quando a função de avaliação for aleatória ; isso é conhecido como efeito Beale e resulta do princípio de que posições que oferecem mais opções e menos oponentes ao oponente geralmente são favoráveis. Uma maneira razoável de gerar avaliações aleatórias de maneira consistente e eficiente é gerar um hash Zobrist para a posição (usando coeficientes escolhidos aleatoriamente no início do jogo) e derivar a avaliação aleatória diretamente do hash.
No extremo oposto da escala, AlphaZero e Leela realizam uma avaliação extremamente sofisticada de cada posição pesquisada, usando uma grande rede neural . É impraticável descrever em termos humanos quais funções essa rede implementa efetivamente, mas é inegavelmente mais eficaz do que a função de avaliação do Stockfish. O trabalho de pesquisa do AlphaZero indica que essa abordagem funciona melhor com o Monte-Carlo Tree Search em vez do Minimax.
Se, por outro lado, você deseja desenvolver um mecanismo de análise para ajudar jogadores ou comentaristas humanos a entender as nuances de uma posição, pode valer a pena implementar uma função de avaliação convencional usando valores de materiais estabelecidos e teoria posicional . Um bom exemplo é dado por Inside Rebel , de Ed Schröder , documentando os principais recursos de design de um mecanismo conceituado usado em vários computadores de xadrez de Mephisto. Você pode usar um certo grau de aprendizado de máquina para determinar a importância relativa de cada elemento de sua função de avaliação e também separá-los individualmente para apresentação em uma GUI.
fonte
Acho que os programadores de xadrez tendem a não confiar no conhecimento de jogadores de xadrez fortes ao projetar suas funções de avaliação, mas, em vez disso, experimentam elementos diferentes e os testam em jogos contra outros mecanismos, e decidem o que manter. Larry Kaufman fala bastante sobre seus pontos de vista sobre o que é um entendimento humano, mas parece que Rajlich e Dailey eram muito orientados a resultados e não adotaram as idéias de Kaufman por atacado.
Um artigo que achei interessante foi Zach Wegner comparando as funções de avaliação de Rybka e Fruit. Uma das áreas em que a Rybka pode ter representado um passo adiante foi a incorporação de tabelas de desequilíbrio de materiais com base em combinações específicas de peças. Kaufman escreveu um artigo sobre isso também.
http://www.top-5000.nl/ZW_Rybka_Fruit.pdf http://danheisman.home.comcast.net/~danheisman/Articles/evaluation_of_material_imbalance.htm
fonte
Este link é o melhor ponto de partida IMHO. Estou usando isso como ponto de partida para o meu próprio programa de xadrez e também acho fácil de entender e útil.
https://chessprogramming.wikispaces.com/Simplified+evaluation+function
fonte
Em poucas palavras, a abordagem padrão para ajustar os parâmetros de um mecanismo de xadrez é:
Em seguida, repita as etapas 3 e 4 até atingir sua meta de desempenho.
A abordagem usual para fazer isso é montar um laboratório onde os motores se enfrentam nos torneios. Vários jogos são usados nos quais o mecanismo reproduz as duas cores. Os principais torneios de interesse envolvem a execução de um mecanismo com o valor do parâmetro definido A contra o mesmo mecanismo com o valor do parâmetro definido B.
Como você provavelmente pode adivinhar, os resultados dessa abordagem dependem fortemente de:
Essa abordagem também consome muito tempo.
Uma abordagem mais recente (e inovadora) foi desenvolvida em 2010 por pesquisadores usando técnicas de Algoritmo Genético para a) especificar os parâmetros eb) ajustar os valores dos parâmetros. Os investigadores primeiro usaram um mecanismo com um conjunto nominal inicial de valores de parâmetros em relação a um conjunto de jogos de grandes mestres para ver se ele poderia efetivamente escolher a "melhor jogada". A "melhor jogada" foi definida como a jogada que o grão-mestre fez *. Onde quer que não o fizesse, foi gravado. Em seguida, foi tentado outro conjunto de valores de parâmetros e determinado o desempenho relativo versus a execução anterior.
Em seguida, tentou-se uma abordagem programática para combinar os valores dos parâmetros , usando o princípio do algoritmo genético de sobrevivência do "mais apto". Aqui, "mais apto" significa aquele que gera saída que mais se aproxima do ideal. (Também é um trocadilho com a técnica estatística de regressão "mínimos quadrados", uma técnica usada para julgar a qualidade da aproximação.)
Somente após a descoberta dos parâmetros do motor que podem imitar um GM razoavelmente bem é que a fase real do torneio do motor começa. Nesta fase, diferentes conjuntos de valores de parâmetros são novamente colocados um contra o outro, desta vez diretamente . Técnicas de aprimoramento de algoritmo genético são aplicadas para gerar gerações sucessivamente melhores do mecanismo.
Neste projeto de pesquisa, foram utilizados 36 parâmetros, incluindo todos os valores materiais das peças e muitos dos critérios de avaliação estratégica mais comuns, como peões para trás, quadrados fracos, pares de bispos etc. No entanto, os pesquisadores adicionaram novos parâmetros, como "pressão do rei", valores de "mobilidade" para cada tipo de peça, torre em um arquivo adjacente ao rei, torre em um arquivo semi-aberto, torre atacando o rei na - / b- / g- / h-file, separação entre um peão passado e o rei defensor e muito mais.
Infelizmente, os pesquisadores não detalham como eles criaram esse conjunto de parâmetros e quais parâmetros alternativos eles podem ter testado e rejeitado. Seria razoável supor que eles começaram com um conjunto muito maior e determinaram (por tentativa e erro) quais tiveram o maior efeito no desempenho e quais eram insignificantes ou derivados e, portanto, poderiam ser descartados.
Se isso parece útil, você pode encontrar a pesquisa aqui .
* Uma ressalva sobre uma fase da abordagem que os pesquisadores usaram está em ordem. Em sua Introdução à Compreensão do Xadrez, Movimento por Movimento , John Nunn escolheu "... jogos muito disputados entre grandes mestres fortes ..." para ilustrar seus temas. Ele então acrescenta:
O argumento levantado pelo Dr. Nunn sugere que a abordagem inicial dos pesquisadores para definir os parâmetros do motor, exigindo que eles imitem os movimentos dos grandes mestres, pode ser falha porque o jogo humano é defeituoso . De fato, está bem estabelecido que os motores já funcionam melhor que os humanos .
Portanto, talvez uma abordagem melhor para definir os parâmetros iniciais seria combinar um novo mecanismo com um superior existente .
fonte
Existe um site legal em:
Ele fornece uma introdução sobre como as funções do Stockfish funcionam.
fonte