Este projeto implementa o clássico jogo da velha (Tic-Tac-Toe) com uma inteligência artificial que utiliza o algoritmo Minimax para tomar decisões. O jogo é jogado no terminal entre um jogador humano e o computador.
O objetivo do jogo da velha é alinhar três de suas peças em uma linha horizontal, vertical ou diagonal antes do oponente. No jogo implementado, você pode escolher ser "X" ou "O", e o computador assumirá a outra escolha.
Aqui estão os principais recursos e detalhes de funcionamento do projeto:
- O jogador humano pode escolher ser "X" ou "O".
- O computador assume a escolha restante.
- O jogador humano decide se deseja começar primeiro ou não.
- O algoritmo Minimax é usado pelo computador para tomar decisões de jogadas.
- O jogo é renderizado no terminal, e o jogador humano faz suas jogadas usando o teclado numérico (1 a 9).
- O jogo verifica vitórias, derrotas e empates, exibindo mensagens apropriadas.
- O jogador pode optar por jogar novamente após o término de uma partida.
- Clone o repositório para sua máquina local.
- Execute o arquivo MinMaxVelha.py, utilizando: python3 MinMaxVelha.py
- Escolha ser "X" ou "O" como jogador humano.
- Escolha se deseja começar primeiro ou não.
- Use o teclado numérico para fazer suas jogadas (1 a 9) durante o jogo
- Após o término da partida, você pode optar por jogar novamente.
O algoritmo Minimax é utilizado pelo computador para tomar decisões sobre as jogadas. Ele funciona da seguinte forma:
- O algoritmo explora todas as possíveis jogadas do jogador humano e do computador, construindo uma árvore de decisão.
- Ele avalia o estado de cada nó da árvore com base em uma função de avaliação.
- O computador escolhe a jogada que maximiza seu valor, enquanto o jogador humano escolhe a jogada que minimiza o valor.
- A Poda Alpha-Beta é implementada para otimizar a busca, eliminando ramos que não afetarão a escolha final.
Segue abaixo o funcionamento do algoritmo minmax
Basicamente ela explora todas as possibilidades de jogadas(na sua respectiva vez de jogar), e vê a melhor posição. Para tornar o algoritmo mais eficiente foi utilizado o conceito de poda na busca(pruning the search on backtracking). O algoritmo é de busca competitiva, isso em IA significa que em jogos mais comuns são aqueles de ambientes determinísticos, completamente observáveis em que existem dois agentes cujas ações se alternam e os valores de utilidade são iguais e simétricos. Por exemplo, se um jogador ganha, recebe +1, o outro que perde recebe -1.
Com o algoritmo MinMaxAlfaBeta usamos a busca em que a cada turno um jogador faz sua ação(min ou max) sendo max tentando o maior valor possível para o grau da árvore, e min tentando o menor possível.
Dessa forma criamos um jogador "mestre" do qual NÃO É POSSÍVEL VENCER, pois para um jogo pequeno como jogo da velha, ele sempre irá pegar a posição mais favorável no tabuleiro. Logo o melhor resultado que o adversário da IA irá conseguir é o empate
