Cara kerja tim penyeimbang di World of Tanks Blitz

WoT Blitz adalah penembak tank mobile di mana pemain bertarung dalam format 7 on 7.
Seorang mak comblang, atau penyeimbang, adalah mekanisme yang, berdasarkan susunan pemain yang ingin memasuki pertempuran, membentuk komposisi tim.

Tank memiliki parameter berikut yang penting untuk perjodohan:

• Level. Tergantung pada levelnya, karakteristik tank yang berbeda berubah (misalnya, kecepatan, penetrasi armor). Di level 1 - tank terlemah, di level 10 - yang terkuat.
  
• Jenis Ada 4 jenis tank di WoT Blitz: perusak ringan, sedang, berat, dan tank (artileri self-propelled anti-tank)
  

Implementasi paling sederhana dari mak comblang adalah dengan melemparkan pemain secara acak ke dalam tim. Tetapi dalam hal ini, pemain di level rendah tidak akan memiliki kesempatan untuk menyebabkan setidaknya beberapa kerusakan, dan itu akan menjadi tidak menarik untuk dimainkan.

Persyaratan

Daftar persyaratan untuk penyeimbang dibentuk berdasarkan umpan balik dari komunitas game dan diperbarui secara berkala hingga hari ini.

Pada saat menulis artikel untuk pertempuran reguler, daftar terdiri dari hal-hal berikut:


Untuk mengembangkan mak comblang, terutama mengingat sejumlah pembatasan seperti itu, adalah tugas yang sangat menarik. Dan pendekatan untuk solusinya bisa sangat banyak.

Balancer membentuk sepasang pemain

Awalnya, di tank mobile, penyeimbang digunakan, yang ia warisi dari kakaknya - tank desktop. Secara umum, ia bekerja dengan cukup baik, tetapi ia memiliki beberapa masalah: pertama, ia tidak memberikan jaminan yang jelas untuk memenuhi persyaratan; kedua, menambahkan persyaratan baru agak sulit.


Mulai dari pertempuran

Oleh karena itu, penyeimbang lain ditulis, yang bekerja sesuai dengan algoritma berikut:

• Kami memecah pemain menjadi kelompok sesuai dengan tingkat dan jenis peralatan;
• Dari pemain yang dihasilkan kami membentuk pasangan;
• Kami menyebarkan pasangan untuk tim yang berbeda: bawa masing-masing pasangan, lemparkan pemain pertama ke tim utama, yang kedua ke tim kedua;
• Di tim yang diterima, kami melakukan penyeimbangan terakhir: untuk memenuhi sebagian besar persyaratan, kami mengganti beberapa pemain dari satu tim dengan pemain dari tim lain.

Penyeimbang yang dihasilkan bekerja 5-10 kali lebih cepat dari versi sebelumnya dan pada awalnya mengumpulkan tim yang memenuhi semua persyaratan pada waktu itu. Aturan baru ditambahkan dengan menulis pass penyeimbangan tambahan.

Pada awalnya, semuanya bekerja dengan baik. Namun seiring waktu, semakin banyak aturan yang ditambahkan, semakin sulit menulis penyeimbangan kembali. Sebagai hasil dari pekerjaan mereka, penyeimbangan ulang yang baru seharusnya tidak merusak pekerjaan yang sebelumnya. Menjadi jelas bahwa ini adalah jalan ke mana-mana.


Bug di mak comblang - tim 9 on 9 berkumpul

Simulasi Annealing Balancer

Dalam versi final, kami memilih penyeimbang yang berfungsi sesuai dengan algoritma berikut. Semua pemain yang mengklik tombol "Untuk Bertempur" termasuk dalam antrian umum. Penyeimbang loop tanpa akhir melakukan hal berikut:

• Memilih parameter pertempuran acak (tingkat pertempuran acak (dari 1 hingga 10), mode acak, peta acak);
  
• Temukan dalam antrian semua pemain yang cocok dengan kriteria yang dipilih di atas (bertempur di tangki pada tingkat yang sesuai, memiliki mode yang dipilih diaktifkan, memiliki peta yang dipilih dimuat);
  
• Mencoba membentuk tim yang memenuhi semua persyaratan di atas (uraian di bawah);
  
• Jika memungkinkan untuk membentuk tim, lempar pemain ini keluar dari garis tunggu dan pertempuran dimulai.
  

Untuk membentuk tim dari daftar pemain yang cocok, metode simulasi anil digunakan. Baca lebih lanjut tentang metode itu sendiri di sini .


Cari maksimum global dengan mensimulasikan anil

Dalam konteks aplikasi untuk pembentukan tim, algoritme adalah sebagai berikut:

• Dimulai dengan dua tim kosong;
  
• Pada setiap iterasi, itu secara acak mengubah status perintah. Untuk melakukan ini, lakukan salah satu dari operasi berikut:
  
  
  • Menambahkan pemain acak dari daftar pemain yang cocok ke tim pertama atau kedua (kami juga mengambil tim acak);
    
  • Menghapus pemain acak dari tim acak;
    
  • Mengganti pemain acak dari daftar yang cocok dengan salah satu yang ada di tim pertama atau kedua;
    
  • Mengubah pemain acak dari tim pertama menjadi pemain acak dari tim kedua.
    
  
  
• Mendapat perkiraan kondisi yang dihasilkan. Untuk melakukan ini, panggil fungsi evaluasi. Fungsi melewati daftar persyaratan dan untuk pelanggaran setiap item meningkatkan hukuman. Semakin kuat poin dilanggar, semakin tinggi penalti. Misalnya, penalti untuk tim 2x2 akan lebih tinggi daripada penalti untuk tim 6x6;
  
• Bergantung pada perubahan nilai estimasi fungsi dan suhu saat ini, kami menentukan probabilitas transisi ke kondisi baru;
  
• Kami melanjutkan proses hingga suhu mencapai minimum yang ditetapkan atau nilai fungsi evaluasi mencapai nol (dalam hal ini, semua persyaratan dipenuhi dan pertempuran dapat dimulai).
  

Keuntungan utama dari pendekatan ini: untuk menambahkan persyaratan baru, cukup untuk memodifikasi fungsi evaluasi. Tidak perlu menulis kode yang akan menjelaskan cara mendapatkan apa yang kita inginkan. Cukup tambahkan aturan yang terlihat pada tim yang terbentuk dan katakan apakah itu seimbang atau tidak.

Contoh yang baik untuk menambahkan aturan semacam itu adalah pertarungan peringkat. Dalam pertarungan peringkat di mak comblang, beberapa aturan baru muncul sekaligus:

• Tim harus seimbang dalam hal peringkat (perbedaan dalam total peringkat pemain antara tim tidak boleh melebihi nilai yang diberikan);
  
• Perbedaan peringkat antara pemain harus minimal (pemain dari liga perunggu tidak boleh berkelahi dengan pemain dari berlian).
  

Contoh profil pemain Diamond League

Aturan pertama diterapkan dengan memodifikasi fungsi evaluasi: penalti ditambahkan untuk melebihi perbedaan maksimum yang diijinkan dalam peringkat. Aturan kedua diterapkan dengan mengubah fungsi yang menarik pemain yang sesuai dari antrian.

Kelemahan dari pendekatan ini adalah kecepatannya yang lambat. Dibandingkan dengan versi sebelumnya, yang saat ini mulai bekerja sekitar 10 kali lebih lambat, walaupun ada beberapa optimasi. Omong-omong, tentang pengoptimalan. Sebagian besar server (kecuali jaringan dan fisika) untuk gim ini ditulis dalam Python. Penyeimbang ditulis ulang dalam C ++ dan diparalelkan dengan banyak utas. Dari Python, permintaan untuk membentuk perintah tiba di kode plus. Selanjutnya, masing-masing aliran secara independen memulai metode anil. Segera setelah beberapa utas menemukan solusi, sisa utas menghentikan proses pencarian, dan solusi yang ditemukan dikembalikan ke Python.


Waktu tunggu dan ukuran antrian di server RU (5 detik di pertarungan normal dan 10 di pertarungan peringkat)

Seiring pertumbuhan online tumbuh, begitu pula beban pada penyeimbang. Musim gugur ini, ketika server online pada server RU mencapai 120 ribu (selama acara Mad Games), penyeimbang berhenti mengatasinya. Sebagai tindakan sementara, kami menonaktifkan beberapa aturan, ini memungkinkan kami untuk mengurangi beban. Untuk menghindari masalah seperti itu di masa depan, kami membuat mak comblang didistribusikan.

Sistem penilaian

Pemain terbaik di liga intan, 21 April 2019

Di banyak game MMO, selain pertarungan acak, ada juga peringkat / peringkat / dll. Gagasan utama mode ini: lawan tidak dicari secara acak, tetapi cocok dalam keterampilan. Jika Anda seorang pemain keterampilan, Anda akan bermain dengan pemain keterampilan yang sama, dan sebaliknya, jika Anda tidak tahu cara bermain, Anda akan menemukan pendatang baru yang sama.

Pada awal musim, pemain melewati serangkaian perkelahian kalibrasi, yang hasilnya menentukan posisi awalnya. Kemudian, tergantung pada keberhasilan selanjutnya dari permainan, pemain naik atau turun di peringkat. Sistem peringkat di Blitz dibuat, pertama-tama, untuk penyeimbangan yang tepat. Itu dipertajam pada keterampilan pemain dan praktis independen dari jumlah permainan yang dimainkan.

Untuk mengimplementasikan pertarungan peringkat, perlu menyelesaikan dua masalah sekaligus. Pertama, perlu untuk memilih sistem penilaian (oleh pemain prinsip apa yang harus dinilai). Kedua, itu perlu untuk memperbaiki penyeimbang sehingga ia mengumpulkan perkelahian dengan mempertimbangkan batasan peringkat akun.

Persyaratan utama untuk sistem peringkat adalah kemampuan untuk secara akurat menentukan level pemain. Untuk mengevaluasi seberapa akurat sistem peringkat satu atau yang lain bekerja, simulator dibuat, pada input yang sejarah pertempuran dan sistem peringkat yang dipilih diserahkan, dan hasilnya adalah keakuratan sistem.

Akurasi dihitung sebagai berikut:

• Semua pemain diberi peringkat awal;
  
• Berdasarkan hasil dari masing-masing pertempuran, peringkat pemain yang berpartisipasi dalam pertempuran ini dihitung ulang sesuai dengan sistem yang dipilih;
  
• Sebelum setiap pertempuran, sistem mencoba memprediksi tim mana yang akan menang;
  
• Akibatnya, persentase pertempuran yang sistemnya berikan prediksi yang tepat dihitung.
  

Sistem perhitungan peringkat paling populer: winrate, Elo , Glicko , TrueSkill . Winrate adalah persentase kemenangan yang biasa. Elo adalah sistem penilaian, awalnya dibuat untuk game dengan dua orang (catur, dll). Dalam sistem ini, seorang pemain diberikan / diambil sejumlah poin untuk menang / kalah, tergantung pada peringkat lawan. Glicko umumnya mirip dengan Elo, tetapi juga memperhitungkan berapa lama pemain tidak aktif. TrueSkill adalah sistem peringkat eksklusif dari Microsoft, di mana setiap pemain memiliki dua parameter: peringkat dan kepercayaan sistem terhadap peringkat ini.

Selama pengembangan versi pertama pertarungan peringkat, kami mempertimbangkan winrate dan Elo (beberapa opsi diadaptasi untuk permainan tim), serta sistem Skor sederhana (di mana para pemain selalu diberi jumlah poin penilaian untuk kemenangan dan diambil untuk kekalahan).



Hasil terbaik ditunjukkan oleh sistem Elo, di mana Ra adalah peringkat pemain, dan Rb adalah perbedaan antara total peringkat tim lawan dan total peringkat tim pemain, dengan pengecualian pemain itu sendiri.

Kesulitan utama yang kami temui setelah peluncuran:

• terlalu banyak variasi dalam peringkat di antara pemain;
  
• kecepatan yang tidak dapat diprediksi saat skor pemain (mencapai liga).
  

Masalah pertama tidak bisa diselesaikan sepenuhnya karena fakta bahwa ada terlalu sedikit pemain keterampilan, mereka harus menunggu lama sebelum pertempuran dimulai, dan sangat sering mereka melihat pemain di tim mereka lebih lemah. Untuk mengurangi efeknya, kami membuat pertarungan peringkat hanya tersedia di jam tayang utama (yaitu, saat jumlah maksimum orang bermain di server).

Kami memecahkan masalah kedua dengan memperkenalkan faktor perlambatan (yaitu, semakin jauh pemain dari peringkat rata-rata, semakin sulit baginya untuk naik atau turun di bawah).

Kami juga mencoba berbagai cara untuk meningkatkan kualitas sistem peringkat. Di versi pertama, untuk mengubah peringkat, kami hanya menggunakan informasi tentang kemenangan / kekalahan. Tetapi kami memiliki permainan tim, dan tidak selalu tindakan baik dari satu pemain tertentu mengarah pada kemenangan seluruh tim. Artinya, bahkan jika pemain bermain bagus dan tim kalah, pemain ini menerima nilai minus yang sama dengan semua pemain lainnya. Untuk mencegah hal ini, kami mulai mencoba memperhitungkan tindakan individu pemain dalam pertempuran.

Untuk tujuan ini, kami mencoba menggunakan pembelajaran mesin: kami mengumpulkan berbagai faktor dan mencoba melatih model untuk memprediksi kemenangan / kekalahan tim sesuai dengan tindakan pemain dalam pertempuran, kemudian menggunakan model ini untuk menentukan koefisien bonus peringkat (yaitu, jika tim kalah, tetapi perilaku pemain serupa) tentang perilaku pemain yang menang, berikan bonus tambahan kepada pemain tersebut).


Pemain dari tim pemenang yang bermain dengan baik menerima peringkat +40. Dan yang buruk hanya +10

Kami mampu membangun model yang baik yang menunjukkan hasil yang jauh lebih baik daripada yang sekarang, tetapi ada satu kesulitan (yang cukup sering merusak segalanya dalam masalah pembelajaran mesin). Modelnya bagus, tapi kadang-kadang ada kesalahan yang jelas terlihat oleh orang. Secara berkala ada situasi ketika seorang pemain yang, dari sudut pandang seseorang menunjukkan hasil yang baik, menerima bonus rendah dari sudut pandang model, dan sebaliknya.

Akibatnya, kami meninggalkan model-ML dan mengambil formula manual yang lebih sederhana. Formula ini hanya memperhitungkan pengalaman bertarung tanpa memperhitungkan bonus untuk kemenangan, x2 dan lainnya. Ini memberikan hasil yang sangat layak, meskipun sedikit lebih rendah daripada model ML.

Kesimpulan

• Sebuah penyeimbang yang didasarkan pada metode simulasi anil memungkinkan kami untuk beralih dari deskripsi solusi (cara merakit tim) ke deskripsi persyaratan (kondisi yang tidak boleh dilanggar);
  
• Dalam pertempuran pemeringkatan tim, sistem Elo yang dimodifikasi menunjukkan dirinya dengan baik, dengan mempertimbangkan aksi individu pemain dalam pertempuran;
  
• Tidak selalu perlu untuk menerapkan metode pembelajaran mesin yang kompleks (terutama ketika interpretasi dan kelengkapan hasil oleh seseorang adalah penting).
  

Kami terus mengembangkan dan meningkatkan penyeimbang. Kami hampir mengalahkan kesan negatif ketidakseimbangan kelas. Masalah utama yang diperhatikan pemain kami adalah ketidakseimbangan dalam keterampilan, turbulensi, dan pemain afk. Ini adalah tantangan serius, kami terus bekerja pada penyeimbang di bidang ini.

Jika Anda memiliki pertanyaan / saran tentang penyeimbang di WoT Blitz, berhenti berlangganan di komentar (atau di forum kami).