SpawELO - Sistem matchmaking gratis skala kecil untuk LAN party

• Di LAN party tahunan para teman yang sudah berlanjut selama 16 tahun, memilih tim Dota 2 secara manual setiap kali makin sulit, sehingga dibuatlah SpawELO untuk mengotomatiskan pemilihan tim
• Karena perbedaan kemampuan dan jumlah peserta yang berubah-ubah, draft manual sering menghasilkan pengulangan tim yang mirip serta ketimpangan saat jumlah pemain ganjil
• Implementasi pertama memakai 35 pertandingan sebelumnya dan skor Elo untuk mencari kombinasi dengan total skor tim yang paling dekat, lalu menyesuaikan skor dengan terus memasukkan hasil pertandingan berikutnya
• Setelah diubah menjadi model prediksi peluang menang, Elo pemain disesuaikan dengan loss L2 dan backpropagation, tetapi saat semua kemenangan diperlakukan sebagai 100%, muncul overfitting yang membuat model menghafal pertandingan lama
• Metode akhirnya memperlakukan hasil pertandingan sebagai kemenangan probabilistik 75% atau 95% untuk mengurangi overfitting, dengan tujuan membuat pencocokan tim yang juga bisa dipakai pada susunan pemain ganjil seperti 4v5

---

Masalah pemilihan tim yang terlihat di LAN party

• Kelompok teman ini telah mengadakan LAN party setidaknya sekali setiap tahun selama 16 tahun terakhir, biasanya berlangsung 4~5 hari, dan pada jam tersibuk dihadiri sekitar 12 orang
• Game utamanya adalah Dota 2, dan mereka juga memainkan Counter-Strike, Wolfenstein: Enemy Territory, Warcraft 3, serta Blobby Volley
• Waktu kedatangan dan kepulangan peserta berbeda-beda, dan ada juga yang sesekali pergi untuk mengurus anak, jadi setiap game tidak selalu dimainkan dengan orang yang sama
• Dota 2 biasanya dimainkan dalam format 5v5 dan satu game berlangsung sekitar 40 menit, sementara pertandingan tidak seimbang seperti 4v5 mudah berat sebelah
• Di dalam grup ada yang rutin bermain Dota 2 dan ada juga yang hanya bermain saat LAN party, sehingga perbedaan skill cukup besar

Batasan draft manual

• Cara lama biasanya membuat dua orang yang paling jago atau justru paling minim pengalaman menjadi pemimpin, lalu mereka bergantian memilih anggota tim seperti memilih pemain di lapangan sekolah
• Urutan pilihannya adalah pemimpin pertama memilih 1 orang, pemimpin kedua memilih 2 orang, lalu pemimpin pertama memilih 2 orang lagi, dan terakhir masing-masing pemimpin memilih 1 orang
  • Ini adalah variasi untuk mengurangi keuntungan pihak yang memilih lebih dulu
• Karena selisih skill cukup besar, hasilnya sering tetap membentuk tim yang mirip atau bahkan sama, dan keseruan melakukan draft setiap kali juga berkurang
• Pemilihan tim manual memakan waktu dan merepotkan, dan tidak ada yang benar-benar ingin menjadi pemimpin
  • Saat jumlah pemain tidak pas, ketimpangan tim menjadi lebih parah

Implementasi pertama: pertandingan lama dan penjumlahan Elo

• Saat ketidakpuasan terhadap proses pemilihan tim memuncak di LAN party terakhir, kode otomatisasi cepat ditulis
• Pertama, data dari 35 pertandingan sebelumnya dikumpulkan dan dimasukkan ke Colab, dan tiap pertandingan berisi daftar pemain dari tim pemenang dan tim yang kalah
• Ide dasarnya adalah menghitung skor pemain dengan Elo rating
  • Semua pemain mulai dari 1000 poin
  • Menang menambah poin dan kalah mengurangi poin
  • Peluang menang dihitung hanya dari selisih Elo dua pemain
• Implementasi sederhana pertama memberi 20 poin kepada pemain yang menang dan mengurangi 20 poin dari pemain yang kalah
• Susunan tim dibuat dengan memeriksa semua kombinasi dari pemain yang diminta, lalu memilih kombinasi dengan selisih total Elo tim yang paling kecil
  • Pada contoh, 8 pemain dibagi menjadi dua tim, dan hasilnya satu tim bernilai 4100 poin sementara tim lain 4080 poin

Model Elo yang ditingkatkan dengan perhitungan berulang

• Karena menelusuri 35 pertandingan hanya sekali dianggap kurang memanfaatkan data, data pertandingan lama diproses berulang kali beberapa putaran
• Pembaruan Elo yang ditingkatkan tidak lagi sekadar menerapkan ±20 poin, melainkan memberi lebih banyak poin saat menang melawan lawan yang lebih kuat dan mengurangi lebih sedikit saat kalah dari lawan yang lebih kuat
  • Sebagai contoh, jika Spawek dengan 1260 poin mengalahkan Goovie dengan 900 poin, ia hanya mendapat 4.47 poin
  • Jika Status dengan 900 poin mengalahkan Dragon dengan 1100 poin, ia mendapat 30.38 poin
• Karena perhitungannya dilakukan per tim, bukan satu lawan satu, yang dipakai adalah total Elo tim pemenang dan tim kalah, lalu poin pembaruan dibagi rata ke semua anggota tim
• Metode ini juga dipakai selama LAN party berlangsung, dan setelah tiap game, data baru bisa ditambahkan untuk membentuk ulang tim selama sisa acara
• Kadang jika terbentuk match yang jelas tidak seimbang, “pertandingan palsu” dengan pemenang yang diperkirakan akan dimasukkan ke data, lalu tim dibuat ulang

Peningkatan kedua: beralih ke model prediksi peluang menang

• Peningkatan berikutnya memperlakukan Elo bukan sekadar tabel skor, melainkan sebagai model untuk memprediksi peluang menang tim
• Model menyimpan Elo tiap pemain dan menghitung probabilitas menang dengan membandingkan SUM(Elo) dari dua tim
• Pada seluruh data pertandingan diterapkan loss L2 sederhana
  • Hitung total Elo tim pemenang dan tim kalah
  • Hitung probabilitas menang
  • Tambahkan kuadrat selisih antara probabilitas aktual dan probabilitas prediksi ke dalam loss
• Proses pelatihan memakai backpropagation
  • Pada forward pass, probabilitas menang prediksi dihitung
  • Dengan loss dan turunan dari fungsi probabilitas menang, dihitung pengaruh Elo tiap pemain terhadap loss
  • Nilai Elo diperbarui dengan LEARNING_RATE = 10_000.0 dan ITERATIONS = 10001
• Cara ini berhasil menurunkan loss, tetapi nilai Elo tidak konvergen

Hasil pertandingan probabilistik untuk mengurangi overfitting

• Model bergaya ML ini mengalami overfitting karena semua peluang menang aktual dari pertandingan lama diperlakukan sebagai 1.0, yaitu kemenangan 100%
• Karena model menghafal tiap pertandingan lama alih-alih menggeneralisasi, pada beberapa pertandingan probabilitas menang prediksinya menjadi hampir 1, seperti 0.999994567526197
• Karena tujuannya bukan mengodekan hasil masa lalu apa adanya melainkan membentuk tim yang bagus, pendekatan diubah agar memakai hasil probabilistik alih-alih menang-kalah yang pasti
• Setelah meninjau lagi catatan pertandingan lama, sifat pertandingan dibagi menjadi dua jenis
  • Pertandingan yang ketat menetapkan peluang menang aktual tim pemenang sebesar 75%
  • Pertandingan yang jelas berat sebelah menetapkan peluang menang aktual tim pemenang sebesar 95%
• Selisih Elo yang diperlukan untuk peluang menang 75% adalah sekitar 200 poin, sedangkan untuk peluang menang 100% berkisar dari sekitar 500 poin hingga tak terbatas, sehingga model jadi lebih sulit menghafal semua pertandingan
• Setelah mengubah real_probability = 1 menjadi real_probability = game["win_probability"] pada fungsi loss dan backpropagation, loss turun dengan cepat dan Elo pemain juga konvergen ke tingkat yang masuk akal

Susunan pemain yang bisa dibuat meski jumlahnya ganjil

• Sistem baru ini bisa memprediksi peluang menang dan membentuk tim bahkan untuk susunan jumlah pemain ganjil
• Contoh susunan awal untuk LAN party yang dimulai dua minggu lagi adalah sebagai berikut
  • team 1: Elo 2660
  • team 2: Elo 2655
• Susunan contoh ini terdiri dari 4 pemain di satu sisi dan 5 pemain di sisi lain
  • team 1: Spawek, Bixkog, Bania, Goovie
  • team 2: Hypys, Muhah, J, Vifon, Status

[GN⁺]

Komentar di Hacker News

• Saya penasaran apakah ada yang pernah mencoba pendekatan untuk game berbasis tim yang tidak berbasis Elo/TrueSkill
  Menjumlahkan atau merata-ratakan Elo tim untuk matchmaking terasa seperti solusi tambal sulam yang memaksakan model matchmaking individu ke matchmaking tim
  Selain itu, banyak informasi tentang kecocokan internal tim hilang, misalnya A dan B saat bermain bersama lebih kuat daripada jumlah Elo individu mereka, tetapi A dan C saat bersama justru lebih lemah

  • Menurut saya, dalam game berbasis tim, Elo pada akhirnya membuat tidak ada yang tersisa selain menang/kalah
    Dalam olahraga, meski tim kalah, pemainnya masih bisa masuk All-Star atau menjadi MVP setelah musim selesai; sebaliknya, seseorang bisa berada di tim juara tetapi bukan pemain kunci
    Dalam e-sports tim, semuanya bertumpu pada kemenangan, sehingga ekspresi pemain seperti bek, penyerang, atau support terbaik di seluruh liga tidak terlacak atau diakui dengan baik
    Seperti banyak olahraga, perlu ada metrik lanjutan yang dilacak dan diperhitungkan sampai batas tertentu. Pemain lebih mirip nilai seperti assist per pertandingan, rebound, poin, RBI, atau yard, bukan Elo itu sendiri
    Dengan begitu akan lebih mudah terlihat apakah sebuah tim lebih membutuhkan skor atau pertahanan, sehingga matchmaking juga bisa menjadi lebih alami daripada sekadar “butuh lebih banyak pemenang/butuh lebih banyak pecundang”
  • Tempat-tempat yang sudah memakai Elo pun tidak menggunakan Elo murni saja. Pengembang game menyesuaikan matchmaking dengan faktor seperti jumlah orang dalam antrean, waktu sejak terakhir bermain, jumlah total permainan, riwayat laporan, dan jumlah item kosmetik yang dibeli
    Kekuatan Elo adalah besarnya informasi yang didapat dibanding biayanya. Intinya adalah satu angka yang mewakili semuanya
    Memang tidak bisa menjelaskan keragaman alam yang indah secara sempurna, tetapi ia mendekati abstraksi paling efisien yang memuat 70% dari hal yang perlu diketahui tentang kemampuan lawan
  • Setuju. Elo adalah model statistik yang kasar tetapi sederhana, dan keunggulan terbesarnya adalah mudah dipahami dan dinalar
    Akan bagus jika ada vektor kemampuan pemain multidimensi atau embedding yang memuat lebih banyak informasi, serta model yang lebih nonlinier di atasnya
    Misalnya, dalam banyak game sebuah tim biasanya membutuhkan pemain support, tetapi satu angka saja tidak cukup untuk memasukkan informasi itu ke matchmaking
  • Saya sudah banyak memikirkannya, tetapi sepertinya tidak ada satu solusi pamungkas; sangat bergantung pada cabang dan variasi aturan yang dimainkan
    Misalnya di table football, ada pemain yang bermain tunggal dan ganda, dan dua bek hebat yang berada dalam satu tim pun bisa kalah dari lawan yang lebih lemah tetapi lebih cocok untuk tiap posisi
    Game yang timnya bisa sangat menopang pemain seperti Counter-Strike, Apex, Overwatch, dan sampai batas tertentu Dota juga berbeda. Di Counter-Strike, satu rekan tim yang lemah karena kurang mahir atau tidak punya headset bisa merusak seluruh permainan, tetapi di Overwatch seseorang bisa memilih kelas support, bersantai di belakang, dan menunggu sisa tim menang
    Ada juga chemistry. Seperti yang terlihat di tempat kerja, sinergi yang hanya muncul pada kombinasi tertentu atau sekadar perbedaan gaya bermain bisa mengubah hasil
    Bahkan dalam varian game yang tampak mirip seperti biliar, ada pemain yang bersinar di satu nomor tetapi kurang berhasil di nomor lain
  • Saya pernah mencoba PageRank sekali dan hasilnya cukup baik. Kemenangan diperlakukan sebagai tautan, skor dibuat mengalir dari yang kalah ke yang menang, dan kekuatan tautan dibuat menurun seiring waktu

• Sepertinya pernah ada, atau masih ada, kompetisi sistem rating di Kaggle
  https://www.kaggle.com/competitions/chess/discussion/107
  Ada cukup banyak sistem rating yang kinerjanya lebih baik daripada Elo

  • Di papan peringkat hanya terlihat nama peserta; saya penasaran bagaimana cara melihat metode masing-masing

• Untuk turnamen, saya suka sistem Swiss, yang setahu saya populer di catur
  [1]: https://en.wikipedia.org/wiki/Swiss-system_tournament

  • Menariknya, komunitas lokal kami baru-baru ini mulai mengadakan turnamen biliar dengan sistem Swiss, dan hasilnya cukup bagus. Namun ada kompromi antara keadilan dan jumlah pemain yang bisa diundang
    Dengan format Swiss, untuk 6 ronde, jumlah yang pas paling banyak sekitar 40 orang; tetapi jika ingin mengundang lebih dari 100 orang, harus memakai bracket eliminasi dua kali kalah. Kalau tidak, turnamennya bisa berlangsung seminggu
    Hal terbaiknya adalah value for money-nya bagus. Terlepas dari hasil, semua orang terus bermain sepanjang turnamen, dan seiring berjalan, lawan makin disesuaikan dengan level kita sehingga semua orang bisa menikmatinya
  • Ini juga umum di turnamen Magic dan game kartu lain, meski dipakai dengan sedikit modifikasi. Format seperti “6 ronde Swiss lalu 8 besar eliminasi satu pertandingan” sering terlihat
  • Kalau dibaca sekilas, setelah melawan tim acak di ronde pertama, pada tiap ronde pemain diurutkan berdasarkan skor kumulatif lalu dipasangkan dengan lawan yang skornya sama atau mirip. Pada saat yang sama, sistem menghindari pertemuan dengan lawan yang sama dua kali
    Saya tidak begitu tahu bagaimana menentukan berapa ronde yang dibutuhkan, tetapi saya juga tidak yakin detail itu adalah poin utamanya
    Melihat bagian analisis, dibanding turnamen knockout, dengan asumsi tidak ada seri, jumlah ronde yang diperlukan untuk menentukan pemenang yang jelas sama dengan knockout
    Keunggulan sistem Swiss adalah tidak ada yang dieliminasi, dan peringkat akhir menunjukkan bukan hanya pemenang, tetapi juga kurang lebih kemampuan relatif seluruh peserta
    Namun jika seorang pemain unggul terlalu jauh, gelar juara bisa sudah dipastikan sebelum ronde terakhir, jadi tidak selalu berakhir dramatis

• Saya penasaran bagaimana kalau mencoba nilai Shapley

  • Karena tidak tahu maksudnya, saya mencarinya; tertulis bahwa itu adalah konsep solusi dalam teori permainan kooperatif, dinamai dari Lloyd Shapley, dan secara unik membagikan surplus total yang dibuat oleh koalisi seluruh pemain kepada tiap pemain
    Ini hampir persis seperti bagian pembuka Wikipedia, tetapi setelah membacanya pun saya masih belum paham. Saya penasaran apa yang dimaksud surplus total dalam permainan kooperatif di sini; apakah seperti jumlah kayu yang dikumpulkan tim di AoE
    Saya juga tidak mengerti bagaimana “membagikan” itu bisa membantu, dan malah terasa seharusnya itu menjadi hasil game. Akan bagus kalau ada yang bisa menjelaskannya dengan sederhana