Bagaimana menemukan tim pokemon yang optimal
Pokemon adalah permainan dimana 2 pemain masing-masing memilih 6 Pokemon (satu tim) di awal permainan tanpa mengetahui tim pemain lain. Setiap Pokemon memiliki satu atau dua jenis. Setiap tipe bisa lemah, netral atau kuat terhadap tipe lainnya. Ini berarti bahwa setiap 2 pertandingan Pokemon akan memiliki pemenang atau seri. Ini juga berarti bahwa tim mana pun dapat diperingkat melawan tim lain berdasarkan jumlah kemenangan pertarungan yang mereka miliki.
Saya ingin menulis sebuah program yang dapat menemukan tim Pokemon yang optimal dari sekumpulan 70 Pokemon yang disediakan. Sebuah tim dianggap optimal jika memiliki jumlah kemenangan terbanyak melawan tim lain. Pada dasarnya, saya ingin menghitung tim mana yang akan memiliki jumlah pertandingan yang menguntungkan paling banyak jika Anda bertarung melawan setiap tim lain yang memungkinkan.
Algoritme apa yang terbaik untuk melakukan ini? Tidaklah mungkin untuk menghitung perbandingan untuk setiap tim yang memungkinkan. Dapatkah saya melakukan semacam pencarian A * dengan pemangkasan yang cukup untuk membuatnya layak secara komputasi?
Jawaban
Setelah komentar awal saya (di mana saya menyarankan bahwa itu mungkin tidak cukup info), saya yakin saya benar-benar mendapatkan ide.
Mulailah dengan kumpulan lengkap pokemon. Untuk setiap jenis yang memungkinkan, identifikasi jumlah pokemon yang kuat terhadap jenis tersebut. Untuk ini, Anda akan mendapatkan file List<(pokemonId, types, List<weakAgainst>)>.
Minimalkan List<weakAgainst>.Count()dan dari kemungkinan kumpulan pokemonIds, pilih satu secara acak. Tanpa mengetahui hal lain selain tipe, pokemon ini sama bagusnya dengan pokemon lain dengan jumlah kelemahan yang sama (inilah inti dari komentar asli saya).
Dari daftar kelemahan yang dimiliki pokemon pilihan ini, pilih pokemon dari daftar anda yang kuat melawan kelemahan tersebut, minimalkan lagi jumlah kelemahannya. Kemungkinan lebih dari satu akan cocok dengan kriteria ini, sekali lagi, pilih satu secara acak.
Terus ulangi pola ini sampai Anda mendapatkan angka 6 di tim Anda. Secara statistik, ini adalah salah satu tim terbaik yang dapat Anda kumpulkan.
Untuk semua kombinasi yang mungkin Anda temukan di sini, beberapa tim akan memiliki lebih sedikit kelemahan, karena kami "secara acak" menelusuri pohon kemungkinan. Ini sangat terdengar seperti algoritma pemangkasan minimum , di mana setiap pilihan pokemon (meminimalkan kelemahan Anda) dapat bertemu dengan lawan potensial yang akan memaksimalkan titik lemah Anda.
Disederhanakan, disatukan:
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
Dari algoritma ini tidak terlihat jelas dimana porsi "max" berada. Kami meminimalkan kerugian (kelemahan) kami tetapi kami mempertimbangkan semua kemungkinan tim lawan secara setara, jadi tidak ada pemaksimalan nyata dari pilihan lawan. Untuk sekumpulan ide, periksa di bawah.
Perhatikan bahwa algoritme ini akan memberi Anda sekumpulan "tim" yang sama baiknya dalam arti bahwa mereka akan memiliki jumlah kelemahan yang diminimalkan dan kekuatan yang dimaksimalkan yang sama terhadap tim lain yang memungkinkan. Tetapi walaupun pokemon itu berbeda, jumlahnya akan sama, hanya jenis yang berbeda.
Untuk pendekatan yang lebih kompleks, Anda mungkin ingin mempertimbangkan seberapa lazimnya beberapa pokemon (Anda mungkin tidak perlu mengoptimalkan jenis mitos yang sangat langka, melainkan jenis yang sangat umum yang tersedia dalam gim), seberapa besar kemungkinan pokemon tertentu dapat memiliki serangan yang lebih baik / lebih cepat, berapa kemungkinan pertempuran IV, seberapa sering pelatih mengganti pokemon dalam pertempuran, dll. Sekali lagi, saya tahu ini bukan yang Anda minta, tetapi demi contoh, ini akan menjadi begitu kompleks bahwa alih-alih algoritma pencarian, pendekatan simulasi (Monte Carlo?) mungkin lebih sederhana untuk membangun tim dari pengujian statistik.