Benchmark do Jev da TypeSafe em Batalha Naval: o modelo empatou com código simples

O Jev da TypeSafe não é um chatbot. Dás-lhe um estado e umas perguntas tipadas, e ele devolve distribuições de probabilidade. Perguntas "qual destas casas tem um navio" e recebes um número para cada casa, não uma frase.

O formato é interessante, por isso quis perceber se o julgamento é mesmo bom. A Batalha Naval acabou por ser uma boa forma de descobrir. As regras cabem num guardanapo, o tabuleiro é pequeno o suficiente para enviar por inteiro, e existe ali mesmo uma baseline conhecida que não usa modelo nenhum.

Sessenta jogos por estratégia, 6.000 chamadas ao modelo, 77 cêntimos.

Duas formas de perguntar

Construí dois jogadores com modelo.

O primeiro, a que chamei jevPure, é a medição verdadeira. Recebe o tabuleiro em bruto e todas as casas por tentar como opções, cerca de 90 a meio do jogo. O código fornece as regras e a lista de jogadas possíveis, mais nada. O resultado que sair é só dele.

O segundo, jevHybrid, é uma colaboração. Um solver de densidade conta todas as posições válidas dos navios que faltam para cada casa, fica com as 16 melhores, e descreve cada uma por palavras. Algo como "continua diretamente 1 acerto na linha de baixo; tem espaço para o navio maior ainda a flutuar; está na zona aberta do meio do tabuleiro". O modelo só escolhe entre essas 16.

Depois três jogadores que nunca chamam o modelo: tiros aleatórios como chão, uma regra simples de caça e perseguição (uma heurística), e o solver de densidade sozinho. A regra é do género que escreverias numa entrevista: procura às cegas até acertares, depois insiste à volta do acerto.

Os cinco jogaram os mesmos 60 tabuleiros, por isso todas as comparações são emparelhadas.

O quadro

Menos é melhor. Dezassete tiros é um jogo perfeito, 100 é o pior que consegues fazer.

Repara no jevPure por um instante. Com o tabuleiro todo e 90 opções, precisa de 85,5 tiros. Jogar aos palpites precisa de 95,3. Portanto está a ler o tabuleiro, e a diferença é real, o p é 1,3e-10.

Só que a heurística de caça e perseguição precisa de 51,9. O modelo perdeu para ela por 33,6 tiros e caiu em 59 dos 60 tabuleiros. Custou 65 cêntimos para ficar à frente dos palpites por pouco.

Porque é que se desfez

Duas razões, ambas na própria documentação da TypeSafe, e ambas que eu devia ter antecipado.

Todas as opções daquela pergunta de escolha têm a mesma etiqueta. A casa A1 e a casa H7 chegam as duas como "uma casa onde ainda não se disparou", porque não há mais nada honesto para dizer sobre elas. A lista de opções não transporta sinal nenhum e todo o trabalho cai em interpretar 2.791 caracteres de estado do tabuleiro.

A segunda razão é mais interessante. O Jev arredonda as probabilidades a duas casas decimais. Espalha uma distribuição por 90 opções e quase tudo arredonda para zero. Num tiro típico só seis casas voltavam com algum valor. O mapa de calor que construí para ver o raciocínio do modelo estava quase sempre vazio, e isso não era um erro meu a desenhá-lo.

Dá-lhe 16 opções descritas e o mesmo modelo chega aos 46,0 tiros, bem à frente da heurística. Mesmo modelo, mesmo tabuleiro, pergunta diferente.

A parte que eu queria que fosse verdade

É aqui que tenho de ter cuidado comigo próprio.

46,0 contra os 48,3 do solver de densidade parece o modelo a acrescentar algo por cima de código já bom. Era esse o título que eu queria. Também não é aquilo que os dados sustentam.

O intervalo de confiança dessa diferença passa pelo zero. O valor de p é 0,13. O modelo ganhou 31 dos 60 tabuleiros, o que é cara ou coroa com passos extra. Sessenta jogos conseguem detetar uma diferença de cerca de 4,7 tiros e a distância que medi é metade disso.

Média de tiros para afundar a frota, com intervalos de confiança a 95%. A sobreposição entre o jevHybrid e a Densidade é o resultado.

Portanto a afirmação honesta é que o jevHybrid iguala o melhor jogador só com código, em vez de o vencer. Resolver isto como deve ser exige à volta de 260 jogos por estratégia, o que dá duas horas e meia e mais 80 cêntimos. É provável que os corra. Mas até lá não vou descrever um empate como uma vitória.

O que posso dizer é mais estreito e continua a ser útil. O modelo faz trabalho a sério, e esse trabalho só aparece depois de o código já ter transformado o problema numa lista curta de opções descritas. Se lhe pedires para encontrar um navio num tabuleiro em bruto, é muito pior do que uma regra que escreverias de cabeça. Ou seja, a configuração em que o modelo parece bom é a mesma em que o código fez o trabalho difícil.

O enviesamento que quase publiquei

O resultado que realmente mudou a forma como vou construir benchmarks não tinha nada a ver com o modelo.

Andava a gerar os tabuleiros de forma uniformemente aleatória, o que me parecia obviamente neutro. Depois experimentei outras famílias. Navios encostados às bordas. Navios longe das bordas. Navios colocados de forma gananciosa nas casas que um mapa de densidade classifica como menos prováveis.

A ordem entre as minhas duas baselines de código inverteu-se.

O mecanismo deixa de ser subtil assim que o vês. O solver de densidade conta posições assumindo uma distribuição uniforme, por isso num tabuleiro vazio classifica o meio a 28,5 e a borda a 18,2 e procura primeiro no meio. Um tabuleiro com tudo encostado à borda põe as 17 casas de navio exatamente onde ele olha por último.

Tabuleiros uniformemente aleatórios não são um conjunto de teste neutro. São a única distribuição que o solver de densidade assume. E o solver de densidade é a fasquia a que eu estava a sujeitar o modelo, portanto testar só em tabuleiros aleatórios teria significado julgar o modelo contra um adversário a jogar em casa, sem nenhum de nós dar por isso.

Se a tua baseline tem uma distribuição assumida lá dentro, e as boas baselines normalmente têm, verifica se o teu conjunto de teste calha ser igual. Agora corro tudo num conjunto misto e cada resultado regista a família que usou.

O que te diria para copiar

Constrói a escada antes de construíres o jogador com modelo. Aleatório no chão, uma heurística ingénua, e depois a melhor solução só com código que tiveres paciência para escrever. Um resultado isolado do modelo não diz nada sem elas, e a baseline mais forte é a que te mantém honesto.

Corre o teste de significância mesmo quando gostas da resposta. Sobretudo aí. Eu tinha uma vantagem de 2,3 tiros e uma história para ir com ela, e a aritmética disse cara ou coroa.

Mantém toda a aritmética no código. O Jev está documentado como pouco fiável a contar, e a Batalha Naval por baixo é um jogo de contagem, por isso todas as contagens de posições e todos os cálculos de probabilidade vivem do meu lado da API. Ao modelo só se pede que julgue entre opções que o código já provou serem legais. É essa restrição que faz o jevHybrid funcionar de todo.

E escreve aquilo que os números não estabelecem no mesmo sítio onde escreves os números. O meu ficheiro de resultados diz que o jevHybrid iguala a densidade e indica o tamanho de amostra que resolveria a questão. Daqui a seis meses já me esqueci, e essa linha é a única coisa entre mim e citar o meu próprio empate como vitória.

A análise completa, com as estatísticas emparelhadas, as três representações de tabuleiro que comparei e a repartição de custos, está aqui.

O código está aberto em github.com/ickas/battleship-vs-jev: o motor, as cinco estratégias, os runners do benchmark e os 228 testes. O npm run bench reproduz a tabela acima.