최적의 포켓몬 팀을 찾는 방법
포켓몬은 2 명의 플레이어가 다른 플레이어의 팀을 모르고 게임 시작시 6 개의 포켓몬 (한 팀)을 선택하는 게임입니다. 모든 포켓몬에는 한두 가지 유형이 있습니다. 모든 유형은 다른 모든 유형에 대해 약하거나 중립적이거나 강합니다. 이것은 모든 2 개의 포켓몬 매치업이 승자가되거나 동점이 될 것임을 의미합니다. 이것은 또한 어떤 팀이 승리 한 매치업 수에 따라 다른 팀과 비교하여 순위를 매길 수 있음을 의미합니다.
제공되는 70 종의 포켓몬 중에서 최적의 포켓몬 팀을 찾을 수있는 프로그램을 작성하고 싶습니다. 다른 팀과의 경기에서 가장 많은 승리를 거둔 팀은 최적으로 간주됩니다. 기본적으로 다른 모든 가능한 팀과 대결을한다면 어느 팀이 가장 유리한 매치업을 가질 것인지 계산하고 싶습니다.
이를 수행하는 데 가장 적합한 알고리즘은 무엇입니까? 가능한 모든 팀의 매치업을 계산하는 것은 불가능합니다. 계산적으로 실행 가능하도록 충분한 가지 치기로 일종의 A * 검색을 수행 할 수 있습니까?
답변
내 초기 의견 (충분한 정보가 아닐 수 있다고 제안하는 부분) 후에 실제로 아이디어가 떠올랐다 고 생각합니다.
전체 포켓몬 세트로 시작하십시오. 가능한 모든 유형에 대해 해당 유형에 대해 강한 포켓몬의 수를 식별하십시오. 이를 위해 List<(pokemonId, types, List<weakAgainst>)>.
최소화 List<weakAgainst>.Count()하고 가능한 pokemonId 집합에서 임의로 하나를 선택합니다. 유형 외에 다른 것을 알지 못하는이 포켓몬은 동일한 약점 수를 가진 다른 포켓몬만큼 좋습니다 (이것이 내 원래 의견의 요점입니다).
이 선택된 포켓몬의 약점 목록에서 약점에 강한 포켓몬을 선택하여 약점의 양을 다시 최소화하십시오. 둘 이상이이 기준과 일치 할 가능성이 있으므로 다시 한 번 무작위로 선택하십시오.
팀에서 6을 얻을 때까지이 패턴을 계속 반복하십시오. 이것은 통계적으로 말하자면 여러분이 모을 수있는 최고의 팀 중 하나입니다.
여기에서 찾을 수있는 모든 조합에 대해 일부 팀은 가능성의 나무를 "무작위로"걷고 있기 때문에 약점이 적습니다. 이것은 각 포켓몬 선택 (약점 최소화)이 약점을 극대화 할 잠재적 인 상대와 만날 수 있는 minimax-prunning 알고리즘 처럼 들립니다 .
단순화, 종합 :
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의 확률은 얼마이며, 트레이너가 전투에서 포켓몬을 얼마나 자주 바꿀 수 있는지 등. 다시 말하지만, 이것이 당신이 요청한 것이 아니라는 것을 알고 있지만, 예를 들어, 이것은 그렇게 될 것입니다 검색 알고리즘 대신 시뮬레이션 (Monte Carlo?) 접근 방식이 통계 테스트에서 팀을 구성하는 것이 더 간단 할 수 있다는 점이 복잡합니다.