SpawELO - Hệ thống ghép trận nhỏ, miễn phí cho LAN party

• Khi việc chọn đội Dota 2 thủ công mỗi lần tại LAN party của nhóm bạn kéo dài suốt 16 năm trở nên khó khăn, SpawELO đã được tạo ra để tự động hóa việc chọn đội
• Do chênh lệch trình độ và số người tham dự thay đổi linh hoạt, draft thủ công thường tạo ra các đội giống nhau lặp lại và mất cân bằng khi số người lẻ
• Phiên bản đầu tiên dùng 35 trận trong quá khứ và điểm Elo để tìm tổ hợp có tổng điểm giữa các đội gần nhau nhất, sau đó liên tục phản ánh kết quả trận đấu để hiệu chỉnh điểm
• Sau khi chuyển sang mô hình dự đoán tỷ lệ thắng, hệ thống điều chỉnh Elo của người chơi bằng L2 loss và lan truyền ngược, nhưng khi xử lý mọi chiến thắng là 100% thì phát sinh overfitting do ghi nhớ các trận cũ
• Cách làm cuối cùng xem kết quả trận đấu là chiến thắng mang tính xác suất 75% hoặc 95% nhằm giảm overfitting, đồng thời hướng tới ghép đội dùng được cả trong cấu hình số người lẻ như 4v5

---

Vấn đề chọn đội lộ rõ tại LAN party

• Nhóm bạn đã tổ chức LAN party ít nhất mỗi năm một lần trong 16 năm qua; sự kiện thường kéo dài 4–5 ngày và vào giờ cao điểm có khoảng 12 người tham gia
• Trò chơi chính là Dota 2, ngoài ra họ cũng chơi Counter-Strike, Wolfenstein: Enemy Territory, Warcraft 3, Blobby Volley
• Người tham dự đến và rời đi vào các thời điểm khác nhau, cũng có người phải rời giữa chừng để chăm con, nên không phải lúc nào trận đấu cũng diễn ra với cùng một nhóm người
• Dota 2 thường chơi 5v5, mỗi ván mất khoảng 40 phút; các trận mất cân bằng như 4v5 dễ nghiêng hẳn về một phía
• Trong nhóm có cả người chơi Dota 2 thường xuyên lẫn người chỉ chơi vào dịp LAN party, nên chênh lệch trình độ rất lớn

Giới hạn của draft thủ công

• Cách làm trước đây thường là chọn hai người giỏi nhất hoặc ít kinh nghiệm nhất làm đội trưởng, rồi lần lượt chọn đồng đội như chọn đội trên sân trường
• Thứ tự chọn là đội trưởng đầu tiên chọn 1 người, đội trưởng thứ hai chọn 2 người, rồi đội trưởng đầu tiên lại chọn 2 người, cuối cùng mỗi đội trưởng chọn thêm 1 người
  • Đây là một biến thể nhằm giảm lợi thế của bên được chọn trước
• Vì chênh lệch trình độ lớn, kết quả là các đội tương tự hoặc giống hệt nhau thường xuyên được tạo ra, và việc draft mỗi lần cũng bớt thú vị
• Chọn đội thủ công tốn thời gian, phiền phức, và còn có vấn đề là không ai muốn làm đội trưởng
  • Khi số người không khớp, mất cân bằng đội đặc biệt lớn

Phiên bản đầu tiên: trận cũ và tổng Elo

• Khi sự bất mãn với quá trình chọn đội tăng lên tại LAN party gần nhất, một đoạn mã tự động hóa đã được viết nhanh
• Trước hết, 35 trận đấu trong quá khứ được thu thập và đưa vào Colab; mỗi trận có danh sách người chơi của đội thắng và đội thua
• Ý tưởng cơ bản là tính điểm người chơi bằng Elo rating
  • Tất cả người chơi bắt đầu từ 1000 điểm
  • Thắng thì được điểm, thua thì mất điểm
  • Tỷ lệ thắng được tính chỉ từ chênh lệch Elo giữa hai người chơi
• Phiên bản đơn giản đầu tiên cộng 20 điểm cho người chơi thắng và trừ 20 điểm của người chơi thua
• Đội hình được tạo bằng cách xét tất cả tổ hợp của những người chơi được yêu cầu, rồi chọn tổ hợp có chênh lệch tổng Elo của đội nhỏ nhất
  • Trong ví dụ, 8 người được chia thành hai đội; một đội có 4100 điểm, đội kia có 4080 điểm

Cải thiện mô hình Elo bằng tính toán lặp

• Việc chỉ duyệt 35 trận một lần được xem là chưa tận dụng đủ dữ liệu, nên dữ liệu trận cũ được xử lý lặp lại nhiều lần
• Cập nhật Elo cải tiến không chỉ áp dụng ±20 điểm đơn giản, mà theo cấu trúc: thắng đối thủ mạnh hơn thì nhận nhiều điểm hơn, thua đối thủ mạnh hơn thì mất ít điểm hơn
  • Ví dụ, Spawek 1260 điểm thắng Goovie 900 điểm thì chỉ nhận 4,47 điểm
  • Status 900 điểm thắng Dragon 1100 điểm thì nhận 30,38 điểm
• Vì tính theo đội thay vì cá nhân đối đầu cá nhân, hệ thống dùng tổng Elo của đội thắng và đội thua, rồi chia đều điểm cập nhật cho các thành viên
• Cách này cũng được dùng trong LAN party; sau mỗi trận, dữ liệu mới được thêm vào để tạo lại đội cho phần còn lại của buổi party
• Đôi khi nếu hệ thống tạo ra một trận rõ ràng mất cân bằng, họ thêm một “trận giả” với người thắng dự kiến vào dữ liệu rồi tạo lại đội

Cải tiến thứ hai: chuyển sang mô hình dự đoán tỷ lệ thắng

• Cải tiến tiếp theo là xem Elo không phải như bảng điểm đơn thuần, mà như một mô hình dự đoán tỷ lệ thắng của đội
• Mô hình lưu Elo của từng người chơi và tính xác suất thắng bằng cách so sánh SUM(Elo) của hai đội
• Trên toàn bộ dữ liệu trận đấu, hệ thống áp dụng L2 loss đơn giản
  • Tính tổng Elo của đội thắng và đội thua
  • Tính xác suất thắng
  • Bình phương chênh lệch giữa xác suất thực tế và xác suất dự đoán rồi cộng vào loss
• Việc huấn luyện dùng backpropagation
  • Tính tỷ lệ thắng dự đoán bằng lan truyền tiến
  • Dùng loss và đạo hàm của hàm tỷ lệ thắng để tính mức ảnh hưởng của Elo từng người chơi lên loss
  • Cập nhật giá trị Elo với LEARNING_RATE = 10_000.0, ITERATIONS = 10001
• Cách này đã giảm được loss, nhưng giá trị Elo không hội tụ

Kết quả trận đấu mang tính xác suất để giảm overfitting

• Mô hình kiểu ML bị overfitting khi xem tỷ lệ thắng thực tế của mọi trận cũ là 1.0, tức thắng 100%
• Khi mô hình ghi nhớ từng trận thay vì khái quát hóa, ở một số trận tỷ lệ thắng dự đoán gần như bằng 1, chẳng hạn 0.999994567526197
• Mục tiêu không phải là mã hóa nguyên xi kết quả quá khứ, mà là tạo đội tốt, nên hệ thống được đổi sang dùng kết quả mang tính xác suất thay vì thắng thua chắc chắn
• Sau khi kiểm tra thêm lịch sử trận đấu, các trận được chia thành hai loại
  • Những trận sít sao được đặt tỷ lệ thắng thực tế của đội thắng là 75%
  • Những trận rõ ràng nghiêng về một phía được đặt tỷ lệ thắng thực tế của đội thắng là 95%
• Chênh lệch Elo cần cho tỷ lệ thắng 75% là khoảng 200 điểm, còn chênh lệch Elo cần cho tỷ lệ thắng 100% nằm trong khoảng từ khoảng 500 điểm đến vô hạn, khiến mô hình khó ghi nhớ mọi trận hơn
• Sau khi đổi trong các hàm loss và backpropagation từ real_probability = 1 sang real_probability = game["win_probability"], loss giảm nhanh và Elo của người chơi cũng hội tụ về mức hợp lý

Tạo lineup ngay cả khi số người lẻ

• Hệ thống mới có thể dự đoán tỷ lệ thắng và tạo đội ngay cả với các đội có số người lẻ
• Ví dụ lineup đầu tiên cho LAN party bắt đầu sau 2 tuần như sau
  • team 1: Elo 2660
  • team 2: Elo 2655
• Lineup ví dụ có một bên 4 người và bên kia 5 người
  • team 1: Spawek, Bixkog, Bania, Goovie
  • team 2: Hypys, Muhah, J, Vifon, Status

[GN⁺]

Ý kiến trên Hacker News

• Tôi tò mò liệu đã có ai từng dùng cách không dựa trên Elo/TrueSkill trong game theo đội chưa
  Việc cộng hoặc lấy trung bình Elo của cả đội để matchmaking có cảm giác như một giải pháp tạm bợ, cố nhét mô hình dành cho matchmaking cá nhân vào matchmaking theo đội
  Ngoài ra, nó làm mất rất nhiều thông tin về độ tương hợp nội bộ trong đội, kiểu A và B chơi cùng nhau thì mạnh hơn tổng Elo cá nhân, nhưng A và C chơi cùng nhau thì lại yếu hơn

  • Tôi cho rằng trong game theo đội, Elo rốt cuộc khiến chẳng còn lại gì ngoài thắng/thua
    Trong thể thao, dù đội thua thì sau mùa giải vẫn có thể có All-Star hoặc MVP, và ngược lại, một người trong đội vô địch chưa chắc đã là nhân tố cốt lõi
    Trong e-sports đồng đội, mọi thứ đều đặt vào chiến thắng, nên biểu hiện của các người chơi như hậu vệ, tấn công, hỗ trợ hàng đầu toàn giải không được theo dõi hay công nhận tốt
    Cần theo dõi và phản ánh phần nào các chỉ số nâng cao như trong nhiều môn thể thao. Người chơi không phải là bản thân Elo, mà gần với các giá trị như kiến tạo mỗi trận, rebound, điểm số, RBI, yard hơn
    Khi đó sẽ dễ thấy đội cần ghi điểm nhiều hơn hay phòng thủ nhiều hơn, nên matchmaking cũng có thể khớp tự nhiên hơn so với “cần thêm người thắng/cần thêm người thua”
  • Ngay cả những nơi đã dùng Elo cũng không chỉ dùng Elo thuần túy. Các nhà phát triển game hiệu chỉnh matchmaking bằng các yếu tố như số người trong hàng đợi, thời gian kể từ lần chơi gần nhất, tổng số trận đã chơi, lịch sử bị report, số vật phẩm trang trí đã mua
    Điểm mạnh của Elo là lượng thông tin thu được so với chi phí rất lớn. Điểm cốt lõi là nó là một con số duy nhất đại diện cho mọi thứ
    Nó không thể giải thích hoàn hảo sự đa dạng đẹp đẽ của tự nhiên, nhưng gần như là phép trừu tượng hóa hiệu quả nhất chứa khoảng 70% những gì cần biết về trình độ đối thủ
  • Đồng ý. Elo là một mô hình thống kê thô nhưng đơn giản, và ưu điểm lớn nhất là dễ hiểu, dễ suy luận
    Sẽ tốt hơn nếu có vector kỹ năng người chơi đa chiều hoặc embedding chứa nhiều thông tin hơn, cùng một mô hình phi tuyến hơn đặt trên đó
    Ví dụ trong nhiều game, một đội thường cần người chơi hỗ trợ, nhưng chỉ một con số thì không đủ để đưa thông tin đó vào matchmaking
  • Tôi đã nghĩ khá nhiều về chuyện này, nhưng có vẻ không có một lời giải tối thượng duy nhất; nó thay đổi rất nhiều tùy theo môn và biến thể luật đang chơi
    Ví dụ trong bi lắc, có những người chơi cả đánh đơn lẫn đánh đôi, nhưng hai hậu vệ giỏi vào cùng một đội vẫn có thể thua một đối thủ yếu hơn nhưng phù hợp hơn với từng vị trí
    Những game mà đội có thể gánh nhau nhiều như Counter-Strike, Apex, Overwatch, và ở mức nào đó là Dota, cũng khác nhau. Trong Counter-Strike, một đồng đội yếu, thiếu kỹ năng hoặc không có headset có thể phá hỏng cả trận, nhưng trong Overwatch thì có thể chọn lớp hỗ trợ, nghỉ ở phía sau và chờ phần còn lại của đội thắng
    Còn có cả chemistry nữa. Như thấy ở nơi làm việc, synergy chỉ xuất hiện ở một số tổ hợp nhất định hoặc khác biệt đơn giản về lối chơi cũng có thể thay đổi kết quả
    Ngay cả trong những biến thể game trông khá giống nhau như bi-a, có người chơi tỏa sáng ở một thể loại nhưng lại không thuận lợi ở thể loại khác
  • Tôi từng thử dùng PageRank một lần và nó hoạt động khá tốt. Tôi xem chiến thắng như liên kết, cho điểm chảy từ người thua sang người thắng, và làm cường độ liên kết giảm dần theo thời gian

• Hình như Kaggle từng có, hoặc hiện vẫn có, một cuộc thi về hệ thống xếp hạng
  https://www.kaggle.com/competitions/chess/discussion/107
  Có khá nhiều hệ thống xếp hạng có hiệu năng tốt hơn Elo

  • Trên bảng xếp hạng chỉ thấy tên người tham gia, tôi tò mò làm sao xem được phương pháp của từng người

• Với tournament, tôi thích hệ Thụy Sĩ, vốn nổi tiếng trong cờ vua
  [1]: https://en.wikipedia.org/wiki/Swiss-system_tournament

  • Một điều thú vị là cộng đồng địa phương của chúng tôi gần đây bắt đầu tổ chức tournament bi-a theo hệ Thụy Sĩ, và khá ổn. Tuy nhiên có sự đánh đổi giữa tính công bằng và số người chơi có thể mời
    Với thể thức Thụy Sĩ, nếu 6 vòng thì tối đa khoảng 40 người là hợp lý, nhưng nếu muốn mời hơn 100 người thì phải dùng nhánh loại sau 2 trận thua. Nếu không tournament sẽ kéo dài cả tuần
    Điểm hay nhất là giá trị nhận được so với chi phí rất tốt. Bất kể kết quả, mọi người vẫn tiếp tục chơi suốt tournament, và càng về sau đối thủ càng được ghép gần với trình độ của mình, nên ai cũng có thể chơi vui
  • Thể thức này cũng phổ biến trong các tournament Magic và những game thẻ bài khác, nhưng thường được chỉnh sửa đôi chút. Cấu trúc như “6 vòng Thụy Sĩ rồi top 8 loại trực tiếp một ván” thường hay thấy
  • Đọc qua thì có vẻ sau khi gặp đội ngẫu nhiên ở vòng đầu, mỗi vòng sẽ sắp xếp người chơi theo điểm tích lũy và ghép với đối thủ có điểm bằng hoặc tương tự. Đồng thời tránh để gặp cùng một đối thủ hai lần
    Tôi không rõ quyết định cần bao nhiêu vòng như thế nào, nhưng cũng không chắc chi tiết đó có phải là cốt lõi không
    Nhìn phần phân tích thì so với tournament loại trực tiếp, nếu giả định không có hòa, số vòng cần để xác định một nhà vô địch rõ ràng là như nhau
    Hệ Thụy Sĩ có ưu điểm là không loại ai, và thứ hạng cuối cùng phần nào cho thấy kỹ năng tương đối của toàn bộ người tham gia, không chỉ người vô địch
    Tuy nhiên nếu một người chơi dẫn trước quá xa, chức vô địch có thể đã được xác định trước vòng cuối, nên không phải lúc nào cũng kết thúc kịch tính

• Không biết thử dùng giá trị Shapley thì sao

  • Tôi không biết nghĩa là gì nên đã tra thử, thấy nói đó là một khái niệm nghiệm trong lý thuyết trò chơi hợp tác, được đặt theo tên Lloyd Shapley, và phân bổ duy nhất tổng thặng dư do liên minh toàn bộ người chơi tạo ra cho từng người chơi
    Gần như y nguyên phần mở đầu Wikipedia, nhưng đọc xong tôi vẫn không hiểu lắm. Tôi tò mò “tổng thặng dư” của trò chơi hợp tác ở đây là gì, có phải kiểu lượng gỗ mà cả đội thu thập trong AoE không
    Tôi cũng không hiểu việc “phân bổ” nó giúp ích thế nào; thậm chí tôi nghĩ đó phải là kết quả của game mới đúng. Nếu ai có thể giải thích dễ hiểu thì tốt quá