Rating System

[benjaminpjones]

From @SameerDalal 's PR #278 - moving this over to decouple discussion from code changes.

Hi Everyone!

Spoke with Prof. Chen today and the next feature we would like to develop is the ELO rating feature for quantum. Here are some of my thoughts/questions:

1). Do we want each user to have a different ELO rating for each type of variant?
2). Players can agree to make (or not to make) a game elo-rated
3). One of the issues with the ELO ranking system is that a person can chose not to play games to maintain their high rank. To combat this, we should implement some type of activity bonus for playing at least one game per month and a consequence if they don't.
4). Players should be matched with others that have similar rank.

[benjaminpjones]

copied from the PR

1). Do we want each user to have a different ELO rating for each type of variant?

Yes, I think. Although it might be interesting to maintain an "overall" rank and see how it compares

2). Players can agree to make (or not to make) a game elo-rated

This is fine, but honestly I'd be okay with just rating all games too.

3). One of the issues with the ELO ranking system is that a person can chose not to play games to maintain their high rank. To combat this, we should implement some type of activity bonus for playing at least one game per month and a consequence if they don't.

The server not well populated yet - I don't want to "punish" people for not playing. I would be okay with increasing the deviation parameter over time though, since accuracy does go down over time.

Also are you/Zi strongly attached to Elo? I understand Glicko2 is generally considered an improvement on ELO (but still similar), and glicko2 does update RD to reflect inactivity.

4). Players should be matched with others that have similar rank.

Auto-match would be great! I imagine that's a feature on its own.

[benjaminpjones]

See also #222, umbrella task for @zcbwh's feature requests

[benjaminpjones]

Not sure what implementation plans are, but just wanted to raise that I'll prefer to use an existing implementation. Ratings code can be complicated, and I want to avoid maintaining the core ratings algorithm if possible. This will ensure that we are using a fairly standard version of the ratings system, and we can take advantage of the hardening that comes from other users of the library.

Just by a quick search, glicko2js seems promising: GitHub/npm
- ~1400 weekly downloads
- last updated today
- bundle size <8kB
- Automated tests (https://github.com/mmai/glicko2js/blob/master/test/glicko2.js)

[SameerDalal]

That works! Prof. Chen is also good with using Glicko as the rating system.

(Also, I might recommend starting a new branch off current govariants/main - no need to start with a merge commit 😃)

I'm a bit confused as to what you mean by a merge commit.

I believe I did create a new branch called elo-rating on my forked repository, so I'm not sure why I had some extra commits when I created PR #278. But right now the main branch in my forked repo is up to date with govariants:main so I shouldn't encounter that issue again.

[benjaminpjones]

I'm a bit confused as to what you mean by a merge commit.

I was talking about this commit:

I'm not sure where it came from (or the other "new commits" commit above it), but here's how I usually start a new feature branch when I'm working from a fork:

git fetch upstream
git checkout upstream/main
git switch -c my-new-branch

I'm referencing an "upstream" above, which you'll need to set up first. This command will set "upstream" to the govariantsteam repo:

git remote add upstream https://github.com/govariantsteam/govariants.git

[SameerDalal]

Got it! So now that my local code is up to date with the upstream code, the changes that I make could be easily merged into the govariants repo?

[benjaminpjones]

Yeah, keeping local and upstream code in sync should make merging easier down the road.

[SameerDalal]

I think it is best to go forward with the Glicko rating implementation. After reading the documentation, it seems that glicko2js works well with tournaments and not individual games, and the documentation suggests that we should not update a game after every match. While GoVariants does not have a tournament feature we can mimic this by updating a player's rank every 5 games or so.

Also since we don't want to punish players for not playing, we don't have to worry about updating ranks for a "Big Database of Players" like mentioned in the documentation: we only update the rank for those who play.

[benjaminpjones]

Awesome, this approach sounds good!

Also since we don't want to punish players for not playing, we don't have to worry about updating ranks for a "Big Database of Players" like mentioned in the documentation: we only update the rank for those who play.

Just to be clear, I am fine with RD increasing over time - I don't see this as a punishment. When I said I don't want to punish players for not playing, it was in response to "we should implement some type of activity bonus for playing at least one game per month and a consequence if they don't."

But if it's simpler for us to not update RD over time, I'm okay with that too.

[SameerDalal]

Sounds good!

[SameerDalal]

Hi Benjamin, I have some questions on how to implement this feature. Here are my thoughts:

Firstly, User will have the following additional properties:

rating: number;
rating_deviation: number;
volatility: number;
games_played: number

Secondly, there will be a Rating class in rating.ts file in shared/src. There will be a function updateRating(playerB: User, playerW: User, game_result: number) The function will check if either players' games_played property is divisible by 5 (we want to update the ranking for a player every 5 games). If true, then a temporary player will be created using ranking.makePlayer(); and the ranking will then be updated. Subsequently, the new rating, rating deviation, etc., will be assigned back to User. If false, then the game will be added to an instance variable array in the class and the ranking will be updated once either player has played their every 5th game.

Do you think this is an appropriate approach? Also, I'm considering directly calling the updateRating() function from the variants file like quantum.ts, however they don't have a User instance, so I wouldn't be able to pass the player parameter in the function. Since I don't want to change the structure of the files by adding another import, are there any other places where I could call the function?

[JonKo314]

Hi Sameer, it's great that you are coding with us!

There's one thing I want to discuss (or at least point out): We don't have a strong/fixed relation between games and users yet. Users can take a seat, play a few moves and leave, right?

That's nice for correspondence-like multiplayer games. If a user can't play anymore, they can give their seat to someone else and the game can proceed. But it makes creating a rating system a bit more complicated.

One simple approach would be to apply the rating change to the user who occupies the seat at the end of the game. And we could also think about declaring games as rated, that are more restrictive regarding seat changes.

[SameerDalal]

Thanks for your feedback!

Users can take a seat, play a few moves and leave, right?

That's correct!

If a user can't play anymore, they can give their seat to someone else and the game can proceed.

I agree with you on this part, however I would say that making a rated game makes sense only if both players are committed to that game, meaning they won't switch seats.

I think that making rated games more restrictive with seat changes would be the way to go. Of course, if players know that seat changes will be made, then they shouldn't make it rated. Essentially, both players can agree to make a game rated or unrated.

[merowin]

I think that making rated games more restrictive with seat changes would be the way to go.

I agree.

Firstly, User will have the following additional properties:

rating: number;
rating_deviation: number;
volatility: number;
games_played: number

I think we should come up with a way to differentiate a users rating for different variants. We could maybe use an index type, for example:

type User {
  [...],
  ratings: {
    [variant: string]: Rating,
  }
}

type Rating {
  rating: number;
  rating_deviation: number;
  volatility: number;
  games_played: number;
}

Also, I'm considering directly calling the updateRating() function from the variants file like quantum.ts, however they don't have a User instance, so I wouldn't be able to pass the player parameter in the function. Since I don't want to change the structure of the files by adding another import, are there any other places where I could call the function?

I'm thinking that on the server, when a move is played, we can check if the game is finished, and in this case update the player ratings. On the server we can access the players array of a game.
That could be done independently of the variant. But the challenge are multiplayer variants - probably we should make it so rated games are only available for 1v1 games.

[benjaminpjones]

Sorry for the delayed response, Sameer. I think your overall design sounds good, and good points from both @merowin and @JonKo314.

If false, then the game will be added to an instance variable array in the class and the ranking will be updated once either player has played their every 5th game.

Keep in mind that the server can restart, and all "instance" variables will be lost. If you want information to persist, best to put it in the db.

One option would be to cache the relevant data on the user class:

User {
  ratings_data: { [variant: string]: 
    recent_rated_game_results: Array<Result>;
    current_rating: Rating;
  }
}

Result {
    player_won: boolean;
    opponent_rating: Rating;
}

We can check when recent_rated_game_results has reached a size of 5 (or whatever threshold), then perform the computation and clear the array.

Also, I'm considering directly calling the updateRating() function from the variants file like quantum.ts, however they don't have a User instance, so I wouldn't be able to pass the player parameter in the function. Since I don't want to change the structure of the files by adding another import, are there any other places where I could call the function?

Best to keep this out of quantum. Variants should mostly hold logic for the rules of the game and not much more.

As far as where to put it, @merowin's idea sounds good to me - when the last move of the game is played. Code-wise, the function that handles played moves is here: https://github.com/govariantsteam/govariants/blob/main/packages/server/src/games.ts#L120

[SameerDalal]

Hi everyone,

Thank you for all the help in making this feature possible. However, Prof. Chen has now asked me to develop an engine for Quantum, likely for the paper he is writing. As I have limited knowledge in developing these engines, most of my effort will into that. If anyone has experience with creating reinforcement-learning models, I would greatly appreciate your help.

[benjaminpjones]

Okay, thanks for the update. I have not built this kind of engine in the past, but you might check out https://github.com/lightvector/KataGo - it's the cutting edge of open source Go AI.

You may even be able to fork the repo, modify the game/ directory, and train a model. Anyway, best of luck, and I'd love to see what you end up building!

[SameerDalal]

Thank you!

You may even be able to fork the repo, modify the game/ directory, and train a model.

I will do this! The theory also seems interesting so l might try to build my own model.

[SameerDalal]

Hi Benjamin!

I was just typing about how I have been in and out with the Govariants and the QuantumBot due to college, but I would like to go ahead and finish up this feature.

[SameerDalal]

Couple thoughts that I had:

So far in api_types.ts this is what I added.

export interface User {
  username?: string;
  id: string;
  rating?:  {
    [variant: string]: Rating
  };
}

export interface Rating {
  tau?: number
  rating: number
  rd: number
  vol: number
}

One option would be to cache the relevant data on the user class:

One concern that I see with this is that this may not work with the way Glicko2 is structured. If a game ends and we add the result to both users, when we update the rating after 5 games have passed (potentially at different times for both players), the same game may update the players rating twice because the result was added to both Users.

Instead, I think that we should create a universal array for each variant where all results are added and stored in the db, which would not be specific to a user. As you mentioned before, the rating should be independent of the variants but we still want each user to have a different rating for each variant. Then every 5 games we can update the array and rating for each user using Glicko2's function called ranking.updateRatings(matches); where matches is the results array for each variant.

Please let me know if you think this will work.

[merowin]

@SameerDalal for a first implementation my suggestion is to add the rating system for only QuantumGo. This way we avoid some previously discussed hurdles like multiplayer variants etc. for now.

[SameerDalal]

Sounds good!

[benjaminpjones]

Ah sorry, I meant to respond earlier. Thanks for taking another look!

If a game ends and we add the result to both users, when we update the rating after 5 games have passed (potentially at different times for both players), the same game may update the players rating twice because the result was added to both Users.

Is this how it works? I thought it would be something like:

1. Player A plays Player B
2. Entries are added for both A and B
3. Player A plays 4 more games
4. Player A's rating is re-calculated, player B's rating remains unchanged

Then only one calculation per-player per-game. Of course, we'll need to save player B's current rating in player A's cache.

for a first implementation my suggestion is to add the rating system for only QuantumGo. This way we avoid some previously discussed hurdles like multiplayer variants etc. for now.

Agreed to start with one variant, but let's try to architect it in a way that is not tightly coupled to QuantumGo. For example, see the SgfRecorder which works for any two-player grid variants. For the ratings system, we can ignore multiplayer, but let's try and organize it into a module that can support any 2-player variant, even if we only turn it on for Quantum to start.

[SameerDalal]

No problem!

Is this how it works?

I believe so. There is no matches array property for each user, but rather one matches array for all users that is updated.

I can start by tinkering with the library and seeing how it actually works to make sure.

[SameerDalal]

@benjaminpjones I have been able to get a good understanding of how the library works, but I am still having some troubles applying it in the GoVariants code.

1). Would I implement the core rating system in a new file called rankings.ts in the server/src folder? I am assuming that we don't want the algorithm close to the client due to potential vulnerabilities but am unsure if I should create a new file or if I should add the rating system to games.ts

2). How can I check if a game has ended yet so that I can call a function that will update rankings?

3). If in the api_types.ts folder I add another property for the User interface called rating, how am I able to update the values for a particular user after a game has ended?

4). How can I get/set values to the database so I can update user rankings?

I believe I can implement the Glicko algorithm, but I want to make sure my implementation matches the current structure of the application. So, I just need a bit more clarity on how different parts of the application connect with each other.

[benjaminpjones]

Would I implement the core rating system in a new file called rankings.ts in the server/src folder?

Depends on how much ratings logic there is, but likely a separate file would be a good idea for organization. You will need to make some update to games.ts though.

we don't want the algorithm close to the client

Yeah, the ratings calculation should happen server-side

How can I check if a game has ended yet so that I can call a function that will update rankings?

Check the phase property of the game object. Time control does similar here:

govariants/packages/server/src/games.ts

Line 172 in 0e30569

if (game_obj.phase === "gameover") {

If in the api_types.ts folder I add another property for the User interface called rating, how am I able to update the values for a particular user after a game has ended?

Be aware - api_types.ts defines the interface we pass over the REST API, not necessarily what is stored in the database. Not a big deal though - they are pretty similar.

How can I get/set values to the database so I can update user rankings?

We have getUser() to get a User object from the database, but we don't have any functions to set values on a user yet. That would need to be added.

We use MongoDB - it depends what you want to do exactly, but be sure to check the documentation! You will likely use the updateOne() function with $set operation. You can also find examples in this codebase if you search for "updateOne"

I want to make sure my implementation matches the current structure of the application. So, I just need a bit more clarity on how different parts of the application connect with each other.

Basically, here is how moves work:

Player clicks on board
  -> move is sent to server
    -> server validates the move  # at this point, we can check whether game has ended and do work accordingly
      -> appends move to game object in database

[benjaminpjones]

The above answer assumes any ratings calculations can be done after a game ends. If we need to do some batch processing, I don't have a great answer for it yet - we don't currently have any features which need to update in bulk.

[SameerDalal]

Thanks, this clears things up!

[SameerDalal]

If we need to do some batch processing, I don't have a great answer for it yet - we don't currently have any features which need to update in bulk.

I see. If we want to create ratings for existing users then we would have to do some batch processing but for new users, we can just create the rating property as the account is created.