Função de avaliação - Evaluation function

Uma função de avaliação , também conhecida como função de avaliação heurística ou função de avaliação estática , é uma função usada por programas de computador para jogos para estimar o valor ou bondade de uma posição (geralmente em uma folha ou nó terminal) em uma árvore de jogo. Uma árvore de tais avaliações é geralmente parte de um minimax ou paradigma de pesquisa relacionado que retorna um nó específico e sua avaliação como resultado da seleção alternada do movimento mais favorável para o lado em movimento em cada camada da árvore do jogo. O valor é um escalar quantizado, geralmente em n- ths do valor de uma peça do jogo, como uma pedra em go ou um peão no xadrez. n pode ser décimos, centésimos ou outra fração conveniente.

Presume-se que o valor representa a probabilidade relativa de vitória se a árvore do jogo for expandida desse nó até o final do jogo. A função olha apenas para a posição atual (ou seja, em quais espaços as peças estão e sua relação entre si) e não leva em consideração o histórico da posição ou explora possíveis movimentos para a frente do nó (portanto estáticos). Isso implica que, para posições dinâmicas onde existem ameaças táticas, a função de avaliação não será uma avaliação precisa da posição. Essas posições são denominadas não quiescentes ; eles exigem pelo menos um tipo limitado de extensão de pesquisa chamada pesquisa de quiescência para resolver ameaças antes da avaliação. Alguns valores retornados pelas funções de avaliação são absolutos em vez de heurísticos, se uma vitória, perda ou empate ocorrer no nó.

Não existem modelos analíticos ou teóricos para funções de avaliação de jogos não resolvidos, nem são tais funções inteiramente ad-hoc. A composição das funções de avaliação é determinada empiricamente inserindo uma função candidata em um autômato e avaliando seu desempenho subsequente. Um corpo significativo de evidências agora existe para vários jogos como xadrez, shogi e go quanto à composição geral das funções de avaliação para eles.

A abordagem geral para construir funções de avaliação é como uma combinação linear de vários termos ponderados determinados para influenciar o valor de uma posição. Cada termo pode ser considerado composto de fatores de primeira ordem (aqueles que dependem apenas do espaço e de qualquer parte dele), fatores de segunda ordem (o espaço em relação a outros espaços) e fatores de ordem n (dependências da história de a posição).

Existe uma relação intrincada entre pesquisa e conhecimento na função de avaliação. A busca mais profunda favorece menos fatores táticos de curto prazo e motivos posicionais mais sutis de longo prazo na avaliação. Há também uma compensação entre a eficácia do conhecimento codificado e a complexidade computacional: a computação do conhecimento detalhado pode levar tanto tempo que o desempenho diminui, portanto, as aproximações do conhecimento exato costumam ser melhores. Como a função de avaliação depende da profundidade nominal da pesquisa, bem como das extensões e reduções empregadas na pesquisa, não existe uma formulação genérica ou independente para uma função de avaliação. Uma função de avaliação que funciona bem em um aplicativo geralmente precisará ser substancialmente reajustada para funcionar efetivamente em outro aplicativo.

Os jogos computadorizados que empregam funções de avaliação incluem xadrez , go , shogi (xadrez japonês), othello , hex e damas . Alguns jogos como o jogo da velha são solucionados fortemente e não requerem pesquisa ou avaliação porque uma árvore de solução discreta está disponível.

No xadrez

As funções de avaliação no xadrez consistem em um termo de equilíbrio material que domina a avaliação, mais um conjunto de termos posicionais geralmente totalizando não mais do que o valor de um peão, embora em algumas posições os termos posicionais possam ficar muito maiores, como quando o xeque-mate é iminente . Uma função de avaliação também codifica implicitamente o valor do direito de movimento, que pode variar de uma pequena fração de um peão para ganhar ou perder. No final do jogo, é possível construir posições onde quem se move vence, embora a posição esteja em equilíbrio; também é possível construir posições onde quem deve se mover perde ( Zugzwang ).

Uma função de avaliação para o xadrez pode assumir a forma

c ₁ * material + c ₂ * mobilidade + c ₃ * segurança do rei + c ₄ * controle central + c ₅ * estrutura do peão + c ₆ * tropismo do rei + ...

Cada um dos termos é um peso multiplicado por um fator de diferença: o valor do material do branco ou pontuação posicional menos o do preto. A pontuação do material é obtida atribuindo-se um valor em unidades de peão a cada uma das peças. Os valores convencionais são: Rainha = 9, Torre = 5; Cavaleiro ou Bispo = 3; Peão = 1; o rei recebe um valor arbitrariamente grande, geralmente maior do que o valor total de todas as outras peças. Não apenas o valor absoluto do material, mas também a proporção entre o material branco e preto importa: sacrificar um peão na abertura pode conferir uma vantagem posicional (a proporção do material dificilmente é afetada), mas a vantagem de um peão em um rei e O jogo final do peão geralmente é suficiente para vencer (a proporção do material é grande). Essa proporção é geralmente implementada como um bônus de troca para baixo de acordo com a regra prática: 'negociar peças, mas não peões quando estiver à frente e vice-versa quando estiver atrás'. A pontuação de mobilidade é o número de movimentos legais disponíveis para um jogador, ou alternadamente a soma do número de espaços atacados ou defendidos por cada peça, incluindo espaços ocupados por peças amigas ou adversárias. A mobilidade efetiva, ou o número de espaços "seguros" para os quais uma peça pode se mover, também pode ser levada em consideração. A mobilidade efetiva para rainhas geralmente é muito baixa, embora o número de seus movimentos legais possa ser bastante alto. A pontuação de segurança do rei é um conjunto de bônus e penalidades avaliados para a localização do rei e a configuração dos peões e peças adjacentes ou na frente do rei, e peças opostas relacionadas aos espaços ao redor do rei. O controle do centro é derivado de quantos peões e peças ocupam ou estão nos quatro espaços centrais e às vezes nos 12 espaços do centro estendido. A estrutura de peões é um conjunto de penalidades e bônus para vários pontos fortes e fracos na estrutura de peões, como penalidades para peões duplos e isolados. O tropismo do rei é um bônus pela proximidade (ou penalidade pela distância) de certas peças, especialmente rainhas e cavaleiros, ao rei adversário.

Os pesos c1, etc., não são necessariamente constantes - são coeficientes de aplicação que podem variar com o estágio do jogo (abertura, meio-jogo, final de jogo), peças no tabuleiro (por exemplo, presença ou ausência de rainhas), outras características do posição, ou estratégia ou planos de alto nível (por exemplo, atribuir maior peso às peças que estão nas casas ao redor do rei adversário se o plano for um ataque do lado do rei).

O foco e, portanto, os termos e pesos relevantes da função de avaliação diferem dependendo do estágio do jogo. Na abertura, as considerações dominantes são o desenvolvimento das peças menores, o roque e a segurança do rei e o controle do centro. As penalidades são geralmente avaliadas para peças não desenvolvidas e roque atrasado. Em jogos finais, a promoção do peão ou o acasalamento com as peças são as considerações dominantes. Em situações de acasalamento, os fatores relevantes são a distância do rei alvo da borda ou canto do tabuleiro e a proximidade do rei e das peças de acasalamento com o rei adversário. Para jogos finais de rei e peão, os fatores relevantes são a proximidade dos reis aos peões, avanço dos peões e controle da (s) casa (s) de coroação.

A equação é um modelo conceitual. Em uma implementação particular, cada pseudo-termo composto pode ser representado por um punhado de possivelmente centenas de termos individuais, cada um com seu próprio peso ou valor calculado. Por exemplo, a estrutura do peão pode ter termos para isolado, dobrado, atrasado, avançado, passado, passado protegido, passado conectado, buracos, arquivos abertos e semiabertos, maiorias de peões, falanges e muitas outras formações. Outros fatores especiais que são frequentemente considerados são: desenvolvimento das peças menores, torres em fileiras abertas ou de sétima linha, torres duplas, cavaleiros de postos avançados (cavaleiros em locais centrais protegidos por um peão e não sujeitos ao ataque de um peão adversário), posse do par de bispos, bispos nas longas diagonais, peças ocupando ou sustentando espaços ao redor do rei adversário e mobilidade dos reis (os reis não devem ser 'apertados', portanto, sujeitos a acasalamento em movimento). Alguns termos, como segurança do rei em um final de jogo com poucas peças, podem e devem ser ignorados dependendo do contexto.

Os termos que compõem alguns fatores, como segurança do rei, combinam-se de forma não linear - uma fraqueza na segurança do rei, como uma coluna aberta adjacente ao rei, pode ser penalizada, por exemplo, por 1/4 de peão, mas duas fraquezas podem precisar ser penalizadas um ou mesmo dois peões completos e três pontos fracos por peça, uma torre ou até mais porque o xeque-mate está se tornando uma possibilidade provável. Fatores envolvidos com o avanço e promoção do peão também se combinam de forma não linear.

Os valores típicos de peões múltiplos atribuídos às peças também não são constantes, mas dependem do contexto: as peças não desenvolvidas valem muito menos, assim como as peças com mobilidade reduzida por qualquer motivo: bispos confinados por seus próprios peões ("o bispo mau") ; os cavalos perdem valor à medida que a posição fica sem peças e os bispos e as torres ganham valor; rainhas valem substancialmente mais se o rei oponente não estiver protegido contra xeques.

As funções de avaliação normalmente contêm dezenas a centenas de termos individuais, e a avaliação de uma posição normalmente varia de mais ou menos uma pequena fração de um peão. Avaliações maiores indicam um desequilíbrio material ou que uma vitória de material geralmente é iminente. Avaliações muito grandes podem indicar que o xeque-mate é iminente.

Na prática, funções de avaliação eficazes são criadas não pela expansão da lista de parâmetros avaliados, mas pelo ajuste cuidadoso dos pesos em relação uns aos outros, de um conjunto modesto de parâmetros como os descritos acima. Para este fim, posições exemplares de jogos master são empregadas, e a eficácia da função de avaliação medida pela porcentagem de movimentos selecionados que concordam com as escolhas dos mestres.

Mesas quadradas

Uma técnica importante na avaliação, pelo menos desde o início da década de 1990, é o uso de tabelas de peças quadradas (também chamadas de tabelas de valor de peças) para avaliação. Cada mesa é um conjunto de 64 valores correspondentes às casas do tabuleiro de xadrez. Há uma mesa separada para cada tipo de peça: rei, rainha, cavalo, bispo, torre, peão. Há um conjunto separado (invertido) de mesas para as peças opostas. Os valores nas tabelas são bônus / penalidades pela localização de cada peça em cada espaço. Os valores codificam uma composição de muitos fatores sutis difíceis de quantificar analiticamente. As tabelas básicas podem ser construídas a partir de princípios de desenvolvimento, controle central, segurança do rei, etc. Em programas de nível mestre e além, as tabelas são construídas a partir de uma composição de posições ocupadas pelas peças em jogos mestre, ajustadas para a aplicação. Por exemplo, os cavaleiros raramente são encontrados nas bordas esquerda e direita do tabuleiro em jogos principais, então pode-se atribuir um valor de penalidade para os espaços da mesa do cavaleiro quadrado-peça proporcional ao quão raramente um cavaleiro é encontrado lá em jogos principais. Freqüentemente, há dois conjuntos de mesas: um para a abertura e outro para o final do jogo; as posições do meio do jogo são interpoladas entre os dois. Autores de programas de xadrez tendem a manter a composição de suas tabelas quadradas de peças, bem como os métodos usados para criá-las, em segredo, porque uma grande quantidade de tempo, esforço, teste e experiência de jogo são necessários para construí-las, e ajuste cuidadoso aqui oferece uma vantagem competitiva.

Avaliação na pesquisa da árvore monte-carlo

Máquinas de xadrez como Leela Chess Zero têm um paradigma de pesquisa e avaliação substancialmente diferente do que o esquema alfabético / minimax convencional com avaliação de nó de folha. Na pesquisa em árvore monte-carlo, o espaço de pesquisa de todas as variações de um nó é amostrado rolando, ou jogando o jogo até o fim, escolhendo alternadamente um movimento aleatório para cada lado. O resultado, vitória, derrota ou empate, é copiado para o nó inicial. A jogada selecionada é aquela que leva a uma posição com o maior número de vitórias, ou maior pontuação média, embora nenhuma linha de jogo específica esteja associada à jogada. Uma situação análoga é a porcentagem de vitórias / empates / derrotas acumuladas para várias aberturas empregadas em jogos master. Se alguém está escolhendo uma abertura, tenderá a escolher aquelas com a maior porcentagem de vitórias ou a maior porcentagem de vitórias + empates. E da mesma forma para cada variação na abertura, se houver estatísticas disponíveis. A fraqueza de tal esquema é que a (s) linha (s) mais forte (s) de jogo para cada lado podem não fazer parte dessa abertura - podem ser oportunidades estreitas em uma abertura que, de outra forma, seria fraca.

Portanto, 'avaliação' em implementações de monte-carlo é uma probabilidade de ganhar, em vez de uma avaliação numérica de uma posição.

Em Go

As funções de avaliação em Go levam em consideração tanto o território controlado, a influência das pedras, o número de prisioneiros e a vida e morte de grupos no tabuleiro.

Veja também

Referências

Shannon, Claude, 1950, "Programming a Computer for Playing Chess", Philosophical Magazine, Ser.7, Vol. 41, No. 314.
Slate, D e Atkin, L., 1983, "Chess 4.5, the Northwestern University Chess Program" em Chess Skill in Man and Machine 2nd Ed., Pp. 93-100. Springer-Verlag, New York, NY.
Ebeling, Carl, 1987, All the Right Moves: A VLSI Architecture for Chess (ACM Distinguished Dissertation), pp. 56-86. MIT Press, Cambridge, MA
Guia de avaliação do Stockfish, [1]

Languages

In other projects