I think we can all agree that the auto-balancer kind of sucks. I've been thinking about this problem for awhile, and while I'm not sure people will be happier with a working auto balancer, I do have a solution.
Lets start with the assumptions I'm working from:
- Players want balanced teams
- The Balancer code has access to the banner of a player (Banner Balance)
- The Balancer code has access to a useful number that abstracts a players "skill / worth" to the team (I'm at work right now, but I recall seeing a number in the log showing the points each team has after a round)
- Balancer has access to a players Attributes, Proficiencies, skills, and gear. We need this to determine their class
- A the teams are balanced when either side has a 50% chance of winning a given round
- There is historical data for each round for all of the above (or will be)
I propose we use simulated annealing
http://en.wikipedia.org/wiki/Simulated_annealing to find a good state of balanced teams.
Why simulated annealing?
- It will find a good solution. It may not return the most balanced teams, but it will come reasonably close
- It can take as much or as little time as you want to run. You don't want something that takes 1 minute to find the most balanced teams. You want something that finds a good solution in a second or two. The longer it runs, the closer it will come to the optimum solution.
- The algorithm itself is agnostic to the search space. You just have to make changes to the energy function. This makes it easy to tweak how the teams are balanced without rewriting the core search algorithm
Heres is the proposed algorithm in English, as plain as I can make it.
This algorithm is trying to find the
lowest energy state (the most balanced teams.)
- Come up with the initial teams. They will have roughly the same number of people and everyone who has a banner will be on the same team with people with the same banner. This is a state. This is now both our best state and our current state.
- Check if we have any time left to balance the teams. Return the best teams we've found if we don't
- Calculate the current temperature. It should be cooler than last time we calculated it.
- Generate a new state by swapping 1 player on one team with one player on the other.
- Calculate the energy of the new state. This takes into account how the banners are set up on each team, how many players are on each team, the total skill of each team, and the class setup of each team. The more balanced the teams, the lower the energy returned.
- Check the energy of the new state against the energy of the old. If the temperature is high, theres a good chance we will make the new state the current state
even if its energy is higher than the current state. If its energy is lower than our current state, make it the new current state. As the temperature drops, the probability of moving to a higher energy state decreases as well. - If our current state is of lower energy then the best state we found, make it our new best state
- Increase the amount of time we've spent balancing teams.
- Goto step 2
And here's the algorithm as directly lifted from wikipedia, because its probably implemented right.
s ← s0; e ← E(s) // Initial state, energy.
sbest ← s; ebest ← e // Initial "best" solution
k ← 0 // Energy evaluation count.
while k < kmax and e > emax // While time left & not good enough:
T ← temperature(k/kmax) // Temperature calculation.
snew ← neighbour(s) // Pick some neighbour.
enew ← E(snew) // Compute its energy.
if P(e, enew, T) > random() then // Should we move to it?
s ← snew; e ← enew // Yes, change state.
if enew < ebest then // Is this a new best?
sbest ← snew; ebest ← enew // Save 'new neighbour' to 'best found'.
k ← k + 1 // One more evaluation done
return sbest // Return the best solution found.
In order to make the work we need to define a few variables and functions.
s0 A state where the number of players on each team is roughly equal and all players with the same banner are on the same team.
neighbor(s) In order to change states, the balancer should swap a player on one team with a player on the opposite team.
E(s)This is the hard one. We need to take a few things into account when calculating the energy level, so I propose splitting it into several sub functions to make it easier.
- The Difference between the number of players on each team. This should return a normalized value between 0 and 1. We will call the function that generates this teamSizeEnergy(s)
- How close we are to the ideal banner situation (All players who share a banner are on the same team). This should return a normalized value between 0 and 1. We will call the function that generates this teamBannerEnergy(s)
- The Difference in player skill between the two teams. Again, this should return a normalized value between 0 and 1. We will call this teamSkillEnergy(s)
- How evenly the classes are distributed. Should return a value between 0 and 1. teamClassEnergy(s)
So, our naive energy function looks like :
function e(s)
energy ← 0
energy ← energy + teamSizeEnergy(s)
energy ← energy + teamBannerEnergy(s)
energy ← energy + teamSkillEnergy(s)
energy ← energy + teamClassEnergy(s)
return energy
end
teamSizeEnergy(s) This one should be pretty easy. Our worst case is everyone is on the same team, our best case is that the teams are completely balanced.
function teamSizeEnergy(s)
energy ← 0
energy ← absoluteValue(s.team1.numPlayers - s.team2.numPlayers)/s.totalPlayers
return energy
end
teamBannerEnergy(s) This is a little trickier. Our best case scenario is that all players are on the same team as players that share their banner. But whats the worst case? Is it half on one team, half on the other? If theres only two people with a banner, that split would suck. But is it just as bad if there are 10 people with the banner? Suggestions would be welcome.
teamSkillEnergy(s) This one should be pretty easy. Out worst case is that all the high skill players are on one team and all low skill players are on the other. Our best case is that both team have an equal amount of skill on them. The hard part is determining a players skill. The best system (that I know of) to do this is TrueSkill. It is much better for a battle/siege scenario than ELO.
http://research.microsoft.com/en-us/projects/trueskill/. However, any reasonably useful abstract ranking would be sufficient.
function teamSkillEnergy(s)
energy ← 0
energy ← absoluteValue(s.team1.totalSkill - s.team2.totalSkill)/s.totalSkill
return energy
end
teamClassEnergy(s) This one will take some work, and any suggestions would be appreciated. Programmatically determining a players class is not as easy as it looks at first glance. For instance, if someone only has archery skill, its pretty easy to see they are an archer. But what if they have 3 riding skill and use a horse? Are they a horse archer? A normal archer? Ill come back to this one at a later date.
So how do we know this will work?You don't. But you don't need a full implementation to check if it will work. If enough data is stored from past battles (Player skill, class, banner) you can apply the energy function to historical data. It will, at the very least, predict when the teams are heavily unbalanced. With some tweaking it could probably even tell you which team is more likely to win. If it can accurately predict which rounds are unbalanced (Or better yet,which team will win), then it can probably do a good job
balancing the teams in its own right.
So we tried it against some historical data, and it sucks. What gives?I said it would require tweaking. Right now each of the energy sub functions returns a value between 0 and 1. So that means that banner balance is just as important as skill balance as far as the algorithm is concerned, and it probably shouldn't be. Some of those function might need to be weighted, or switched from returning a linear curve to an exponential or logarithmic curve. As I said, it will need to be tweaked and run against historical data.
So why do you care so much about class?Because it sucks when 80% of the archers are on one team and they won't stop defending. It sucks when 80% of the cavalry are on one team and your cav is too dead or scared to chase them off. I believe a good balancer should take this into account.
So whats next?Well, any input you have would be greatly appreciated (especially if its on determining class & class balance). Better yet, if we can managed to scrounge up some data, I will implement it myself and see how well it does. Hell, I'll write a web app that will let you tweak those values yourself, run it against any data I can scrounge up, and tell you how well it worked. That way anyone car try and and come up with an optimal solution.
So how can I help?- Take a screenshot of the scoreboard at the end of the match (the last scoreboard before the map changes) and post it in this thread (Battle and siege only please). That by itself is useful data. Its even more useful if you include the date/time.
- Post your name,build, and what class you think you are. If you don't want to do post your build, name and class will do as well.
- Post what class you think other people are. Anything helps.
- Post your thoughts on the energy functions. Do you think I'm missing something, or including something thats not important?
I'll be posting any data I find myself, incase anyone else finds it useful.[/list]
