TrueSkill là hệ thống xếp hạng người chơi của Microsoft trên Xbox Live. So với hệ ELO nổi tiếng trong làng cờ quốc tế, TrueSkill là một bước tiến dài mang tính thế hệ, với khả năng phân tích các trận đấu nhiều đội, nhiều người. Trên hết, mô hình toán học của TrueSkill có khả năng ước lượng các biến động về phong độ của đấu thủ và khả năng tự đánh giá độ chắc chắn của bảng xếp hạng về trình độ thực sự của đấu thủ.

Bản lược dịch này cố gắng giới thiệu các nguyên tắc và quy trình cơ bản của TrueSkill theo cách đơn giản nhất. Độc giả thích toán học hoặc yêu cầu chính xác đến từng chi tiết có thể tham khảo bản gốc tại:

http://www.moserware.com/2010/03/computing-your-skill.html

http://www.moserware.com/assets/computing-your-skill/The%20Math%20Behind%20TrueSkill.pdf

Đo trình độ bằng gì

Trình độ không phải thứ dễ đo đếm. Phong độ thật khi thi đấu không chỉ phụ thuộc vào tài năng và rèn luyện mà nhiều khi cả một chút may mắn. Vậy làm sao ta đánh giá trình độ của một đấu thủ? Chính đấu thủ đó cũng không thể biết chính xác trình độ của mình, nhất là khi con người luôn có xu hướng tự đánh giá cao bản thân.

Chúng ta có thể bắt đầu bằng một câu hỏi căn bản: đo trình độ bằng đơn vị gì? Trong môn chạy 100m, có thể tính thời gian trung bình của một số lần chạy. Tuy nhiên với các môn thi đấu chỉ có thắng thua (hoặc hòa), câu trả lời không đơn giản. Nếu chỉ tính số trận thắng thua, sẽ không công bằng giữa người đấu nhiều và người đấu ít. Nếu chỉ tính tỷ lệ thắng, sẽ không công bằng giữa kẻ chuyên bắt nạt trẻ con với người chuyên thách đấu cao thủ. Vậy thay vì đi tìm đơn vị đo trình độ tuyệt đối, chúng ta đặt mục tiêu đơn giản hơn: làm sao xếp hạng các đấu thủ xem ai trình cao hơn ai. Mỗi đấu thủ sẽ có một số đo trình độ, nhưng bản thân con số này không có đơn vị gì. Số đo trình độ chỉ có ý nghĩa khi so sánh các đấu thủ với nhau: ai có trình độ cao hơn sẽ dễ thắng hơn. Nếu mô hình xếp hạng đủ chính xác, chúng ta còn có thể dự đoán xác suất thắng trận của từng đấu thủ dựa trên mức chênh lệch về trình độ.

Trình độ chỉ là ước tính

Dù có học toán hay không, con người ai cũng có khái niệm ít nhiều về xác suất. Nếu ai chơi tung đồng xu 3 lần chắc ít nhất cũng thắng 1 lần. Nếu Việt Nam đá bóng với Brazil 3 trận, thua hết cũng là bình thường.

Trong mọi hệ thống xếp hạng, hai đấu thủ có số đo trình độ ngang nhau sẽ có xác suất thắng trận ngang nhau (nếu là trận đấu một chọi một thì mỗi bên có 50% cơ hội). Số đo trình độ càng chênh lệch, xác suất thắng của cửa trên càng lớn. Hệ thống TrueSkill dùng hàm Gauss (Gaussian distribution) để ước lượng xác suất thắng theo số đo trình độ:

Tuy nhiên cần nhớ rằng bản thân số đo trình độ chỉ là ước tính, không bao giờ 100% chính xác. Quá trình ước tính trình độ lại dựa vào kết quả thi đấu, do đó sẽ kém chính xác hơn đối với người đấu ít. Hệ thống TrueSkill xử lý yếu tố bất định này bằng cách coi trình độ của mỗi đấu thủ là một biến ngẫu nhiên, trong đó yếu tố ngẫu nhiên là do chúng ta không có thông tin trực tiếp về trình độ của các đấu thủ mà chỉ suy luận từ kết quả các trận đấu. Giá trị mean (trung bình) của biến ngẫu nhiên là trình độ của đấu thủ, còn standard deviation (độ lệch chuẩn) của biến này đại diện cho sự bất định trong ước tính trình độ đấu thủ đó.

Mỗi khi có kết quả trận đấu, TrueSkill cập nhật cả mean và standard deviation cho mỗi đấu thủ để phản ánh hai điều:

  • Thứ nhất, kết quả thực tế có thể thuận với ước tính (cửa trên thắng) hoặc ngược với ước tính (cửa dưới thắng), do đó cần cập nhật số đo trình độ cho phù hợp hơn với thực tế.
  • Thứ hai, chúng ta vừa có thêm thông tin về các đấu thủ nên sự bất định phải giảm, nhưng giảm bao nhiêu thì phụ thuộc vào từng đấu thủ.

Giả sử Natalia (mean = 25, sd = 8.33) thắng Eric (mean = 30.00, sd = 1.25).

Trước trận đấu, Eric không những được đánh giá cao hơn mà còn thi đấu nhiều hơn nên TrueSkill khá chắc chắn về trình độ của anh (đồ thị màu đỏ rất hẹp). Trong khi đó hệ thống có ít thông tin về Natalia nên độ bất định cao hơn hẳn: tuy trình độ ước tính của cô thấp hơn Eric nhưng vẫn có khả năng đáng kể là trình độ thật của cô cao hơn Eric (phần đồ thị màu xám bên phải màu đỏ).

Do Natalia thắng, có vẻ lúc đầu hệ thống đã đánh giá quá cao Eric so với cô, vì vậy trình độ của Natalia cần được ước tính cao hơn trước còn Eric phải thấp hơn trước:

Có thể thấy đồ thị của Eric gần như không thay đổi, chỉ dịch sang trái một chút. Lý do là TrueSkill đã biết rất chắc chắn về trình độ của anh, nên kết quả một trận đấu không có nhiều ý nghĩa. Trong khi đó đồ thị của Natalia không những di chuyển hẳn sang phải mà còn hẹp lạị. Vì trước đó hệ thống biết rất ít về Natalia nên dễ dàng thay đổi đánh giá về cô hơn với Eric. Mặt khác kết quả một trận đấu có giá trị thông tin tương đối lớn về Natalia (do thông tin về cô vốn còn ít), nên độ bất định về Natalia được giảm đi đáng kể.

Mô hình TrueSkill

Về mặt toán học, TrueSkill cập nhật số đo trình độ theo nguyên tắc thống kê Bayes:

http://www.scholarpedia.org/article/Bayesian_statistics

Để minh họa cách TrueSkill hoạt động trong thực tế, chúng ta lấy làm ví dụ một trận đấu ba bên (hai người chơi lẻ và một đội 2 người), trong đó một trong hai người chơi lẻ thắng.

Sơ đồ cập nhật các chỉ số như sau:

Ở trên p1 và p4 là hai người chơi lẻ (ứng với các đội t1 và t3), p2 và p3 cùng đội (t2). Trong mô hình này, s1 cho đến s4 là trình độ của các đấu thủ, còn d1 và d2 là chênh lệch về phong độ giữa các đội.

Có thể chia nhỏ mô hình này thành các bước sau:

Ước tính trình độ

Trong bước đầu tiên, TrueSkill ước tính trình độ mỗi đấu thủ (hình tròn đỏ) từ một phân bố tiên nghiệm (hình vuông đen), chưa tính đến kết quả trận đấu vừa rồi. Phân bố tiên nghiệm có độ bất định để phản ánh sự thiếu thông tin về từng đấu thủ.

Từ trình độ đến phong độ

Ở bước tiếp theo, phong độ của mỗi đấu thủ trong trận đấu không chỉ phụ thuộc vào trình độ mà còn có yếu tố ngẫu nhiên. Yếu tố bất định này có giá trị nhỏ đối với các môn thi đấu ít bất ngờ như đánh cờ, và giá trị lớn với các môn nhiều bất ngờ như đánh bài. Mũi tên màu đen có nghĩa là trình độ ước tính của các đấu thủ sẽ được cập nhật sau này, từ bằng chứng về phong độ thật trong trận đấu.

Cá nhân và đồng đội

Công thức của TrueSkill ở bước này rất đơn giản: phong độ của đội là tổng phong độ các thành viên, có thể nhân với hệ số thời gian thi đấu (trong trường hợp thành viên không tham gia cả trận). Cũng như bước trước, phong độ cá nhân của các đấu thủ sẽ được cập nhật khi có bằng chứng về phong độ chung của đội.

Đấu trường

TrueSkill tính hiệu số về phong độ giữa các đội để dự đoán kết quả trận đấu, trong đó có một tham số đại diện cho ngưỡng hòa của môn thi đấu (thí dụ ngưỡng hòa với cờ vua hoặc bóng đá sẽ cao hơn với môn nhảy cao):

Kết quả dự đoán được đối chiếu với kết quả thật của trận đấu để cập nhật các ước tính bên trên. Nguyên tắc chung là kết quả giống với dự đoán dẫn đến thay đổi nhỏ, trong khi các kết quả nhiều bất ngờ sẽ dẫn đến thay đổi lớn về các chỉ số trong mô hình.

Vòng cập nhật

Các chỉ số về phong độ các đội và hiệu số phong độ được cập nhật theo vòng lặp nói trên đến khi hội tụ. Sau đó các chỉ số ở phần trên của sơ đồ sẽ được lần lượt cập nhật theo thứ tự, cho đến khi TrueSkill có được ước tính mới cho trình độ từng đấu thủ.

Đặng Hoàng Vũ – FPT HO

Tin liên quan: