Como identificar uma vitória no jogo da velha usando Javascript?

A um bom tempo atrás eu estava tentando imaginar como poderia ser um algoritmo que simulasse uma inteligência artifical capaz de responder a jogadas no jogo da velha de forma inteligente. O foco era conseguir descobrir um tipo de algoritmo capaz de fazer este feito, não valeria fazer algo mais tradicional apenas verificando o jogo, mas sim algo que fosse capaz de aprender.

Como não sou nenhum cientista da computação com especialidade em IA, é óbvio que eu não conseguiria achar a resposta apenas pensando sobre isso nas madrugadas onde eu deveria estar dormindo. Porém, só o fato de tentar conceber a ideia na imaginação, é algo interessante de se pensar.

Tempo depois, em conversas com um amigo, o assunto voltou a tona. Mas desta vez não se tratava de resolver o jogo da velha com um algoritimo de IA, mas sim a ideia de como que se poderia resolver o problema com um algoritmo que fosse capaz de identificar a vitória dentro um determinado cenário no jogo.

Foi aí que a minha ficha caiu!

Pois apesar de eu ter acreditato em que tinha a resposta certa de cara, ao longo dos meu pensamentos fui percebendo que as coisas não eram tão simples assim rsrsrs. Sabe quando você projeta uma solução em sua mente, mas logo no meio do caminho aborta a ideia, por perceber que ela não resolveria? Então, foi isso que aconteceu quando eu tentei encontrar uma solução para este problema.

Em busca da solução do problema

Depois de que eu me toquei que as coisas não eram tão simples assim como eu imaginava, eu comecei a tentar pensar numa solução nos dias e horas mais aleatórios do meu dia-a-dia. E nestes pensamento as vezes eu pensava “E eu ingenuamente tentando imaginar um algoritimo de IA sobre o jogo, sendo que nem consigo descobrir uma maneira simples de identificar um estado de vitória dentro do jogo kkk “.

Porém num certo dia eu tentei ser mais minucioso nos meus pensamentos, segui a doutrina de um antigo professor de programação da faculdade que falava “Vamos por partes, estilo Jack…”, e apenas me concentrei em resolver as partes de qual eu ao menos sabia começar.

Projetanto o algoritmo

Um jogo da velha, nada mais é do que uma matriz 3×3 com seus estados finitos de configuração. Vamos primeiro visualizar esta estrutura da forma que conhecemos e sua versão via código javascript:

 

 

 

 

 

 

Se você parar para observar, conseguimos entender que o estado do jogo na esquerda esquivale a dizer que o nosso array em javascript está com sua matriz (a variável) “jogo_da_velha” com a string ‘O’ nas seguintes posições:

jogo_da_velha[0][0] //possui a string 'O'

jogo_da_velha[1][1] //possui a string 'O'

jogo_da_velha[2][2] //possui a string 'O'

onde [0][0] indica que estamos acessando o primeiro array de dentro da variável jogo_da_velha. Lembrese-se que esta variável possui três elementos (a1, a2, a3) e cada um deles é um array conforme a imagem da direita.

Então se eu declaro a seguinte instrução: jogo_da_velha[0][0] eu estou dizendo para capturar o primeiro elemento de dentro da variável jogo_da_velha que é o a1, e o próximo [0] indica que eu devo capturar o primeiro elemento de dentro do array a1. Pois este contém um outro array de 3 elementos. Neste caso eu estou pendindo apenas o primeiro, o que está na posição 0.

Então, tendo esta explicação em mente, eu posso afirmar que jogo_da_velha[0][0] contém o elemento ‘O’ conforme a imagem a esquerda. Em jogo_da_velha[0][1] eu tenho o elemento ‘X’ e na posição jogo_da_velha[0][2] eu tenho um espaço vazio.

Ok! Agora como eu consigo identificar se o meu jogo possui um estado de vitória?

Agora que você entendeu sobre o posicionamento de cada elemento dentro da matriz do jogo. Podemos avançar para a próxima parte.

Existem duas solução para este problema que eu consegui visualizar. A primeira solução envolve muito mais lógica de controle e computação por conta das inúmeras verificações que devem ser feita.

Ao meu ver, poderíamos fazer um loop pala matriz do jogo (jogo_da_velha) e tentar calcular se a posição atual do elemento combinado a outras posições do jogo configuram uma posição de vitória.

Por exemplo:

 No início do meu loop, eu estou na posição [0][0] que segundo a imagem inicial a esquerda, contém uma ‘O’. Neste algoritmo, eu poderia montar as próximas posições válidas que configuram uma vitória para verificar se dentro delas contém alguma string com o caracter ‘O’ que representa uma bolinha preenchida. E para fazer isso eu devo seguir conforme a imagem acima, onde 3 arrays foram identificados (os 3 arrays estão marcados em vermelho!).

Ou seja, primeiro você acessa as duas próximas posições do array a1 e verifica se dentro delas consta a string ‘O’. se não constar, você deve acessar o próximo array que configura uma possível posição de vitória. Neste caso seria a posição diagonal e por fim a posição adjacente a posição diagonal.

Mas lembre-se que o acesso as estas posições deve ser feito a partir da variável jogo_da_velha que vai te facilitar para acessar tais elementos.

E desta forma vai seguindo o loop conforme as imagens abaixo:

 

 

 

 

 

 

Observe que a cada loop, a gente pega cada elemento e identifica as posições que combinado com ele, pode resultar numa condição de vitória. Caso cada um dos 3 elementos contenham juntos as strings de ‘O’ ou ‘X’, podemos parar o loop e indicar que houve uma condição de vitória.

Entretanto esta versão, é a mais complicada na minha opinião e além disso, eu apenas a concebi mentalmente. Eu não cheguei a tentar codificar na prática pra saber se resolve de verdade ou não. Talvez esta solução não funcione, eu não sei! Só sei que achei ela bem mais trabalhosa e por isso eu optei pela segunda opção.

Trabalhando na segunda opção

Na segunda opção que encontrei, a ideia principal é ter armazenado num array todas as condições de vitória, ou seja, para cada item do array de vitórias, deverá conter um outro array de 3 posições que será responsável por identificar as posições de cada item.

Por exemplo:

let posicoes_validas = [

    [ [0,0], [1,1], [2,2] ],
    [ [0,0], [0,1], [0,2] ],
    [ [1,0], [1,1], [1,2] ],
    [ [2,0], [2,1], [2,2] ],
    [ [0,0], [1,0], [2,0] ],
    [ [0,1], [1,1], [2,1] ],
    [ [0,2], [1,2], [2,2] ],
    [ [0,2], [1,1], [2,0] ]

];

Neste exemplo acima, tome um array onde para cada posição deste array, tomos um novo array que indica uma coleção de posições. Tais posições também são um array de dois elementos onde um indica a linha a outra a coluna para saber a posição de um ‘X’ ou ‘O’ marcado na matriz.

A ideia do algoritimo é simplesmente percorrer o array de condições de vitória, como vamos estar percorrendo este array, para cada iteração nós vamos ter um array que contém outro array dentro dele com todas as infomacões da posição de cada elemento em condição de vitória. Tomamos como exemplo o segundo array que representa:

[ [0,0], [0,1], [0,2] ]

Esta posição representa uma vitória conforme a imagem abaixo:

Durante o loop eu consigo fazer este tipo de verificação com a seguinte instrução abaixo em javascript:

posicoes_validas.forEach((posicao, k) => {
    let e1i = posicao[0][0];
    let e1j = posicao[0][1];

    let e2i = posicao[1][0];
    let e2j = posicao[1][1];

    let e3i = posicao[2][0];
    let e3j = posicao[2][1];

//continua...

Neste código acima tudo que ele busca fazer é apenas acessar o array da vez durante o loop, este array é representado pela variável “posicao” que armazena dentro de si a posição de cada um dos elementos em condição de vitória.

Lembre-se bem que apesar da instrução acima poder confundir um pouco, tenha em mente que os termos posicao[0][0] e posicao[0][1] das variáveis e1i e e1j, o primeiro 0 em colchetes se referencia ao primeiro elemento do array [ [0,0], [0,1], [0,2] ].

Ou seja, para eu acessar o valor 0 dentro deste array, eu preciso declarar [0][0], para acessar o segundo 0 seria [0][1]. Para acessar os valores 0 e 1 da segunda posição deste array, seria: [1][0] para obter o valor 0 e [1][1] para obter o valor 1. Perceba que este exemplo se enquadra perfeitamente na instrução do código abaixo em:

let e2i = posicao[1][0];
let e2j = posicao[1][1];

Tendo isso em mente, a cada iteração você terá armazenado nas variáveis:

let e1i = posicao[0][0];
let e1j = posicao[0][1];

let e2i = posicao[1][0];
let e2j = posicao[1][1];

let e3i = posicao[2][0];
let e3j = posicao[2][1];

Todas as posições que configuram uma vitória no jogo da velha. Sendo assim, se em todas estas posições forem encontrados a mesma string, seja ‘O’ ou ‘X’, nós vamos conseguir encontrar a condição de vitória e podemos parar o loop.

A instrução abaixo verifica se a condição foi satisfeita, se sim, conseguimos identificar que houve uma vitória:

if(jogo_da_velha[e1i][e1j] == 'o' && jogo_da_velha[e2i][e2j] == 'o' && jogo_da_velha[e3i][e3j] == 'o') {
    console.log("bolinha ganhou!");
}


if(jogo_da_velha[e1i][e1j] == 'x' && jogo_da_velha[e2i][e2j] == 'x' && jogo_da_velha[e3i][e3j] == 'x') {
    console.log("x ganhou!");
}

Perceba que as intruções if, estão verificando exatamente três posições que representam as condições necessárias para conseguirmos identificar uma vitória.

Veja o código completo abaixo

Copie e cole este código em algum lugar para rodar este javascript.

const responses = [
    [ [0,0], [1,1], [2,2] ],
    [ [0,0], [0,1], [0,2] ],
    [ [1,0], [1,1], [1,2] ],
    [ [2,0], [2,1], [2,2] ],
    [ [0,0], [1,0], [2,0] ],
    [ [0,1], [1,1], [2,1] ],
    [ [0,2], [1,2], [2,2] ],
    [ [0,2], [1,1], [2,0] ]
];

let table = [
    ['o', 'o', 'x'],
    [' ', ' ', 'x'],
    ['x', 'o', 'x']
];

responses.forEach((response, k) => {
     let e1i = response[0][0];
     let e1j = response[0][1];

    let e2i = response[1][0];
    let e2j = response[1][1];

    let e3i = response[2][0];
    let e3j = response[2][1];

    if(table[e1i][e1j] == 'o' && table[e2i][e2j] == 'o' && table[e3i][e3j] == 'o') {
        console.log("bolinha ganhou!");
    }

    if(table[e1i][e1j] == 'x' && table[e2i][e2j] == 'x' && table[e3i][e3j] == 'x') {
        console.log("x ganhou!");
    }
});

Finalizo aqui este artigo e até a próxima!