Imagine a 1 on 1 (not teams) competition between AI bots, like the Google AI Challenge. The various bots are assigned an ELO rating based on the outcome of the various versus matches. The reason I specify AI bots as they can compete 24/7 without regard for player fatigue, geolocation, etc.

Given limited server resources only so many bouts can be run per day. I'm looking for a heuristic (or an optimal algorithm) to choose which two bots should compete next.

All the past competitions have been tracked. By this I mean that the algorithm has more to work with than just the ELO ratings.

The use cases I'm partitularly interested in:

  • The competition has been pairing randomly for while and now I want to make intelligent pairing decision.
  • The Elo rating have stabilized and a bot is updated.
  • The Elo ratings have stabilized and new bot is introduced to the competition.

I need to clarify. I'm not looking for an algorithm that will provide fair matches. I'm looking for an algorithm that will find matches most likely to update the Elo ratings of the bots to their "true" ratings with the least number of matches.

  • \$\begingroup\$ As far as I know, there is no such thing as a "true" rating (don't take my word for it). Elo and other adaptive ratings were developed so temporary good or bad streaks would have little effect on player ratings, therefore, they are thought for players that do change across time. In other words, Elo ratings are not meant to be static, so there are no "true" ratings. I'm not really sure if Elo ratings is what you're looking for, for bot battles. The best way to get good rating values is to have as many matches as possible, optimally between opponents of similar strength. \$\endgroup\$ – slcpfmmm Mar 24 '11 at 6:22

Given a normal Elo system, such a thing probably doesn't exist. It varies the scores based on the difference between an expected score and the actual score, so you can see that if you pair up people of equal skill, they're likely to draw (or have a 50% chance of winning) so the scores won't change, and if you pair up complete opposites, the veteran will almost always beat the novice (as expected) so the scores won't change there either.

The only thing that is likely to make one Elo score less accurate than another is having played fewer bouts. This means you will want them to play more. You don't have any information yet as to their actual skill level so the important thing is to get them to enter bouts and start to establish that level.

So, under these conditions, I'd just opt for ensuring that bots play as many different bots as possible, picking any bot they haven't competed against before, and favouring the selection of bots who haven't played much. New bots joining the system should be favoured in order to quickly establish their approximate levels.

  • \$\begingroup\$ Great answer. I was hoping for some math about confidence bounds, but your common sense answer is irrefutable. \$\endgroup\$ – deft_code Mar 24 '11 at 18:41

I know you already marked an answer, but to be honest it's over-simplified and doesn't really address any of the core issues of an ELO system whether you're dealing with bots or real players. For example, the core considerations when creating a fair/accurate ELO system would be: number of players, number of matches, relative impact of skill (ie: chance) on outcome, matchmaking efficiency, and how much variance there is in rating per win/loss.

In an ideal world you'd be able to match people of equal skill, and in a game of skill they would achieve a 50% win-rate. However, that assumes you know everyone's skill and that the impact of chance is relatively small. Since you don't know the former (and you didn't specify the latter) there are a number of things you need to do in order to accurately determine skill in an efficient manner and it isn't as simple as having bots play as many different bots as possible:

1) You need to set up a baseline of skill for "new" players on a scale such that they can move up or down and that the baseline represents the expected average on a normal bell curve. IE: 1250 on a scale of 1-2500.

2) New players need to play a certain number of "placement" games in order to establish their initial rating, which is typically done in 10-20 games that are rated more heavily than subsequent games. IE: rating gain/loss is double during placements what it would be later in order to encourage quick separation of players.

3) You need to account for other factors in your matchmaking such as win-rate relative to total matches so that players on extreme ends of the skill curve are moved at a faster speed to their "true" skill by facing people more above or below their current rating. IE: a player with a 80% win rate over a decent sample size should face people further above their rating and climb the ladder faster than someone with a 55% win-rate that is closer to their true skill.

4) You need to have a good understanding of how chance impacts outcome and you need to account for matchmaking speed (queue times) when determining who to match in order to keep skill variance reasonable. Using the previous scale you shouldn't have a 1250 player facing a 2000 player under any circumstances (other than when both are unrated). It isn't a fair match-up and it doesn't allow you to accurately add/remove points from their ELO.

The way I would set a system up would be to create two modifiers to a base point gain/loss value, one using the expected outcome based on rating variance and one based on a win-rate to total matches value. IE: someone with a 1500 rating who has a 70% win rate that beats a 1600 rated player will gain more points for having a high win rate AND for beating a higher rated player.

Then you just need to ensure that players complete a reasonable sample size of games and you will have the "most efficient" system based on how much chance is involved in the "game" you're implementing the ELO system for. A game with relatively low chance could take as few as a couple dozen games to be accurate, a game with relatively high chance could take hundreds...

PS: for the record, you don't want people of drastically different skill levels playing because it just dilutes the accuracy of the system. Even if you skew it so that matches above a certain variance have very little impact it creates problems because players will either feel unrewarded or overly punished for matches with high variance.

edit: I forgot to address the "already rated" part of your question, but it's pretty straight forward. You match people based on closest skill rating available in the queue, because that's the most even match and the gain/loss of points (assuming similar win-rates) will be the static value. If the players are accurately rated they would maintain the 50% win-rate and neither climb or fall. If they aren't then the more skilled player will win more than lose and their rating will update.

Introducing a new player is even simpler, they start at the baseline and get matched against players of that skill (with the increased gain/loss) until their placements are completed. So let's assume the normal point gain/loss per match is 15 without any modifier, here's an example new player placements and rating (with double gain/loss):

  • Initial: 0-0 (1250) - faces 1250 opponent
  • Loss: 0-1 (1220) - faces 1220 opponent
  • Loss: 0-2 (1190) - faces 1190 opponent
  • Win: 1-2 (1220) - faces 1220 opponent
  • Win: 2-2 (1250) - faces 1250 opponent
  • Win: 3-2 (1280) - faces 1280 opponent
  • Win: 4-2 (1310) - faces 1310 opponent
  • Loss: 4-3 (1280) - faces 1280 opponent
  • Win: 5-3 (1310) - faces 1310 opponent
  • Win: 6-3 (1340) - faces 1340 opponent
  • Win: 7-3 (1370)
  • final rating: 1370

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.