Estou tentando implementar um algoritmo de IA para o Bomberman. Atualmente, tenho uma implementação rudimentar funcional, mas não muito inteligente (a IA atual é excessivamente zelosa ao colocar bombas).
Esta é a primeira IA que eu já tentei implementar e estou um pouco preso. Os algoritmos mais sofisticados que tenho em mente (aqueles que espero tomar melhores decisões) são complicados demais para serem boas soluções.
Quais dicas gerais você tem para implementar uma IA do Bomberman? Existem abordagens radicalmente diferentes para tornar o bot mais defensivo ou ofensivo?
Edit: algoritmo atual
Meu algoritmo atual é mais ou menos assim (pseudo-código):
1) Tente colocar uma bomba e, em seguida, encontre uma célula segura de todas as bombas, incluindo a que você acabou de colocar. Para encontrar essa célula, percorra as quatro direções; se você encontrar uma célula divergente segura e alcançá-la a tempo (por exemplo, se a direção for para cima ou para baixo, procure uma célula que se encontre à esquerda ou à direita desse caminho), é seguro colocar uma bomba e mover-se nessa direção.
2) Se você não encontrar células divergentes seguras, tente NÃO colocar uma bomba e olhe novamente. Desta vez, você só precisará procurar uma célula segura em apenas uma direção (não precisa divergir dela).
3) Se você ainda não conseguir encontrar uma célula segura, não faça nada.
for $(direction) in (up, down, left, right):
place bomb at current location
if (can find and reach divergent safe cell in current $(direction)):
bomb = true
move = $(direction)
return
for $(direction) in (up, down, left, right):
do not place bomb at current location
if (any safe cell in the current $(direction)):
bomb = false
move = $(direction)
return
else:
bomb = false
move = stay_put
Esse algoritmo deixa o bot muito feliz em disparar (ele colocará bombas com muita frequência). Ele não se mata, mas tem o hábito de se tornar vulnerável entrando em becos sem saída, onde pode ser bloqueado e morto pelos outros jogadores.
Você tem alguma sugestão de como eu posso melhorar esse algoritmo? Ou talvez eu devesse tentar algo completamente diferente?
Um dos problemas desse algoritmo é que ele tende a deixar o bot com muito poucas (geralmente apenas uma) células seguras nas quais ele pode estar. Isso ocorre porque o bot deixa um rastro de bombas para trás, desde que não se mate.
No entanto, deixar um rastro de bombas para trás deixa poucos lugares onde você pode se esconder. Se um dos outros jogadores ou bots decidir colocar uma bomba em algum lugar perto de você, muitas vezes acontece que você não tem onde se esconder e você morre.
Preciso de uma maneira melhor de decidir quando colocar bombas.
Respostas:
O problema que você está enfrentando é que sua IA nunca para para tomar uma decisão inteligente sobre onde deve colocar sua próxima bomba, o que a deixa cair bombas sempre que pode e depois elaborando "merda, merda, o que eu faço agora! ? "
Parando para pensar
No momento, sua IA apenas vagueia para lugar nenhum em particular. Às vezes, no entanto, ele deve realmente estar se movendo para um alvo. Por exemplo, se ele vê um poder e pensa que pode alcançá-lo antes do jogador, talvez deva encontrar um caminho seguro para esse ladrilho e se mover para lá, mantendo-se atento às bombas e evitando-as pelo caminho.
O mesmo comportamento de movimentação para o alvo pode ser usado quando se pensa em onde colocar sua próxima bomba .
Quando sua IA pode colocar uma bomba, em vez de fazê-lo imediatamente, deve usar brevemente um algoritmo de pesquisa para escolher os locais de colocação de bombas disponíveis com base em critérios como:
Quando essa decisão foi tomada, a IA escolheu um local de colocação de bombas e um local para se esconder de sua explosão. Agora ele pode caminhar até o local, colocar sua bomba e depois caminhar até seu esconderijo. Quando chegar ao seu esconderijo, convém continuar andando e encontrando os locais das bombas (se houver várias bombas), desde que tenha em mente evitar o caminho da bomba que caminhou aqui para evitar.
Ao caminhar e encontrar um caminho seguro
Você pode desenvolver para a sua IA um único método walk-to-point e usá-lo sempre que quiser que ele caminhe em algum lugar. Este método pode usar o algoritmo de busca A * para encontrar seu caminho.
Para manter a IA segura, convém verificar novamente seu caminho sempre que uma nova bomba for colocada. Para evitar explosões, ele pode verificar o tempo até a bomba explodir e considerar um possível ladrilho de explosão seguro para atravessar se a bomba não explodir enquanto estiver atravessando esse ladrilho - e se não for seguro, tratá-lo como um ladrilho intransitável .
Para apresentar falhas de IA (para que às vezes possa explodir), deve ocorrer erros de cálculo: esquecer uma bomba distraidamente, subestimar o tamanho da explosão ou o tempo até a bomba explodir, etc.
Nota lateral: Você também pode fazer com que sua caminhada aleatória pareça mais objetiva, escolhendo aleatoriamente pontos para caminhar, ou sempre tendo em mente um novo local de colocação de bombas para caminhar, em vez de apenas escolher aleatoriamente um bloco adjacente para o qual caminhar. Dessa forma, ele não ficará vagando no mesmo local como se não pudesse se decidir.
fonte