Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

Update:
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.

share|improve this question
    
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. –  slcpfmmm Mar 24 '11 at 6:22
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
Great answer. I was hoping for some math about confidence bounds, but your common sense answer is irrefutable. –  deft_code Mar 24 '11 at 18:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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