So finden Sie das optimale Pokemon-Team
Pokemon ist ein Spiel, bei dem 2 Spieler zu Beginn des Spiels jeweils 6 Pokemon (ein Team) auswählen, ohne das Team des anderen Spielers zu kennen. Jedes Pokemon hat einen oder zwei Typen. Jeder Typ ist entweder schwach, neutral oder stark gegen jeden anderen Typ. Dies bedeutet, dass jedes 2-Pokemon-Matchup entweder einen Gewinner oder ein Unentschieden hat. Dies bedeutet auch, dass jedes Team anhand der Anzahl der gewonnenen Matchups gegen jedes andere Team eingestuft werden kann.
Ich möchte ein Programm schreiben, das aus 70 bereitgestellten Pokémon das optimale Pokemon-Team findet. Ein Team gilt als optimal, wenn es gegen ein anderes Team die meisten Siege erzielt. Grundsätzlich möchte ich berechnen, welches Team die meisten günstigen Matchups hat, wenn Sie gegen jedes andere mögliche Team antreten.
Welcher Algorithmus wäre dafür am besten geeignet? Es ist nicht möglich, Matchups für jedes mögliche Team zu berechnen. Kann ich eine Art A * -Suche mit genügend Schnitt durchführen, um sie rechnerisch durchführbar zu machen?
Antworten
Nach meinem ersten Kommentar (wo ich vorschlage, dass es möglicherweise nicht genug Informationen gibt) glaube ich, dass ich tatsächlich auf eine Idee gekommen bin.
Beginnen Sie mit dem vollständigen Satz von Pokemon. Identifizieren Sie für jeden möglichen Typ die Anzahl der Pokémon, die gegen diesen Typ stark sind. Dafür erhalten Sie am Ende eine List<(pokemonId, types, List<weakAgainst>)>.
Minimieren Sie List<weakAgainst>.Count()und wählen Sie aus dem möglichen Satz von pokemonIds eine nach dem Zufallsprinzip aus. Ohne etwas anderes als Typ zu wissen, ist dieses Pokemon so gut wie jedes andere mit der gleichen Schwachstellenanzahl (dies ist der Punkt meines ursprünglichen Kommentars).
Wählen Sie aus der Liste der Schwachstellen, die dieses ausgewählte Pokémon aufweist, ein Pokémon aus Ihrer Liste aus, das gegen die Schwachstelle stark ist, und minimieren Sie die Anzahl der Schwachstellen erneut. Wahrscheinlich wird mehr als eines diesen Kriterien entsprechen. Wählen Sie erneut eines nach dem Zufallsprinzip aus.
Wiederholen Sie dieses Muster so lange, bis Sie die 6 in Ihrem Team erhalten. Dies ist statistisch gesehen eines der besten Teams, die Sie zusammenstellen können.
Bei allen Kombinationen, die Sie hier finden, haben einige Teams weniger Schwächen, da wir "zufällig" einen Baum von Möglichkeiten hinuntergehen. Dies klingt sehr nach einem Minimax-Prunning-Algorithmus , bei dem jede Pokemon-Auswahl (Minimierung Ihrer Schwächen) mit potenziellen Gegnern getroffen werden kann, die Ihre Schwachstellen maximieren.
Vereinfacht, zusammengestellt:
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
Aus diesem Algorithmus ist nicht ersichtlich, wo sich der "maximale" Anteil befindet. Wir minimieren unsere Verluste (Schwächen), berücksichtigen aber alle möglichen gegnerischen Teams gleichermaßen, sodass es keine wirkliche Maximierung der gegnerischen Entscheidungen gibt. Eine Reihe von Ideen finden Sie unten.
Beachten Sie, dass dieser Algorithmus Ihnen eine Reihe von "Teams" liefert, die in dem Sinne gleich gut sind, dass sie die gleiche Anzahl minimierter Schwächen und maximierter Stärken gegenüber anderen möglichen Teams aufweisen. Aber selbst wenn Pokemon unterschiedlich sind, sind die Zahlen gleich, nur verschiedene Typen.
Für einen komplexeren Ansatz möchten Sie vielleicht überlegen, wie häufig einige Pokémon vorkommen (Sie müssen möglicherweise nicht gegen einen sehr seltenen mythischen Typ optimieren, sondern gegen die im Spiel häufig vorkommenden Typen), wie wahrscheinlich es ist, dass bestimmte Pokémon dies können bessere / schnellere Angriffe haben, wie hoch ist die Wahrscheinlichkeit von Kampf-IVs, wie häufig kann ein Trainer im Kampf das Pokémon wechseln usw. Ich weiß wieder, dass dies nicht das ist, wonach Sie gefragt haben, aber für das Beispiel wird dies so sein Komplex, dass anstelle eines Suchalgorithmus ein Simulationsansatz (Monte Carlo?) einfacher sein könnte, Teams aus statistischen Tests zusammenzusetzen.