O jogo
Tic-tac-toe é um jogo muito popular para dois jogadores, X e O, que se revezam marcando os espaços em uma grade de 3×3. O jogador que conseguir colocar três de suas marcas em uma linha vertical, horizontal ou diagonal ganha o jogo.,
Propriedades Matemáticas
a Partir de um ponto de vista matemático, o jogo tem duas propriedades importantes:
Propriedade 1:
O jogo admite o jogador que usa esta estratégia ideal será vitória ou empate, mas ele não irá perder.
Property 2:
The number of possible different matches is relatively small.
no início, o primeiro jogador pode marcar qualquer um dos 9 espaços. Na curva seguinte, o segundo jogador pode marcar um dos 8 espaços restantes e assim por diante., O jogo continua até que todos os espaços estejam marcados ou um dos jogadores ganhar.
é então fácil de entender que o número total de fósforos diferentes é menor que:
987….1 = 9! = 362880
Que é um número razoavelmente pequeno para um computador.
o algoritmo
das propriedades 1 e 2 segue-se que um algoritmo prático e geral para ganhar/desenhar o jogo é usar a pesquisa Alfa Beta.,
em cada turno, o algoritmo avalia todas as possíveis consequências de cada movimento (possível devido à propriedade 2) e escolhe o que irá garantir uma vitória ou um empate (possível devido à propriedade 1).
Um jogador AI que escolhe cada movimento com o alpha beta algoritmo de busca nunca vai perder. Para tornar o jogo mais realista, é bom introduzir um fator estocástico para que cada vez com uma probabilidade pré-definida o jogador de IA se mova aleatoriamente ao invés de seguir o algoritmo alpha beta., Isso vai tornar o jogo mais realista, como ele vai fazer o jogador de IA mais humano e, às vezes, ele vai perder.