Redes neurais vs algoritmos genéticos em jogos como o Tic Tac Toe?

9

Atualmente, estou desenvolvendo um projeto para criar uma IA para jogar o jogo Gomoku (é como um jogo da velha, mas joguei em um tabuleiro de 15 * 15 e requer 5 em sequência para vencer). Eu já implementei com sucesso uma IA do jogo da velha perfeita usando Q learning e tendo estados / ações de jogos armazenados em uma tabela, mas para um tabuleiro de 15 * 15, os possíveis estados de jogo se tornam grandes demais para implementar este projeto.

Minha pergunta é: devo usar redes neurais ou algoritmos genéticos para esse problema? E, mais especificamente, como devo implementar isso?

Conway
fonte
2
Bem-vindo à AI! Excelente pergunta imho.
DukeZhou

Respostas:

7

Para o gomoku, parece um pouco exagerado usar redes neurais ou o algoritmo genético, pois ambos demoram um pouco e, com mais frequência do que não, não vão como você deseja. A árvore do jogo gomoku é bastante grande, mas você pode obter uma IA decente do minimax, poda da árvore do jogo e uma boa função heurística (que inclui contar metade e 2s, 3s, 4s, etc. etc) em oposição ao mapeamento fora de todo o espaço.

Se você não estiver familiarizado com a poda alfa beta e o minimax, consulte https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm

Se você realmente deseja usar redes neurais ou algoritmos genéticos, pode usar a experiência de aprendizado. Em relação às redes neurais, uma maneira de fazer isso é a seguinte:

  • Defina uma função heurística que recebe uma entrada do estado da placa (sequência de 0,1,2 para vazio, preto, branco) e gera um valor de "qualidade" do estado da placa. A rede neural é a nossa função heurística.
  • Supondo que as jogadas nesse jogo sejam ótimas, afaste-se da diferença entre a melhor jogada atualmente (pelos seus parâmetros atuais) e a que seus dados dizem ser a melhor. É assim que definimos nossa função de erro! Portanto, você está minimizando essa diferença para que o que a sua rede neural diz que é mais forte seja idealmente o que os dados do jogo dizem que é mais forte (a otimização dessa função de erro pode ser feita por meio de retropropagação ou algoritmo genético).
  • Idealmente, nesse ponto, agora você pode usar sua função de avaliação baseada em rede neural ('forte') para suas avaliações de movimentação da árvore de jogos em vez de heurísticas codificadas.

Claro que essa é apenas uma maneira, e você precisaria encontrar os dados do jogo primeiro.

Uma observação lateral: a aplicação do algoritmo genético pode ocorrer de várias maneiras, como otimização de parâmetros em uma rede neural, como mencionado acima, ou pesquisa em árvore de jogos, para garantir que você esteja claro como define a configuração do problema! O mesmo vale para formas alternativas de aplicar uma rede neural.

Finalmente, é útil saber que o gomuku está resolvido. Consulte /programming/6952607/ai-strategy-for-gomoku-a-variation-of-tic-tac-toe para obter os pensamentos e idéias de outras pessoas.

sma
fonte
2
Bom ponto sobre o gomoku como um jogo resolvido. Isso facilita a validação da força da IA ​​(ou seja, resolve o jogo e expressa o jogo perfeito, ou está apenas jogando de maneira mais otimizada do que um oponente, como no caso do AlphaGo.)
DukeZhou