Uma abordagem de pontuação para oponentes de computador que precisa ser equilibrada

Esta pergunta é sobre uma abordagem aos oponentes de computador que eu criei e que estão sendo usados ​​atualmente ou planejamos ser usados ​​em vários jogos de computador.

fundo

No ano passado, ao tentar melhorar um oponente de computador para um jogo chamado "Minesweeper Flags" (breve descrição: Uma versão multiplayer baseada em turnos do Minesweeper, na qual você precisa levar mais minas que seu oponente) , mudei fortemente a maneira como meus algoritmos funcionavam . Em vez de usar uma abordagem como if-else-if-else, estou usando um conjunto de "pontuadores" com pesos especificados para determinar qual é a melhor jogada.

Você pode pensar que, para um jogo como o Minesweeper Flags, é apenas fazer movimentos que oferecem a maior probabilidade de pegar uma mina, mas não é tão simples assim. O movimento que o computador fará geralmente depende de vários recursos para esse movimento específico no estado atual do jogo. Exemplos de recursos:

• Qual é a probabilidade desse movimento marcar uma mina?
• Qual é a probabilidade de revelar algo ao meu oponente aqui?

Descrição do sistema

O sistema basicamente funciona assim:

1. "Pré-marcadores": Algumas pré-análises são feitas para o estado atual do jogo (em termos das Bandeiras do Campo Minado, isso geralmente é: Calculando todas as probabilidades)
2. "Artilheiros": Um conjunto de artilheiros comuns é solicitado a determinar a pontuação para cada jogada possível, cada apontador aplica pontuações de acordo com seus próprios critérios. Os apontadores podem verificar os resultados da pré-análise que foi feita.
3. As pontuações calculadas na etapa acima são somadas e estão definidas para serem as pontuações de uma jogada.
4. Os movimentos são classificados de acordo com sua pontuação e classificados de forma que todos os movimentos com a mesma pontuação obtenham a mesma classificação.
5. "Pós-marcadores": o resultado acima pode ser enviado aos "Pós-marcadores" que têm a possibilidade de modificar as pontuações de qualquer campo da maneira que desejar, de acordo com as próprias regras do pós-marcador.

Ao combinar um monte de pré-marcadores, marcadores (com seus pesos) e pós-marcadores, torna-se o que eu chamo de configuração de pontuação .

Resultado de exemplo

Este é um exemplo de pontuação aplicada às Bandeiras do Campo Minado. Este é o mapa que foi pontuado:

E esta é a saída de uma configuração de pontuação real. Ele mostra a classificação dos movimentos possíveis, onde 1 é a melhor classificação e foi destacada em branco:

Graças à criação de código altamente flexível, essa abordagem de IA também pode ser inserida em outros jogos.

Vantagens e desvantagens

Abaixo estão algumas vantagens e desvantagens deste sistema que consigo pensar em mim

Vantagens

• É muito fácil criar várias configurações diferentes para IAs.
• É possível usar com algoritmos genéticos: cada apontador tem um peso associado, o peso pode se tornar o gene.
• Usando algumas ferramentas, é possível verificar por que uma jogada específica foi feita e quais apontadores foram os principais responsáveis ​​por essa jogada
• Usando ferramentas, é possível criar um mapa da pontuação geral / classificação dos movimentos possíveis (como na captura de tela acima)
• Aplicando pontuações na maneira como o ser humano toca, é possível criar um "#AI_Mirror" que tenta fazer movimentos que acha que o ser humano faria

Desvantagens

• Pode ser extremamente difícil ajustar uma configuração de pontuação "corretamente", para tornar a IA o melhor possível.

Questões

• O sistema que eu construí aqui é amplamente conhecido no mundo da IA? Como seria chamado em termos reais de IA?

• Essa abordagem faz sentido ou existe uma abordagem diferente que você recomendaria?

• De que maneiras existem que poderiam facilitar o processo de ajustar uma configuração de pontuação?

Com relação à última pergunta, estou ciente da possibilidade de usar algoritmos genéticos, também estou ciente do SARSA (e acho que meus marcadores se assemelham à descrição de recursos desse site com pesos, mas, pelo meu entendimento, não foi exatamente isso que criei aqui). Eu acho que um problema com a SARSA é que você não conhece a recompensa até o jogo terminar, a melhor jogada é geralmente uma jogada que não dá uma recompensa (uma mina). Suas chances atuais de ganhar dependem da pontuação atual (quantas minas você e seu oponente fizeram) e a aparência do mapa atual.

_{Esta pergunta foi originalmente publicada em um site agora extinto de Inteligência Artificial .
O código (Java) usado para essa abordagem agora foi publicado na Revisão de Código .}

Em geral, é um sistema especialista (como lógica difusa). Como você não está executando um algoritmo para realizar feedback sobre os parâmetros de decisão com base na saída, isso não é realmente um aprendizado. No entanto, realizar feedback não é o único indicador se um alogirthm é AI. Alguém poderia argumentar que, se ele agir de uma maneira que pareça inteligente, isso é tudo o que importa - especialmente quando o jogo é jogado por um oponente humano.

O tipo de algoritmo que você especificou é realmente uma equação parametrizada, o tipo que você encontrará nos cálculos de seguro. Após cada movimento, o espaço de entrada muda, mas o algoritmo não precisa de memória do estado anterior; portanto, trata cada movimento como um novo quadro separado.

Usando algoritmos genéticos

Existem duas opções claras para algoritmos genéticos:

• Use os parâmetros para o genoma (como você sugeriu). Você otimizará as regras que possui, mas ainda terá um sistema especialista.
• Use o Learning Classifier System (LCS) para escolher as regras para você. Um LCS é um tipo de algoritmo genético em que você codifica as regras e os parâmetros. Eles levam mais tempo para convergir e são sensíveis à função de condicionamento físico. Eu acho que a maneira resultante de jogar pode ser mais interessante para ele.

Recozimento simulado

Outra maneira de resolver o problema é usar o Simulated Annealing (SA). Seu problema é um espaço de entrada limitado e você pode escrever analiticamente uma função que encontre o melhor quadrado para escolher em qualquer cenário. O uso do recozimento simulado encontrará um ótimo global para seus parâmetros.

Em torná-lo muito bom

Eu sei que você deseja que o algoritmo seja o melhor possível, mas não esqueça que um humano está jogando contra ele. Existe uma maneira taticamente perfeita de jogar esse tipo de jogo determinístico e, se o jogador de IA o fizer, seria apenas pura sorte, o que significa que o jogador vence.

Sim, a técnica de atribuir pontuações com base em certos aspectos da posição é padrão ao escrever AIs para jogar. Por exemplo, quase todos os programas de xadrez funcionam marcando posições com base mais significativa nas peças disponíveis, com bônus menores com base em suas posições (por exemplo, peões se protegendo). Eles então tentam calcular a melhor jogada disponível usando um algoritmo de pesquisa adversário, como alfa-beta.

A pesquisa adversa pode ser difícil aqui por causa do grande fator de ramificação - em qualquer posição, os movimentos legais são para marcar ou revelar qualquer quadrado desconhecido. Por outro lado, é possível reduzir muito o fator de ramificação por heurísticas. Por exemplo, marcar ou revelar um quadrado sobre o qual você não sabe nada muito raramente será a melhor jogada. Por outro lado, se você souber a localização de algumas minas não marcadas, marcar uma delas presumivelmente será a melhor jogada, na maioria das vezes. Manter uma tabela de transposição também provavelmente ajudaria.