SpawELO - LAN पार्टी के लिए छोटा मुफ्त matchmaking system

• 16 साल से चली आ रही दोस्तों की LAN party में हर बार Dota 2 teams हाथ से चुनना मुश्किल होने लगा, तो team selection को automate करने के लिए SpawELO बनाया गया
• skill gap और बदलती attendance की वजह से manual draft अक्सर लगभग वही teams दोहराता था और odd number of players होने पर imbalance पैदा करता था
• पहली implementation ने 35 पुराने matches और Elo scores के आधार पर ऐसी team combinations खोजीं जिनमें team-wise total score सबसे करीब हो, और बाद में match results को बार-बार reflect करके scores adjust किए
• win-rate prediction model पर जाने के बाद L2 loss और backpropagation से player Elo adjust किया गया, लेकिन हर जीत को 100% मानने पर model पुराने matches याद करने लगा और overfitting हुआ
• final approach match results को 75% या 95% की probabilistic wins की तरह treat करता है ताकि overfitting कम हो, और 4v5 जैसे odd-player setups में भी usable team matching देना इसका लक्ष्य है

---

LAN party में सामने आई team selection की समस्या

• दोस्तों का group पिछले 16 सालों से हर साल कम से कम एक LAN party करता रहा है; आम तौर पर यह 4–5 दिनों तक चलती है और peak time पर करीब 12 लोग शामिल होते हैं
• मुख्य game Dota 2 है, और साथ में Counter-Strike, Wolfenstein: Enemy Territory, Warcraft 3, Blobby Volley जैसे games भी खेले जाते हैं
• attendees के arrival और departure times अलग-अलग होते हैं, और बीच में बच्चे की देखभाल के लिए जाने वाले लोग भी होते हैं, इसलिए हर game में वही player count नहीं रहता
• Dota 2 आम तौर पर 5v5 खेला जाता है और एक match में करीब 40 मिनट लगते हैं; 4v5 जैसे imbalanced matches आसानी से एक तरफ झुक जाते हैं
• group में ऐसे लोग भी हैं जो Dota 2 regular खेलते हैं और ऐसे भी जो सिर्फ LAN party के समय खेलते हैं, इसलिए skill gap बड़ा है

Manual draft की सीमाएं

• पुराना तरीका आम तौर पर यह था कि सबसे अच्छे या सबसे कम experienced दो लोग leaders बनते थे, और school playground में teams चुनने की तरह बारी-बारी से teammates चुनते थे
• selection order ऐसा था: पहला leader 1 player चुनता, दूसरा leader 2 players, फिर पहला leader 2 players चुनता, और अंत में हर leader 1 player चुनता
  • यह पहले चुनने वाले side के advantage को कम करने के लिए एक variation था
• skill gap बड़ा होने के कारण आखिरकार अक्सर मिलती-जुलती या वही teams बन जाती थीं, और हर बार draft करने का मज़ा भी कम हो गया
• manual team selection में समय लगता था और यह झंझट भरा था; साथ ही कोई भी leader बनना नहीं चाहता था
  • जब player count match नहीं करता था, तब खासकर team imbalance बढ़ जाता था

पहली implementation: पुराने matches और Elo totals

• पिछली LAN party में team selection process से frustration बढ़ने पर, जल्दी से automation code लिखा गया
• पहले 35 पुराने match data इकट्ठा कर Colab में डाले गए, और हर match में winning team और losing team के players की list थी
• basic idea था Elo rating से player scores calculate करना
  • सभी players 1000 points से शुरू करते हैं
  • जीतने पर points मिलते हैं और हारने पर points खोते हैं
  • दो players के Elo difference से ही win rate calculate किया जाता है
• पहली simple implementation में winning player को 20 points जोड़ने और losing player से 20 points घटाने का तरीका था
• team composition requested players की सभी combinations देखकर बनाई जाती थी, और वह combination चुना जाता था जिसमें team Elo total का difference सबसे कम हो
  • example में 8 लोगों को दो teams में बांटा गया; एक team 4100 points और दूसरी 4080 points निकली

Iterative calculation से बेहतर Elo model

• सिर्फ 35 matches को एक बार scan करना data का कम उपयोग माना गया, इसलिए historical match data को कई बार repeat process किया गया
• improved Elo update सिर्फ ±20 points apply नहीं करता; stronger opponent को हराने पर ज्यादा points मिलते हैं और stronger opponent से हारने पर कम points घटते हैं
  • उदाहरण के लिए 1260 points वाले Spawek को 900 points वाले Goovie को हराने पर सिर्फ 4.47 points मिलते हैं
  • 900 points वाला Status अगर 1100 points वाले Dragon को हराता है तो उसे 30.38 points मिलते हैं
• calculation player-vs-player नहीं बल्कि team level पर था, इसलिए winning team और losing team के team Elo totals इस्तेमाल किए गए और update points teammates में बराबर बांटे गए
• यह तरीका LAN party के दौरान भी इस्तेमाल हुआ, और हर game के बाद नया data जोड़कर party के बाकी समय के लिए teams फिर बनाई जा सकती थीं
• कभी-कभी अगर साफ तौर पर imbalanced match generate होता, तो expected winner के साथ एक “fake match” data में जोड़कर teams फिर generate की जातीं

Win-rate prediction model वाला दूसरा improvement

• अगला improvement Elo को simple score table नहीं, बल्कि team win rate predict करने वाले model की तरह treat करना था
• model हर player का Elo store करता है और दो teams के SUM(Elo) की तुलना करके win probability calculate करता है
• पूरे match data पर simple L2 loss apply किया जाता है
  • winning team Elo total और losing team Elo total calculate किया जाता है
  • win probability calculate की जाती है
  • actual probability और predicted probability के difference का square लेकर loss में add किया जाता है
• training में backpropagation इस्तेमाल किया गया
  • forward pass से predicted win rate calculate किया गया
  • loss और win-rate function की derivative से यह calculate किया गया कि हर player का Elo loss को कितना प्रभावित करता है
  • LEARNING_RATE = 10_000.0, ITERATIONS = 10001 से Elo values update की गईं
• इस approach ने loss घटाने में सफलता पाई, लेकिन Elo values converge नहीं हुईं

Probabilistic match results से overfitting कम करना

• ML-style model ने पुराने matches के actual win rate को सभी जगह 1.0, यानी 100% win माना, जिससे overfitting हुआ
• model हर match को generalize करने के बजाय याद करने लगा, और कुछ matches में predicted win rate 0.999994567526197 जैसा लगभग 1 के बराबर हो गया
• goal पुराने results को ज्यों का त्यों encode करना नहीं, बल्कि अच्छी teams बनाना था, इसलिए definite win/loss की जगह probabilistic results इस्तेमाल करने में बदलाव किया गया
• पुराने match records को और देखकर matches को दो categories में बांटा गया
  • close games के लिए winning team का actual win rate 75% set किया गया
  • साफ तौर पर one-sided games के लिए winning team का actual win rate 95% set किया गया
• 75% win rate के लिए जरूरी Elo difference करीब 200 points है, और 100% win rate के लिए जरूरी Elo difference करीब 500 points से infinity तक है, इसलिए model के लिए सभी matches याद करना मुश्किल हो गया
• loss और backpropagation functions में real_probability = 1 के बजाय real_probability = game["win_probability"] इस्तेमाल करने के बाद loss तेजी से नीचे आया और player Elo भी reasonable level पर converge हुए

Odd number of players के साथ भी lineups बनाना

• नया system odd number of players वाली teams में भी win probability predict करके teams बना सकता है
• 2 हफ्ते बाद शुरू होने वाली LAN party की first lineup का example इस तरह है
  • team 1: Elo 2660
  • team 2: Elo 2655
• example lineup में एक side पर 4 लोग और दूसरी side पर 5 लोग हैं
  • team 1: Spawek, Bixkog, Bania, Goovie
  • team 2: Hypys, Muhah, J, Vifon, Status

[GN⁺]

Hacker News की राय

• जानना चाहता हूँ कि क्या किसी ने टीम-आधारित गेम्स में Elo/TrueSkill के अलावा कोई और तरीका इस्तेमाल किया है
  टीम का Elo जोड़कर या उसका औसत निकालकर matchmaking करना ऐसा लगता है जैसे व्यक्तिगत matchmaking के मॉडल में टीम matchmaking को जबरन फिट किया गया हो
  साथ ही, A और B साथ खेलें तो वे अपने व्यक्तिगत Elo के योग से भी मजबूत हो सकते हैं, लेकिन A और C साथ खेलें तो कमजोर पड़ सकते हैं — इस तरह की टीम के अंदर की तालमेल/अनुकूलता की बहुत-सी जानकारी खो जाती है

  • मेरा मानना है कि टीम-आधारित गेम्स में Elo आखिरकार जीत/हार के अलावा कुछ भी बचने नहीं देता
    खेलों में टीम हार जाए तब भी सीज़न के बाद All-Star या MVP निकल सकते हैं, और उल्टा चैंपियन टीम में होते हुए भी कोई खिलाड़ी मुख्य कारण न हो सकता है
    टीम ईस्पोर्ट्स में सब कुछ जीत पर टिका होता है, इसलिए लीग के सर्वश्रेष्ठ डिफेंडर, अटैकर, सपोर्ट जैसे खिलाड़ियों का प्रतिनिधित्व ठीक से ट्रैक या मान्यता नहीं पाता
    कई खेलों की तरह कुछ हद तक advanced metrics को ट्रैक करके शामिल किया जाना चाहिए। खिलाड़ी Elo स्वयं नहीं है, बल्कि assists per game, rebounds, points, RBIs, yards जैसे मूल्यों के ज़्यादा करीब है
    ऐसा करने पर यह ज़्यादा आसानी से दिखेगा कि किसी टीम को scoring की ज़रूरत है या defense की, इसलिए matchmaking भी “जीतने वाला ज़्यादा चाहिए/हारने वाला ज़्यादा चाहिए” की तुलना में अधिक स्वाभाविक रूप से फिट बैठेगी
  • जहाँ पहले से Elo इस्तेमाल होता है वहाँ भी अक्सर सिर्फ़ शुद्ध Elo नहीं होता। गेम डेवलपर matchmaking को adjust करने के लिए queue में लोगों की संख्या, पिछली बार खेलने के बाद बीता समय, कुल खेलों की संख्या, reports का इतिहास, खरीदे गए cosmetic items की संख्या जैसे factors इस्तेमाल करते हैं
    Elo की ताकत यह है कि लागत के मुकाबले इससे मिलने वाली जानकारी बहुत अधिक होती है। एक ऐसा एकल नंबर जो सब कुछ represent करता है — यही इसका सार है
    यह प्रकृति की सुंदर विविधता को पूरी तरह समझा नहीं पाता, लेकिन प्रतिद्वंद्वी की skill के बारे में जो जानना ज़रूरी है उसका 70% समेटने वाली सबसे कुशल abstraction के करीब है
  • सहमत हूँ। Elo एक rough लेकिन simple statistical model है, और इसकी सबसे बड़ी ताकत यह है कि इसे समझना और इससे अनुमान लगाना आसान है
    अच्छा होगा अगर multi-dimensional player skill vectors या embeddings, और उनके ऊपर चलने वाले अधिक non-linear models हों
    उदाहरण के लिए, कई गेम्स में टीम को आम तौर पर support players चाहिए होते हैं, लेकिन सिर्फ़ एक संख्या में वह जानकारी matchmaking के लिए काफ़ी नहीं समाती
  • मैंने इस पर बहुत सोचा है, लेकिन शायद कोई एक अंतिम समाधान नहीं है; यह खेल और खेले जा रहे variant rules पर बहुत निर्भर करता है
    उदाहरण के लिए, table football में ऐसे खिलाड़ी होते हैं जो singles और doubles दोनों खेलते हैं; दो बेहतरीन defenders एक टीम में हों तब भी वे उन अपेक्षाकृत कमजोर विरोधियों से हार सकते हैं जो अपने-अपने positions में बेहतर फिट बैठते हों
    Counter-Strike, Apex, Overwatch, और कुछ हद तक Dota जैसे गेम्स, जहाँ टीम बहुत सहारा दे सकती है, वे भी एक-दूसरे से अलग हैं। Counter-Strike में skill की कमी वाला या headset के बिना एक कमजोर teammate पूरे गेम को बिगाड़ सकता है, जबकि Overwatch में कोई support class चुनकर पीछे आराम से खेल सकता है और बाकी टीम के जीतने का इंतज़ार कर सकता है
    Chemistry भी होती है। जैसा हम workplace में देखते हैं, कुछ synergies सिर्फ़ खास combinations में बनती हैं, या साधारण playstyle differences भी नतीजे बदल सकती हैं
    billiards जैसे देखने में मिलते-जुलते variant games में भी कुछ खिलाड़ी एक format में चमकते हैं लेकिन दूसरे में उतना अच्छा नहीं कर पाते
  • मैंने एक बार PageRank इस्तेमाल किया था, और वह काफ़ी अच्छा चला। जीत को links की तरह माना, score को हारने वाले से जीतने वाले की ओर बहने दिया, और link strength को समय के साथ घटने दिया

• लगता है Kaggle पर rating systems की कोई competition थी, या शायद अब भी है
  https://www.kaggle.com/competitions/chess/discussion/107
  Elo से बेहतर प्रदर्शन करने वाले rating systems काफ़ी हैं

  • leaderboard में सिर्फ़ प्रतिभागियों के नाम दिखते हैं; जानना चाहता हूँ कि हर किसी का तरीका कैसे देखा जा सकता है

• tournaments के लिए मुझे Swiss system पसंद है, जो मेरी जानकारी में chess में काफ़ी लोकप्रिय है
  [1]: https://en.wikipedia.org/wiki/Swiss-system_tournament

  • मज़ेदार बात यह है कि हमारे स्थानीय community ने हाल ही में billiards tournament Swiss system से शुरू किया, और वह काफ़ी अच्छा है। बस fairness और आमंत्रित किए जा सकने वाले खिलाड़ियों की संख्या के बीच एक समझौता है
    6 rounds वाले Swiss format में लगभग 40 लोग उचित लगते हैं, लेकिन अगर 100 से अधिक लोगों को बुलाना हो तो 2-loss elimination bracket इस्तेमाल करना पड़ता है। नहीं तो tournament में एक हफ़्ता लग जाएगा
    इसकी सबसे अच्छी बात यह है कि लागत के हिसाब से value बहुत अच्छी मिलती है। नतीजा चाहे जो हो, आप पूरे tournament में खेलते रहते हैं, और जैसे-जैसे यह आगे बढ़ता है विरोधी आपके level के करीब आते जाते हैं, इसलिए हर कोई मज़े से खेल सकता है
  • Magic और दूसरे card game tournaments में भी यह आम है, बस थोड़ा modified रूप में। “Swiss 6 rounds के बाद top 8 single-elimination” जैसी संरचना अक्सर दिखती है
  • मोटे तौर पर पढ़ने पर लगता है कि पहले round में आपको किसी random team से मिलाया जाता है, फिर हर round में खिलाड़ियों को cumulative score के आधार पर sort किया जाता है और समान या मिलते-जुलते score वाले प्रतिद्वंद्वियों से मिलाया जाता है। साथ ही, एक ही opponent से दो बार खेलने से बचा जाता है
    कितने rounds होने चाहिए, यह कैसे तय करते हैं, यह मुझे ठीक से नहीं पता, लेकिन शायद वही मुख्य बात नहीं है
    analysis section को देखें तो knockout tournament की तुलना में, अगर draw न हों, तो स्पष्ट विजेता तय करने के लिए जितने rounds चाहिए वे उतने ही होते हैं जितने knockout में
    Swiss system का फ़ायदा यह है कि इसमें किसी को eliminate नहीं किया जाता, और final standings सिर्फ़ विजेता ही नहीं बल्कि पूरे field की relative strength का भी कुछ हद तक संकेत देती हैं
    हालाँकि, अगर कोई खिलाड़ी बहुत आगे निकल जाए तो आख़िरी round से पहले ही उसकी जीत पक्की हो सकती है, इसलिए इसका अंत हमेशा dramatic नहीं होता

• सोच रहा हूँ कि Shapley value आज़माना कैसा रहेगा

  • इसका मतलब नहीं पता था, तो खोजा। लिखा था कि यह cooperative game theory का एक solution concept है, Lloyd Shapley के नाम पर, और यह पूरे खिलाड़ियों के coalition द्वारा बनाए गए total surplus को हर खिलाड़ी में uniquely distribute करता है
    यह लगभग Wikipedia की शुरुआत जैसा ही है, लेकिन पढ़ने के बाद भी ठीक से समझ नहीं आया। यहाँ cooperative game का total surplus क्या है — क्या AoE में टीम ने जितनी लकड़ी जुटाई वह जैसी कोई चीज़?
    और उसे “distribute” करने से मदद कैसे मिलेगी, यह भी समझ नहीं आता; बल्कि लगता है कि वही तो game result होना चाहिए। अगर कोई इसे आसान भाषा में समझा सके तो अच्छा होगा