Como encontrar o time pokémon ideal

Question

Pokémon é um jogo em que 2 jogadores selecionam cada um 6 Pokémon (uma equipe) no início do jogo sem conhecer a equipe do outro jogador. Cada Pokémon tem um ou dois tipos. Cada tipo é fraco, neutro ou forte contra qualquer outro tipo. Isso significa que cada confronto de 2 Pokémon terá um vencedor ou um empate. Isso também significa que qualquer time pode ser classificado contra qualquer outro time com base no número de confrontos vencedores que eles possuem.

Eu quero escrever um programa que possa encontrar o time Pokémon ideal entre um conjunto de 70 Pokémon fornecidos. Uma equipe é considerada ótima se tiver o maior número de vitórias em confrontos com qualquer outra equipe. Basicamente, quero calcular qual time terá o maior número de confrontos favoráveis ​​se você batalhar contra todos os outros times possíveis.

Qual algoritmo seria o melhor para fazer isso? Não é possível computar matchups para todas as equipes possíveis. Posso fazer algum tipo de pesquisa A * com poda suficiente para torná-la viável computacionalmente?

Answer 1

Após meu comentário inicial (onde sugiro que pode não ser informação suficiente), acredito que realmente tive uma ideia.

Comece com o conjunto completo de Pokémon. Para cada tipo possível, identifique a contagem de Pokémon que são fortes contra aquele tipo. Para isso, você acabará com um List<(pokemonId, types, List<weakAgainst>)>.

Minimize List<weakAgainst>.Count()e, a partir do conjunto possível de pokemonIds, selecione um aleatoriamente. Sem saber mais nada além do tipo, este pokemon é tão bom quanto qualquer outro com a mesma contagem de fraquezas (este é o ponto do meu comentário original).

Da lista de fraquezas que este Pokémon selecionado possui, selecione um Pokémon de sua lista que seja forte contra a fraqueza, minimizando a quantidade de fraquezas novamente. Provavelmente mais de um atenderá a esses critérios, novamente, selecione um aleatoriamente.

Continue repetindo esse padrão até obter o 6 em sua equipe. Esta é, estatisticamente falando, uma das melhores equipes que você pode reunir.

Para todas as combinações que você pode encontrar aqui, algumas equipes terão menos pontos fracos, já que estamos "aleatoriamente" descendo uma árvore de possibilidades. Isso soa muito como um algoritmo minimax-prunning , onde cada seleção de pokémon (minimizando suas fraquezas) pode ser encontrada com oponentes em potencial que irão maximizar seus pontos fracos.

Simplificado, reúna:

input: allPokemon: list<pokemonId, weakAgainst, strongAgainst>

var: teamWeakAgainst: []
var: teamStrongAgainst: []
var: selectedTeam: []

while (size(selectedTeam) < 6)
  goodMatches <- allPokemon.max(p -> size(p.strongAgainst.intersect(teamWeakAgainst)))
  goodMatches <- goodMatches.min(p -> size(p.weakAgainst))
  goodMatches <- goodMatches.max(p -> size(p.strongAgainst))

  selectedPokemon <- goodMatches.random()

  teamWeakAgainst -= selectedPokemon.strongAgainst
  teamWeakAgainst += selectedPokemon.weakAgainst # not counting previously selected pokemon because the current one adds another "weakness", even if it was already accounted for

  selectedTeam += selectedPokemon

output: selectedTeam

A partir desse algoritmo, não fica óbvio onde está a porção "máxima". Estamos minimizando nossas perdas (fraquezas), mas estamos considerando todos os times oponentes possíveis igualmente, então não há maximização real das escolhas do adversário. Para um conjunto de ideias, verifique abaixo.

Observe que esse algoritmo fornecerá um conjunto de "equipes" que são igualmente boas no sentido de que terão a mesma quantidade de pontos fracos minimizados e pontos fortes maximizados contra outras equipes possíveis. Mas mesmo que os pokémons sejam diferentes, os números serão os mesmos, apenas tipos diferentes.

Para uma abordagem mais complexa, você pode querer considerar o quão prevalentes são alguns pokémons (você pode não precisar otimizar contra um tipo mítico super-raro, mas sim os tipos muito comuns disponíveis no jogo), qual a probabilidade de que certos pokémons possam tenha ataques melhores / mais rápidos, qual é a probabilidade de Battle IVs, com que frequência um treinador pode trocar de Pokémon na batalha, etc. Mais uma vez, eu sei que não foi isso que você pediu, mas pelo exemplo, isso se tornará verdadeiro complexo que, em vez de um algoritmo de busca, uma abordagem de simulação (Monte Carlo?) pode ser mais simples para formar equipes a partir de testes estatísticos.