Jogo da Velha desenvolvido na linguagem C para a displina Algoritmos e Estruturas de Dados II. Possui a implementação de uma inteligência artificial desenvolvida pelo algoritmo minimax.
A utilização de TADs é amplamente difundida na linguagem C. Trata-se de um recurso que permite a modularização do código e seu reaproveitamento. Sua funcionalidade é análoga à das classes nas linguagens orientadas a objeto. O trabalho em questão aplica isso através da simulação de um jogo da velha que envolve interação do usuário e até mesmo a criação de uma inteligência artificial rudimentar para interagir, além de manipulação de arquivos.
O tipo de dados escolhido para o trabalho foi o vetor de duas dimensões chamado tab. O usuário digitará um valor N que indicará a dimensão da matriz que será, então, alocada dinamicamente na memória.
O TAD possui três variáveis externas do tipo inteiro, chamadas ERRO, TRUE e FALSE. Elas foram criadas para aumentar a legibilidade do código e permitir que ele se torne mais facilmente portável a linguagens diferentes. Mesmo que a linguagem C já ofereça recursos para retornar verdadeiro ou falso, ao usar variáveis específicas eu deixo mais claro quando o valor inteiro de retorno tem algum significado ou quando ele apenas sinaliza verdadeiro ou falso.
As variáveis recebem o modificador extern para permitir que elas, assim como as funções, sejam inicializadas no .c e não no .h e seus valores escolhidos foram, respectivamente, -1,1 e 0.
void SetTamanho(Tabuleiro *T, int n): recebe um tabuleiro por referência e define o tamanho dele como sendo n. Se n for maior que 10, menor que 0 ou se outra chamada da função já foi resolvida (o que implica que o vetor já foi alocado), a função retorna sem fazer nada. Caso contrário, ele aloca dinamicamente a matriz e cada uma de suas linhas.
int GetTamanho(Tabuleiro T): Recebe um tabuleiro e retorna seu tamanho. Foi feita para poupar o programador da tarefa de acessar a variável n dentro do tabuleiro, o que também vai a favor do princípio dos TADs de que é responsabilidade do programador do TAD criar métodos para obter as características da variável por ele criada.
void LiberaTamanho(Tabuleiro *T): Recebe um tabuleiro por referência e libera a memória alocada dinamicamente pela função setTamanho. Vale lembrar que, devido a decisões tomadas na setTamanho, uma vez liberada a memória não poderá ser realocada na mesma execução do programa, logo, esta função deve ser usada apenas quando se tem certeza que o vetor não será mais acessado.
void SetElemento(Tabuleiro *T, int i, int j, char c): Recebe um tabuleiro por referência e posiciona o char c na posição tab[i][j]. Se i e j forem fora dos limites, retorna sem fazer nada.
void MarcaTodos(Tabuleiro *T, char c): Recebe um tabuleiro por referência e posiciona o char c em todas as posições do tabuleiro.
char GetElemento(Tabuleiro T, int i, int j): Recebe um tabuleiro e retorna o elemento na posição tab[i][j]. Similar ao setElemento, esta também verifica se i e j são valores válidos. Porém, devido ao tipo de retorno, desta vez é retornado um valor de erro int TestaDiferente(Tabuleiro T, int i): Recebe uma linha i e compara todos os elementos entre si. Se todos forem diferentes, retorna TRUE. Se houverem dois ou mais iguais, retorna FALSE. Se i é um valor inválido, retorna ERRO.
void Imprime(Tabuleiro T): Recebe um tabuleiro, itera sobre ele e imprime na tela seus valores. Valores na mesma linha são separados por um espaço simples e as linhas são separadas umas das outras por uma quebra de linha.
int procuraElemento(Tabuleiro T,char c): Itera pela matriz à procura de um elemento equivalente ao parâmetro c. Retorna a primeira aparição dele; caso ele não exista, retorna erro. Para retornar corretamente o endereço do elemento, o valor correspondente à linha é multiplicado por 10 e somado à coluna. Por exemplo, se o elemento está na posição [2][2] o valor retornado é 22. A pesquisa usada é a pesquisa sequencial. Os valores são comparados um a um com o parâmetro e quando o sucesso acontece o valor é retornado.
int TestaLinha(Tabuleiro T, int i, char c): Recebe um tabuleiro por valor junto com um parâmetro para representar a linha e retorna TRUE se todos os valores da linha forem iguais aos do char, FALSE caso contrário e ERROR caso i seja um valor inválido.
int testaLinha(Tabuleiro T, int i): Recebe um tabuleiro por valor junto com um parâmetro para representar a linha e retorna TRUE se todos os valores da linha forem idênticos, FALSE caso contrário e ERROR caso i seja um valor inválido. Difere da função anterior ao passo em que não se importa se os valores são iguais a um terceiro parâmetro, apenas entre si.
int TestaColuna(Tabuleiro T, int j, char c): Recebe um tabuleiro por valor junto com um parâmetro para representar a coluna e retorna TRUE se todos os valores da coluna forem iguais aos do char, FALSE caso contrário e ERROR caso i seja um valor inválido.
int testaColuna(Tabuleiro T, int j): Recebe um tabuleiro por valor junto com um parâmetro para representar a coluna e retorna TRUE se todos os valores da coluna forem idênticos, FALSE caso contrário e ERROR caso i seja um valor inválido. Difere da função anterior ao passo em que não se importa se os valores são iguais a um terceiro parâmetro, apenas entre si.
int TestaDiagonalED(Tabuleiro T, char c): Recebe um tabuleiro por valor retorna TRUE se todos os valores da diagonal Esquerda-Direita (identificáveis por terem o valor da linha e da coluna iguais) forem iguais aos do char e FALSE caso contrário.
int testaDiagonalED(Tabuleiro T): Recebe um tabuleiro por valor retorna TRUE se todos os valores da diagonal Esquerda-Direita (identificáveis por terem o valor da linha e da coluna iguais) forem iguais e FALSE caso contrário. Difere da função anterior ao passo em que não se importa se os valores são iguais a um terceiro parâmetro, apenas entre si.
int TestaDiagonalDE(Tabuleiro T, char c): Recebe um tabuleiro por valor retorna TRUE se todos os valores da diagonal Direita-Esquerda (identificáveis por terem o valor da linha e da coluna, somados, igual ao tamanho do vetor menos um) forem iguais aos do char e FALSE caso contrário.
int testaDiagonalDE(Tabuleiro T): Recebe um tabuleiro por valor retorna TRUE se todos os valores da diagonal Direita-Esquerda (identificáveis por terem o valor da linha e da coluna, somados, igual ao tamanho do vetor menos um) forem iguais aos do char e FALSE caso contrário. Difere da função anterior ao passo em que não se importa se os valores são iguais a um terceiro parâmetro, apenas entre si.
Este programa pega os parâmetros a partir da linha de comando e, fazendo uma análise, decide o que executa.
Se o parâmetro for inválido ou não existir, o jogo padrão é o humano x máquina. Neste caso, a máquina joga usando o algoritmo recursivo minimax para que seja virtualmente invencível.
Se o parâmetro for 1, o jogo é o padrão humano x humano. Se for 3, será lido de um arquivo. Nota-se que, caso a leitura do arquivo termine em erro, seja porque o arquivo foi inválido, seja porque o arquivo terminou antes que a partida terminasse, o programa retorna e executa o humano x máquina.
Na hora do jogo em si, algumas decisões foram tomadas para verificar os dados. Caso os dados sejam inválidos, ambos os valores são descartados o usuário terá novas chances de inserir valores até que um válido seja devidamente inserido. Em todos os casos, uma mensagem de erro própria é exibida. É importante mencionar isso porque na hora de fazer a leitura por arquivo, basta um valor entre linha e coluna ser inválido para que ambos sejam descartados. Também é importante mencionar que eles são verificados juntos, ou seja, se seu primeiro parâmetro for inválido e o segundo válido, ele será descartado mesmo assim.
Por último, é importante já começar a detalhar o funcionamento do minimax, algoritmo usado para que a máquina jogue. Ele é um algoritmo que identifica a melhor jogada através da análise recursiva de todas as combinações possíveis. É muito usado na teoria de jogos para solucionar jogos determinísticos, especialmente aqueles com um número relativamente pequeno de combinações possíveis, tais como dama e jogo da velha. Em jogos estocásticos, como o de baralho, e determinísticos porém com ordem de 10^10 combinações possíveis, tais como xadrez, ele também pode ser usado mas precisa sofrer ajustes para prever uma jogada no cenário de a informação não ser perfeita e no cenário de não ser possível prever todas as combinações finais em tempo hábil.
void novoJogo(Tabuleiro *T): Recebe um tabuleiro, inicializa ele com “_” em todas as posições e imprime na tela. É a função usada para começar um jogo e reiniciar caso o anterior tenha sido concluído.
int isVencedor(Tabuleiro T,char c): Verifica as condições de vitória (linha, coluna e diagonais), retornando 1 caso exista um vencedor e 0 caso contrário.
void setVencedor(char *c,Tabuleiro *T): Função auxiliar que imprime na tela quem venceu e reinicia o jogo.
int verificarVencedor(Tabuleiro *T): Usa as funções isVencedor, isVelha e SetVencedor para ver se o jogo acabou e então, caso positivo, reinicia o jogo e retorna TRUE. Caso contrário, retorna FALSE.
int isVelha(Tabuleiro T): Verifica se todos os quadrados do tabuleiro estão ocupados por caracteres diferentes de “_”. Se encontra um, retorna FALSE, caso contrário, retorna TRUE. Importante salientar que, na hora de usar, esta função deve ser chamada depois das verifica vencedor pois ela vai retornar verdadeiro caso alguém tenha vencido o jogo no último movimento.
int jogar(Tabuleiro *T,int lin, int col, char c): Função que permita que o jogador humano jogue. Analisa se as linhas e colunas são válidas e retorna uma mensagem de erro caso não sejam. Depois analisa se o lugar está vago (isto é, se o caractere na posição é “_”) e emite uma mensagem de erro. Dado que os dados estejam certos, posiciona o char c na posição indicada.
void Jogar(Tabuleiro *T): Função usada para que a máquina jogue, ela é responsável por invocar a função minimax e analisar seus resultados.
double minimax(Tabuleiro *T,int player): Função que define a melhor jogada para a máquina. É recursiva e sua condição de parada é o jogo chegar a um final, seja este alguém vencer ou dar velha. Se ela venceu, retorna 1. Se o vencedor foi o oponente, retorna -1. Se deu velha, retorna 0. Os valores foram multiplicados por um valor arbitrariamente escolhido baseado na variável player para garantir que, dada duas escolhas que culminam com um resultado, ele dará preferência para a que garante o melhor resultado mais rápido ou o pior resultado mais lento.
Para identificar a melhor jogada, é criado um vetor análogo ao tabuleiro chamado moves, que é então inicializado com um valor pré-definido. O tabuleiro original é então percorrido, posição por posição, em busca dos espaços vagos, identificados pelo char “_”. Então, para cada espaço vago, a função minimax se chama recursivamente, passando como parâmetro o mesmo tabuleiro e um valor inteiro que é o valor recebido +1. O resultado desta chamada é guardado numa posição análoga no vetor tabuleiro.
Uma vez que o vetor moves tenha sido preenchido ele é percorrido e a partir disso a melhor escolha é decidida. A ideia é que, sendo velha um jogo de soma zero (para alguém vencer, outro tem necessariamente que perder), seu objetivo é maximizar o seu resultado enquanto o objetivo do oponente é minimizar o resultado para você (inclusive é disso que vem o nome minimax do algoritmo). Se for a vez do oponente (identificado a partir do resto da divisão da variável de controle por 2), percorre o vetor e retorna o resultado mais baixo. Se for a sua vez, percorre o vetor e retorna o resultado mais alto.
De modo a garantir variedade nas partidas, no caso de várias casas terem igual possibilidade, ele escolhe aleatoriamente entre elas. Desta forma, isso garante que a máquina não fará sempre os mesmos movimentos, desde que sejam equivalentes. Na hora de retornar, se foi uma chamada posterior, retorna o valor obtido para aquela posição. Agora se foi a primeira chamada, ao invés disso retorna a posição em si onde deve ser feita a jogada.
void Um(Tabuleiro *T): Função referente ao modo de jogo humano x máquina, definida como modo 1. Inicia um novo jogo e recebe o endereço da jogada do humano que, caso seja inválido, poderá jogar novamente. A máquina depois joga usando a função Jogar que invocará a minimax. Por último, se os jogadores desejarem, poderão jogar novamente.
void Dois(Tabuleiro *T): Análoga à um, mas ao invés de ser humano x máquina é humano x humano. As verificações de dados são feitas duas vezes ao invés de apenas uma o que implica num código com mais linhas mas que não necessariamente é mais complexo. Assim como no anterior, diversos jogos poderão ser jogados.
int Tres(Tabuleiro *T,char *file): Recebe um arquivo e lê os dados. Se em algum momento for encontrado um erro, retorna e executa a função Um. Caso contrário, o arquivo é lido sequencialmente até encontrar um caractere válido (no caso, os números 0, 1 e 2), ignorando todos os outros. O valor é então convertido para inteiro e salvo numa variável. A partir disso, a execução prossegue como nas funções anteriores.
Ao fazer o código, como já mencionado, eu optei por usar constantes para identificar casos em que o valor retornado significava verdadeiro, falso ou erro. Desta forma, eu não teria dificuldades de diferenciar, ao corrigir o código, um valor de retorno igual a zero e um valor de retorno igual a falso, que, na linguagem C, são equivalentes.
No jogo da velha, montei um algoritmo que soluciona ele, o que implica em uma complexidade maior do algoritmo como um todo.
void SetTamanho(Tabuleiro *T, int n):Executa algumas operações com O(1) para alocar a matriz e depois itera pelas n linhas para aloca-las dinamicamente, logo, O(n).
int GetTamanho(Tabuleiro T): Retorna apenas um valor independente dos parâmetros, logo, O(1).
void LiberaTamanho(Tabuleiro *T): Similar à setTamanho, itera pelas n linhas liberando a memória alocada e depois libera a memória da matriz em si, logo, complexidade O(n).
void SetElemento(Tabuleiro *T, int i, int j, char c): Executa apenas uma operação de atribuição que independe dos parâmetros. Complexidade O(1).
void MarcaTodos(Tabuleiro *T, char c): Itera pelas n linhas e n colunas da matriz para marcar todos os valores. Complexidade O(n²).
char GetElemento(Tabuleiro T, int i, int j): Executa apenas uma operação de retorno que independe dos parâmetros. Complexidade O(1).
int TestaDiferente(Tabuleiro T, int i): Pega uma linha de tamanho n e itera sobre ela comparando seus elementos. Complexidade O(n).
void Imprime(Tabuleiro T): Itera pelas n linhas e n colunas imprimindo seus valores. Complexidade O(n²).
int procuraElemento(Tabuleiro T,char c): Função interessante, itera sobre as linhas e colunas até encontrar um valor específico e retorna ele. Na melhor das hipóteses o valor está na primeira posição, o que resultaria numa complexidade O(1). Na pior ele está na última, o que resultaria numa complexidade O(n²). Já que a notação O especifica um limite, a complexidade desta função deve ser analisada usando o pior caso, o que resulta em O(n²).
int TestaLinha(Tabuleiro T, int i, char c), int TestaColuna(Tabuleiro T, int j, char c), int testaLinha(Tabuleiro T, int i), int testaColuna(Tabuleiro T, int j): Todas essas funções fazem essencialmente a mesma coisa: iteram sobre uma linha/coluna comparando os valores entre si. Logo, todas elas possuem um comportamento O(n) no pior caso.
int TestaDiagonalED(Tabuleiro T, char c), int TestaDiagonalDE(Tabuleiro T, char c), int testaDiagonalED(Tabuleiro T),i nt testaDiagonalDE(Tabuleiro T): De forma análoga aos anteriores, iteram sobre uma categoria do vetor. Neste caso, porém, trabalha-se com duas dimensões ao invés de uma o que implica que uma discussão maior sobre o código pode ser feita. Estas funções iteram simultaneamente sobre as linhas e as colunas; as funções testaDiagonalED fazem uma iteração com apenas uma variável de controle enquanto as TestaDiagonalDE fazem uma iteração com duas variáveis de controle. Em ambos os casos, são feitas apenas O(n) comparações, o que implica em complexidade final O(n).
void novoJogo(Tabuleiro *T): É a soma da complexidade da função marcaTodos com a Imprime. O(n²) + O(n²)= O(n²).
int isVencedor(Tabuleiro T,char c): Soma das funções testaDiagonal, testaLinha e testaColuna, todas O(n), por consequência, esta também é O(n).
void setVencedor(char *c,Tabuleiro *T): Executa função constante e a novoJogo que é O(n²). Logo, esta também é O(n²).
int verificarVencedor(Tabuleiro *T): Executa várias vezes a função isVencedor e algumas operações constantes. 3*O(n) + C = O(n).
int isVelha(Tabuleiro T): Itera sobre a matriz inteira atrás dos valores especificados. Iterar pela matriz é fazer n vezes n comparações, logo, complexidade O(n²).
int jogar(Tabuleiro *T,int lin, int col, char c): Faz verificações de dados de custo constant e imprime uma vez, operação O(n²). Complexidade O(n²).
double minimax(Tabuleiro *T,int player): Não irei demonstrar, mas a complexidade da minimax é O(n²).
void Jogar(Tabuleiro *T): Executa funções de custo constante, a minimax que é O(n²) e a jogar que é O(n²). Complexidade O(n²).
void Um(Tabuleiro *T): Executa, no máximo, n² jogadas. Cada jogada é composta de uma invocação da função jogar, cuja complexidade é O(n²). No total, temos n² execuções de algo que é O(n²), totalizando O(n^4).
void Dois(Tabuleiro *T): Executa, no máximo, n² jogadas. Cada jogada é composta de uma invocação da função jogar, cuja complexidade é O(n²). No total, temos n² execuções de algo que é O(n²), totalizando O(n^4).
int Tres(Tabuleiro *T,char *file): Análoga às anteriores, executa n² vezes a função jogar na pior das hipóteses, o que implica O(n^4).
int main(int argc, char *argv[]): Não importa qual caminho seja tomado, no fim das contas uma função O(n^4) será executada. Visto que o que importa é a maior complexidade, temos uma main que é O(n^4).