Local Server Player Value

Not sure where else to post this.

Part of a problem with autobalance is how poorly the skill stack problem is handled in empires.

I think that if there was a somewhat complex system for calculating a "skill coefficient" it would help reduce the skill problem in empires.

To not make it too far fetched, the noobiest of the noobiest (new player, no stats, even negative score) will always be at 1.00

The maximum coefficient would be at ~1.25

So that a team of 4 vets would be equal to a team of 5 noobs

A team of 8 vets would equal to a team of 10 noobs

The coefficient would depend on kill death ratio, kills + deaths combined (to determine the amount of time spent playing ), time spent on server. Wages spent per kill (this one would be good as the better players would learn to preserve their tanks).

Each of these "sub" categories would only give a maximum of 0.05 pts, and let's say there's 5 of said categories, each has a threshold for the 0.01,2,3,4,5 points.

I don't have some complex formula in my head, but surely through collaborative effort in this thread we can come up with one?

 

4 vets = 5 noobs? what?!?

more like 1 vet = 5+ noobs.

also... talked over to death and still no result.

 

Are you implying that a team of 5 vets would win against a team of 25 noobs?

If so you are delusional.

Of course this system couldn't be perfect, but it would be better than it currently is.

EDIT: I don't mean total noobs, I mean like 1.05 noobs

 

I believe that it was talked to death and no result because there was simply no smart way to calculate it.

With a base being 1 for 1 player, and then ((Kills + Deaths)/Deaths)/100 (to a maximum of 0.05), time? 3hrs = 0.01, 8hrs = 0.02, 18 hrs = 0.03, 36 hrs = 0.04, 60 hrs = 0.05.

 

Once again, here's the link to the system I suggested. link

Unless this is practically impossible, I don't see why to not even try.

We used to have similar shit on VIPER and few other servers, you just have to make it more complicated(accurate), and figure out how to allow the system to affect the game and solve skill stack.

 

How to properly autobalance Empires is currently one of the most difficult unsolved problems in computer science, along with P=NP and travelling salesman. We've tried to figure it out, but there's no solution.

 

Every ranking system that comes into place has one of two major flaws:

The first type is for ranking systems such as ELO that are relative to other players. A ranking system that is relative to other players requires a few simple tunings to do properly, but far more importantly is that it has a consistent, active playerbase. And that doesn't refer to the playerbase as a whole, it needs to be one where player turnover is incredibly low relative to the size of the population. There needs to be a large core of players that are consistently playing, which is why ELO works in games such as MOBAs, because they have a strong core that the system can be balanced around and be built off of. There's a reason that some games will disregard a player's first X number of matches for their ranking, and that's because a player's early matches are a poor measurement of a player's skill. The obvious problem with Empires is that it has a relatively high turnover rate compared to the number of core players. I would consider, as a rough off-the-cuff estimate, that a "core" player would be one that, over the course of a month, plays somewhere around a minimum of 15 days with a fairly even distribution throughout the month, where in each of those days they play a minimum of two rounds. Again, rough and off the cuff, but it gives an idea of what would constitute an active, consistent player. Empires doesn't have enough players like that relative to the total number of players to form a strong core that would provide the basis of a relative ranking system such as ELO.

The second type, such as the one proposed here, is much simpler with a much simpler but still critical flaw. First, when you provide a strict upper bound on a rank, you run into the issue where multiple people at that rank are all good relative to everyone else, but some will definitely be better and others definitely worse than the average at that upper bound. Second, fine-tuning and providing a proper metric or collation of metrics to rate players is hell in and of itself.

Finally, there's another flaw independent of the ranking system that's actually of interest to me. Trying to organize the teams actually IS NP-hard. When you give each player a value and a weight, you then want the teams to have the closest possible values and the total weights of both to be the same. Obviously each player has a weight of one. Sounds familiar yet? If you have a recreational interest in mathematics and/or algorithmic complexity, you might recognize the basis of the Knapsack Problem!. Specifically, the multiple knapsack problem, where there are two knapsacks, each player has a value that's a function of their rank and a weight of one. What's more, for the teams to be balanced, every time a player joins a team, the server would have to solve the Knapsack problem again. I wonder if there's a variant of the multiple knapsack problem where the goal is to minimize the difference between the weight of each knapsack...

In other words, balancing the teams in Empires algorithmically is NP-Hard.

 

i'd rather have something like people who just installed the game/played a little bit are at 1.0, and everyone else is at 1.5. just so that it accounts for new player a little bit.

 

The system, will give each player a value, right? How about we make it this way : You can't join the team that has a *fill a number here* higher total value than the other team.
Suppose that number is 100. A has 1241, B has 1422, I can't join B since its value is 181(greater than 100) higher. Even if I am being a bitch and refuse to help A, B is only "stacked" by 181 unit.
Again, I might be too sleepy atm, but I honestly can't see why this is even 1% as difficult as Knapsack problem, it's an 'if'. In the beginning of a round, players are joining one by one, like this.
https://dl.dropboxusercontent.com/u/22159878/joining.png
We might want to give new players a low-med level of default value, it would solve a lot of problems. For example, a pro has 300, we let new players have 100. Probably also set up an absolute bottom, perhaps 50, your value can't go lower.

Now, how to make a "not inaccurate" system in the first place? We have quite a few systems around us already, the ones we had before, the ones in this thread, the ones I suggested...etc. They are definitely far from good, but they shouldn't be shit for beta ver 1.0. Of course, you wouldn't let beta ver 1.0 possess the power of balancing the teams. You can let beta ver 15.2 do the job. The button is so tapped to your palm.
You may check if the system is "not inaccurate" by checking the total value of each team and see if the round goes accordingly. (Want to contribute through specpires? Here's your choice.)

In the end, even if you don't want to balance the teams through this system, it's still a fancy and attractive feature.
Last but not least, it's gonna be some hard works and no one's getting paid for doing this. But this is most likely going to give Empires a nice jolt. If you have the spare time, it shouldn't be a bad thing to try this.

 

Yeah, it's hard to be correct.

But it's good that you don't have to be correct. You just need to be close. There's more wiggle room than you think.

I could dump a metric fuckton of examples of man-made models whose parameters are way too clean/pretty to be the statistic population parameters for their respective systems. But no one would read that shit.

Just trust me. It's cool to guess.

So the first can't deal with players for which it doesn't have enough data and the second can't deal with players for which it has too much data?

You're a sharp fella, so I'm sure you you've thought of a "hybrid" system that transitions players to an ELO-based skill system once they've hit the peak level of the first skill system.

But how could you possibly know the perfect transition point? You guessed it. You make it up, because it doesn't matter if you're right as long as you're close.

 

Shattered galaxy had a system similar to this where you couldn't join a battle or something that had too high of a power level for your own team, in a way to balance between higher levels. It worked pretty well, although that was a game where if you had a higher level that meant you had more assets at your own control.

 

Not the data on the players, but data on the playerbase as a whole. Relative ranking systems work because there's a large core base with lots of data that everyone can be compared to. Absolute systems work because of days and weeks and months of fine-tuning based off observation of how beneficial an action actually is.

I said this earlier to Security, so I'll just copy-paste what I said:

To continue with that, while a popular game would easily be able to select players to fill in the gaps until the teams are balanced both skill- and number-wise, Empires simply does not have the proper number of players. I'd bet money you wouldn't even be able to form a good approximation.

Simply put, you can end up with situations where one team has five good players and the other has ten decent players or fifteen bad players.

I know that, I'm a CS major. Approximations are the name of the game. Hell, all basic video game lighting boils down to programmers trying to approximate this terrifying integral.

But approximations are only good if they're close. I'm saying that Empires doesn't have enough objects to even get close, especially if you add the constraint that the teams need to be of somwhat equal size. The basic greedy algorithm for solving the knapsack problem is as follows for objects of the same weight. Coincidentally, if all objects are the same weight, this algorithm is already optimal:

Code:

for Object in ObjectsSortedByValue{
        if (SackIsFull)
                break;
        AddObjectToSack;
}

So now we loosen a constraint and add another one. First we now have n knapsacks of unlimited space. In this case, two teams means n = 2. The new constraint is that all knapsacks need to be similar in value. And like all optimization problems, a greedy algorithm exists to solve this:

Code:

for Object in ObjectsSortedByValue{
        if (SackAValue > SackBValue)
                AddObjectToSackB;
        else
                AddObjectToSackA;
}

As far as greedy algorithms go, it doesn't get much more simpler than that. You add the object with the highest value to the sack with less total value until that sack has higher total value. Then you repeat with the other sack, until all items are gone.

But this leads to an obvious problem. A skewed distribution of players or just a random distribution of players can cause one team to be significantly larger than the other. If you add the constraint that you want both teams to be within one or two players of each other, then you'll quickly run into many cases where trying to partition the players is impossible.

So now you need to ask yourself. Do you want skill to be close but sizes to not be, or do you want sizes to be close but skill to not be? To me, both of those choices are bad. You can loosen those constraints of course; if we ranked players from 0 - 100 and teams by the sum skill of its players, we could say that the most two teams can differ in skill is some function of the difference in the number of players, for example 100x the difference or some other number. But loosening them will quickly just mean that you end up with a system that'll make teams about as balanced as they are currently.

EDIT: Before I forget to mention, this obviously only works while people are joining at the beginning. If people join in the middle of a round after the initial partitioning, that's an even harder problem to deal with.

 

You guys are overcomplicating the issue.

It's really not that difficult.

The system isn't meant to be perfect. Yes I realize there will be quite a number of players with the highest coefficient, it's not meant to be a relative one, but rather a simple method to keep noobs in the game when playing against a stacked team.

This is not a system-rank comparison between high skilled players!

 

While I get what BJ is saying, I honestly still think it can be far simpler. Hours of gameplay is decent enough a measurement 90% of the time.

0-10 hours = 0.5 players.
10-100 = 1.0 players.
100-1000 = 1.5 players.
1000+ = 2.0 players.

Obviously you could mess about with those boundaries, make the range smaller than that. But it's simple enough that people wouldn't really grind it to get a better rating, and while it wouldn't be perfect, I honestly think it would be easier and far less hassle than some rating system that tries to understand your contribution to the team, which is virtually impossible.

 

Especially when your com building the fow rax or engy squad lead, thats about to mass rev, gets evicted to the other team.

Limit to pre-game and im ok with it though.

 

Those sample values are shit, but using gameplay time would be excellent way to differentiate between a noob and a competent player.

The problem is that there's no exchange rate between clueless noobs and competent players. A single squad of players that understand Empires can easily demolish two dozen noobs that don't get the Empires win conditions.

So the best you can do is attempt to put an even number of noobs on each team. They are all equally worthless, so it's a close enough way of doing it.

But then you also have differentiate competent players. Now you can look at exchange rates. You can say that two Spartacuses (Spartaci?) are worth one Neony or whatever. This is where it starts to get murky.

Again, I come back to that "hybrid" system that I previously mentioned.

Even Counts: You take all of the players under 100 (or w/e) hours and assume that they are equally worthless. They get uniformly distributed amongst the two teams.

Even Skills: Then the "vets" can separately have a system that evens the collective "vet" skill between the teams. This is where one Hopfi can equal two Spartacuses. Yeah, we have less than 200 players in that pool, but it probably wouldn't be that bad. You can have a weak constraint that each pool of "vets" must have more than one player when there are at least four "vets" in the game.

I'd use the same "greedy" algorithm to plop players on a team whether they join before the match starts or if they join midway into the match.

Yes, it's the wrong way to do it, but I'm not convinced that we need to get that accurate.

 

Very nice deduction. Looking at the approximation algorithms available, it seems that we'd have a hard time because we have limited supply in our items and their value can vary wildly.

For people who don't understand the gravity of Candles' statement: Candles has deduced that perfectly auto-assigning players will take a very long time. How long?

Let's say we want to auto-assign 40 players in the most optimal way possible. Let's say that the computational complexity is 2^n, so we would need to do 2^40 computations (most of them being comparisons). Let's say our computer needs to do 3 instructions per computation (load the two numbers, then compare). Now, we need to find the speed at which a computer can process instructions. The Intel Core 2 Extreme QX9770 (Quad core), which is what I think is in the EPIC dedicated server, can handle 59,455 MIPS. So, let's plug this all into our calculation:

(2^40) / (59455000000/3) = 55.4795203655 seconds

So, for 40 players, the server will completely halt and spend nearly a minute churning away to get us that answer. In reality, the MIPS value is wildly optimistic, and of course there are other things vying for processor attention, so my wild guess would be anywhere from 5 to 20 minutes. For a single, full, auto-assign of 40 players.

To further illustrate how ridiculously intense this calculation is, we can sort 30 billion numbers in a time of 30000000000 * lg 3000000000 seconds, which takes just a little more time than auto-assigning 40 players.

 

I don't think we'd need full auto-assign/scramble to do the job.

My idea is that we put an "if" to stop people from joining a stacked team. Just like autobalance, but with a more complicated algorithm(this is the point).