Um pouco de fundo: como uma maneira de aprender árvores multinode em C ++, decidi gerar todas as placas TicTacToe possíveis e armazená-las em uma árvore de tal forma que o ramo começando em um nó são todas as placas que podem ser seguidas desse nó, e os filhos de um nó são placas que seguem em um movimento. Depois disso, achei que seria divertido escrever uma IA para jogar TicTacToe usando essa árvore como uma árvore de decisão.

O TTT é um problema solucionável em que um jogador perfeito nunca perderá, por isso pareceu uma AI fácil codificar pela primeira vez a tentar uma IA.

Agora, quando implementei a IA pela primeira vez, voltei e adicionei dois campos a cada nó após a geração: o número de vezes que o X vencerá e o número de vezes O vencerá em todas as crianças abaixo desse nó. Eu imaginei que a melhor solução era simplesmente ter minha IA em cada jogada escolhida e descer na subárvore onde ela ganha mais vezes. Então descobri que, embora seja perfeito na maior parte do tempo, descobri maneiras de superá-lo. Não foi um problema com o meu código, simplesmente um problema com a maneira como eu fiz a AI escolher seu caminho.

Então decidi escolher a árvore com as vitórias máximas para o computador ou as perdas máximas para o humano, o que fosse mais. Isso fez com que fosse melhor, mas ainda não era perfeito. Eu ainda poderia vencê-lo.

Então eu tenho duas idéias e espero que a entrada seja melhor:

1) Em vez de maximizar os ganhos ou perdas, em vez disso eu poderia atribuir valores de 1 para uma vitória, 0 para um empate e -1 para uma derrota. Em seguida, escolher a árvore com o maior valor será o melhor movimento, porque o próximo nó não pode ser um movimento que resulte em uma perda. É uma mudança fácil na geração da placa, mas mantém o mesmo espaço de pesquisa e uso de memória. Ou...

2) Durante a geração da board, se houver uma board tal que X ou O venham a ganhar na próxima jogada, apenas a criança que impedir essa vitória será gerada. Nenhum outro nó filho será considerado e, em seguida, a geração continuará normalmente após isso. Ele encolhe o tamanho da árvore, mas então eu tenho que implementar um algoritmo para determinar se existe um único movimento e acho que isso só pode ser feito em tempo linear (fazendo a geração de tabuleiros muito mais lenta, eu acho?)

Qual é melhor ou existe uma solução ainda melhor?