SpawELO - LAN partileri için küçük ölçekli ücretsiz eşleştirme sistemi

• LAN partisi geleneğini 16 yıldır sürdüren bir arkadaş grubunda, Dota 2 takımlarını her seferinde elle seçmek zorlaşınca takım seçimini otomatikleştiren SpawELO ortaya çıktı
• Yetenek farkları ve değişken katılımcı sayısı nedeniyle manuel draft sık sık benzer takımların tekrarlanmasına ve tek sayılı oyuncularda dengesizliğe yol açıyordu
• İlk uygulama, 35 geçmiş maç ve Elo puanları ile takım başına toplam puanı en yakın olan kombinasyonu buldu; ardından maç sonuçlarını tekrar tekrar yansıtarak puanları düzeltti
• Kazanma olasılığı tahmin modeline geçildikten sonra oyuncu Elo'ları L2 kaybı ve geri yayılım ile ayarlandı; ancak tüm galibiyetler %100 kabul edilince geçmiş maçları ezberleyen bir aşırı öğrenme ortaya çıktı
• Son yaklaşım, maç sonuçlarını %75 veya %95'lik olasılıksal galibiyet olarak ele alarak aşırı öğrenmeyi azalttı ve 4v5 gibi tek sayılı oyuncu düzenlerinde de kullanılabilecek takım eşleştirmeyi hedefledi

---

LAN partisinde ortaya çıkan takım seçimi sorunu

• Arkadaş grubu son 16 yıldır her yıl en az bir kez LAN partisi düzenliyor; etkinlik genelde 4-5 gün sürüyor ve en yoğun zamanda yaklaşık 12 kişi katılıyor
• Ana oyun Dota 2, ancak Counter-Strike, Wolfenstein: Enemy Territory, Warcraft 3 ve Blobby Volley gibi oyunlar da oynanıyor
• Katılımcılar farklı zamanlarda geliyor ve ayrılıyor; hatta arada çocuğuyla ilgilenmeye gidenler de olduğundan oyunlar her seferinde aynı kadroyla oynanmıyor
• Dota 2 genelde 5v5 oynanıyor ve bir maç yaklaşık 40 dakika sürüyor; 4v5 gibi dengesiz maçlar ise kolayca tek taraflı hale gelebiliyor
• Grup içinde Dota 2'yi düzenli oynayanlarla yalnızca LAN partisinde oynayanlar karışık olduğu için beceri farkı büyük

Manuel draftın sınırları

• Önceki yöntemde genelde en iyi oynayan ya da en az deneyimli iki kişi lider oluyor, okul bahçesinde takım seçer gibi sırayla oyuncu seçiliyordu
• Seçim sırası, ilk liderin 1 kişi seçmesi, ikinci liderin 2 kişi seçmesi, sonra ilk liderin 2 kişi seçmesi ve en sonda her liderin 1'er kişi seçmesi şeklindeydi
  • Bu, ilk seçen tarafın avantajını azaltmak için yapılan bir uyarlamaydı
• Beceri farkı büyük olduğundan sonuçta sık sık benzer ya da aynı takımlar oluşuyor, her seferinde draft yapmanın eğlencesi de azalıyor
• Manuel takım seçimi zaman alıyor ve uğraştırıyordu; ayrıca kimse liderliği üstlenmek istemiyordu
  • Oyuncu sayısı tam uymadığında takım dengesizliği özellikle büyüyordu

İlk uygulama: geçmiş maçlar ve Elo toplamı

• Son LAN partisinde takım seçme sürecine yönelik memnuniyetsizlik artınca otomasyonu hızlıca sağlayan bir kod yazıldı
• Önce 35 geçmiş maç verisi toplanıp Colab'a eklendi; her maçta kazanan takım ve kaybeden takım oyuncularının listesi yer alıyordu
• Temel fikir, oyuncu puanlarını Elo rating ile hesaplamaktı
  • Tüm oyuncular 1000 puanla başlıyordu
  • Kazanırsan puan alıyor, kaybedersen puan kaybediyordun
  • Kazanma olasılığı yalnızca iki oyuncu arasındaki Elo farkından hesaplanıyordu
• İlk basit uygulama, kazanan oyunculara 20 puan ekleyip kaybeden oyunculardan 20 puan düşüyordu
• Takım oluşturma, istenen oyuncuların tüm kombinasyonlarına bakıp takım Elo toplamı farkı en küçük olan kombinasyonu seçerek yapılıyordu
  • Örnekte 8 kişi iki takıma ayrıldı ve bir takım 4100 puan, diğeri 4080 puan olarak hesaplandı

Yinelemeli hesaplamayla geliştirilen Elo modeli

• Yalnızca 35 maçı bir kez taramanın veriyi yeterince kullanmadığı düşünülerek geçmiş maç verileri birkaç kez tekrar işlendi
• Geliştirilmiş Elo güncellemesi, sadece ±20 puan uygulamak yerine daha güçlü rakibi yenince daha fazla puan kazandıran ve daha güçlü rakibe kaybedince daha az puan kaybettiren bir yapıdaydı
  • Örneğin 1260 puanlı Spawek, 900 puanlı Goovie'yi yenerse yalnızca 4.47 puan kazanıyor
  • 900 puanlı Status, 1100 puanlı Dragon'u yenerse 30.38 puan kazanıyor
• Hesaplama bire bir değil takım bazında yapıldığı için, kazanan ve kaybeden tarafın takım Elo toplamı kullanıldı ve güncelleme puanları takım üyelerine eşit dağıtıldı
• Bu yöntem LAN partisi sırasında da kullanıldı; her oyundan sonra yeni veri eklenerek partinin kalanında takımlar yeniden oluşturulabildi
• Bazen açıkça dengesiz bir eşleşme çıktığında, beklenen kazananı içeren “sahte maç” veriye eklenip takımlar yeniden oluşturuluyordu

Kazanma olasılığı tahmin modeline dönüştürülen ikinci geliştirme

• Sonraki geliştirme, Elo'yu basit bir puan tablosu değil, takımın kazanma olasılığını tahmin eden bir model gibi ele alma yaklaşımıydı
• Model her oyuncunun Elo'sunu saklıyor ve iki takımın SUM(Elo) değerlerini karşılaştırarak kazanma olasılığını hesaplıyordu
• Tüm maç verisi üzerinde basit bir L2 kaybı uygulandı
  • Kazanan takımın Elo toplamı ve kaybeden takımın Elo toplamı hesaplanıyor
  • Kazanma olasılığı hesaplanıyor
  • Gerçek olasılık ile tahmin edilen olasılık arasındaki farkın karesi kayba ekleniyor
• Eğitimde backpropagation kullanıldı
  • İleri yayılım ile tahmini kazanma olasılığı hesaplanıyor
  • Kayıp ve kazanma olasılığı fonksiyonunun türeviyle her oyuncunun Elo'sunun kayıp üzerindeki etkisi hesaplanıyor
  • LEARNING_RATE = 10_000.0, ITERATIONS = 10001 ile Elo değerleri güncelleniyor
• Bu yaklaşım kaybı azaltmakta başarılı oldu, ancak Elo değerleri yakınsamadı

Aşırı öğrenmeyi azaltan olasılıksal maç sonuçları

• ML tarzı model, geçmiş maçların gerçek kazanma olasılığını hep 1.0 yani %100 galibiyet olarak ele aldığı için aşırı öğrenme oluştu
• Model her maçı genellemek yerine ezberledi ve bazı maçlarda tahmini kazanma olasılığı 0.999994567526197 gibi neredeyse 1'e ulaştı
• Amaç geçmiş sonuçları aynen kodlamak değil iyi takımlar kurmak olduğundan, kesin galibiyet/mağlubiyet yerine olasılıksal sonuçlar kullanılacak şekilde değiştirildi
• Geçmiş maç kayıtları yeniden incelenerek maçların yapısı iki türe ayrıldı
  • Çekişmeli geçen maçlarda kazanan takımın gerçek kazanma olasılığı %75 olarak belirlendi
  • Açık biçimde tek tarafa kayan maçlarda kazanan takımın gerçek kazanma olasılığı %95 olarak belirlendi
• %75 kazanma olasılığı için gereken Elo farkı yaklaşık 200 puan; %100 kazanma olasılığı için gereken fark ise yaklaşık 500 puandan sonsuza uzandığı için modelin tüm maçları ezberlemesi zorlaştı
• loss ve backpropagation fonksiyonlarında real_probability = 1 yerine real_probability = game["win_probability"] kullanılınca kayıp hızla düştü ve oyuncu Elo'ları da makul seviyelerde yakınsadı

Tek sayılı oyuncularda da kadro oluşturma

• Yeni sistem, tek sayılı oyuncu bulunan takımlarda da kazanma olasılığını tahmin edip takım oluşturabiliyor
• İki hafta sonra başlayacak LAN partisinin ilk kadro örneği şöyle
  • team 1: Elo 2660
  • team 2: Elo 2655
• Örnek kadroda bir tarafta 4, diğer tarafta 5 oyuncu var
  • team 1: Spawek, Bixkog, Bania, Goovie
  • team 2: Hypys, Muhah, J, Vifon, Status

[GN⁺]

Hacker News yorumları

• Takım tabanlı oyunlarda Elo/TrueSkill tabanlı olmayan bir yöntemi kullanan olup olmadığını merak ediyorum
  Takımın Elo’sunu toplamak ya da ortalamasını alıp eşleştirme yapmak, bireysel eşleştirme modeline takım eşleştirmesini zorla uydurulmuş geçici bir çözüm gibi geliyor
  Ayrıca A ve B birlikte oynayınca bireysel Elo toplamlarından daha güçlü olurken, A ve C birlikte oynayınca daha zayıf olabiliyorsa, takım içi uyum bilgisi büyük ölçüde kayboluyor

  • Bence Elo, takım tabanlı oyunlarda sonuçta galibiyet/mağlubiyet dışında hiçbir şeyi bırakmıyor
    Sporlarda takım kaybetse bile sezon sonunda all-star ya da MVP çıkabilir; tersine şampiyon takımda olup da kilit oyuncu olmayabilirsin
    Takım e-sporlarında her şey galibiyete bağlı olduğundan, lig genelindeki üst düzey savunmacı, hücumcu ya da destek gibi oyuncu tiplerinin temsili iyi takip edilmiyor ya da takdir edilmiyor
    Birçok sporda olduğu gibi belli ölçüde ileri istatistikler izlenip hesaba katılmalı. Oyuncu, Elo’nun kendisinden ziyade maç başına asist, ribaund, sayı, RBI, yard gibi değerlere daha yakın
    Böyle olunca takımın daha fazla skora mı yoksa daha fazla savunmaya mı ihtiyaç duyduğu kolayca görülür; bu da eşleştirmeyi “daha çok kazanana ihtiyaç var / daha çok kaybedene ihtiyaç var” yaklaşımından daha doğal hale getirir
  • Elo kullanan yerler bile zaten saf Elo kullanmıyor. Oyun şirketleri eşleştirmeyi ayarlamak için kuyruktaki kişi sayısı, son oyundan beri geçen süre, toplam oynama sayısı, rapor geçmişi, satın alınan kozmetik sayısı gibi etkenleri kullanıyor
    Elo’nun gücü, maliyetine kıyasla sağladığı bilginin fazla olmasında. Tek bir sayının her şeyi temsil etmesi asıl mesele
    Doğanın güzel çeşitliliğini kusursuz açıklamasa da, rakibin becerisi hakkında bilmen gereken şeylerin %70’ini taşıyan en verimli soyutlamaya yakın
  • Katılıyorum. Elo kaba ama basit bir istatistiksel model ve en büyük avantajı anlaşılmasının ve onun üzerinden akıl yürütmenin kolay olması
    Daha fazla bilgi taşıyan çok boyutlu oyuncu beceri vektörleri ya da embedding’ler ve bunların üstüne kurulan daha doğrusal olmayan modeller güzel olurdu
    Örneğin birçok oyunda takımın genelde bir destek oyuncusuna ihtiyacı olur ama tek bir sayıyla bu bilgiyi eşleştirmeye taşımak zor
  • Bunu çok düşündüm ama tek bir nihai çözüm varmış gibi görünmüyor; spor dalına ve oynanan varyanta göre çok değişiyor
    Örneğin masa futbolunda hem teklerde hem çiftlerde oynayan oyuncular var; iki harika savunmacı aynı takımda olsa bile, her pozisyona daha uygun daha zayıf rakiplere yenilebilirler
    Counter-Strike, Apex, Overwatch ve belli ölçüde Dota gibi takım desteğinin büyük fark yarattığı oyunlar da birbirinden farklı. Counter-Strike’ta yetersiz ya da kulaklığı olmayan tek bir zayıf takım arkadaşı tüm oyunu mahvedebilirken, Overwatch’ta destek sınıfını seçip arkada nispeten rahat oynayıp takımın geri kalanının maçı kazanmasını bekleyebilirsin
    Bir de kimya var. İş yerinde de gördüğümüz gibi, yalnızca belli kombinasyonlarda ortaya çıkan sinerji ya da basit oyun tarzı farkları sonucu değiştirebilir
    Bilardo gibi benzer görünen varyant oyunlarda bile bazı oyuncular bir disiplinde parlayıp diğerinde aynı performansı gösteremeyebiliyor
  • Bir kez PageRank kullandım ve epey iyi çalıştı. Galibiyetleri bağlantı gibi ele aldım, puanın kaybedenden kazanana akmasını sağladım ve bağlantı gücünü zaman geçtikçe azalttım

• Kaggle’da derecelendirme sistemleriyle ilgili bir yarışma vardı ya da hâlâ var sanırım
  https://www.kaggle.com/competitions/chess/discussion/107
  Elo’dan daha iyi performans veren epey derecelendirme sistemi var

  • Sıralama tablosunda yalnızca katılımcı adları görünüyor; herkesin hangi yöntemi kullandığını nasıl görebileceğimizi merak ediyorum

• Turnuvalar için, satrançta popüler olduğunu bildiğim İsviçre sistemi hoşuma gidiyor
  [1]: https://en.wikipedia.org/wiki/Swiss-system_tournament

  • İlginç bir şekilde, yerel topluluğumuz yakın zamanda bir bilardo turnuvasını İsviçre sistemi ile başlattı ve oldukça iyi gidiyor. Yine de adalet ile davet edilebilecek oyuncu sayısı arasında bir ödünleşim var
    İsviçre sisteminde 6 tur için en fazla yaklaşık 40 kişi makul; ama 100’den fazla kişiyi davet etmek istiyorsanız 2 mağlubiyetle elenilen bir fikstür kullanmanız gerekiyor. Yoksa turnuva bir hafta sürer
    En iyi yanı, maliyetine göre çok değer sunması. Sonuç ne olursa olsun turnuva boyunca oynamaya devam ediyorsun ve ilerledikçe rakipler seviyene daha uygun hale geliyor; bu yüzden herkes için eğlenceli olabiliyor
  • Magic ve diğer kart oyunu turnuvalarında da yaygın ama biraz değiştirilmiş biçimde kullanılıyor. “6 tur İsviçre, ardından ilk 8 tek maç eleme” gibi yapılar sık görülüyor
  • Kabaca okuyunca anladığım kadarıyla ilk turda rastgele bir takımla eşleşiyorsun; sonra her turda oyuncular kümülatif puana göre sıralanıyor ve aynı ya da benzer puandaki rakiplerle eşleştiriliyor. Aynı rakiple iki kez oynamaktan da kaçınılıyor
    Kaç tur oynanacağına nasıl karar verildiğini pek bilmiyorum ama asıl kritik ayrıntı bu mu emin değilim
    Analiz kısmına bakınca, beraberlik olmadığı varsayımıyla net bir şampiyon çıkarmak için gereken tur sayısının eleme usulüyle aynı olduğu söyleniyor
    İsviçre sisteminin avantajı, kimseyi elemeden sadece şampiyonu değil tüm katılımcıların göreli gücünü de bir ölçüde göstermesi
    Yine de bir oyuncu fazla öne geçerse son turdan önce şampiyonluğu garantileyebilir; yani her zaman dramatik bir finalle bitmeyebilir

• Shapley değeri denemek nasıl olur diye merak ediyorum

  • Ne demek olduğunu bilmediğim için baktım; kooperatif oyun teorisinde bir çözüm kavramıymış, adını Lloyd Shapley’den alıyormuş ve tüm oyuncular koalisyonunun ürettiği toplam fazlalığı her oyuncuya benzersiz biçimde dağıttığı yazıyor
    Bu neredeyse Wikipedia girişinin aynısı ama okuyunca yine de pek anlamadım. Buradaki kooperatif oyunun toplam fazlalığı nedir; mesela AoE’de takımın topladığı odun miktarı gibi bir şey mi diye merak ediyorum
    Bunu “dağıtmanın” nasıl yardımcı olacağını da anlamıyorum; hatta bunun oyunun sonucu olması gerekmez mi diye düşünüyorum. Bunu basitçe açıklayabilecek biri olursa harika olur