Existe um mecanismo de xadrez que NÃO use a busca por força bruta?

Todo mecanismo de xadrez que eu já ouvi falar (incluindo tudo o que encontrei listado na Wikipedia) usa a pesquisa de força bruta com uma função de avaliação (algoritmo minmax) para decidir sua mudança.

Não é assim que a maioria dos humanos aborda o jogo, empregando reconhecimento geral de padrões; portanto, em princípio, seria possível que os computadores fizessem o mesmo.

Existe algum mecanismo de xadrez que não dependa da abordagem da força bruta para encontrar seus movimentos?

Nos anos 80, houve tentativas de escrever máquinas de xadrez com bases de conhecimento que escolhessem movimentos candidatos como seres humanos, mas não tiveram sucesso. O problema é que a correspondência de padrões humanos é difícil de colocar em palavras; portanto, a criação de regras para a base de conhecimento foi extremamente difícil.

Treinar uma rede neural para escolher candidatos a candidatos parece uma linha de pesquisa promissora. Aqui e aqui pode haver dois documentos pertinentes. (FWIW, não é o meu campo de ficção científica)

Você pode dar uma olhada no Giraffe, que foi publicado recentemente nas notícias:

https://thestack.com/iot/2015/09/14/neural-network-chess-computer-abandons-brute-force-for-selective-human-approach/

O hype é que em 3 dias ele aprendeu o jogo e atingiu o nível de IM. Por outro lado, a pesquisa está em

http://arxiv.org/abs/1509.01549

Gostaria de adicionar detalhes à resposta de @ Ian_Bush sobre Giraffe.

Na resposta de Ian_Bush, note-se que Giraffe não usa computação de força bruta. Isso não está certo , porque o Giraffe ainda é um mecanismo alfa-beta (nega-max). A única diferença para um mecanismo padrão é que a função de avaliação é ajustada automaticamente pelo aprendizado profundo. Portanto, o mecanismo aprende a jogar sozinho.

Tradicionalmente, o programador de mecanismos ajusta automaticamente os parâmetros em um mecanismo. Eu já fiz muito. Por exemplo, quanto peso você deve dar a um bispo e a um cavaleiro? 3.0? 3.1? 3,2? É difícil dizer.

Giraffe aborda o problema de uma maneira muito mais inteligente. Começa com alguns valores iniciais. O mecanismo usa o algoritmo de subida de gradiente para ajustar esses valores. Não precisamos codificar explicitamente quanto peso uma dama deve ter no código. É isso que queremos dizer "aprender". Isso não significa que o mecanismo possa jogar xadrez sem procurar.

EDIT : Giraffe modela os nós das árvores como probabilidade de eles caírem na principal variação. Verifique o papel para obter detalhes. Pessoalmente, não acredito nessa abordagem, e o artigo mostra poucas evidências de quão útil seria.

É meio discutível se você puder chamar uma pesquisa baseada em heurística e avaliar a abordagem como força bruta. Atualmente, a maioria dos mecanismos de xadrez de primeira linha segue uma abordagem baseada em regras para avaliar uma posição e uma função de pesquisa baseada em regras para remover movimentos.

Na verdade, não é garantido que você escolha a opção "global ideal", mas essas opções são boas o suficiente para o propósito. Nesse sentido, a maioria dos mecanismos de xadrez está usando uma aproximação do ótimo global e realmente se saindo bem.

Até o momento, não temos muitos mecanismos de xadrez bem-sucedidos no nível superior, usando uma abordagem diferente, pelo menos não em hardware barato.

Claude Shannon propôs dois tipos de algoritmos para a criação de mecanismos de xadrez. Um mecanismo "tipo A" examina todos os movimentos possíveis até uma profundidade finita, minimiza a árvore e, em seguida, executa o movimento com a avaliação mais alta da árvore minimizada (também conhecida como força bruta). Os mecanismos do tipo B limitam sua pesquisa a apenas um subconjunto de movimentos possíveis com base em alguns critérios. Eu acreditava que ele preferia o Tipo B como mais promissor.

Os motores criados na década de 1970 (por exemplo, Hitech, Kaissa) tendiam a ser pura força bruta, sem poda ou apenas alfa-beta, mas as pessoas logo viram o valor de podar a árvore de movimentos e linhas que dificilmente se mostrariam fortes. . Quase todos os mecanismos recentes cortam a árvore de linhas que são claramente mais fracas (alfa-beta), e a maioria dos mecanismos também usa vários tipos de poda para a frente (futilidade, redução de movimentos tardios, movimento nulo, corte). Nesse sentido, não existem muitos motores que usem mais força bruta.

Nos anos 70, Botvinnik estava trabalhando em um mecanismo chamado Pioneer, concebido em torno da noção de caminhos de ataque que teriam sido orientados pela avaliação. Nunca chegou ao ponto em que poderia jogar um jogo completo de xadrez.

Nos anos 90, Chris Wittington falou a favor do uso da incorporação de mais conhecimentos sobre xadrez e criou um programa chamado Chess System Tal, que era bastante forte para a época.

Kasparov, Anand e Tord Romstad observaram que o Hiarcs parece ter uma avaliação mais detalhada do que muitos dos principais mecanismos cuja força vem de uma pesquisa rápida.

Basicamente todos eles!

Os motores de xadrez realmente só usam força bruta quando:

• disse para
• estão analisando posições (resolução de problemas)
• Procurando por um xeque-mate (resolução de problemas, não quando estiver jogando contra, como "encontre o parceiro em N")

Caso contrário, eles têm uma "pesquisa seletiva", isso considerará todos os movimentos possíveis para um determinado layout do tabuleiro, mas apenas explorará alguns deles. Um mecanismo pode mudar para força bruta, porém, se classificar dois movimentos de maneira muito semelhante (mais de um movimento forte) ou se não conseguir encontrar um movimento que goste (sem movimentos fortes).

Eles também tendem a ter força bruta como última linha de defesa, se você viu as chances de um xeque-mate, é possível vê-lo chegando e ele vai querer se esforçar muito para desenhar e não consegue encontrar uma saída (o "efeito Horizonte" "é um problema com os motores, suponha que ele perca a rainha e tenha sido limitado a apenas 4 peças de profundidade; se puder trocar peões e adiar a perda da rainha por 4 movimentos, ele pensará que a salvou. , no processo, perderá pelo menos 1 peão (quando o próximo movimento aproxima o horizonte de antes) e o peso que coloca em salvar a rainha pode significar que ele sacrifica alguma defesa, por nada, se a morte ultrapassar o horizonte) .

Também terá força bruta quando a pesquisa seletiva não for muito útil. É por isso que os motores demoram mais quando restam 3 peças. Eles precisam de força bruta porque o algoritmo de seleção não pode classificar um movimento. O algoritmo de seleção é ótimo durante o meio do jogo, porque pode ser como "Oohh, fazer isso com o peão bloqueia o seu [tanto faz] e faz o backup do meu [tanto faz] e [o que seja] que eu tenho um número menor de defesa do que atacando" - por exemplo .

Se você tem um rei no meio do tabuleiro, há 8 jogadas, a busca seletiva será do tipo "Nada disso faz nada de útil, não sei dizer".

Você pode pensar na busca seletiva como tendo duas partes, é tático no sentido de tentar detectar movimentos táticos, ignorará o peso das peças envolvidas geralmente porque uma rainha que não faz parte de nenhuma estratégia não vale a pena. mais do que um peão vital para isso. Também é estratégico, pois irá explorar movimentos que reforçam uma defesa e se abrirão mais tarde para possíveis ataques.

O mecanismo faz o mesmo do seu ponto de vista, e para trás e para frente e para trás e para frente.

Algo chamado tabela de transposição é uma grande lista de coisas em que ele pensou; dessa forma, se acabar considerando algo que já fez, sabe e não precisa reavaliar.

A menos que (seletivo :)) chegue lá de uma maneira diferente ou queira explorar mais. Suponha que, por exemplo, descubra que sua torre é essencial para um ataque iminente, o mecanismo pode reavaliar uma linha quando descobrir isso. O peso anterior colocado nessa torre (por exemplo, 5 pontos, quão importante é para você) pode ser uma subestimação.

A busca seletiva também pode voltar atrás, como, por exemplo, considerar um bispo se mudar para o território inimigo; para o seletor de movimento, não é importante que possa ser tomada facilmente. Diga que descobre que estrategicamente é uma jogada excelente! Pode então voltar atrás e tentar encontrar uma maneira de proteger a praça para levar o bispo até lá. Suponha que envolva um peão para fazê-lo.

O método da força bruta consideraria a linha que envolve o movimento do peão, e (por força bruta) o bispo também, e as mesmas coisas que classificam a posição do tabuleiro (a busca seletiva em si) dirão "isso é bom", de modo que o tabuleiro taxas que variam muito, ambas a encontram.

É muito difícil classificar uma posição usando o método da força bruta, é por isso que a pesquisa seletiva funciona tão bem.

A força bruta da posição inicial pode encontrar o famoso companheiro em 4 que envolve uma rainha f7 coberta por um bispo, e se a classificação era alta (eu encontrei um checkmate! Trabalho feito! Jogo!) estaria errado porque o preto obviamente se oporia. A pesquisa seletiva classifica uma posição (para avaliação posterior) porque parece ser boa. Isso significa que, ao considerar sua resposta, ele pode decidir o que seria bom para você ....

Portanto, o material que a pesquisa seletiva usa para classificar as coisas é usado pela força bruta de qualquer maneira, porque "encontrou um xeque-mate envolvendo esse movimento" não é suficiente para dizer que o movimento é bom.

Portanto, quais são os primeiros movimentos escolhidos (branco) pelos motores de xadrez de força bruta?