1

Pitch: Uma IA de Batalha Naval sem machine learning: o que as regras já provam

Dá para fazer um oponente de Batalha Naval bem competente sem modelo, sem treino e sem nenhuma heurística mágica. O modo Difícil do nosso jogo tem três ideias, e todas saem das próprias regras. Depois de explicar cada uma, mostro quanto elas valem em 20.000 partidas simuladas.

As regras usadas aqui: mar de 10 × 10, cinco navios retos (5, 4, 3, 3 e 2 quadrados) que nunca se encostam, nem pela quina.

A regra zero: nada de espiar

A função recebe o estado do mar, mas só lê o que um jogador também saberia: onde já atirou, quais acertos pertencem a navios afundados e quais tamanhos ainda estão flutuando. Um computador que olha as posições não é difícil, é trapaceiro.

1. Riscar o que as regras já provam ser água

Como dois navios nunca se encostam, cada informação elimina casas de graça:

  • toda a borda de um navio afundado é água;
  • as diagonais de um acerto também são água, mesmo com o navio ainda vivo, porque um navio reto não ocupa a diagonal.

Essas casas saem da lista de candidatas antes de qualquer outra decisão:

for (const h of live) for (const d of diagonals(h)) water.add(d);
const candidates = open.filter((i) => !water.has(i));

2. Depois de acertar, terminar o navio

Com um acerto, os alvos são os quatro vizinhos ortogonais. Com dois acertos, a direção está definida e só restam as duas pontas da linha. Enquanto existe navio ferido, o computador não procura outro.

3. Procurar em xadrez, com o passo do menor navio vivo

Esta é a parte de que eu mais gosto:

const afloat = sea.ships.filter((s) => !isSunk(sea, s)).map((s) => s.cells.length);
const step = afloat.length ? Math.min(...afloat) : 1;
const parity = candidates.filter((i) => {
  const [x, y] = xy(i);
  return (x + y) % step === 0;
});

Por que isso não deixa navio nenhum escapar? Um navio reto de tamanho L ocupa casas em que x + y assume L valores consecutivos. Entre step ou mais inteiros consecutivos, sempre existe um múltiplo de step. Como todo navio vivo tem tamanho maior ou igual a step, todo navio vivo cruza pelo menos uma casa da grade.

E o melhor: quando o menor navio afunda, step pode crescer e a grade fica mais esparsa sozinha. Sobrando só navios de 3 ou mais, basta olhar uma diagonal a cada três.

Quanto isso vale, medido

Rodei o código real em 20.000 partidas por modo, com frotas aleatórias, contando os tiros até afundar tudo:

ModoMédiaMedianaPior partida
Fácil (tiros ao acaso)95,497100
Difícil sem o xadrez49,85085
Difícil completo44,24468

Duas leituras:

  • A maior parte do ganho vem de seguir o navio e de descartar água: de 95,4 para 49,8 tiros.
  • O xadrez economiza 5,6 tiros na média, mas o efeito mais visível está nas partidas ruins: o percentil 95 cai de 66 para 55 tiros.

Dois limites: esses números valem para frotas aleatórias e para a regra de navios que não se encostam, que ajuda bastante o computador. E esta não é a estratégia ótima: dá para ir além calculando, a cada turno, a densidade de posições possíveis de cada navio. Não implementamos nem medimos essa versão, então não sei dizer quanto ela ganharia aqui.

Testar na prática

Este é o código do jogo gratuito de Batalha Naval que fazemos no Gift Club. Roda no navegador e não precisa de cadastro. Se quiser ver a grade em ação, jogue no modo Difícil e repare onde caem os primeiros tiros. Se você tiver uma estratégia melhor, conta nos comentários.

Carregando publicação patrocinada...