Come trovare la squadra pokemon ottimale
Pokemon è un gioco in cui 2 giocatori selezionano ciascuno 6 Pokemon (una squadra) all'inizio del gioco senza conoscere la squadra dell'altro giocatore. Ogni Pokemon ha uno o due tipi. Ogni tipo è debole, neutro o forte contro ogni altro tipo. Ciò significa che ogni 2 Pokemon matchup avrà un vincitore o sarà un pareggio. Ciò significa anche che qualsiasi squadra può essere classificata contro qualsiasi altra squadra in base al numero di matchup vincenti che hanno.
Voglio scrivere un programma che possa trovare la squadra ottimale di Pokemon su un set di 70 Pokemon forniti. Una squadra è considerata ottimale se ha il maggior numero di matchup vincenti contro qualsiasi altra squadra. Fondamentalmente, voglio calcolare quale squadra avrà il maggior numero di matchup favorevoli se dovessi affrontarla contro ogni altra squadra possibile.
Quale algoritmo sarebbe il migliore per farlo? Non è possibile calcolare gli abbinamenti per ogni squadra possibile. Posso fare una sorta di ricerca A * con una potatura sufficiente per renderla computazionalmente fattibile?
Risposte
Dopo il mio commento iniziale (in cui suggerisco che potrebbero non essere sufficienti informazioni) credo di aver avuto davvero un'idea.
Inizia con il set completo di pokemon. Per ogni tipo possibile, identifica il conteggio dei Pokemon forti rispetto a quel tipo. Per questo, ti ritroverai con un file List<(pokemonId, types, List<weakAgainst>)>.
Riduci a icona List<weakAgainst>.Count()e dal possibile set di pokemonIds, selezionane uno a caso. Senza sapere nient'altro oltre al tipo, questo pokemon è buono come qualsiasi altro con lo stesso numero di punti deboli (questo è il punto del mio commento originale).
Dall'elenco dei punti deboli che ha questo pokemon selezionato, seleziona un pokemon dal tuo elenco che è forte contro il punto debole, riducendo nuovamente al minimo la quantità di punti deboli. Probabilmente più di uno corrisponderà a questo criterio, selezionane uno a caso.
Continua a ripetere questo schema finché non ottieni il 6 nella tua squadra. Questa è, statisticamente parlando, una delle migliori squadre che puoi riunire.
Per tutte le combinazioni che potresti trovare qui, alcune squadre avranno meno punti deboli, dal momento che stiamo camminando "casualmente" lungo un albero di possibilità. Questo suona molto come un algoritmo di minimax , in cui ogni selezione di pokemon (riducendo al minimo i tuoi punti deboli) può essere affrontata con potenziali avversari che massimizzeranno i tuoi punti deboli.
Semplificato, messo insieme:
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
Da questo algoritmo non è ovvio dove sia la porzione "max". Stiamo minimizzando le nostre perdite (punti deboli) ma stiamo considerando tutte le possibili squadre avversarie allo stesso modo, quindi non c'è una reale massimizzazione delle scelte dell'avversario. Per una serie di idee, controlla di seguito.
Nota che questo algoritmo ti darà una serie di "squadre" che sono ugualmente buone, nel senso che avranno la stessa quantità di punti deboli ridotti al minimo e punti di forza massimizzati contro altre squadre possibili. Ma anche se i pokemon sono diversi, i numeri saranno gli stessi, solo tipi diversi.
Per un approccio più complesso, potresti voler considerare quanto sono diffusi alcuni pokemon (potresti non aver bisogno di ottimizzare contro un tipo mitico super raro, ma piuttosto i tipi molto comuni disponibili nel gioco), quanto è probabile che alcuni pokemon possano farlo avere attacchi migliori / più veloci, qual è la probabilità di IV di battaglia, quanto spesso un allenatore può cambiare pokemon in battaglia, ecc. Ancora una volta, so che questo non è quello che hai chiesto, ma per il bene dell'esempio, diventerà così complesso che invece di un algoritmo di ricerca, un approccio di simulazione (Monte Carlo?) potrebbe essere più semplice per creare team partendo da test statistici.