Any ideas how to make ranking less random?

[Astek]

As we all see only first place is not changing at all - gratz Gábor!

Rest of the rankings are changing a lot (for example bots ranked 2-5 are swapping all the time) . So in current situation final ranking will be in many cases matter of luck in last few games (depend on opponent and map).

Let me explain it in one sentence:
If for last few fights your bot will have to face opponents with much lower ranking and in current situation maps are so different so there is always possibility to lose than statistically he will be in worse situation than bot close to him which will face better opponents.

http://en.wikipedia.org/wiki/Elo_rating_system

In short: Let bots at specific score fight with other bots with almost the same score at the end of the finals.

So I think that if organizers will agree to lower range of picking opponents than we will have less random ranking.

What is your opinion?

Adrian

[antimatroid]

A lot of time has been spent discussing this on irc, it's really hard to work out a way that is in every way ideal.

While for a given set of maps, a round robin would probably give a decent ranking over the bots, it simply isn't possible with the number of bots entered (which is only expected to rise into the future), especially not with a decent sample size of maps. Janzert also makes some good points, that is that It is incredibly inefficient, while it's good to have bots play bots from all ranking regions, there is no point in having the top bots playing the bottom bots half of the time, it's just a huge waste of time, and it has the potential of ruining a bots one pairing on a map they're actually half decent on.

Completely random pairings was done for tron, and it was horrible, the top bots got very very few games with bots of a similar rank, which means the top ranked bots weren't so much decided on how good they performed against each other, I really don't think going back to that would be an improvement over what is currently being done. One option might be to start the official contest with completely random pairings, then once the bots are somewhat approaching their rightful places to turn on the better pairing algorithm for on average playing more games against closer ranked bots, but even that has issues.

The other options that I see are to incrementally freeze the bottom end of the rankings, before finally running a top x round robin on m maps, or possibly a merge sort type process, of spliting the leaderboard up into groups, with the final round being a round robin amongst each group to finalise rankings inside those groups. The biggest floor I see here is that I think rankings really need to be reset for each iteration, which means actual final rankings in your region are strictly determined from other bots inside that range.

At the end of the day, ranking is a very complicated process, what we have here is a hell of a lot better than any kind of sporting event or even a human chess championship etc. so however the rankings end, we'll just have to take them as is.

What I would like to see happen before the next contest is a whole bunch of pseudo contests run with these bots trying out different ranking methods, trying to work out which methods seem to give the most consistent rankings over the bots. A particularly good idea might be to pick out a few decently ranked bots and enter them twice, then work out how far apart they end up in the rankings. I also like the idea of using a brand new map for every game.

Edit: just noticed I didn't address your actual question, no I don't particularly like the idea of final rankings being decided based off just bots around your ranking, not to mention that doesn't help the fact that some bots are supposedly currently outside their true ranking value

[Kyunez]

I have only one little suggestion, where I completely agree with "antimatroid". We need as much maps from the generator as possible. If, for example, one Bot has some advantages on the only one map from the set, but is very week on the other fields his luck should not repeat. I think It makes the sense.

As for the group division. If the discision was mine I would do the following:
I would do the cutoff 2048,1024... 32. But it would mean that if cutoff is 32. Bots with rank higher than 33 can face any bot as upper 32-th place and so lower, but two bots with rank lower than 32 can not play with each other.

Hope it could help.

[Astek]

[Mistmanov]

/checks rank

I'd suggest that for the final day, only the top 100 plays games, and adversaries are selected randomly. With ~100 games per minute, everyone would get 2 games per minute (since there are 2 players per game). 2*60*24 = 2880 games for each bot, or every bot will play each other bot ~29 times. For even better results you could add another day, where just the top50 plays each other, which would give each bot 4*60*24/50 = 115 games against every other bot.

edit: this might now work if all of the top bots are a lot slower than the lower ranked bots. If all the top bots take the full second per turn instead of just ~10 ms, the amount of games played per minute will also be divided by 100, and thus every bot would only get 1.15 game against every other bot.. But I believe/hope that at least a majority of the top50 bots are still reasonably fast.

[Kyunez]

[Kyunez]

[Kyunez]

Interesting fact:
For last few hours I've left about 100 points, but my rank upped for 3 places.
I feel like bocsimacko indirectly eating our ELO O_o

[Janzert]

Yes, unfortunately whenever there is only a small gap in elo it would take 1000's of games per bot to completely nail down the order. In order to help give people an idea of how certain there superiority over others is I'm hoping to add information to the leaderboard that will show how far up or down the rankings you have to go before reaching 90% certainty all the bots further away are better or worse. Unfortunately this can't be done live as it takes far too long to compute. Also don't expect this as soon as the finals close it will probably take a while (think on the order of days) before I can this integrated and up.

The pairing cutoff will keep moving up to try and assure the top bots get the narrowest range as possible.

Janzert

[narnach]

The current method of ranking (Bayes ELO) seems to work quite well for my bot: after an initial peak at rank 270-ish, the stronger bots have gotten more plays and pushed my bot down to hover around rank 370. I think it took about 10 matches for my bot to get to the top 400.
Before the finals, this version of my bot was up for over a week and ended at rank 378. For my bot, if it is 370 or 380 does not matter much, rounding to the nearest 10 is accurate enough for me. If my bot was top 100, every rank would be important to me as each rank would mean a lot more.

Since precise rankings are more meaningful the higher one gets on the ladder, an obvious conclusion for me is to let higher ranked bots play more often. That way the get more games to make their rankings more precise.

For the finals there are the cutoffs that will ensure the higher ranked bots eventually get more plays, but for the regular competition this makes no sense: since it is ongoing, hard cutoffs are impractical.

For the competition, you want to give new submissions a chance to move rapidly through the ranks to move in the general direction of their "true" ranking. But after those initial 10 or so games, let them play more or less based on how high they rank.

Let's play a bit with numbers. Assume we have 5000 bots and we can play 5000 matches per hour on the servers. This means that a bot can play 2 times per hour if match scheduling is done purely by chance and there is no bias.

If instead you give higher ranked bots a higher chance to play than lower ranked bots, the breakdown of 5000 matches played could look like this:

* The top 8 get 10 plays per hour (40 games total)
* The top 9-16 get 9 plays per hour (36 games total)
* The top 17-32 get 8 plays per hour (64 games total)
* The top 33-64 get 7 plays per hour (112 games total)
* The top 65-128 get 6 plays per hour (192 games total)
* The top 129-256 get 5 plays per hour (320 games total)
* The top 257-512 get 4 plays per hour (512 games total)
* The top 513-1024 get 3 plays per hour (768 games total)
* The top 1025-2048 get 2 plays per hour (1024 games total)
* The top 2049-5000 get 1 play per hour (1476 games total)
* The 456 matches that are left unscheduled can be used to give recent submissions an increased amount of plays during their first X games.

By giving crashing bots, starter bots and weaker bots 1 game less than they could get on average, the competition has gotten a lot more interesting for people who are more actively/strongly participating.