Feature #403

Add bayesian skill rating

Added by Spyhawk over 3 years ago. Updated 4 months ago.

Status:Fixed% Done:

100%

Priority:Normal
Assignee:Spyhawk
Category:Mod generic
Target version:2.76
OS: Arch:

Description

The idea is simple: Implement a new, proved metric that can be used to compare skill of players over time.

The existing XPs count measures player’s score based on of specific action (kills, construction, revive, ..) but is far from evaluating all aspects of the 'skill’ of a player. Also, XPs are useful to control the various skill levels, but don’t give any indication of the real global performance - they basically only give a hint about the time the player has played on a specific server (xpsave).

A 'skill rating’ could be defined as a metric measuring "all the parameters of a player that help his team to win" and the only way to do that is by a probabilistic, Bayesian approach. It simply should look at the global output of a game instead of the various micro-parameters (accuracy, number of kill, ... you-name-it).

ETPub implements such a metric with its "Player Rating", giving a normalized skill score. The TrueSkill system is a more modern algorythm that has been developed by MicroSoft for its XBox matching service. It has the advantage over the ETPub PR that it starts very low and increases over time (like XPs), before stabilizing when the skill rating is accurate (like the ETPub PR).

The algorythm is well documented (see Mooserware below) and several existing implementation can be found on the Internet, including this Lua implementation.

Also, we could use that Skill Rating to develop several nice feature later (showing probability of winning a map, team balancing, or even match making with players of similar skills, ... )

Update:

More detail and analysis is available on the wiki here Bayesian skill rating


Related issues

Related to Lua scripts for the Legacy mod - Feature #181: Add some kind of user management to the mod for online se... In Progress 29.01.2013
Related to ET: Legacy Development - Feature #887: Add new skill levels and expand military ranks like NQ Mod New 10.11.2015
Related to ET: Legacy Development - Bug #1001: End of game stats not always displayed in console Confirmed 16.02.2017
Related to ET: Legacy Development - Bug #1010: Engine db_mode 1 isn't accessible from mod and LuaSQL New 27.02.2017
Blocked by ET: Legacy Development - Feature #309: ET:L database connectivity Fixed 03.06.2013
Blocked by ET: Legacy Development - Feature #906: Create luasql lib and add it to installs Fixed 13.12.2015

Associated revisions

Revision a6dc54d6
Added by Spyhawk over 1 year ago

misc: added optional FEATURE_RATING, refs #403

Revision 0704e00b
Added by Spyhawk over 1 year ago

misc: updated easybuild.sh, refs #403

Revision 41a8f57c
Added by Spyhawk over 1 year ago

game: added initial skill rating code, refs #403

Revision 37037b62
Added by Spyhawk over 1 year ago

game: added skill rating partial play, refs #403

Revision e2764f28
Added by Spyhawk over 1 year ago

mod: added skill rating in scoreboard, refs #403

Revision f5e84f58
Added by Spyhawk over 1 year ago

mod: added skill rating in stats window, refs #403

Revision b218a576
Added by Spyhawk over 1 year ago

mod: added skill rating in debriefing window, refs #403

Revision d11b073a
Added by Spyhawk over 1 year ago

mod: added skill rating in console stats dump, refs #403

Revision de4979d6
Added by Spyhawk over 1 year ago

game: don’t update skill rating in stopwatch and LMS, refs #403

Revision d89a352e
Added by Spyhawk over 1 year ago

mod: show rating scoreboard only if rating is enabled, refs #403

Revision 226ac1e1
Added by Spyhawk over 1 year ago

mod: added win probability, refs #403

Revision f837d448
Added by Spyhawk over 1 year ago

mod: send only complete rating to clients, refs #403

Revision ab09f983
Added by Spyhawk over 1 year ago

mod: send delta rating to clients, refs #403

Revision 8c155ab9
Added by Spyhawk over 1 year ago

game: extended rating algorithm with map parameter, refs #403

Revision 903247dd
Added by Spyhawk over 1 year ago

game: log match result, refs #403

Revision f07e0620
Added by Spyhawk over 1 year ago

game: removed debug stats, refs #403

Revision b79909ed
Added by IR4T4 over 1 year ago

game: fix overwriting map vote values in CS_LEGACYINFO when
g_skillRating is enabled refs #403

Revision e8657df8
Added by IR4T4 over 1 year ago

mod: make g_skillRating latched. Don’t execute rating code when disabled
(WIP) refs #403

Revision 1005d01b
Added by Spyhawk 11 months ago

mod: do not execute rating code when disabled, refs #403

Revision 46f4d36d
Added by Spyhawk 11 months ago

game: disable g_skillrating by default, refs #403

Revision c9118341
Added by Spyhawk 11 months ago

cmake: enabled FEATURE_RATING by default, refs #403

Revision bd8fc227
Added by Spyhawk 11 months ago

game: fixed variable initialization, refs #403

Revision 4ddfaa84
Added by Spyhawk 11 months ago

cgame: removed useless code, refs #403

Revision 40d67460
Added by Spyhawk 11 months ago

cgame: fixed unintialized pointer read, refs #403

Revision 86d98cd6
Added by Spyhawk 11 months ago

game: added no division by zero check, refs #403

in case the check above doesn’t catch it

Revision 3b57ec90
Added by Spyhawk 11 months ago

misc: enable FEATURE_RATING in easybuild.sh too, refs #403

Revision 4b6ffab1
Added by Spyhawk 11 months ago

game: cleanup, refs #403

Revision 83b26ab5
Added by Spyhawk 11 months ago

cgame: stats info label alignment, refs #403

Revision aa8ba49f
Added by Spyhawk 11 months ago

game: added missing map win bias, refs #403

Revision 937d8a43
Added by Spyhawk 11 months ago

cgame: display map prob on scoreboard, refs #403

Revision 4fba9212
Added by Spyhawk 11 months ago

mod: do not display negative rating and cleanup, refs #403

Revision 506bf1d3
Added by Spyhawk 11 months ago

cgame: fixed rating in stats window not updating when spec, refs #403

Revision b5ffb5b4
Added by Spyhawk 11 months ago

cgame: hide skill rating in debriefing when disabled, refs #478 #403

Revision 75e31804
Added by Spyhawk 11 months ago

cgame: fixed debriefing stats not displaying when rating is disabled, refs #403

Revision 845e2330
Added by Spyhawk 11 months ago

mod: do not send any rating data when disabled, refs #403

Revision cba8e697
Added by Spyhawk 10 months ago

mod: do not send delta rating in client userinfo, refs #403

Revision 0416a7d7
Added by Spyhawk 10 months ago

mod: entirely removed rating from user configstring, refs #403

Revision 7ad92968
Added by Aranud 9 months ago

cgame: fix logical dead code (Coverity) + fix some Clang warning

Revision a19f62ea
Added by Aranud 9 months ago

cgame: clean up + uncrustify

Revision 9d97cf94
Added by Spyhawk 6 months ago

game: fixed total play time, refs #403

Revision 9d193942
Added by Spyhawk 6 months ago

mod: use highest ranking as first award, refs #403 #894

Revision 52ee97dc
Added by Spyhawk 6 months ago

misc: added g_skillRating in default config file, refs #403

Revision efdfbdd1
Added by Spyhawk 5 months ago

game: do not display meaningless total rating stats, refs #403

Revision 29a636ce
Added by Spyhawk 5 months ago

game: fixed individual rating update with partial play, refs #403

Revision 8681cbf4
Added by Spyhawk 5 months ago

misc: enable FEATURE_DBMS if FEATURE_RATING is enabled, refs #403

Revision d69d1ae1
Added by Spyhawk 5 months ago

game: use engine database for skill rating, refs #403

Revision 8f3d76a2
Added by Spyhawk 5 months ago

game: added map rating bias and continuity correction, refs #403

Revision ff73c3e6
Added by Spyhawk 5 months ago

game: set RO flag on Lua rating variables, refs #403

Revision b1590142
Added by Spyhawk 5 months ago

game: set PRAGMA sync off with db_mode 2, refs #403

Revision e56cbaae
Added by Spyhawk 5 months ago

game: added shuffle by rating cmds, refs #403

Revision 03c7fff9
Added by Spyhawk 5 months ago

ui: added shuffle by rating menu options, refs #403

Revision 4a6029ac
Added by Spyhawk 5 months ago

mod: added highest rated player award, refs #403 #894

Revision e26c6463
Added by Spyhawk 5 months ago

game: set RO flag for time related Lua fields, refs #403

Revision 6a497024
Added by Spyhawk 5 months ago

game: fixed logically dead code, refs #403

Revision 0b9bab5b
Added by Spyhawk 5 months ago

mod: display endgame stats float values with two digits, refs #403 #894

Revision f908a1c5
Added by Spyhawk 5 months ago

game: skill rating send function cleanup, refs #403

Revision c11f4030
Added by Spyhawk 5 months ago

game: win prob takes disconnected players into account, refs #403

Revision f73bb192
Added by Spyhawk 5 months ago

game: fixed missing guid assignment and small optimization, refs #403

Revision 240a61e9
Added by Spyhawk 5 months ago

game: code cleanup, refs #403

Revision 1eb2ab85
Added by Spyhawk 5 months ago

game: do not display rating award if not positive, refs #403 #894

Revision 69b25451
Added by Spyhawk 5 months ago

game: tied ranks to rating when enabled, refs #403

Revision 27ab8137
Added by Spyhawk 5 months ago

game: enabled skill rating by default, refs #403

Revision 1bb1f37e
Added by Spyhawk 5 months ago

game: sanitize rank level and cleanup, refs #403

Revision 777f46b2
Added by Spyhawk 5 months ago

game: capped display of max rating, refs #403

Revision a5ca3b40
Added by Spyhawk 5 months ago

game: capped rating also in stats window and award, refs #403

Revision 48802e57
Added by Spyhawk 5 months ago

game: update ranks at intermission, refs #403

Revision 40559e74
Added by Spyhawk 5 months ago

game: use map bias for slightly better rating shuffle, refs #403

History

#1 Updated by Spyhawk over 3 years ago

  • Description updated (diff)

#2 Updated by Spyhawk over 3 years ago

  • Assignee set to Spyhawk

#3 Updated by Spyhawk over 2 years ago

  • Description updated (diff)

#4 Updated by Spyhawk almost 2 years ago

  • Description updated (diff)

#5 Updated by Spyhawk almost 2 years ago

  • Description updated (diff)

Added link to some documentation in the wiki here: Bayesian skill rating

#6 Updated by Spyhawk almost 2 years ago

  • Category deleted (Lua scripts)

#7 Updated by Dragonji almost 2 years ago

I’d say it would be nice to have it in the mod itself so it’s easy to integrate it to current stats that are already in the game. It can’t be nicely integrated in this aspect if it’s a Lua script.

#8 Updated by Spyhawk almost 2 years ago

Dragonji wrote:

I’d say it would be nice to have it in the mod itself so it’s easy to integrate it to current stats that are already in the game. It can’t be nicely integrated in this aspect if it’s a Lua script.

You are right, and that is actually the way I’m implementing it. The algorithm itself and integration in the mod are mostly done, but I’m still wondering if the loading/writing of data itself would be better done in Lua.

Can’t change the category of the ticket though, so it’s stuck to "Lua scripts" for the time being.

#9 Updated by Spyhawk almost 2 years ago

  • Project changed from Lua scripts for the Legacy mod to ET: Legacy Development
  • Category set to Mod generic

#10 Updated by Spyhawk almost 2 years ago

  • Related to Feature #181: Add some kind of user management to the mod for online servers added

#11 Updated by IR4T4 over 1 year ago

  • Related to Feature #887: Add new skill levels and expand military ranks like NQ Mod added

#12 Updated by Spyhawk over 1 year ago

  • Target version changed from ALL to 2.75

#13 Updated by Spyhawk over 1 year ago

#14 Updated by Harlekin over 1 year ago

Would it be possible to let the server adjust some settings for a team based on team rating? Eg let them spawn a little faster, give them extra ammo on spawn, faster recharge of ammo/health cabinets, longer spawnprotection or some kind of other support for a very underpowered team.

#15 Updated by Spyhawk over 1 year ago

Harlekin wrote:

Would it be possible to let the server adjust some settings for a team based on team rating? Eg let them spawn a little faster, give them extra ammo on spawn, faster recharge of ammo/health cabinets, longer spawnprotection or some kind of other support for a very underpowered team.

Anything is possible, but as a first step we’ll include only informative rating. Note that rating takes strength of teams into account, so it’s actually "fair" to lose against a stronger team. But if you beat a stronger team, your rating would be increased much more than usual.

#16 Updated by Spyhawk over 1 year ago

The base TrueSkill algorithm has been implemented (using session to keep values for now), and I extended it for taking map and time parameters.
However, to use this extension I’ll need to collect data about played maps.

Data collected would be:
  • number of time the map was played,
  • number of time each side won the map,
  • average time before a team won the map (not really necessary)

Here are a few possibilities:

1/ use a database through LuaSQL or the new engine DB feature;
2/ extend the existing mapvoteinfo.txt file system, and collect data in other gametypes (maybe apart from stopwatch);
3/ use a database system and move the existing mapvoteinfo data collect to a common database.

Option 3/ might be the cleanest, but 2/ will also work.
Opinion/suggestion?

#17 Updated by Spyhawk over 1 year ago

  • % Done changed from 0 to 70

#18 Updated by Spyhawk over 1 year ago

  • Blocked by Feature #906: Create luasql lib and add it to installs added

#19 Updated by Spyhawk 11 months ago

  • Add missing Lua code (maybe as a WolfAdmin plugin) (code is moved to C)
  • enable FEATURE_RATING (done)
  • disable g_skillrating by default (done)

#20 Updated by Spyhawk 11 months ago

  • Target version changed from 2.75 to 2.76

I’ll rework the existing mapvoteinfo data to use a common database system with the map parameter extension.

Edit: After some thought, the code has been modified so map stats management can be done entirely on the Lua side (using CS_LEGACYINFO). This should stay separate from the mapvote data.

Only the accompanying Lua script is missing now.

#21 Updated by Spyhawk 10 months ago

The Lua script has been partially written. It works and takes connected players at the end of the match to compute the rating update. Also, players that disconnected and reconnected later in the same match are correctly handled. However, to take the performance of all disconnected players into account, we need to loop over all players that played in the match, and not only level.numConnectedClients.

This require the use of an intermediary DB. I am unsure about the best way to implement this, as the C code needs to be adjusted but the DB stuff is for now entirely handled on the Lua side.

#22 Updated by Spyhawk 6 months ago

I’m hitting a wall with that DB-Lua stuff. I now believe the best way to do it is to implement directly in C, taking advantage of the engine DB.
It also makes sense since the rating system is deeply integrated in the mod code already.

Special commands can still be done in Lua, in the form of a WolfAdmin plugin or independent script.

#23 Updated by Spyhawk 5 months ago

  • Related to Bug #1001: End of game stats not always displayed in console added

#24 Updated by Spyhawk 5 months ago

  • Put Highest ranking officer award on top
  • Add variable in config file
  • Tie ranks to rating instead of XPs (see G_CalcRank() and G_UpgradeSkill(), might require explicit rank update, adjust the big PM message somehow)
  • track number of matches played in DB (not useful for rating)
  • use ribbon (like etnam) (not useful for rating)
  • remove meaningless tot_rating in G_printMatchInfo()
  • enable g_skillrating by default
  • add new award for best rated player
  • add shuffleteamsrating, shuffleteamsrating_norestart votes
  • add info commands such as /rating, /allrating (should be done in Lua)
WIP: move from Lua to C code: done!
  • DB Init in g_main
  • DB DeInit in g_main.c
  • DB Deinit in g_vote.c (map, campaign, nextmap, maprestart, mapreset)
  • check users, match, map tables
  • empty match table at init
  • disable rating if failure
  • ClientConnect → retrieve rating from match or users tables, or create new one
  • ClientDisconnect → write in match table
  • End of game G_LogExit(): adjust G_UpdateSkillRating for use of match table
  • Add created and last updated time tracking
  • Fix edge case player connects/disconnect in intermission
  • Fix edge case player connects/disconnect in warmup
  • Fix bug where rating from rating_users table in warmup isn’t taken over playing session (use empty rating_match instead)
  • Fix disconnected players aren’t taken into account in scoreboard real time win probability
  • Retrieve Map prob, Save map prob
  • Display updated map rating in intermission scoreboard with g_skillRating 2
  • Fix now broken delta rating
  • Check log print G_Printf vs G_LogPrintf
  • Proper headers doc
  • Optimize speed with PRAGMA or single INSERT transaction for db_mode 2
  • Set RO flag on Lua rating variables
  • db_mode 1 with memory mode (see #1010)

#25 Updated by Spyhawk 5 months ago

  • Related to Bug #1010: Engine db_mode 1 isn't accessible from mod and LuaSQL added

#26 Updated by Spyhawk 5 months ago

  • Status changed from New to In Progress
  • % Done changed from 70 to 90

#27 Updated by Spyhawk 5 months ago

Some results from the DB data after 1 week of data collection (initial mu: 25, initial sigma: 8.33, rating = mu - 3*sigma = 0):

  • 73 entries, from which 18 are bots (55 humans players)
  • best/worst rated player
    • mu = 42.3, sigma = 6.17 (rating: 23.75).
    • mu = 20.6, sigma = 7.89 (rating: -3.10)
  • human players with smallest sigma:
    • mu = 19.3, sigma = 6 .15 (rating: 0.84)
    • mu = 42.3, sigma = 6.17 (rating: 23.75)

This shows that ranks based on rating and distributed in a purely linear manner (0-5: Private, .., 45-50: General) are indeed viable. With the very limited number of players and initial bots ratings, it would requires about 3 weeks for the rating to stabilize (lower variance). The more players with higher rating (low uncertainty), the more the system can rate players quickly.

However, using a more log-like distribution of ranks (lower ranks requiring a lower rating, f.e. 0-2: Private, 2-5: Private Fist Class, ..., 40-50: General) might increase diversity of ranks on a server and also motivate new players to stay on the same server.

#28 Updated by Spyhawk 5 months ago

  • Status changed from In Progress to Feedback
  • % Done changed from 90 to 100

Ranks are now tied to rating in a linear manner when rating is enabled. Otherwise, behavior is still the same with ranks tied to skill levels and XPs.

We lose the Ranks popup as the ratings and thus ranks aren’t updated in-game but right before intermission, but I don’t think it is worth adding complexity just to show these popup at the start of next map.

#29 Updated by Spyhawk 4 months ago

  • Status changed from Feedback to Fixed

Also available in: Atom PDF