Thành viên:Jsaidoru/nháp

Tổng quan

Mark Glickman đã tạo ra hệ thống xếp hạng Glicko vào năm 1995 như một cải tiến trên hệ thống xếp hạng Elo. Cả hai hệ thống xếp hạng Glicko và Glicko-2 đều thuộc phạm vi công cộng và đã được triển khai trên các máy chủ trò chơi trực tuyến như Counter-Strike: Global Offensive, Team Fortress 2, Dota 2, Guild Wars 2, Splatoon 2, Lichess và chess.com. Độ lệch của xếp hạng (RD) đo lường độ chính xác của xếp hạng của một người chơi, trong đó RD bằng một độ lệch chuẩn. Giả sử, một người chơi có xếp hạng 1500 và RD là 50 có xếp hạng thực sự từ 1400 đến 1600 (hai độ lệch chuẩn từ 1500) với độ tin cậy 95%. 2 lần (chính xác là 1.96) RD được cộng và trừ vào xếp hạng của họ để tính phạm vi này. Sau một ván đấu, xếp hạng thay đổi phụ thuộc vào RD: ít hơn khi RD của người chơi thấp (vì xếp hạng của họ đã được coi là chính xác) và cả khi RD của đối thủ cao (vì xếp hạng thực của đối thủ không được rõ ràng, do đó có rất ít thông tin thu được). Chính RD cũng giảm sau một ván đấu, nhưng nó sẽ tăng chậm theo thời gian không hoạt động. Hệ thống đánh giá Glicko-2 cải thiện hệ thống đánh giá Glicko và tiếp tục giới thiệu sự biến động xếp hạng σ. Một phiên bản được sửa đổi rất ít của hệ thống xếp hạng Glicko-2 được Liên đoàn Cờ vua Úc triển khai.

Thuật toán của Glicko

Bước 1: Tính độ lệnh của xếp hạng

Độ lệnh của xếp hạng mới ($RD$) được tính ra sử dụng Độ lệnh của xếp hạng cũ($RD_{0}$):

$RD=\min \left({\sqrt {{RD_{0}}^{2}+c^{2}t}},350\right)$

Với $t$ là khoảng thời gian (chu kỳ đánh giá) kể từ cuộc thi cuối cùng và ‘350’ được coi là RD của một người chơi chưa xếp hạng. Nếu nhiều trận đấu diễn ra trong một chu kỳ đánh giá, phương pháp này sẽ xem chúng như đã xảy ra đồng thời. Khoảng thời gian xếp hạng có thể kéo dài vài tháng hoặc ngắn chỉ vài phút, tùy thuộc vào tần suất sắp xếp các trận đấu. Hằng số $c$ dựa trên sự không chắc chắn về kỹ năng của người chơi trong một khoảng thời gian nhất định. Nó có thể được rút ra từ phân tích dữ liệu kỹ lưỡng hoặc ước tính bằng cách xem xét khoảng thời gian phải vượt qua trước khi độ lệch xếp hạng của người chơi sẽ tăng lên thành của một người chơi chưa xếp hạng. Nếu giả định rằng sẽ mất 100 khoảng thời gian xếp hạng để độ lệch xếp hạng của người chơi trở về độ không chắc chắn ban đầu là 350 và một người chơi điển hình có độ lệch xếp hạng là 50 thì hằng số có thể được tìm thấy bằng cách giải $350={\sqrt {50^{2}+100c^{2}}}$ cho $c$.

Hay

$c={\sqrt {(350^{2}-50^{2})/100}}\approx 34.6$

Bước 2: Tính xếp hạng mới

Xếp hạng mới, sau một loạt m ván, được xác định bởi phương trình sau:

$r=r_{0}+{\frac {q}{{\frac {1}{RD^{2}}}+{\frac {1}{d^{2}}}}}\sum _{i=1}^{m}{g(RD_{i})(s_{i}-E(s|r_{0},r_{i},RD_{i}))}$

Với:

$g(RD_{i})={\frac {1}{\sqrt {1+{\frac {3q^{2}(RD_{i}^{2})}{\pi ^{2}}}}}}$

$E(s|r_{0},r_{i},RD_{i})={\frac {1}{1+10^{\left({\frac {g(RD_{i})(r_{0}-r_{i})}{-400}}\right)}}}$

$q={\frac {\ln(10)}{400}}=0.00575646273$

$d^{2}={\frac {1}{q^{2}\sum _{i=1}^{m}{(g(RD_{i}))^{2}E(s|r_{0},r_{i},RD_{i})(1-E(s|r_{0},r_{i},RD_{i}))}}}$

$r_{i}$ đại diện cho xếp hạng của các đối thủ riêng lẻ.

$RD_{i}$ đại diện cho độ lệch của xếp hạng của các đối thủ riêng lẻ.

$s_{i}$ đại diện cho kết quả của các ván riêng lẻ. Một chiến thắng là 1, một trận hòa là ${\frac {1}{2}}$, và một trận thua là 0.

Bước 3: Xác định độ lệnh của xếp hạng mới

Chức năng của phép tính RD trước là tăng RD một cách phù hợp để tính đến sự gia tăng không chắc chắn về mức độ kỹ năng của người chơi trong khoảng thời gian mà mô hình không quan sát được. Giờ, RD được cập nhật (giảm) sau các loạt ván đấu:

$RD'={\sqrt {\left({\frac {1}{RD^{2}}}+{\frac {1}{d^{2}}}\right)^{-1}}}$

Thuật toán của Glicko-2

Glicko-2 hoạt động tương tự như thuật toán Glicko ban đầu, với sự bổ sung của độ biến động xếp hạng $\sigma$ đo lường mức độ dao động dự kiến trong xếp hạng của người chơi, dựa trên mức độ thất thường của hiệu suất của họ. Chẳng hạn, sự biến động xếp hạng của người chơi sẽ thấp khi hiệu suất của họ ở mức ổn định và sẽ tăng nếu họ đạt được kết quả xuất sắc sau một giai đoạn ổn định. Dưới đây là một giải thích đơn giản về thuật toán Glicko-2:

Bước 1: Tính các đại lượng phụ trợ

Trong một chu kỳ xếp hạng, một người chơi có xếp hạng hiện tại $\mu$ và độ lệch của xếp hạng $\phi$ chơi với các đối thủ $m$, với xếp hạng $\mu _{1},...,\mu _{m}$ và các RD là $\phi _{1},...,\phi _{m}$, kết quả điểm số là $s_{1},...,s_{m}$. Trước hết ta cần tính toán các đại lượng phụ trợ $v$ và $\Delta$:

$v=\left[\sum _{j=1}^{m}g(\phi _{j})^{2}E(\mu ,\mu _{j},\phi _{j})\{1-E(\mu ,\mu _{j},\phi _{j})\}\right]^{-1}$

$\Delta =v\sum _{j=1}^{m}g(\phi _{j})\{s_{j}-E(\mu ,\mu _{j},\phi _{j})\}$

Với

$g(\phi _{j})={\frac {1}{\sqrt {1+3\phi _{j}^{2}/\pi ^{2}}}},$

$E(\mu ,\mu _{j},\phi _{j})={\frac {1}{1+\exp\{-g(\phi _{j})(\mu -\mu _{j})\}}}.$

Bước 2: Tính Sự biến động xếp hạng mới

Chúng ta sau đó cần chọn một hằng số nhỏ $\tau$ để giới hạn sự biến động theo thời gian, chẳng hạn $\tau =0.2$ $\tau =0.2$ (giá trị nhỏ hơn của $\tau$ ngăn chặn sự thay đổi xếp hạng đột ngột sau những kết quả bất ngờ). Sau đó, với

$f(x)={\frac {1}{2}}{\frac {e^{x}(\Delta ^{2}-\phi ^{2}-v-e^{x})}{(\phi ^{2}+v+e^{x})^{2}}}-{\frac {x-\ln({\sigma ^{2}})}{\tau ^{2}}},$

ta cần tìm giá trị của $A$ thỏa mãn $f(A)=0$. Một cách hiệu quả để giải quyết là sử dụng thuật toán Illinois, một phiên bản sửa đổi của phuơng pháp cát tuyến procedure (xem phuơng pháp cát tuyến § Thuận toán Illinois để biết chi tiết về cách cái này được thực hiện). Khi quy trình lặp lại này hoàn tất, ta đặt sự biến động xếp hạng mới $\sigma '$ là

$\sigma '=\exp\{A/2\}.$

Bước 3: Tính độ lệch của xếp hạng mới và xếp hạng

Ta sau đó xác định RD mới

$\phi '=1{\Big /}{\sqrt {{\frac {1}{\phi ^{2}+\sigma '^{2}}}+{\frac {1}{v}}}},$

và xếp hạng mới

$\mu '=\mu +\phi '^{2}\sum _{j=1}^{m}g(\phi _{j})\{s_{j}-E(\mu ,\mu _{j},\phi _{j})\}.$

Các xếp hạng và RD này ở quy mô khác với thuật toán Glicko gốc và sẽ cần được chuyển đổi để so sánh đúng cả hai.

Cũng xem

• Hệ thống đánh giá cờ vua

Liên kết ngoài

• Professor Glickman's Glicko-Website Lưu trữ 2020-12-12 tại Wayback Machine
• TrueSkill [1] Lưu trữ 2019-10-16 tại Wayback Machine rating system by Microsoft borrows many ideas from Glicko.
• forwardloop/glicko2s Lưu trữ 2020-11-12 tại Wayback Machine Glicko-2 implementation for the JVM
• RobKohr/glicko Lưu trữ 2019-10-16 tại Wayback Machine JavaScript Glicko-2 implementation.
• mmai/glicko2js Lưu trữ 2020-12-12 tại Wayback Machine Client side javascript and node.js Glicko-2 implementation
• deepy/glicko2 Lưu trữ 2020-09-12 tại Wayback Machine Python Glicko-2 implementation.
• sublee/glicko2 Lưu trữ 2021-01-06 tại Wayback Machine Python Glicko-2 implementation.
• PlayerRatings Lưu trữ 2020-05-14 tại Wayback Machine R Glicko implementation by Alec Stephenson and Jeff Sonas.
• scala-glicko2 Lưu trữ 2019-10-16 tại Wayback Machine Scala Glicko-2 implementation.
• dimos/glicko2 Lưu trữ 2022-02-16 tại Wayback Machine Glicko-2 implementation for Scala and Scala.js