Computer Go - Computer Go

Este artigo é sobre o estudo do Go (jogo) em inteligência artificial. Para a linguagem de programação de computador chamada Go, consulte Go (linguagem de programação) .
Não deve ser confundido com o software Go .
Parte de uma série sobre
Ir
Vá embarcar part.jpg
Especificidades do jogo
História e cultura
Jogadores e organizações
Computadores e matemática

Computer Go é o campo da inteligência artificial (IA) dedicado à criação de um programa de computador que joga o tradicional jogo de tabuleiro Go . O jogo Go tem sido um assunto fértil de pesquisa de inteligência artificial por décadas, culminando em 2017 com AlphaGo Master vencendo três de três jogos contra Ke Jie , que na época ocupava continuamente o 1º lugar do ranking mundial por dois anos.

atuação

Go é um jogo de tabuleiro complexo que requer intuição, pensamento criativo e estratégico. Há muito tempo é considerado um desafio difícil no campo da inteligência artificial (IA) e é consideravelmente mais difícil de resolver do que o xadrez . Muitos no campo da inteligência artificial consideram que Go requer mais elementos que imitem o pensamento humano do que o xadrez . O matemático IJ Good escreveu em 1965:

Vá em um computador? - Para programar um computador para jogar um jogo razoável de Go, e não apenas um jogo legal - é necessário formalizar os princípios da boa estratégia, ou desenhar um programa de aprendizagem. Os princípios são mais qualitativos e misteriosos do que no xadrez e dependem mais do julgamento. Portanto, acho que será ainda mais difícil programar um computador para jogar uma partida razoável de Go do que de xadrez.

Antes de 2015, os melhores programas Go só conseguiam atingir o nível de dan amador . No pequeno tabuleiro 9 × 9, o computador se saiu melhor e alguns programas conseguiram ganhar uma fração de seus jogos 9 × 9 contra jogadores profissionais. Antes de AlphaGo, alguns pesquisadores afirmavam que os computadores nunca derrotariam os melhores humanos em Go.

Primeiras décadas

O primeiro programa Go foi escrito por Albert Lindsey Zobrist em 1968 como parte de sua tese sobre reconhecimento de padrões . Ele introduziu uma função de influência para estimar o território e o hashing de Zobrist para detectar ko .

Em abril de 1981, Jonathan K Millen publicou um artigo na Byte discutindo Wally, um programa Go com uma placa 15x15 que cabia na RAM de 1K do microcomputador KIM-1 . Bruce F. Webster publicou um artigo na revista em novembro de 1984 discutindo um programa Go que ele havia escrito para o Apple Macintosh , incluindo a fonte do MacFORTH .

Em 1998, jogadores muito fortes foram capazes de vencer programas de computador, dando handicaps de 25-30 pedras, um handicap enorme que poucos jogadores humanos suportariam. Houve um caso no Campeonato Mundial de Computador Go de 1994 em que o programa vencedor, Go Intellect, perdeu todos os três jogos contra os jogadores jovens, recebendo uma desvantagem de 15 pedras. Em geral, os jogadores que entendiam e exploravam as fraquezas de um programa podiam vencer com handicaps muito maiores do que os jogadores típicos.

século 21

Os desenvolvimentos na pesquisa de árvore de Monte Carlo e no aprendizado de máquina trouxeram os melhores programas para alto nível de dan na pequena placa 9x9. Em 2009, o primeiro desses programas apareceu que poderia alcançar e manter classificações de baixo nível dan no KGS Go Server na placa 19x19 também.

Em 2010, no Congresso Europeu de Go 2010 na Finlândia, o MogoTW jogou 19x19 Go contra Catalin Taranu (5p). MogoTW recebeu uma desvantagem de sete pedras e venceu.

Em 2011, o Zen alcançou 5 dan no servidor KGS, jogando jogos de 15 segundos por jogada. A conta que alcançou essa classificação usa uma versão em cluster do Zen em execução em uma máquina de 26 núcleos.

Em 2012, o Zen venceu Takemiya Masaki (9p) por 11 pontos no handicap de cinco pedras, seguido por uma vitória de 20 pontos no handicap de quatro pedras.

Em 2013, Crazy Stone venceu Yoshio Ishida (9p) em um jogo de 19 × 19 no handicap de quatro pedras.

O Codecentric Go Challenge de 2014, uma partida melhor de cinco em um jogo uniforme de 19x19, foi disputado entre Crazy Stone e Franz-Jozef Dickhut (6d). Nenhum jogador mais forte jamais havia concordado em disputar uma competição séria contra um programa go em termos iguais. Franz-Jozef Dickhut venceu, mas Crazy Stone venceu a primeira partida por 1,5 pontos.

2015 em diante: a era do aprendizado profundo

Mais informações: AlphaGo versus Fan Hui , AlphaGo versus Lee Sedol e AlphaGo versus Ke Jie

Em outubro de 2015, o programa AlphaGo do Google DeepMind venceu Fan Hui , o campeão europeu de Go, cinco vezes em cinco em condições de torneio.

Em março de 2016, AlphaGo venceu Lee Sedol nas primeiras três das cinco partidas. Esta foi a primeira vez que um mestre de 9 dan jogou um jogo profissional contra um computador sem deficiência. Lee venceu a quarta partida, descrevendo sua vitória como "inestimável". AlphaGo venceu a partida final dois dias depois.

Em maio de 2017, AlphaGo venceu Ke Jie , que na época era o melhor classificado do mundo, em uma partida de três jogos durante o Future of Go Summit .

Em outubro de 2017, a DeepMind revelou uma nova versão do AlphaGo, treinada apenas por meio do self play, que havia superado todas as versões anteriores, batendo a versão Ke Jie em 89 de 100 jogos.

Como os princípios básicos do AlphaGo foram publicados na revista Nature , outras equipes foram capazes de produzir programas de alto nível. Em 2017, tanto o projeto Fine Art do Zen quanto do Tencent eram capazes de derrotar profissionais de alto nível algumas vezes e o mecanismo de código aberto Leela Zero foi lançado.

Obstáculos ao desempenho de alto nível

Por muito tempo, foi uma opinião amplamente difundida que o computador Go apresentava um problema fundamentalmente diferente do xadrez computadorizado . Acreditava-se que métodos baseados em busca global rápida com relativamente pouco conhecimento de domínio não seriam eficazes contra especialistas humanos. Portanto, uma grande parte do esforço de desenvolvimento do computador Go foi durante esses tempos focado em maneiras de representar o conhecimento especializado semelhante ao humano e combinando isso com a busca local para responder a questões de natureza tática. O resultado disso foram programas que lidaram bem com muitas situações, mas que tinham fraquezas muito pronunciadas em comparação com o modo geral de lidar com o jogo. Além disso, esses programas clássicos não ganharam quase nada com os aumentos no poder de computação disponível per se e o progresso na área foi geralmente lento.

Alguns pesquisadores perceberam o potencial dos métodos probabilísticos e previram que eles viriam a dominar os jogos de computador, mas muitos outros consideraram um programa Go-playing forte algo que só poderia ser alcançado em um futuro distante, como resultado de avanços fundamentais em tecnologia de inteligência artificial geral. O advento de programas baseados na pesquisa de Monte Carlo (iniciado em 2006) mudou essa situação de várias maneiras, com os primeiros jogadores profissionais de Go de 9 dan sendo derrotados em 2013 por computadores multicore , embora com handicap de quatro pedras.

Tamanho do tabuleiro

O quadro grande (19 × 19, 361 interseções) é freqüentemente apontado como uma das principais razões pelas quais um programa forte é difícil de criar. O grande tamanho do quadro evita que um pesquisador alfa-beta alcance uma visão futura profunda sem extensões de pesquisa significativas ou heurísticas de poda .

Em 2002, um programa de computador denominado MIGOS (MIni GO Solver) resolveu completamente o jogo Go para o tabuleiro 5 × 5. As pretas vencem, levando todo o tabuleiro.

Número de opções de movimentação

Continuando a comparação com o xadrez, os movimentos de Go não são limitados pelas regras do jogo. Para a primeira jogada no xadrez, o jogador tem vinte opções. Os jogadores de Go começam com uma escolha de 55 movimentos legais distintos, levando em consideração a simetria. Esse número aumenta rapidamente à medida que a simetria é quebrada, e logo quase todos os 361 pontos do tabuleiro devem ser avaliados. Alguns movimentos são muito mais populares do que outros e alguns quase nunca são executados, mas todos são possíveis.

Função de avaliação

Embora uma avaliação de contagem de material não seja suficiente para um jogo decente no xadrez, o equilíbrio do material e vários fatores posicionais, como a estrutura do peão, são fáceis de quantificar.

Esses tipos de regras de avaliação posicional não podem ser aplicados de forma eficiente ao Go. O valor de uma posição Go depende de uma análise complexa para determinar se o grupo está vivo ou não, quais pedras podem ser conectadas umas às outras e heurísticas em torno da extensão em que uma posição forte tem influência, ou até que ponto uma posição fraca posição pode ser atacada.

Mais de um movimento pode ser considerado o melhor, dependendo da estratégia usada. Para escolher um movimento, o computador deve avaliar os diferentes resultados possíveis e decidir qual é o melhor. Isso é difícil devido aos delicados trade-offs presentes no Go. Por exemplo, pode ser possível capturar algumas pedras inimigas ao custo de fortalecer as pedras do oponente em outro lugar. Se esta é uma boa troca ou não, pode ser uma decisão difícil, mesmo para jogadores humanos. A complexidade computacional também é mostrada aqui, pois um movimento pode não ser imediatamente importante, mas depois de muitos movimentos pode se tornar altamente importante à medida que outras áreas do tabuleiro tomam forma.

Problemas combinatórios

Às vezes, é mencionado neste contexto que vários problemas combinatórios difíceis (na verdade, qualquer problema NP-difícil ) podem ser convertidos em problemas do tipo Go em uma placa suficientemente grande; entretanto, o mesmo é verdadeiro para outros jogos de tabuleiro abstratos, incluindo xadrez e campo minado , quando adequadamente generalizados para um tabuleiro de tamanho arbitrário. Os problemas NP-completos não tendem, em seu caso geral, a ser mais fáceis para humanos sem ajuda do que para computadores adequadamente programados: é duvidoso que humanos sem ajuda seriam capazes de competir com sucesso contra computadores na resolução, por exemplo, de instâncias do problema de soma de subconjuntos .

Endgame

Dado que o jogo final contém menos jogadas possíveis do que o jogo inicial ( fuseki ) ou meio-jogo, pode-se supor que é mais fácil de jogar e, portanto, um computador deve ser capaz de enfrentá-lo facilmente. No xadrez, os programas de computador geralmente têm um bom desempenho em finais de xadrez , especialmente quando o número de peças é reduzido a ponto de permitir o aproveitamento de bases de mesa de final de jogo resolvidas .

A aplicação de números surreais ao final do jogo em Go, uma análise geral do jogo iniciada por John H. Conway , foi desenvolvida por Elwyn R. Berlekamp e David Wolfe e descrita em seu livro Mathematical Go ( ISBN  978-1-56881- 032-4 ). Embora não seja de utilidade geral na maioria das circunstâncias de jogo, ajuda muito na análise de certas classes de posições.

No entanto, embora um estudo elaborado tenha sido conduzido, jogos finais em Go provaram ser difíceis de PSPACE . Existem muitas razões pelas quais eles são tão difíceis:

  • Mesmo que um computador possa jogar cada área de endgame local perfeitamente, não podemos concluir que suas jogadas seriam perfeitas em relação a todo o tabuleiro. Outras áreas de consideração em jogos finais incluem relacionamentos de sente e gote , priorização de diferentes jogos finais locais, contagem e estimativa de território, e assim por diante.
  • O final do jogo pode envolver muitos outros aspectos do Go, incluindo 'vida e morte', que também são conhecidos por serem NP-difíceis .
  • Cada uma das áreas finais locais podem afetar uma à outra. Em outras palavras, eles são dinâmicos por natureza, embora visualmente isolados. Isso torna difícil raciocinar para computadores e humanos. Esta natureza leva a algumas situações complexas como Triple Ko, Quadruple Ko, Molasses Ko e Moonshine Life.

Portanto, os algoritmos Go tradicionais não podem jogar o jogo final Go perfeitamente no sentido de calcular diretamente um melhor movimento. Algoritmos de Monte Carlo fortes ainda podem lidar bem com situações normais de final de jogo de Go e, em geral, as classes mais complicadas de problemas de final de vida ou morte são improváveis ​​de aparecer em um jogo de alto nível.

Ordem de jogo

Os motores Go baseados em Monte-Carlo têm a reputação de serem muito mais dispostos a jogar tenuki , movimentos em outras partes do tabuleiro, ao invés de continuar uma luta local do que jogadores humanos. Pode ser difícil calcular diretamente quando uma mudança local específica é necessária. Isso costumava ser percebido como uma fraqueza no início da existência desses programas. Dito isso, essa tendência persistiu no estilo de jogo do AlphaGo com resultados dominantes, então isso pode ser mais uma "peculiaridade" do que uma "fraqueza".

Busca tática

Uma das principais preocupações de um jogador de Go é quais grupos de pedras podem ser mantidos vivos e quais podem ser capturados. Essa classe geral de problemas é conhecida como vida e morte . A estratégia mais direta para calcular a vida e a morte é realizar uma busca em árvore nos movimentos que potencialmente afetam as pedras em questão e, em seguida, registrar o status das pedras no final da linha principal de jogo.

No entanto, dentro das limitações de tempo e memória, geralmente não é possível determinar com total precisão quais movimentos podem afetar a 'vida' de um grupo de pedras. Isso implica que alguma heurística deve ser aplicada para selecionar quais movimentos considerar. O efeito líquido é que, para qualquer programa, há uma compensação entre a velocidade de reprodução e as habilidades de leitura de vida ou morte.

Com o algoritmo de Benson , é possível determinar as cadeias que estão incondicionalmente vivas e, portanto, não precisariam ser verificadas no futuro para segurança.

Representação estadual

Um problema que todos os programas Go devem resolver é como representar o estado atual do jogo. Para programas que usam técnicas de pesquisa extensas, esta representação precisa ser copiada e / ou modificada para cada novo movimento hipotético considerado. Essa necessidade impõe a restrição adicional de que a representação deve ser pequena o suficiente para ser copiada rapidamente ou flexível o suficiente para que uma movimentação possa ser feita e desfeita facilmente.

A maneira mais direta de representar um tabuleiro é como uma matriz unidimensional ou bidimensional, em que os elementos da matriz representam pontos no tabuleiro e podem assumir um valor correspondente a uma pedra branca, uma pedra preta ou uma interseção vazia . Dados adicionais são necessários para armazenar quantas pedras foram capturadas, de quem é a vez e quais interseções são ilegais devido à regra de Ko .

A maioria dos programas, entretanto, usa mais do que apenas as informações brutas do conselho para avaliar as posições. Dados como quais pedras estão conectadas em fios, quais fios estão associados entre si, quais grupos de pedras estão em risco de captura e quais grupos de pedras estão efetivamente mortos são necessários para fazer uma avaliação precisa da posição. Embora essas informações possam ser extraídas apenas das posições das pedras, muitas delas podem ser calculadas mais rapidamente se forem atualizadas em uma base incremental por movimento. Essa atualização incremental requer que mais informações sejam armazenadas como o estado da placa, o que pode fazer com que a cópia da placa demore mais. Esse tipo de compensação é indicativo dos problemas envolvidos na criação de programas Go rápidos para computador.

Um método alternativo é ter uma única placa e fazer e retirar movimentos de forma a minimizar as demandas de memória do computador e ter os resultados da avaliação da placa armazenados. Isso evita ter que copiar as informações repetidamente.

Projeto de sistema

Novas abordagens para problemas

Historicamente, as técnicas GOFAI (Good Old Fashioned AI) têm sido usadas para abordar o problema da Go AI. Mais recentemente, as redes neurais têm sido usadas como uma abordagem alternativa. Um exemplo de programa que usa redes neurais é o WinHonte.

Essas abordagens tentam mitigar os problemas do jogo Go com um alto fator de ramificação e inúmeras outras dificuldades.

Os resultados da pesquisa Computer Go estão sendo aplicados a outros campos semelhantes, como ciências cognitivas , reconhecimento de padrões e aprendizado de máquina . A Teoria dos Jogos Combinatória , um ramo da matemática aplicada , é um tópico relevante para o computador Go.

Filosofias de design

A única escolha que um programa precisa fazer é onde colocar sua próxima pedra. No entanto, essa decisão é dificultada pela ampla gama de impactos que uma única pedra pode ter em todo o tabuleiro e pelas complexas interações que vários grupos de pedras podem ter entre si. Várias arquiteturas surgiram para lidar com esse problema. O uso mais popular:

Poucos programas usam apenas uma dessas técnicas exclusivamente; a maioria combina partes de cada um em um sistema sintético.

Pesquisa de árvore Minimax

Uma técnica tradicional de IA para criar software de jogo é usar uma pesquisa de árvore minimax . Isso envolve jogar todos os movimentos hipotéticos no tabuleiro até um certo ponto e, em seguida, usar uma função de avaliação para estimar o valor dessa posição para o jogador atual. O movimento que leva ao melhor tabuleiro hipotético é selecionado e o processo é repetido a cada turno. Embora as buscas em árvores tenham sido muito eficazes no xadrez de computador , elas tiveram menos sucesso nos programas Computer Go. Em parte, isso ocorre porque tradicionalmente tem sido difícil criar uma função de avaliação eficaz para um tabuleiro Go, e em parte porque o grande número de movimentos possíveis de cada lado pode fazer com que cada um leve a um alto fator de ramificação . Isso torna essa técnica muito cara do ponto de vista computacional. Por causa disso, muitos programas que usam árvores de pesquisa extensivamente só podem ser reproduzidos em tabuleiros menores de 9 × 9, em vez de tabuleiros de 19 × 19 completos.

Existem várias técnicas que podem melhorar muito o desempenho das árvores de pesquisa em termos de velocidade e memória. As técnicas de poda, como a poda alfa-beta , Principal Variation Search e MTD (f), podem reduzir o fator de ramificação efetivo sem perda de força. Em áreas táticas como vida e morte, Go é particularmente receptivo a técnicas de armazenamento em cache, como tabelas de transposição . Isso pode reduzir a quantidade de esforço repetido, especialmente quando combinado com uma abordagem de aprofundamento iterativa . Para armazenar rapidamente uma placa Go de tamanho normal em uma tabela de transposição, geralmente é necessária uma técnica de hashing para resumir matematicamente. O hashing Zobrist é muito popular em programas Go porque tem baixas taxas de colisão e pode ser atualizado iterativamente a cada movimento com apenas dois XORs , em vez de ser calculado do zero. Mesmo usando essas técnicas de aprimoramento de desempenho, as pesquisas de árvore completa em uma placa de tamanho normal ainda são proibitivamente lentas. As buscas podem ser aceleradas usando grandes quantidades de técnicas de poda específicas de domínio, como não considerar movimentos onde seu oponente já é forte, e extensões seletivas como sempre considerar movimentos próximos a grupos de pedras que estão prestes a serem capturados . No entanto, ambas as opções apresentam um risco significativo de não considerar um movimento vital que teria mudado o curso do jogo.

Os resultados das competições de computador mostram que as técnicas de correspondência de padrões para escolher um punhado de movimentos apropriados combinadas com buscas táticas localizadas rápidas (explicadas acima) já foram suficientes para produzir um programa competitivo. Por exemplo, GNU Go era competitivo até 2008.

Sistemas baseados em conhecimento

Os novatos geralmente aprendem muito com os registros de jogos antigos jogados por jogadores experientes. Há uma forte hipótese que sugere que adquirir conhecimento Go é a chave para fazer um computador forte Go. Por exemplo, Tim Kinger e David Mechner argumentam que "acreditamos que, com melhores ferramentas para representar e manter o conhecimento Go, será possível desenvolver programas Go mais fortes". Eles propõem duas maneiras: reconhecer configurações comuns de pedras e suas posições e se concentrar em batalhas locais. "Os programas de Go ainda carecem de conhecimento em qualidade e quantidade."

Após a implementação, o uso de conhecimento especializado provou ser muito eficaz na programação do software Go. Centenas de diretrizes e regras gerais para um jogo forte foram formuladas por amadores e profissionais de alto nível. A tarefa do programador é pegar essas heurísticas , formalizá-las em código de computador e utilizar correspondência de padrões e algoritmos de reconhecimento de padrões para reconhecer quando essas regras se aplicam. Também é importante ter um sistema para determinar o que fazer no caso de duas diretrizes conflitantes serem aplicáveis.

A maioria dos resultados relativamente bem-sucedidos vem das habilidades individuais dos programadores em Go e de suas conjecturas pessoais sobre Go, mas não de afirmações matemáticas formais; eles estão tentando fazer o computador imitar a maneira como jogam Go. "A maioria dos programas competitivos exige de 5 a 15 anos de trabalho por pessoa e contém de 50 a 100 módulos que tratam de diferentes aspectos do jogo."

Até recentemente, esse método era a técnica de maior sucesso na geração de programas Go competitivos em uma placa de tamanho normal. Alguns exemplos de programas que dependem fortemente de conhecimento especializado são Handtalk (mais tarde conhecido como Goemate), The Many Faces of Go, Go Intellect e Go ++, cada um dos quais em algum momento foi considerado o melhor programa Go do mundo.

No entanto, adicionar conhecimento de Go às vezes enfraquece o programa porque algum conhecimento superficial pode trazer erros: "os melhores programas geralmente executam bons movimentos de nível mestre. No entanto, como todo jogador sabe, apenas um movimento ruim pode arruinar um bom jogo. Desempenho do programa ao longo de um jogo completo pode ser muito inferior ao nível de mestre. "

Métodos Monte-Carlo

Artigo principal: Pesquisa em árvore de Monte-Carlo

Uma das principais alternativas ao uso de pesquisas e conhecimentos codificados manualmente é o uso de métodos de Monte Carlo . Isso é feito gerando uma lista de jogadas potenciais e, para cada jogada, milhares de jogos são jogados aleatoriamente no tabuleiro resultante. O lance que leva ao melhor conjunto de jogos aleatórios para o jogador atual é escolhido como o melhor lance. A vantagem dessa técnica é que ela requer muito pouco conhecimento de domínio ou entrada de especialistas, a compensação sendo o aumento dos requisitos de memória e processador. No entanto, como os movimentos usados ​​para avaliação são gerados aleatoriamente, é possível que um movimento excelente, exceto por uma resposta específica do oponente, seja erroneamente avaliado como um bom movimento. O resultado disso são programas fortes em um sentido estratégico geral, mas taticamente imperfeitos. Este problema pode ser atenuado adicionando algum conhecimento de domínio na geração de movimentação e um maior nível de profundidade de pesquisa no topo da evolução aleatória. Alguns programas que usam técnicas de Monte-Carlo são Fuego, The Many Faces of Go v12, Leela, MoGo, Crazy Stone , MyGoFriend e Zen.

Em 2006, uma nova técnica de pesquisa, limites de confiança superiores aplicados a árvores (UCT), foi desenvolvida e aplicada a muitos programas 9x9 Monte-Carlo Go com excelentes resultados. UCT usa os resultados dos play outs coletados até agora para orientar a busca ao longo das linhas de jogo mais bem-sucedidas, enquanto ainda permite que linhas alternativas sejam exploradas. A técnica UCT, juntamente com muitas outras otimizações para jogar no tabuleiro maior de 19x19, levou o MoGo a se tornar um dos programas de pesquisa mais fortes. As primeiras aplicações bem-sucedidas dos métodos UCT para 19x19 Go incluem MoGo, Crazy Stone e Mango. MoGo venceu a Olimpíada de Computador de 2007 e venceu um (de três) jogo de blitz contra Guo Juan, 5º Dan Pro, no muito menos complexo Go 9x9. The Many Faces of Go venceu a Olimpíada de Computador de 2008 após adicionar a pesquisa UCT ao seu mecanismo tradicional baseado em conhecimento.

Aprendizado de máquina

Embora os sistemas baseados em conhecimento tenham sido muito eficazes no Go, seu nível de habilidade está intimamente ligado ao conhecimento de seus programadores e especialistas de domínio associados. Uma maneira de quebrar essa limitação é usar técnicas de aprendizado de máquina para permitir que o software gere regras, padrões e / ou estratégias de resolução de conflitos de regras automaticamente.

Isso geralmente é feito permitindo que uma rede neural ou algoritmo genético analise um grande banco de dados de jogos profissionais ou jogue muitos jogos contra si mesmo ou contra outras pessoas ou programas. Esses algoritmos são então capazes de utilizar esses dados como um meio de melhorar seu desempenho. AlphaGo usou isso com grande efeito. Outros programas que usavam redes neurais anteriormente eram o NeuroGo e o WinHonte.

As técnicas de aprendizado de máquina também podem ser usadas em um contexto menos ambicioso para ajustar parâmetros específicos de programas que dependem principalmente de outras técnicas. Por exemplo, Crazy Stone aprende padrões de geração de movimentos de várias centenas de jogos de amostra, usando uma generalização do sistema de classificação Elo .

AlphaGo

Artigo principal: AlphaGo

AlphaGo , desenvolvido pelo Google DeepMind , fez um avanço significativo ao derrotar um jogador humano profissional em outubro de 2015, usando técnicas que combinavam aprendizado profundo e pesquisa em árvore de Monte Carlo . AlphaGo é significativamente mais poderoso do que outros programas Go anteriores, e o primeiro a vencer um profissional humano de 9 dan em um jogo sem limitações em um tabuleiro de tamanho normal.

Lista de programas de computador Go-playing

Veja também: software Go
  • AlphaGo , o primeiro programa de computador a vencer em partidas pares contra um jogador profissional de Go humano
  • AYA por Hiroshi Yamashita
  • BaduGI por Jooyoung Lee
  • Crazy Stone de Rémi Coulom (vendido como Saikyo no Igo no Japão)
  • Darkforest pelo Facebook
  • Belas Artes por Tencent
  • Fuego, um programa de código aberto de Monte Carlo
  • Goban, programa Macintosh OS X Go da Sen: te (requer extensões Goban gratuitas)
  • GNU Go , um programa Go clássico de código aberto
  • Go ++ de Michael Reiss (vendido como Strongest Go ou Tuyoi Igo no Japão)
  • Leela , o primeiro programa de Monte Carlo à venda ao público
  • Leela Zero , uma reimplementação do sistema descrito no artigo AlphaGo Zero
  • The Many Faces of Go, de David Fotland (vendido como AI Igo no Japão)
  • MyGoFriend por Frank Karger
  • MoGo de Sylvain Gelly; versão paralela por muitas pessoas.
  • Programa de código aberto Pachi Monte Carlo de Petr Baudiš, versão online Peepo de Jonathan Chetwynd, com mapas e comentários enquanto você joga
  • Smart Go por Anders Kierulf, inventor do Smart Game Format
  • Steenvreter por Erik van der Werf
  • Zen de Yoji Ojima também conhecido como Yamato (vendido como Tencho no Igo no Japão); versão paralela de Hideki Kato.

Competições entre programas de computador Go

Várias competições anuais acontecem entre os programas de computador Go, sendo a mais proeminente os eventos Go nas Olimpíadas de Computador . Competições regulares, menos formais, entre programas costumavam ocorrer no KGS Go Server (mensalmente) e no Computer Go Server (contínuo).

Programas proeminentes de go-playing incluem Crazy Stone, Zen, Aya, Mogo, The Many Faces of Go, pachi e Fuego, todos listados acima; e Coldmilk de autoria de Taiwan, Steenvreter de Autoria Holandesa e DolBaram de Autoria Coreana.

História

A primeira competição Go de computador foi patrocinada pela Acornsoft , e as primeiras regulares pela USENIX . Eles funcionaram de 1984 a 1988. Essas competições introduziram o Nemesis, o primeiro programa competitivo de Go de Bruce Wilcox , e o G2.5 de David Fotland , que mais tarde evoluiria para Cosmos e The Many Faces of Go.

Um dos primeiros impulsionadores da pesquisa de computador Go foi o Ing Prize, um prêmio em dinheiro relativamente grande patrocinado pelo banqueiro taiwanês Ing Chang-ki , oferecido anualmente entre 1985 e 2000 no World Computer Go Congress (ou Ing Cup). O vencedor deste torneio teve permissão para desafiar jovens jogadores em um handicap em uma partida curta. Se o computador vencesse a partida, o prêmio era concedido e um novo prêmio anunciado: um prêmio maior para vencer os jogadores com um handicap menor. A série de prêmios Ing foi definida para expirar 1) no ano de 2000 ou 2) quando um programa pudesse vencer um profissional de 1 dan sem handicap por 40 milhões de dólares NT . O último vencedor foi Handtalk em 1997, ganhando 250.000 NT dólares por vencer uma partida de handicap de 11 pedras contra três amadores de 11–13 anos de 2–6 dans. Na época em que o prêmio expirou em 2000, o prêmio não reclamado era de 400.000 NT dólares por vencer uma partida com handicap de nove pedras.

Muitos outros grandes torneios regionais de Go ("congressos") tinham um evento Go de computador conectado. O European Go Congress patrocina um torneio de computador desde 1987, e o evento USENIX evoluiu para o US / North American Computer Go Championship, realizado anualmente de 1988 a 2000 no US Go Congress.

O Japão começou a patrocinar competições de Go de computador em 1995. A FOST Cup foi realizada anualmente de 1995 a 1999 em Tóquio. Esse torneio foi suplantado pelo Desafio Gifu, que foi realizado anualmente de 2003 a 2006 em Ogaki, Gifu. A Computer Go UEC Cup é realizada anualmente desde 2007.

Problemas de formalização de regras em jogos de computador

Quando dois computadores jogam um contra o outro, o ideal é tratar o jogo de maneira idêntica a dois humanos jogando, evitando qualquer intervenção de humanos reais. No entanto, isso pode ser difícil durante a pontuação do jogo final. O principal problema é que o software Go playing, que normalmente se comunica usando o Go Text Protocol (GTP) padronizado , nem sempre concorda com relação ao status de vida ou morte das pedras.

Embora não haja uma maneira geral de dois programas diferentes "falarem" e resolverem o conflito, esse problema é evitado em sua maior parte usando as regras chinesas , Tromp-Taylor ou American Go Association (AGA), nas quais o jogo continua ( sem penalidade) é necessária até que não haja mais desacordo sobre o status de quaisquer pedras no tabuleiro. Na prática, como no KGS Go Server, o servidor pode mediar uma disputa enviando um comando GTP especial para os dois programas clientes, indicando que eles devem continuar colocando as pedras até que não haja dúvidas sobre o status de qualquer grupo em particular (todas as pedras mortas foram capturados). O CGOS Go Server geralmente vê os programas serem encerrados antes mesmo de um jogo atingir a fase de pontuação, mas, no entanto, suporta uma versão modificada das regras Tromp-Taylor exigindo um jogo completo.

Esses conjuntos de regras significam que um programa que estava em uma posição de vitória no final do jogo sob as regras japonesas (quando ambos os jogadores passaram) pode perder por causa de um jogo ruim na fase de resolução, mas isso não é uma ocorrência comum e é considerado uma parte normal do jogo em todos os conjuntos de regras de área.

A principal desvantagem do sistema acima é que alguns conjuntos de regras (como as regras japonesas tradicionais) penalizam os jogadores por fazerem esses movimentos extras, impedindo o uso de playout adicional para dois computadores. No entanto, a maioria dos programas Go modernos suportam as regras japonesas contra humanos e são competentes tanto no jogo quanto na pontuação (Fuego, Many Faces of Go, SmartGo, etc.).

Historicamente, outro método para resolver esse problema era ter um especialista humano para julgar a mesa final. No entanto, isso introduz subjetividade nos resultados e o risco de que o especialista perca algo que o programa viu.

Testando

Muitos programas estão disponíveis que permitem que os motores Go do computador joguem uns contra os outros e quase sempre se comunicam através do Go Text Protocol (GTP).

GoGUI e seu addon gogui-twogtp podem ser usados ​​para jogar dois motores um contra o outro em um único sistema de computador. SmartGo e Many Faces of Go também oferecem esse recurso.

Para jogar com a maior variedade possível de oponentes, o KGS Go Server permite o jogo com motor Go vs. motor Go, bem como motor Go vs. humano em partidas classificadas e não classificadas. CGOS é um computador dedicado versus um servidor Go de computador.

Veja também

Referências

Leitura adicional

links externos