So, the most common way to assign numbers to players of a skill-based game to try to capture their skill level is with an Elo system. And I think mathematically the way it works makes a lot of sense.
But I want to try to design my own ranking system. It'll probably turn out worse than Elo's. I have a specific thing I want to try out though. I want to try to be able to ask of a game: how many tiers of domination are there between the best in the world at the game and the worst? In other words, what's the longest chain of players such that each player wins basically 100% of games against the next in the chain?
Elo's system can kind of answer this by looking at the spread between the top player's rating and the lowest. But, you kind of have to decide for yourself what win rate counts as "dominating". You have to pick a percentage (strictly less than 100) at which you consider it dominating to determine what a "tier" is for the purposes of my question. So, my system's goal is to not be arbitrary in the definition of "tier". Or as I'll call them, "epoch"s.
Okay, so let's say we give every player a ranking. We want this to mean something about their skill. So, let's say, like with Elo's system, the ratings should roughly predict the probability of one player beating another. My solution is to take the most childish approach, which is way less mathematically sound than Elo's. Given two player's ratings , the probability that player 1 wins is (clamped between 0 and 1).
Basically: if players have equal scores, they have equal chances of winning. If a player's score is more than 1 point higher than the other's, then the first player should win 100% of the time. Interpolate linearly. If it's half a point higher, then it's halfway in between (75%). And so on.
This way, we get our system declaring literal probabilities of 1, which shouldn't exist, but we need to exist for the purpose of this experiment. This then lets us answer the question of how many epochs of skill there are in the game. By just taking the difference between the top rated player and the bottom.
In a future post, I'll discuss how this system might work in some real world examples, and how it compares to Elo's. I'll also discuss how to go about actually assigning ratings to players.
I like collecting facts about natural numbers where the number is an answer to a natural-ish question. Here are two such facts:
5 is the number of Euclidean solids.
14 is the largest number of distinct sets obtainable by repeatedly applying the set operations of closure and complement to a given starting subset of a topological space.
Okay, so today's thing is more like a blog post in format than an image or interactive thing. Much of this was worked out around a decade ago, but I'm re-working it out as I'm finally getting around to writing it up now.
Basically, I was thinking about a player's progression through building up resources in a board game, and I came up with a toy model that oversimplifies a lot of things (that's what being a toy model is, after all). The model goes like this: imagine a 1-player game where your goal is to maximize your total number of widgets; on every turn, you have a single choice to make between two options: (1) build a widget-factory, or (2) have each widget factory you own produce one widget. The toy model doesn't account for when the game ends. If you know that the game is going to end after some specified number of turns, then it's pretty trivial to solve for the right answer: spend the first half of your turns building and the second half producing. The proof is left as an exercise to the reader.
Now, how do we want to handle the more interesting case where you don't know when the game ends? Well, perhaps the most obvious way is to pick some probability , and say each turn with probability the game ends. You could pick a specific or just use as a variable in your calculations. This isn't what I decided to do. I decided to handle it differently. I decided to make the game infinite instead. My question became: what strategy creates the fastest-growing number of widgets as a function of time? In other words, what sequence of moves gets you the best asymptotic behavior? This is the core question I aim to answer.
Okay, let's start by getting an upper bound. At time/turn , the most widgets you could have by then (as determined above) is to build for the first half and produce for the second half. No real strategy could obviously achieve this for every , but if one could, they would see that at time , they have widgets. So that's our upper bound.
Now, let's pick some obvious strategies and see what they gets us, just to get a feel for the problem. Obviously the two trivial strategies of build every turn or produce every turn get us zero widgets. But, we could build once and then produce every turn thereafter. At turn That gets us widgets. We can do better by building twice and then producing every turn. Or better yet, building times and then producing every turn. That gets us . Still not great. Not even quadratic.
Let's try the next most obvious thing: diagonalizing. That is, let's alternate build and produce every turn. At turn (let's just assume is even for simplicity), we have . Wow! This is only slightly worse than half of the unattainably optimal upper bound!
(End of part 1. To be continued...)