Um ser humano pode derrotar um forte programa no Reversi?

Afinal, é possível ou não um ser humano derrotar um forte programa no Reversi?

Depois de conversar com gente que entende do ramo, desde programadores a campeões mundiais, formei um leque de caracteres que têm mais um quê de NÃO, do que de SIM nessa questão, mas que inegavelmente, carrega sinais de algumas possibilidades e truques que fariam, ou dariam momentânea vantagem a humanos nesse impasse. Então configure sua retina, ajuste suas pupilas, decodifique os caracteres alfabéticos romanos e venha comigo nessa viagem tecnológica!

Em uma postagem que fiz em 2009, intitulada: “Como um Programa Pensa”, eu abordei nomes técnicos como “Pattern-Matching” para elucidar como o engenho e a rede sináptica do cérebro humano trabalham para buscar no arquivo de memórias, imagens mentais que se assemelhassem ao “desenho” de jogo ali presente. Em prática seria o mesmíssimo método adotado pelo cérebro para reconhecer rostos humanos, para saber se aquela pessoa que passou pela calçada e nos cumprimentou é um antigo colega do colégio que não víamos há anos, ou se era nosso primo que vimos um dia antes. Nessa postagem, que teve como pilar os estudos do programador, matemático e diretor executivo da On Time Systems, Matthew L. Ginsberg, foi explicado a absurda desvantagem humana contra as máquinas no jogo Reversi, devido ao sistema de busca bruta das mesmas para a solução objetiva dos “problemas” no jogo. O método das máquinas para se jogar um jogo como o Reversi, é, dentre outros, o “Alpha – Beta Pruning”, que faz com que a busca acorra através de “nós” específicos dentro da árvore de busca, garimpando junto a MiniMax, objetivos práticos e claros no melhor caminho para a vitória, algo que não da muita chance ao limitado cérebro humano, que estaria apenas a analisar “desenhos” de jogos, para junto com uma intuição, armar um ataque ou uma defesa durante o jogo, usando como pilar um objetivo a curto prazo, longe dos cálculos seriais e longínquos de uma máquina; e, é claro que no endgame, a mente humana é capaz de contar corretamente o caminho da melhor vitória, por exemplo, mas estamos falando aqui de partidas inteiras, o que é muito mais difícil de fazer.

Quase quatro anos mais tarde, fiz uma outra postagem sobre o tema, “Estrutura da Inteligência Artificial no Jogo Othello” mas dessa vez utilizando como base o trabalho acadêmico de alunos da Unicamp, onde foram explicados outros pilares interessantes de um bom programa de Reversi, coisa das quais se pode ver em áreas completamente diferentes da vida humana, como planejamento social, filosofia, matemática e ética. Estes pilares seriam a Heurística e a MiniMax. Que em resumo, seria a capacidade de um programa intitular o que é mais importante a fazer dentro das regras do jogo para formar uma boa defesa e um bom ataque. Priorizar as bordas, os cantos ou os dois? Reverter poucas peças ou o máximo possível? Tudo que envolve o planejamento está dentro da linguagem da Heurística. Na MiniMax teríamos as limitações, as regras do jogo. No caso do jogo Reversi, assim como disse o Arnaldo: “As regras são claras”, não há informações escondidas nesse jogo, as regras são as mesmas no início, no meio e no fim. Por exemplo: Duas peças pretas cercando uma peça branca, a reverte em preta, a regra será essa durante todo o jogo, não esperem mudanças. Citei até mesmo o exemplo de um jogo de dados, onde ao jogar de um lance pode mudar todo o jogo de uma forma imprevisível; o que não acontece no jogo Reversi, que mesmo que um lance de reverter de peças mude a configuração da partida, ainda assim é algo previsível, é determinístico. Esses mesmos princípios são utilizados na matemática e engenharia, por exemplo.

Enfim, essa foi só uma pequena introdução para explanar um pouco do que já foi dito aqui nesse blog sobre o tema, e para formar a base do raciocínio e investigação a seguir, com essas informações já podemos observar o quão abstrato pode ser um bom programa de Reversi, e o quanto padeceríamos tentando vencê-los, mas... Talvez isso aos meros e mortais jogadores de Othello/Reversi, mas e os campeões, o que acham disso? Antes de discorrer sobre as opiniões referente ao programa mais famoso hoje em dia, o WZebra de Gunnar Andersson e Lars Ivansson, vamos voltar na história e ver o que encontramos. E pegando essa máquina do tempo, nos encontramos em Pasadena na California, nos Estados Unidos no ano de 1976, que foi justamente o ano em que o campeão japonês Fumio Fujita do Japão, derrotou o programa IAGO, fato marcante, mas o jogador japonês tinha derrotado um bebê digital apenas, e esses bebês iriam crescer rapidamente e a coisa iria ficar brava. Em 1981 o bicampeão mundial Hiroshi Inouie, também do Japão, foi derrotado durante um campeonato entre humanos e programas, pelo programa The Moor. E como a lei de Moore é bem preditiva, sabemos que a capacidade de processamento das máquinas tendem a dobrar com o tempo e, obedecendo a esses preceitos, tendo em mãos bons programadores (obviamente que existem toneladas silíticas de programas mal programados e fracos ainda hoje) alguns desses programas com o tempo se tornariam quase imbatíveis, e foi mais ou menos isso que aconteceu durante o ano de 1997, quando desafiaram o tricampeão mundial Takeshi Murakami para um confronto contra o programa Logistello, embate esse que foi acompanhado, fotografado e arquivado para a história e, caso você busque as partidas para ver, verá que o fortíssimo jogador japonês perdeu por 6 a 0... Foi uma surra. No mesmo ano, nascia o WZebra (que na verdade surgiu dois anos antes, em 1995, mas era fraco e teve seu código fonte refeito) programa que já veio para ser um dos melhores softwares de Reversi da história, chegou a atingir 2650 Pontos na plataforma IOS de Igor Durdanovic, e ocupar excelentes posições em outros torneios para programas. É um programa que se bem configurado, e tendo partidas arquivadas em sua biblioteca de jogos e, que se elevado a uma profundidade de busca e com pouca ou nenhuma aleatoriedade, tornar-se quase imbatível para um ser humano, mesmo para um campeão mundial. Seu livro de aberturas tem mais de 500.000 posições, e o sistema de busca é o NegaMax e Multi Prob-Cut, só para se ter uma ideia, o NegaMax é mais potente que o Alpha-Beta Phoda por exemplo. Bom, tendo isso em mãos, será mesmo que um ser humano poderia derrota tal máquina? Levando em  consideração que eu me restringi a discorrer sobre as possibilidades inerentes ao programa WZebra, outros softwares como Ntest, Pointy, Forest, Edax ficaram de fora, pois todos têm mais ou menos a mesma força que o WZebra. Aplicativos como DroidZebra, The Othello, Ultima Reversi  são fortes, mas por serem inferiores aos programas para rodar em máquinas, ficaram de fora também.

Então, voltando a pergunta anterior, a resposta é sim e não, mas o sim é malandro. Vejamos:

Como disse Vlad Petric, jogador de Othello da United States of America, seria possível se: (A) Evitar que o programa aprenda jogadas, (B) Jogar somente contra as piores aberturas do programa, (C) Decorar variáveis, e mesmo assim, ainda seria muito difícil derrotá-lo.

Eu pessoalmente fiz esse teste, mas de uma forma um pouco diferente. No caso, eu programei o WZebra, mesmo que no nível 16, a jogar com alta aleatoriedade, para isso fui em “Configurações de Zebra”, logo em seguida em “Biblioteca” e cliquei em “Enorme Aleatoriedade”, depois fui em “Meio Jogo” também no mesmo menu, e fiz o mesmo. E não deu outra! O programa mesmo no nível 16, ficou bem mais fraco, algo até fora do normal. Eu diria que se parecia com o nível 6 em termos de habilidades e profundidade de busca. Existem truques para deixar o WZebra mais fraco e, até mesmo derrotá-lo, dentro dessa configuração, eu joguei sem pensar muito e em algumas partidas eu somente perdi por 38 a 26, o que é anormal! Normalmente o WZebra no nível 16 ou superior, de profundidade, não deixa possibilidade alguma de vitória a humanos, nem ao menos seríamos capazes de nos defender de um programa forte assim,(o normal para um bom jogador é ser derrotado por 52-12 ou 48-16 por exemplo) mas usando alguns truques, sim. Alta Aleatoriedade deixa, aparentemente, o WZebra mais fraco, uma vez que não consegue fazer buscas eficientes, o deixando caótico, e essa é a chance de um ser humano mais bem treinado, derrotá-lo, mesmo que em um nível mais alto, como o 20 por exemplo. Mas sem isso, não meu amigo(a), pode até ser, mas é quase impossível derrotar o WZebra em sua totalidade operacional. E foi mais ou menos o que disse o jogador Henry Aspenryd da Suécia, um dos principais jogadores do país há anos, e integrante do Comitê de Regras da Federação Mundial de Othello, onde o mesmo disse que mesmo com as configurações certas, as chances de se derrotar o WZebra seriam ainda improváveis, algo, segundo suas palavras, como ganhar na loteria. Garry Edmead, que participou do mundial de Othello de 1996, lembrou do massacre que o jogador japonês Takeshi Murakami levou do programa Logistello em 1997, (ele próprio pode jogar presencialmente contra Murakami em 1996) e disse jogar periodicamente contra o WZebra nos níveis 16/20, e nunca ter ganhado na vida. Ele ainda aposta que isso poderia ser possível talvez, para um dos jogadores TOPs do mundo, mas também citou o que aconteceu em 1997 com o jogador japonês, ou seja, acredita ser pouco provável para um ser humano derrotá-lo. Mas o que falaria um campeão mundial sobre esse tema? Bom, o blog Othello Classic não é fraco não, e conseguiu fazer essa pergunta a um, no caso, o jogador norte-americano, Ben Seeley, bicampeão mundial de Othello (2003-2004), e o mesmo disse que jogadores fortes como Yusuke Takanashi (tetracampeão mundial) jogou jogos perfeitos, ou quase perfeitos perdendo 1 disco no final do jogo. E disse que isso ainda assim, seria muito raro de acontecer, mas caso acontecesse, poderia ao menos garantir um empate contra o WZebra.

Mas e ai, talvez um programador especializado no jogo Reversi tenha uma ideia um pouco diferente sobre esse tema, o que será que um falaria a respeito disso?

Bom, para isso o blog Othello Classic foi atrás de nada mais nada menos que o italiano Beppi Menozzi. Tá, e quem é ele? Ele é o criador de um dos programas de Reversi mais famosos da história desse jogo, o Happy End.  E o que esse especialista disse foi realmente o tiro de misericórdia nas esperanças daqueles que pretendem (ou falam) derrotar o WZebra em uma boa profundidade e em sua força total, leiam o que ele disse na íntegra:

“Minha curta resposta é: não.

Um programa é, de longe, mais capaz de explorar as consequências a longo prazo de um movimento, então não há nenhuma maneira possível para um cérebro humano se aproximar de um programa que pode avançar 26 movimentos em profundidade no meio do jogo, conhece centenas de aberturas e joga perfeitamente em “28 vazias”.

De qualquer forma, um programa pode vencer outro programa, por isso não é teoricamente impossível vencer o Zebra. Os desenvolvedores de torneios entre programas geralmente costumavam analisar aberturas de oponentes específicos para, descobrir onde a biblioteca do oponente ou o algoritmo falharam com um trabalho profundo antes do torneio. Não sei se isso é possível, porquê, obviamente, durante os anos as bibliotecas cresceram e o jogo Othello foi explorado quase que totalmente.

Há outra maneira teórica de vencer um programa: assim que qualquer algoritmo de análise é baseado em valores estatísticos, significa que geralmente um programa foi treinado em jogos genéricos, há posições que apareceram muitas vezes e outras que são raras (por exemplo, sabemos que 2 + furo + 3 em uma borda é muito mais raro do que 1 + furo + 4). Essas posições podem ter uma pontuação menos precisa e então gerar erros na função de avaliação.

Esta não é uma estratégia fácil, porém, porque o nosso cérebro funciona exatamente da mesma maneira e, posições estranhas são definitivamente mais difíceis de avaliar do que as combinações normais. Mesmo assim, se você decidir seguir caminhos estranhos em um jogo, você pode ter certeza de que na avaliação a função é menos precisa, mas não significa que você estará indo em um caminho vencedor.

Então, minha longa resposta é: sem estudar movimento por movimento em um jogo específico de ponta a ponta, com o único propósito de encontrar pequenos vazamentos na avaliação do programa, nenhum humano pode vencer um programa em Othello.

Isso também se deve à complexidade do jogo. Em Othello há (se eu me lembro bem desses números) em média, cerca de 12-15 possíveis movimentos por turno. No Xadrez é cerca de 25, Conexão – 4  apenas 4 ou 5, damas em torno de 6-7 e GO ... Centenas. Os seres humanos têm um pensamento mais estratégico e gráfico em relação aos computadores com um pensamento sequencial e metódico e, de fato, um computador superou o Mestre de Go apenas muito recentemente por esse motivo. O jogo Othello, infelizmente, não é bastante complexo para permitir que um humano compita com um programa.”

Ou seja, aparentemente não é uma tarefa fácil derrotar o WZebra em uma configuração profunda e sem aleatoriedade. Seria surreal aprender as artimanhas do programa e derrotá-lo periodicamente, uma vez o mesmo programado em sua melhor operação; seria o mesmo que uma pessoa sedentária, fraca, “periodicamente” dar uma surra no Anderson Silva toda vez que volta para casa do trabalho no meio do caminho, ou acertar um tiro a 10 Km de distância em um alvo do tamanho de uma maçã enquanto toma o café da manhã, não seria impossível nenhuma dessas coisas, mas seriam extremamente improváveis. Agora, quem sabe... Jogando areia nos olhos do lutador e amarrando suas mãos e pés, talvez suas chances aumentem, ou quem sabe, aumentando o alvo ao tamanho de um prédio de 50 andares, com mais uns 30.000 m², e utilizando uma arma com precisão cirúrgica, quem sabe suas chances de não errar subissem mais.


Essas minhas analogias toscas ilustram mais ou menos a dificuldade que é vencer um programa forte no Reversi, somos meros mortais formados de carbono, querendo enfrentar máquinas especializadas. Como bem disseram os experientes jogadores e programadores acima, se você for realmente um jogador de ponta, (um bom lutador ou atirador profissional) obtendo algumas pré-vantagens antes (areia/cordas – aumento de tamanho de alvo/arma de precisão) suas chances podem aumentar ao ponto de garantir uma vitória, caso o contrário, suas chances serão sempre irrisórias perante uma máquina, a não ser que você seja o cara! Como bem disse o Seeley, o jogador Yusuke Takanashi fez jogos perfeitos, então, quem sabe tenhamos mais “Takanashis” por ai só esperando a oportunidade de mostrar que sim, os humanos são melhores que as máquinas no Othello/Reversi, mas enquanto esse dia não chega, só nos resta mesmo esperar e apanhar mais um pouco. J

Referências:

Como o Programa Pensa

http://othelloclassic.blogspot.com.br/2009/10/como-um-programa-pensa.html 

Estrutura da Inteligência Artificial no Jogo Othello

http://othelloclassic.blogspot.com.br/2013/01/estrutura-da-inteligencia-artificial.html 

Othello: Game of the Century by Takeshi Murakami (Japan Quarterly, 2000)

http://othellonews.weebly.com/november-2013.html 

Sobre o Programa WZebra

http://radagast.se/othello/zebra.html


Os diálogos dos participantes na íntegra:

Vlad Petric

“I think for 16/20 it should be possible, if you a) don't let WZebra learn; b) find an opening that it plays poorly (at least -5), by playing it against, say NTest at depth 30, and c) memorizing it and its variants.

Pretty darn difficult, even as such.” 


Henry Aspenryd

“In theory, if you have some setting that make zebra play a none optimal opening (like human opening style), and ends up with a losing opening. The player could play perfect play by luck. It's so far fetched that I would say your statement is correct, but then again people win on lottery tickets too”


Garry Edmead

“I play regularly at level 16 to 20 and beaten it an amazing 0 times. Maybe a top 10 world player could give it a go but I can remember Takeshi Murakami playing a computer many years ago and getting beaten in every game.”


Ben Seeley

“Top humans like Takanashi have played games which were literally perfect, or in which they only lost 1 disc. It's incredibly rare to do that, but normally that should be enough to beat or at least tie Zebra on that setting.”


Beppi Menozzi
“My short answer is: no.

A program is by far more capable of exploring consequences at long term of a move, so there's no possible way for a human brain to even get close to a program that can go 26 moves deep in midgame, knows hundreds of openings and plays perfectly at 28 empties.

Anyway, a program can beat another program, so it's not teoretically impossible to beat Zebra. On program tournaments developers generally used to analyze openings by specific opponents to find where opponent's library or algorhythm fail, with a pre-tournament deep work. I don't know if this is possible anymore, because obviously during the years the libraries have grown and Othello has been explored almost fully.

There's another teoretical way to beat a program: as soon as any analysis algorithm is based on statistical values, generally a program has been trained on generic games, there are positions that appeared very often and others that are rare (for example, we know that 2+hole+3 on an edge is far more rare than 1+hole+4). These positions could have less precise score and then lead to errors in the evaluation function.

This is not an easy strategy though, because our brain works in the exact same manner and strange positions are definitely tougher to evaluate than usual combinations.Even more, if you decide to follow strange paths in a game, you can be sure that the evaluation function is less precise, but not that you are taking a winning path.

So, my long answer is: without studying move by move a specific game from start to end with the only purpose of finding small leaks in the program's evaluation, no human can beat a program in Othello.

This is also due to the complexity of the game. In Othello there are - if I remember well these numbers - on average around 12-15 possible moves per turn. In Chess is around 25, 4-in-a-row just 4 or 5, checkers around 6-7 and Go... hundreds. Humans have more strategical and graphical thinking in respect to computers with a sequential and methodic thinking, and indeed a computer has beaten the Go master only very recently for this reason.Othello, unfortunately, is not enough complex to allow a human to compete with a program.”