口袋妖怪是一种游戏，其中 2 名玩家在游戏开始时每人选择 6 个口袋妖怪（一个团队），而不知道其他玩家的团队。每个口袋妖怪都有一两种类型。每种类型要么弱，要么中立，要么强于其他类型。这意味着每 2 个 Pokemon 对决要么有赢家，要么打成平手。这也意味着任何球队都可以根据他们所拥有的获胜对决次数与任何其他球队进行排名。
我想编写一个程序，可以从一组提供的 70 个口袋妖怪中找到最佳口袋妖怪团队。如果一支球队与任何其他球队的比赛获胜次数最多，则该球队被认为是最佳球队。基本上，我想计算如果你要与其他所有可能的球队交战，哪支球队将拥有最多的有利对决。
什么算法最适合这样做？为每个可能的球队计算比赛是不可行的。我可以通过足够的修剪进行某种 A* 搜索以使其在计算上可行吗？
在我最初的评论（我建议它可能没有足够的信息）之后，我相信我实际上想出了一个想法。
从全套口袋妖怪开始。对于每种可能的类型，确定对抗该类型的口袋妖怪的数量。为此，您最终会得到一个List<(pokemonId, types, List<weakAgainst>)>.
最小化List<weakAgainst>.Count()并从可能的一组 pokemonIds 中随机选择一个。除了类型之外，不知道其他任何东西，这个口袋妖怪和任何其他具有相同弱点的口袋妖怪一样好（这是我最初评论的重点）。
从这个选定的口袋妖怪的弱点列表中，从你的列表中选择一个对弱点强的口袋妖怪，再次最小化弱点的数量。可能不止一个会匹配此标准，再次，随机选择一个。
不断重复这个模式，直到你在你的团队中获得 6。从统计上讲，这是您可以聚集的最好的团队之一。
对于您可能在此处找到的所有组合，一些团队的弱点会更少，因为我们是“随机”沿着可能性树走的。这听起来非常像极小极大修剪算法，其中每个口袋妖怪选择（最小化你的弱点）都可以遇到潜在的对手，从而最大化你的弱点。
简化，放在一起：
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
从这个算法来看，“最大”部分在哪里并不明显。我们正在最小化我们的损失（弱点），但我们正在平等地考虑所有可能的对手球队，因此没有真正最大化对手的选择。有关一组想法，请查看以下内容。
请注意，此算法将为您提供一组同样优秀的“团队”，因为它们在对抗其他可能的团队时将具有相同数量的最小化弱点和最大优势。但是即使口袋妖怪不同，数量也会相同，只是类型不同。
对于更复杂的方法，您可能需要考虑某些口袋妖怪的流行程度（您可能不需要针对超级稀有的神话类型进行优化，而是针对游戏中非常常见的类型进行优化），某些口袋妖怪的可能性有多大有更好/更快的攻击，战斗IV的概率是多少，训练师在战斗中切换口袋妖怪的频率等。再说一次，我知道这不是你要求的，但为了举例，这将变得如此复杂的，而不是搜索算法，模拟（蒙特卡洛？）方法可能更简单地从统计测试中建立团队。