Inteligência Artificial ZERANDO o jogo da cobrinha (SNAKE) - YouTube

No vídeo anterior nós vimos que criar um algoritmo pra zerar o jogo da cobrinha não

tem nenhum mistério, basta ficar varrendo o tabuleiro desse jeito, sempre deixando um

espaço pra voltar, que vai dar pra zerar tranquilamente.

Essa estratégia se chama Ciclo Hamiltoniano e o único problema dela é que ela é bem

ineficiente, já que dá muitos passos desnecessários… daí nós mudamos o objetivo de “zerar o

jogo” para “zerar com a menor quantidade de passos possível”, e pra isso, a gente

colocou uma rede neural pra aprender a jogar.

O resultado final você já viu, a rede não conseguiu zerar porque ela acabava deixando

a cobrinha presa em si mesma

Se você conheceu o canal agora e ainda não viu o vídeo da rede neural aprendendo a jogar,

não tem problema, eu vou deixar o link dele no final desse vídeo aqui.

então hoje, nós vamos superar isso e vamos criar um algoritmo, que além de não se prender,

consegue zerar o jogo com uma quantidade bem menor de passos.

levando em consideração que o ciclo hamiltoniano precisa de mais ou menos 40 mil passos pra

zerar num tabuleiro 20x20,

Quantos passos você acha que esse novo algoritmo vai precisar?

Seja muito bem vindo ao universo programado!

Eu me chamo Victor Dias, programador e editor desse canal.

Pra você que é novo aqui, o objetivo desse canal é te mostrar a beleza da Ciência da

Computação, programando alguns algoritmos que são verdadeiras obras de arte.

Se você gosta desse tipo de conteúdo, se inscreve no canal pra receber os próximos

vídeos.

E pra você que já é velho aqui no canal, considere se tornar um membro, assim você

nos apoia a fazer mais vídeos como esse.

Os benefícios estão ali no botão Seja membro!

e como diria o poeta: “mais vale um passo na direção certa, do que dois na direção

errada”

vam bora pro vídeo

No vídeo anterior nós vimos que a rede neural tava jogando razoavelmente bem, só que ainda

assim tava se prendendo no próprio corpo.

E realmente, se a gente parar pra pensar, esse é o verdadeiro desafio do jogo.

Evitar que a cobrinha se prenda no próprio corpo.

Pro nosso algoritmo conseguir essa façanha, ele tem que de alguma forma, levar o futuro

em consideração na hora de tomar a decisão de pra onde ele vai virar.

Ele precisa saber quais direções levam pra um caminho sem saída.

Se liga nessa situação: apenas olhando pra essa imagem e conhecendo

as regras do jogo, você sabe quase instintivamente que ela não deve virar pra esquerda, porque

o seu cérebro humano é capaz de projetar o futuro, ainda mais numa situação simples

como essa.

O nosso cérebro é tão bom nisso que fica extremamente óbvio que ela vai se prender,

E isso é tão nítido que a sensação que dá é quase como se a gente tivesse realmente

enxergando o futuro.

Você consegue facilmente imaginar e visualizar na sua cabeça a cobrinha chegando no final

do caminho e batendo.

Antecipar o futuro é essencial pra você poder tomar a decisão certa hoje, agora.

Porque em alguns casos, deixar pra tomar essa decisão em cima da hora pode ser tarde demais.

Se ela estiver errada, não dá mais pra desfazer.

e é justamente essa habilidade que a gente quer dar pro algoritmo.

a de enxergar o futuro.

Pra ele conseguir ter essa habilidade, nós vamos fazer várias simulações do jogo antes

de escolher uma direção pra virar.

Nós vamos criar vários clones da cobrinha.

Só que esses clones vão jogar aleatoriamente.

Fazendo isso a gente consegue experimentar vários futuros diferentes e consequentemente

descobrir qual é a melhor direção pra virar.

Só que pera ai, clones jogando??

isso te lembra alguma coisa?

se você viu o vídeo da rede neural jogando o 2048, sim, é ele mesmo

O Monte Carlo

Se você não sabe ou não lembra como esse algoritmo funciona, vamos recapitular rapidamente

em apenas X segundos.

crie vários clones 100% identicos a cobrinha coloque todos pra jogarem aleatoriamente

quando todos perderem, calcule a pontuação final de cada um deles.

das 3 direções que a cobrinha original pode seguir, encontre aquela que teve a maior pontuação

média dentre os clones. aplica ela na cobrinha original.

e repete tudo de novo

A ideia desse algoritmo é descobrir quais direções levam ao fracasso.

por exemplo, nesse caso, os clones que foram pra frente bateram na

parede e não fizeram pontos. os clones que foram pra esquerda pegaram uma

comida só, ficaram presos e depois perderam. já os clones que foram pra direita não se

prenderam, alguns vão conseguir dar a volta e pegar a comida e outros vão conseguir até

mesmo pegar a próxima a comida.

A probabilidade de pegar a comida jogando aleatoriamente é bem baixa, mas como a quantidade

de clones é bem alta, uma coisa compensa a outra e alguns clones acabam conseguindo

chegar lá.

Aí o algoritmo vai concluir que a direita é a melhor direção pra seguir, já que

os clones que foram nessa direção ganharam mais pontos que os clones que foram nas outras

direções

Então na prática é como se o algoritmo estivesse ‘’atirando pra todos os lados’’

e vendo qual é a direção mais promissora.

Agora vamos colocar o monte carlo pra jogar…

Isso é o que acontece quando a gente tenta desenhar todos os clones jogando ao mesmo

tempo… uma verdadeira bagunça.

Deixa eu dar uma acelerada aqui...

show.

Nessa partida os clones estão 100% aleatórios e a métrica que classifica se o clone foi

bem sucedido ou não é apenas a quantidade de comidas que ele pegou.

Agora vamos ocultar os clones pra gente ver a cobrinha original jogando… ó, repara

que ela tá bem eficiente, ela tá indo direto pra comida, sem ficar dando voltas. e mano,

isso é sensacional. sério, reflete sobre isso...

A média dos clones, que são livres pra fazerem o que quiserem, converge pro menor caminho.

Eu particularmente acho esse algoritmo extremamente bonito.

Ele consegue encaixar a matemática e a programação de uma forma muito boa.

A programação torna possível fazer as simulações e a matemática se encarrega da convergência.

Como dizia meu professor:

“Esse é um daqueles algoritmos elegantes, que usam terno e gravata!”

mas tem um problema… olha só esse momento, a cobrinha se prendeu sem a menor necessidade.

Isso aconteceu por causa do formato dela no tabuleiro e o fato da comida ter nascido lá

do outro lado… Nessa situação ficou muito difícil dos clones conseguirem chegar lá

na comida jogando aleatoriamente, a maioria bateu na cauda e os outros perderam no caminho.

Aí ninguém fez pontos e aconteceu um empate na hora de decidir a direção que a cobrinha

original tinha que seguir.

Aí o algoritmo teve que desempatar escolhendo uma direção aleatória.

E infelizmente, ele deu azar.

Existem algumas formas de consertar isso:

Uma delas é aumentando a quantidade de clones, pra aumentar a chance de pelo menos um deles

conseguir chegar lá na comida e assim evitar o empate.

Só que essa não é uma boa forma de resolver o problema.

Aumentar a quantidade de clones só vai empurrar o problema pra frente… Isso vai continuar

acontecendo quando a cobrinha atingir tamanhos maiores.

Aí a gente teria que aumentar a quantidade de novo, de novo e de novo... e não dá pra

ficar aumentando pra sempre.

Nesse exemplo eu to usando 30 mil clones e mesmo assim não foi suficiente, ela perdeu

no tamanho 55.

Se eu aumentar pra 100 mil clones o meu computador já leva alguns vários segundos pra calcular

apenas 1 passo da cobrinha original.

Quanto mais clones, mais lento e mais pesado fica o algoritmo.

A boa notícia é que existem outras formas muito melhores de resolver esse problema.

Em vez de simplesmente aumentar a quantidade de clones, nós podemos melhorar os clones

que a gente já tem, deixando eles um pouco mais inteligentes.

Se liga:

Como o clone decide a direção que ele vai seguir de forma 100% aleatória, ele acaba

se jogando na parede ou no próprio corpo, e perde o jogo sem a menor necessidade.

e como a função do clone é coletar informações sobre o futuro, quanto mais tempo ele ficar

vivo melhor. mais informações ele coleta.

Perder prematuramente é péssimo pro algoritmo.

Pra corrigir isso e deixar o clone um pouco mais inteligente,

a gente pode fazer o seguinte: na hora de sortear uma direção pra virar, se essa direção

faz ele bater em alguma coisa, então ela tá fora do sorteio.

Assim ele não consegue mais se jogar na parede nem no próprio corpo e as únicas formas

de perder passam a ser: acabando a energia ou ficando preso em si mesmo.

Que são duas coisas que a gente não tem como evitar.

Se você não sabe que energia é essa, ela tá explicada no vídeo anterior.

Fazendo isso a gente transforma os clones de meros jogadores aleatórios para exploradores

inteligentes que evitam perder a toa.

E só com essa modificação a cobrinha já conseguiu ultrapassar os 55 pontos e chegar

em 146.

Um resultado bem próximo da nossa rede neural do vídeo anterior.

só que o problemas, com certeza, ainda não acabaram.

olha o que tá acontecendo: Nessa situação, os clones que viraram pra

direita conseguiram pegar a comida mas se prenderam e perderam.

Já os clones que foram pro lado esquerdo não se prenderam, mas também não conseguiram

pegar a comida.

Mesmo eles sendo exploradores inteligentes, nessa situação ficou muito difícil chegar

na comida com movimentos aleatórios.

Olha quantas camadas de cobrinha dividem a comida dos clones que foram pra esquerda.

Aí, diante desse dilema, o que o algoritmo escolheu?

Claro, a comida.

e isso faz todo sentido, já que a pontuação do clone só leva em consideração a quantidade

de comidas que ele pegou.

Um ser humano jogando saberia que o certo seria ficar seguindo a cauda até chegar perto

da comida pra pegar.

Mas esse nosso algoritmo ainda tá muito Ganancioso.

Ele não tá conseguindo perceber a vantagem em esperar agora, pra ganhar no futuro.

E nós precisamos consertar isso.

Saber o que levar em consideração na hora de calcular a pontuação do clone é muito

importante.

Essa pontuação é chamada de Heurística, e você precisa ficar testando vários tipos

até encontrar a que performa melhor no seu problema.

Se a gente quiser que a cobrinha sobreviva por mais tempo, a gente precisa, de alguma

forma, dizer pra ela que a comida não é a coisa mais importante, a gente precisa dizer

pra ela que percorrer o tabuleiro pra não se prender também é necessário.

E pra fazer isso, a gente vai mudar a Heurística, em vez dela levar em consideração apenas

a quantidade de comidas, agora ela vai ser uma multiplicação entre a quantidade de

comidas e a distância que o clone andou.

Dessa forma, os clones também ganham pontos quando se movimentam pelo tabuleiro, fazendo

a cobrinha ser menos gananciosa em relação à comida.

De cara a gente já vê uma diferença no comportamento dela, repara que ela não tá

mais fazendo o menor caminho.

Ela continua indo até a comida, mas agora ela tá curtindo um pouco mais o passeio,

sem pressa de chegar no destino, porque quanto mais ela anda, mais pontos ela ganha.

E essa heurística deu tão certo que ela conseguiu bater o recorde da rede neural e

chegou no tamanho 239, e só perdeu porque ficou sem energia.

e foi nesse momento que eu percebi que o segredo tava na distância percorrida pelo clone,

e que ele deveria dar mais importância pra ela do que pra quantidade de comidas.

então vamos aumentar o peso da distância percorrida no cálculo da heurística.

Aí o clone vai ganhar ainda mais pontos quando ele andar e vai focar ainda mais em não se

prender ao invés de focar em pegar a comida.

Assim a gente consegue diminuir ainda mais a ganância e fazer a cobrinha focar mais

no longo prazo.

E como fazemos isso?

Elevando a distância ao quadrado, ou ao cubo, por exemplo.

Só que, se a gente fizer isso, olha o que vai acontecer:

No início do jogo a cobrinha vai ficar ainda mais ineficiente.

Já que ela tá ganhando muitos pontos apenas por andar.

Se antes de aumentar o peso ela já tava dando um passeio maneiro até pegar a comida, imagina

agora, que a distância tá ao cubo.

Como o nosso objetivo é zerar com a menor quantidade de movimentos possível, nós vamos

ter que fazer mais uma otimização.

Quando você joga esse jogo, você percebe que no início, nem sequer passa pela sua

cabeça evitar de se prender.

Ela ainda é pequena demais pra isso te preocupar.

Você apenas vai na direção da comida e pronto.

Só que ao longo da partida, ela vai crescendo e aos poucos a situação vai complicando,

até o momento em que evitar de se prender passa a ser a prioridade.

Ou seja, o nosso comportamento vai mudando ao longo da partida.

O que era prioridade no início, deixa de ser no final.

Só que a nossa heurística é estática, ela permanece a mesma ao longo de toda a partida.

E como é a heurística quem define o comportamento da cobrinha, acaba que ela se comporta da

mesma maneira durante toda a partida.

A solução pra isso é fazer uma ‘’heurística dinâmica’’.

Se a gente quiser que o comportamento da cobrinha mude ao longo da partida, a gente precisa

que a heurística mude também.

A gente precisa de uma heurística que evolua junto da cobrinha.

E pra isso, nós vamos colocar o cálculo da heurística em função do tamanho dela.

ou seja, quando a partida começar, o expoente da distância percorrida vai ser igual 0,

pra cobrinha poder focar totalmente em pegar a comida o mais rápido possível…

e a medida que ela for crescendo, esse expoente vai crescendo junto.

Dessa forma, o peso da distância vai aumentando aos poucos e ela, consequentemente, vai deixando

de ser gananciosa ao longo da partida.

Dessa forma a gente consegue ter o melhor dos 2 mundos.

Pegar a comida rápido no início e não ser ganancioso no final.

e mano, o jeito que o Monte Carlo joga sempre me surpreende… É estranho.

É um jeitão meio aleatório mas ao mesmo tempo estratégico...

Dá uma sensação de que ele realmente tá enxergando o futuro e não apenas simulando.

Tem situações que você acha que ele vai se prender.

Mas ele não se prende.

Porque os clones dele conseguem enxergar muito mais longe do que a gente.

Que algoritmo bonito mano.

e o final desse jogo é tão complicado que olha só a situação que ela se meteu. e

agora???

Pra frente ela bate, pra esquerda ela se prende, e pra direita também.

Essa é uma daquelas situações em que deixar pra tomar a decisão em cima da hora é tarde

demais.

Ela deveria ter se organizado quando ainda tava aqui, aí sim, ela teria chance de sobreviver

e zerar o jogo.

Aí depois de mais alguns testes e mais ajustes na heurística.

Esse foi o formato que teve o melhor desempenho e finalmente conseguiu zerar o jogo usando

29 mil passos.

Lembrando que a quantidade de comidas e a distância percorrida são relativas ao clone,

e não ao total da cobrinha original.

Por exemplo, Se o clone andou 200 blocos e pegou 1 comida antes de perder, são esses

números que vão pro cálculo da pontuação..

Uma coisa que eu achei muito interessante nessa heurística é que o fato de colocar

a distância percorrida no cálculo da pontuação faz com que o comportamento dela no final

do jogo fique muito parecido com o ciclo hamiltoniano, e isso faz todo sentido, já que os clones

que se espalham mais ganham mais pontos.

Olha só esse momento mano, olha como ela vai preenchendo certinho todos os espaços.

Sensacional.

Só que ainda existem 3 problemas nesse algoritmo:

O primeiro é que 29 mil passos ainda é um valor alto, dá pra diminuir ainda mais essa

quantidade e fazer a cobrinha zerar com menos passos.

O segundo problema é que ele não consegue zerar em 100% das partidas.

Às vezes acontece isso ó.

Bem no finalzinho do jogo, a comida nasceu na frente dela, e depois nasceu de novo.

Como a cobrinha tava muito perto da cauda, não sobrou espaço pra ela andar depois que

o tamanho aumentou 2 vezes, aí ela perdeu faltando apenas 2 comidas pra ganhar.

E o último problema é que, se a gente aumentar o tamanho do tabuleiro, a dificuldade vai

aumentar exponencialmente mais, daí a gente teria que aumentar a quantidade

de clones pra conseguir explorar a mesma área de antes, só que uma hora isso chega no limite

e o algoritmo não consegue zerar mais.

Isso significa que, no próximo vídeo dessa série, nós vamos ver outro algoritmo que

também consegue zerar esse jogo, só que ele resolve esses 3 problemas.

Esse algoritmo consegue zerar o jogo 100% das vezes, com uma quantidade de passos menor

que o Monte Carlo e em tabuleiros maiores.

Eu to deixando um vídeo com a partida inteira na descrição, pra quem tiver interesse em

assistir o monte carlo jogando do início ao fim.

E se você quiser saber mais sobre inteligência artificial, você pode seguir o canal no instagram,

que é por lá que eu respondo as dúvidas de vocês.

Aqui na esquerda tem o vídeo anterior dessa série, aquele onde a rede neural aprende

a jogar.

E aqui na direita tem o próximo vídeo dessa série, onde nós vamos ver o algoritmo que

resolve os 3 problemas do monte carlo.

Pra assistir qualquer um dos dois, é só clicar neles.

Tamo junto galera e até daqui a pouco!