Strategi / algoritma untuk membagi tim yang adil berdasarkan sejarah

Kami adalah sekelompok orang yang bermain bola lantai bersama secara teratur. Setiap sesi dimulai dengan tugas yang menakutkan dari membagi tim ...

Jadi apa yang lebih baik daripada aplikasi untuk memilih tim secara otomatis?

Jadi, mengingat sejarah kombinasi tim dan hasil, dan daftar orang yang muncul untuk sesi khusus ini, apa strategi yang baik untuk menemukan tim yang optimal? Secara optimal, maksud saya tim sederajat mungkin.

Ada ide?

Sunting: Untuk memperjelas, data yang saya gunakan sebagai dasar pengambilan, akan menjadi seperti ini:

[{ team1: ["playerA", "playerB", "playerC"],
   team2: ["playerD", "playerE", "playerF"],
   goals_team1: 10,
   goals_team2:  8 
 },
 { team1: ["playerD", "playerB", "playerC"],
   team2: ["playerA", "playerE", "playerG"],
   goals_team1:  2,
   goals_team2:  5
 },
 { team1: ["playerD", "playerB", "playerF"],
   team2: ["playerA", "playerE", "playerC"],
   goals_team1:  4,
   goals_team2:  2
 }]

Hal pertama yang perlu dipertimbangkan, ini adalah untuk sesuatu yang biasa saja. Itu tidak merancang sistem untuk menentukan putaran untuk piala dunia bola lantai. Ini untuk permainan penjemputan biasa dengan sekelompok orang yang menikmati permainan yang baik daripada kemenangan yang berat sebelah.

Saya ingat sesuatu tentang Google yang memiliki generator peluang foosball. Cukup banyak pekerjaan yang dilakukan untuk itu daripada yang saya lakukan dalam hal ini. Mencari referensi untuk itu, saya menemukan sebuah artikel di SO dan kalkulator True Skill yang digunakan oleh Microsoft untuk xbox .

Mengambil pendekatan yang jauh lebih sederhana, setiap pemain mendapatkan skor rasio poin yang dimiliki tim mereka untuk pertandingan. Untuk Game 1, pemain A akan mendapatkan 1,25 (10/8) sementara pemain D akan mendapatkan 0,8 poin (8/10). Temukan rata-rata dari semua angka dan itu adalah skor pemain.

Untuk set game yang dijelaskan, ini menyediakan:

  A 1.42
  B 1.22
  C 0.72
  D 1.07
  E 1.27
  F 1.40
  G 2.50

Pada titik ini, Anda memiliki masalah yang mirip dengan masalah partisi dengan kendala bahwa setiap tim membutuhkan jumlah pemain yang sama dan nilai tidak perlu tepat (tapi sedekat mungkin).

Pendekatan cepat dan kotor:

Hitung skor untuk setiap pemain yang merupakan total poin untuk sisi di mana pemain itu dibagi dengan total poin dalam permainan untuk setiap permainan yang mereka ikuti. Kemudian urutkan pemain berdasarkan skor. Tempatkan pemain pertama di tim A. Kemudian untuk setiap pemain, tambahkan mereka ke tim dengan skor agregat terendah hingga separuh pemain berada di satu tim. Semua pemain yang tersisa pergi ke tim lain.

Jika Anda tidak ingin menggali dunia Bayorian Priors (pdf) yang memabukkan dan semacamnya, pendekatan yang menarik adalah menetapkan urutan total untuk semua pemain (berdasarkan rasio menang / kalah, poin kumulatif, dll) dan kemudian bagi ke tim menggunakan fungsi paritas sebagai berikut.

Ambil daftar pemain yang disortir (terbaik ke terburuk) dan pisahkan mereka ke dalam tim Even and Odd berdasarkan jumlah 1 bit dalam indeks mereka (mulai dari 0). Itu memberikan distribusi berikut:

• 0000 (terbaik) - Even
• 0001 - Ganjil
• 0010 - Ganjil
• 0011 - Bahkan
• 0100 - Ganjil
• 0101 - Merata
• 0110 - Bahkan
• 0111 - Ganjil

... dll.

Fungsi paritas akan memastikan jumlah pemain yang sama di setiap tim, untuk jumlah pemain genap. Kemudian akan bergantian memberikan keuntungan dari pemain bernomor ganjil ke satu tim atau yang lain sedemikian rupa sehingga efeknya cenderung menyeimbangkan dari waktu ke waktu.

Fungsi ini bekerja paling baik ketika distribusi keterampilan pemain datar. Pada kenyataannya, keterampilan pemain cenderung mengikuti distribusi "penjumlahan nilai acak", alias Gaussian (walaupun waspadai aplikasi selimut dari asumsi itu dalam sistem seperti TruSkill.)

Untuk mengimbangi kesenjangan keterampilan yang besar, Anda dapat menerapkan permutasi ke daftar ini. Misalnya, untuk melawan pemain top yang sangat kuat 0000, Anda dapat menukar pemain 0011 dengan pemain Ganjil yang lebih rendah, seperti 0100. Di sinilah keadaan menjadi bergelombang, tetapi setidaknya itu memberikan titik awal yang baik yang tidak membutuhkan ukuran keterampilan absolut yang akurat, tetapi hanya pemesanan berdasarkan keterampilan relatif.

Tergantung pada berapa banyak waktu yang Anda miliki, mulailah beberapa sesi pertama dengan memilih kapten tim secara acak, dan miliki konsep sebelum setiap pertandingan. Melacak yang mana pemain memilih pergi. Pilihan sebelumnya mendapatkan peringkat lebih tinggi:

Round #1 = 8 pts, Round #2 = 6 pts, Round #3 = 4 pts, etc

Winning a game = 5 pts

Semua ini akan tergantung pada jumlah pemain per tim. The total poin yang mungkin perlu dikonversi ke harian atau permainan rata-rata jika ada perbedaan besar dalam partisipasi. Anda juga dapat memberikan tim untuk margin kemenangan yang lebih besar.

Pemain yang dipilih lebih awal dan bermain di tim pemenang mendapatkan poin kekuatan terbanyak.

Kemudian biarkan komputer melakukan perancangan (pemilihan tim) dengan menyeimbangkan poin daya untuk setiap tim dan menempatkan tim dengan nilai yang hampir sama terhadap satu sama lain. Pemain yang dipilih lebih awal, tetapi terus bermain di tim yang kalah akan turun di peringkat.

Solusi termudah adalah memberikan nilai / bobot keterampilan yang diperkirakan dan mencoba menyeimbangkan skor untuk setiap tim.

Dari sana, Anda dapat menyemai jaringan bayesian dengan nilai-nilai ini dan kemudian Anda akan menyimpulkan mundur berdasarkan hasil yang diamati dari setiap pertandingan dalam data historis yang Anda miliki.

Sebagai bagian yang menarik bagi saya: Infer.NET membuat ini relatif mudah untuk dibayangkan dan berpotensi diimplementasikan, dan itu bisa memprediksi peluang kemenangan yang diberikan pertarungan tim. Infer.NET adalah sesuatu yang saya benar-benar mulai masuki belakangan ini.

Mari kita asumsikan demi diskusi Anda dapat menetapkan nilai integer setiap pemain dan nilai-nilai itu bertambah, yaitu pemain dengan skor X sama berharganya dengan tiga pemain dengan skor A, B dan C, jika A + B + C = X. Tujuannya adalah untuk memisahkan grup menjadi dua tim sehingga kedua tim memiliki nilai penjumlahan yang sama.

Ini adalah versi optimisasi dari masalah PARTISI terkenal yang merupakan NP-complete. Karena itu, masalah Anda adalah untuk semua yang kami tahu sulit untuk dipecahkan. Namun, PARTISI lemah melengkapi NP dan mengakui beberapa strategi perkiraan yang masuk akal.

Salah satu contoh adalah pendekatan serakah yang mirip dengan apa yang diusulkan Steven. Ini adalah perkiraan 4/3, yaitu tim yang lebih kuat tidak pernah lebih dari sekitar 33% lebih kuat dari pada pembagian optimal.

Perhatikan bahwa Anda mungkin memiliki kendala tambahan seperti Anda membutuhkan setidaknya jumlah pemain tetap per tim. Jadi, jika Anda menempatkan Michael Jordan di kelas anak-anak prasekolah, Anda tidak akan dapat membuat tim yang hampir adil yang memiliki angka penuh. Batas bawah tim yang demikian (konstan) seharusnya tidak memengaruhi kekerasan masalah yang mendasarinya, tetapi hal itu dapat menghancurkan batas perkiraan yang berlaku untuk masalah umum.

Seberapa konyol yang ingin Anda dapatkan? Anda selalu dapat menggunakan regresi linier berganda untuk menghasilkan koefisien untuk setiap pemain berdasarkan skor tim mereka di pertandingan sebelumnya. Kemudian urutkan daftar dan pilih.

Pada kenyataannya itu mungkin tidak akan bekerja karena tidak model dinamis antara pemain, namun itu akan memberi Anda alasan untuk bermain-main dengan R . (<- lihat, saya menyimpannya terkait pemrograman)

Jika Anda ingin algoritma Anda masuk akal, algoritma sederhana tidak akan memotongnya. Mereka akan sering memberi Anda hasil yang aneh

Anda harus menggunakan ELO atau sistem Trueskill (ELO tidak bekerja untuk tim tanpa modifikasi).