Colocando uma bomba inteligente AI da Bomberman

13

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.

Paul Manta
fonte
É difícil pensar em algo que funcione 100% do nada. Mas talvez se você adicionar o algoritmo que você possui atualmente, todos nós podemos ajudar a melhorá-lo gradualmente. Você provavelmente também não é o primeiro hobby a tentar implementar uma IA do Bomberman, e eu encontrei algumas competições da AI do Bomberman com uma pesquisa aleatória no Google que poderia ser uma fonte inestimável de informações para você.
Roy T.
Eu acho que você pode generalizar a IA do homem-bomba em duas coisas: 1) tentando se proteger de ser atingido por bombas de outros jogadores 2) colocando bombas no tabuleiro do jogo para tentar fazer os outros morrerem (mantendo a regra 1 em mente): para evitar ser atingido / preso por suas próprias bombas).
tigrou
Provavelmente seria melhor se você publicasse pelo menos uma visão geral de alto nível da sua implementação atual (supondo que seja muito código) e talvez possamos ajudá-lo a resolver seu problema, pois eles são excessivamente zelosos ao colocar bombas.
Tétrada
@ Tetrad Estou no processo de implementar um novo algoritmo. Vou ver como isso vai e postar o algoritmo aqui, se necessário.
Paul Manta
embora não seja uma dica real, mas você pode dar uma olhada no código clanbomber . é um jogo de muitas maneiras semelhante ao bomberman.
Ali1S232

Respostas:

4

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:

  • É perto? (para que ele não caminhe até o canto diagonal oposto do mapa toda vez que quiser colocar uma bomba)
  • Existe um lugar onde eu possa me esconder da explosão - e posso chegar lá antes que a bomba exploda?
  • A explosão explodirá telhas e me dará poderes?
  • Isso potencialmente atacará o jogador? (uma IA mais fácil pode evitar isso no início do jogo, uma IA agressiva vai perseguir isso - sem esquecer os upgrades)

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.

doppelgreener
fonte
Esqueci de dar alguns detalhes relevantes sobre o jogo. É uma versão simplificada do Bomberman: sem power-ups, os jogadores sempre podem colocar bombas ilimitadas e as bombas sempre têm alcance máximo (de uma extremidade ao outro do mapa). O sistema de pontos é diferente também ... [continuação]
Paul Manta
[cont.] Você ganha 1 ponto por colocar uma bomba, mas 0 ponto por destruir uma parede. Você também recebe 30 pontos por morte, 15 por assistência e -20 por suicídio. [continua]
Paul Manta
[cont.] Com isso em mente, a IA deve tentar colocar uma bomba com a maior frequência possível (porque colocar bombas dá bombas), mas não precisa ser particularmente cuidadoso com o local onde a bomba é colocada. É preciso ter cuidado para sempre ter um lugar seguro para ir. [continua]
Paul Manta
[cont.] Você acha que, ao escolher uma direção, basta escolher a que leva a uma área segura . Em vez de procurar uma célula segura, eu procuraria a maior área segura, para poder me esconder de bombas colocadas por outros jogadores também, não apenas a minha. Além disso, seria uma boa ideia favorecer direções que me aproximem de um dos outros jogadores?
Paul Manta
3
Bem, então não estamos falando sobre Bomberman e sua IA! Nós somos apenas sobre um jogo com bombas que se assemelha superficialmente a Bomberman, mas sob o capô é completamente diferente e incentiva você a ser um gatilho Happy Lunatic , e eu tenho muito menos experiência em lidar com esse jogo.
22412 doppelgreener