Print Page - Proposed change to team-balance algorithim

cRPG => Suggestions Corner => Topic started by: Vanthor on February 20, 2014, 07:49:25 pm

Title: Proposed change to team-balance algorithim
Post by: Vanthor on February 20, 2014, 07:49:25 pm

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)

http://en.wikipedia.org/wiki/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.

(click to show/hide)

And here's the algorithm as directly lifted from wikipedia, because its probably implemented right.

(click to show/hide)


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.

(click to show/hide)

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/ (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]

Title: Re: Proposed change to team-balance algorithim
Post by: Vanthor on February 20, 2014, 07:50:28 pm

Class/build

(click to show/hide)

Title: Re: Proposed change to team-balance algorithim
Post by: Sniger on February 20, 2014, 07:53:39 pm

hardcore.

will prep a .zip for ya

Title: Re: Proposed change to team-balance algorithim
Post by: Kafein on February 20, 2014, 08:11:57 pm

Lots of text for something in the end relatively simple (and to be honest quite mainstream in this kind of problem). I mean I know it would work very nicely but you could present it more succinctly. For example you should remove all the physics analogies, they serve no purpose.

I'm also quite sure the dev team has people qualified enough to come up with good optimizers already. The real problem here isn't the algorithm, but it's the definition of what is a set of balanced teams. It's your energy function.

Title: Re: Proposed change to team-balance algorithim
Post by: Vanthor on February 20, 2014, 08:32:27 pm

Thanks for the input Kafein, I'll see what I can do to re-arrange it so the energy function piece more prominent / succinct.

Title: Re: Proposed change to team-balance algorithim
Post by: Sniger on February 20, 2014, 08:33:14 pm

i think it was real awesome post sure i had to read alot but i like details and stuff

everyone is not a programming guru like kaf :twisted:

Title: Re: Proposed change to team-balance algorithim
Post by: Elindor on February 20, 2014, 08:50:05 pm

Wow, that's very thought out...

Here's what I would say.
Whether the dev team has the knowhow is one thing, but bottom line is - THE BALANCE SYSTEM SUCKS AND HAS SUCKED AND IS PROBABLY THE BIGGEST DETERENT OF THIS GAME so them having the knowhow is irrelevant really...maybe they do need a good suggestion?

I am not 100% sure that "class balance" is really as important a factor as just plain old BALANCING of a player's score/kdr, whether that is derived from his current performance or a combo of current and overall stats that the server keeps.

------

BIGGEST ISSUE which should be rather simple to change is the following:
When a clan stack is going strong, the balancer will often STILL give good, well performing players to that side.

Let's consider a scenario that you might see quite often in game:
- A clan stacked team is winning 3-0 and the top half of their team has scores like 11/1, 8/2, 5/1 and many scores in the 100's.
- Meanwhile the other team has lost all the rounds that map, it's top half of the team has kdrs like 5/2, 4/3, 3/3 and scores in the 50's or so.

In this situation, it has to keep the banner stack together, but shouldn't it give any "free agent or small clan" that is doing well to the OTHER TEAM? And yet, it does not.
This seems insane to me and it kills gameplay....

** WHETHER ITS FROM A STACK OR NOT - The end result of a map should be that the top half of the scoreboard should look RELATIVELY similar as far as kdrs/scores **
Doesn't have to be exact, but the current results (similar to the scenario I posted above) are so obviously one sided. If this were fixed you would see a lot more close matches instead of so many steamrolls.

Title: Re: Proposed change to team-balance algorithim
Post by: Vanthor on February 20, 2014, 08:58:38 pm

Quote from: Elindor on February 20, 2014, 08:50:05 pm

BIGGEST ISSUE which should be rather simple to change is the following:
When a clan stack is going strong, the balancer will often STILL give good, well performing players to that side.

Let's consider a scenario that you might see quite often in game:
- A clan stacked team is winning 3-0 and the top half of their team has scores like 11/1, 8/2, 5/1 and many scores in the 100's.
- Meanwhile the other team has lost all the rounds that map, it's top half of the team has kdrs like 5/2, 4/3, 3/3 and scores in the 50's or so.

In this situation, it has to keep the banner stack together, but shouldn't it give any "free agent or small clan" that is doing well to the OTHER TEAM? And yet, it does not.
This seems insane to me and it kills gameplay....

I think everyone's seen that happen. Thats why I included

Quote from: Vanthor on February 20, 2014, 07:49:25 pm

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)

in the lists of assumptions I was making. I know that the server calculates some kind of skill/worth value for every player, but I have no idea how its calculated or how useful it is. It doesn't really matter what system your using to balance teams if they rely on a bogus skill value.

Title: Re: Proposed change to team-balance algorithim
Post by: Jona on February 21, 2014, 12:46:44 am

I was playing late-night (read: really early morning) battle last night, with only 5v5 or 6v6ish for a while. The balancer put the two top players on the same team after round 1. They each had more score than every player on the entire enemy team combined. The thing is, they weren't even in the same clan, so there was no reason they should be put together. The total score of the two teams after one round was about 16 points vs 60. Makes sense, right?

The thing is, this isn't a problem limited to low-pop servers. It is just far more noticeable and easier to point out the flaws in the system when you can count up the total scores of each team in a matter of seconds.

Title: Re: Proposed change to team-balance algorithim
Post by: korppis on February 21, 2014, 08:48:42 am

Quote from: Vanthor on February 20, 2014, 07:49:25 pm

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.

Splitting would suck unless that banner is too dominant in numbers. Say, 10 with same banner is not a problem if there's 80 players, but it can be a problem if there's only 30. Do we really have to calculate banner energy if they're less than x% of population and there's enough people to balance around? I wouldn't even mind slight class unbalance versus splitting banners.

Quote from: Vanthor on February 20, 2014, 07:49:25 pm

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.

It doesn't have to be so accurate.

No matter the melee/archery proficiency, if the player has 4 or less in riding, it doesn't really change anything. Those lower tier horses are crap and he'd turn slow, so why even count that? But if he has 6 or so, those heavier horses start to make difference.

Also, is it really worth sorting HA from other cav? Why not just keep balancing mounted as a whole?

Same with weapon wpf, hybrids with less than 100 in some skill hardly make a difference.

Title: Re: Proposed change to team-balance algorithim
Post by: zagibu on February 21, 2014, 10:16:56 am

Here is the current team balance code, feel free to modify it directly:

Quote from: zagibu on February 11, 2014, 11:24:08 pm

Someone asked for the team balance code, here it is, prepare to grease your scroll wheels:

Code: [Select]
#script_cf_crpg_autobalance ("cf_crpg_autobalance", [ (multiplayer_is_server), (store_script_param, ":type", 1), #(display_message, "@AB called"), #(assign, reg1, ":type"), #(server_add_message_to_log, "@new autobalance start, type:{reg1}"), (store_script_param, ":param", 2), (assign, ":switch_player_no", -1), (try_begin), (eq, ":type", 0), #type0 = shuffle teams #check if autobalance is set to 2 - sort by banners (eq, "$g_multiplayer_auto_team_balance_limit", 2), (assign, ":type", 3), (else_try), (eq, ":type", 1), #type1 = balance teams, in favor of :team_favor (assign, ":team_favor", ":param"), #team favor: #-1 = no team favor #0 = favor team 0 #1 = favor team 1 (else_try), (eq, ":type", 2), #type2 = switch player :switch_player_no #(display_message, "@Type: 2"), (assign, ":switch_player_no", ":param"), (assign, ":switch_player_score", -1), (store_script_param, ":param2", 3), (assign, ":force_switch", ":param2"), (try_end), ##calculate the current team levels (try_begin), #(this_or_next|eq, ":type", 1), #balance #(eq, ":type", 2), #switch player (assign, ":level_team_0", 0), (assign, ":level_team_1", 0), (assign, ":player_team_0", 0), (assign, ":player_team_1", 0), (assign, ":kd_team_0", 0), (assign, ":kd_team_1", 0), (get_max_players, ":num_players"), (try_for_range, ":player_no", 0, ":num_players"), #t_player1 (store_add, ":slot_index", ":player_no", multi_data_player_index_list_begin), (troop_set_slot, "trp_multiplayer_data", ":slot_index", 0), (try_begin), (player_is_active, ":player_no"), (ge, ":player_no", 0), (player_get_team_no, ":player_team", ":player_no"), (is_between, ":player_team", 0, 2), #make sure he is no spec (troop_set_slot, "trp_multiplayer_data", ":slot_index", 1), (call_script, "script_cf_crpg_autobalance_get_level", ":player_no"), (assign, ":player_score_plus_death", reg0), (try_begin), (eq, ":switch_player_no", ":player_no"), (assign, ":switch_player_score", reg0), (try_end), (try_begin), (eq, ":player_team", 0), (neq, ":switch_player_no", ":player_no"), #do not take the switcher player into calc (val_add, ":player_team_0", 1), (val_add, ":level_team_0", ":player_score_plus_death"), (store_add, ":cur_troop", "trp_player0_multiplayer", ":player_no"), (ge, ":cur_troop", 0), (troop_get_slot, ":kd", ":cur_troop", slot_troop_crpg_kd_ratio), (val_add, ":kd_team_0", ":kd"), (else_try), (eq, ":player_team", 1), (neq, ":switch_player_no", ":player_no"), (val_add, ":player_team_1", 1), (val_add, ":level_team_1", ":player_score_plus_death"), (store_add, ":cur_troop", "trp_player0_multiplayer", ":player_no"), (ge, ":cur_troop", 0), (troop_get_slot, ":kd", ":cur_troop", slot_troop_crpg_kd_ratio), (val_add, ":kd_team_1", ":kd"), (try_end), (try_begin), (neq, ":player_score_plus_death", 0), #dont disable the slot by accident (neq, ":player_score_plus_death", -1), (troop_set_slot, "trp_multiplayer_data", ":slot_index", ":player_score_plus_death"), (try_end), (try_end), (try_end), #t_player1_end = this checked for levels and assigned each player his value (try_end), (assign, "$ab_score_team_0", ":level_team_0"), (assign, "$ab_score_team_1", ":level_team_1"), (assign, reg9, -3), (neq, "$g_multiplayer_auto_team_balance_limit", 0), #if it's 0, return false, then the player selection is used (neq, "$g_multiplayer_auto_team_balance_limit", 3), #if it's 3, return false, then the player selection is used (neq, "$g_multiplayer_game_type", multiplayer_game_type_defend_the_village), #don't do any AB in dtv (assign, ":do_autobalance", 1), #start with assigned autobalance (try_begin), (eq, ":type", 1), #type1 = balance teams, in favor of :team_favor #one team should be in favor - check if the favored team has less level (try_begin), (eq, ":team_favor", 0), (ge, ":level_team_0", ":level_team_1"), #if level0 > #level1 skip autobalance (assign, ":do_autobalance", 0), (else_try), (eq, ":team_favor", 1), (ge, ":level_team_1", ":level_team_0"), #if level1 > #level0 skip autobalance (assign, ":do_autobalance", 0), (try_end), (try_end), (try_begin), (eq, ":type", 2), #type2 = switch player :switch_player_no (assign, ":do_autobalance", 0), #stop autobalance here, because it's done inside this #check if the player in question is on the lower leveled team already (player_get_team_no, ":player_team", ":switch_player_no"), #(display_message, "@Type 2 AB"), (try_begin), (eq, ":player_team", 0), (gt, ":level_team_0", ":level_team_1"), #if level0 > #level1 do moving (assign, reg9, 1), (try_begin), (eq, ":force_switch", 1), (call_script, "script_crpg_switch_player_team", ":switch_player_no", 1), (try_end), (val_add, "$ab_score_team_1", ":switch_player_score"), (else_try), (eq, ":player_team", 1), (gt, ":level_team_1", ":level_team_0"), #if level1 > #level0 do moving (assign, reg9, 0), (try_begin), (eq, ":force_switch", 1), (call_script, "script_crpg_switch_player_team", ":switch_player_no", 0), (try_end), (val_add, "$ab_score_team_0", ":switch_player_score"), (else_try), #he's a spec (try_begin), #team-switch disable in siege (player_get_slot, ":player_previous_team", ":switch_player_no", slot_player_crpg_last_team), (is_between, ":player_previous_team", 0, 2), (eq, "$g_multiplayer_game_type", multiplayer_game_type_siege), #(eq, "$g_multiplayer_game_type", multiplayer_game_type_battle), #(display_message, "@Previous team is 0 or 1"), (try_begin), (eq, ":player_previous_team", 0), (assign, reg9, 0), #(call_script, "script_crpg_switch_player_team", ":switch_player_no", 0), (player_set_team_no, ":switch_player_no", 0), #(display_message, "@Moving player to team 0"), (val_add, "$ab_score_team_0", ":switch_player_score"), (else_try), (eq, ":player_previous_team", 1), (assign, reg9, 1), #(call_script, "script_crpg_switch_player_team", ":switch_player_no", 1), (player_set_team_no, ":switch_player_no", 1), #(display_message, "@Moving player to team 1"), (val_add, "$ab_score_team_1", ":switch_player_score"), (try_end), (else_try), (ge, ":level_team_1", ":level_team_0"), #if level1 > #level0 do moving (assign, reg9, 0), (try_begin), (eq, ":force_switch", 1), (call_script, "script_crpg_switch_player_team", ":switch_player_no", 0), (try_end), (val_add, "$ab_score_team_0", ":switch_player_score"), (else_try), (assign, reg9, 1), (try_begin), (eq, ":force_switch", 1), (call_script, "script_crpg_switch_player_team", ":switch_player_no", 1), (try_end), (val_add, "$ab_score_team_1", ":switch_player_score"), (try_end), (try_end), (try_end), (try_begin), #current situation: #if type = 0, autobalance = 1 #if type = 1, autobalance = 1 if teams are unfair #if type = 2, autobalance = 0, player got moved already (eq, ":do_autobalance", 1), (assign, ":new_level_0", 0), (assign, ":new_level_1", 0), (try_begin), (eq, ":type", 3), #3(by banners) is very special and checked separately #a) get all different banners, sort them in b array (try_for_range, ":array", crpg_banner_number_start, crpg_banner_number_end*2), (troop_set_slot, "trp_temp_array_a", ":array", 0), #a = if the banner exists or not (troop_set_slot, "trp_temp_array_b", ":array", 0), #b = the score of the banner (try_end), (store_add, ":level_score_halfed", ":level_team_0", ":level_team_1"), (store_div, ":level_score_halfed_regulars", ":level_score_halfed", 9), (val_div, ":level_score_halfed", 3), (try_for_range, ":player_no", 0, ":num_players"), #t_player2 (player_is_active, ":player_no"), (store_add, ":slot_index", ":player_no", multi_data_player_index_list_begin), (neg|troop_slot_eq, "trp_multiplayer_data", ":slot_index", 0), (neg|troop_slot_eq, "trp_multiplayer_data", ":slot_index", -1), (player_get_banner_id, ":banner", ":player_no"), (try_begin), (le, ":banner", -1), (store_random_in_range, ":banner", crpg_banner_number_start, crpg_banner_number_end), (try_end), (troop_get_slot, ":rank", "trp_temp_array_b", ":banner"), (troop_get_slot, ":player_value", "trp_multiplayer_data", ":slot_index"), (try_begin), (is_between, ":banner", crpg_banner_number_start, crpg_banner_number_end), (assign, ":score", ":level_score_halfed_regulars"), (else_try), (assign, ":score", ":level_score_halfed"), (try_end), (val_add, ":rank", ":player_value"), (try_begin), (ge, ":rank", ":score"), #security mechanism - if one side has more than 50% power, split them #(val_add, ":banner", 1), #just take the next banner, doesn't matter (store_random_in_range, ":banner", crpg_banner_number_start, crpg_banner_number_end), #this is better (troop_get_slot, ":rank", "trp_temp_array_b", ":banner"), (val_add, ":rank", ":player_value"), (try_end), (troop_set_slot, "trp_temp_array_a", ":banner", 1), (troop_set_slot, "trp_temp_array_b", ":banner", ":rank"), (player_set_slot, ":player_no", slot_player_crpg_ab_banner, ":banner"), (try_end), (try_for_range, ":banner_id", crpg_banner_number_start, crpg_banner_number_end*2), (troop_get_slot, ":rank", "trp_temp_array_b", ":banner_id"), (gt, ":rank", 100), (assign, ":power", 1), (set_fixed_point_multiplier, 10000), (convert_to_fixed_point, ":power"), (convert_to_fixed_point, ":rank"), (val_mul, ":power", 11), (val_div, ":power", 10), #result: 1.1 (store_pow, ":tmp", ":rank", ":power"), (assign, ":rank", ":tmp"), (convert_from_fixed_point, ":rank"), (troop_set_slot, "trp_temp_array_b", ":banner_id", ":rank"), (try_end), #(assign, ":assign_players_to_team", 0), #b) loop through banners, get the one with the highest number (try_for_range, ":banner_id", crpg_banner_number_start, crpg_banner_number_end*2), (troop_slot_eq, "trp_temp_array_a", ":banner_id", 1), (assign, ":selected_banner_id", -1), (assign, ":selected_banner_score", -1), (try_for_range, ":ranking_banner_id", crpg_banner_number_start, crpg_banner_number_end*2), (neg|troop_slot_eq, "trp_temp_array_b", ":ranking_banner_id", 0), (troop_get_slot, ":rank", "trp_temp_array_b", ":ranking_banner_id"), (ge, ":rank", ":selected_banner_score"), (assign, ":selected_banner_score", ":rank"), (assign, ":selected_banner_id", ":ranking_banner_id"), (try_end), (gt, ":selected_banner_id", -1), #it's valid (troop_set_slot, "trp_temp_array_b", ":selected_banner_id", 0), #removed from the loop pool #b2) select the proper team: (try_begin), (eq, ":new_level_0", 0), (eq, ":new_level_1", 0), (store_current_scene, ":cur_scene"), #assign the start team randomly, based on scene nr (store_mod, ":assign_players_to_team", ":cur_scene", 2), (else_try), (gt, ":new_level_1", ":new_level_0"), (assign, ":assign_players_to_team", 0), (else_try), (assign, ":assign_players_to_team", 1), (try_end), #c) highest banner selected, switch all players of this banner to team (try_for_range, ":player_no", 0, ":num_players"), #t_player2 (player_is_active, ":player_no"), (store_add, ":slot_index", ":player_no", multi_data_player_index_list_begin), (neg|troop_slot_eq, "trp_multiplayer_data", ":slot_index", 0), (neg|troop_slot_eq, "trp_multiplayer_data", ":slot_index", -1), #(player_get_banner_id, ":banner", ":player_no"), #banner can now be overridden: (player_get_slot, ":banner", ":player_no", slot_player_crpg_ab_banner), (eq, ":banner", ":selected_banner_id"), (troop_get_slot, ":value", "trp_multiplayer_data", ":slot_index"), (troop_set_slot, "trp_multiplayer_data", ":slot_index", 0), #removed from the loop pool (try_begin), (eq, ":assign_players_to_team", 0), (val_add, ":new_level_0", ":value"), (else_try), (eq, ":assign_players_to_team", 1), (val_add, ":new_level_1", ":value"), (try_end), (player_get_team_no, ":curr_team", ":player_no"), (try_begin), (neq, ":curr_team", ":assign_players_to_team"), (call_script, "script_crpg_switch_player_team", ":player_no", ":assign_players_to_team"), (try_end), (try_end), (try_end), (assign, "$ab_score_team_0", ":new_level_0"), (assign, "$ab_score_team_1", ":new_level_1"), (try_end), (neq, ":type", 3), #3(banners) is very special and checked before, fail if done (try_for_range, ":unused", 0, ":num_players"), #t_player1 (player_is_active, ":unused"), (assign, ":max_score_plus_death", -30000030), (assign, ":max_score_plus_death_player_no", -1), (try_for_range, ":player_no", 0, ":num_players"), #t_player2 (player_is_active, ":player_no"), (store_add, ":slot_index", ":player_no", multi_data_player_index_list_begin), (neg|troop_slot_eq, "trp_multiplayer_data", ":slot_index", 0), (neg|troop_slot_eq, "trp_multiplayer_data", ":slot_index", -1), (troop_get_slot, ":value", "trp_multiplayer_data", ":slot_index"), (try_begin), (eq, ":type", 0), #check if it's shuffle command (gt, ":value", ":max_score_plus_death"), (assign, ":max_score_plus_death", ":value"), (assign, ":max_score_plus_death_player_no", ":player_no"), (else_try), (eq, ":type", 1), #check if it's autobalance command (neg|troop_slot_eq, "trp_multiplayer_data", ":slot_index", 0), #wasnt moved yet #calculate the team diff (store_sub, ":level_diff", ":level_team_0", ":level_team_1"), #divide by 2 (val_div, ":level_diff", 2), (try_begin), (gt, ":level_diff", 0), #team0 has higher level (assign, ":from_team", 0), (else_try), (lt, ":level_diff", 0), #team1 has higher level (val_abs, ":level_diff"), (assign, ":from_team", 1), (else_try), (assign, ":from_team", -1), (try_end), #get team (player_get_team_no, ":player_team", ":player_no"), (eq, ":player_team", ":from_team"), (val_sub, ":level_diff", ":value"), (ge, ":level_diff", 0), (this_or_next|eq, ":max_score_plus_death", -30000030), (lt, ":level_diff", ":max_score_plus_death"), (assign, ":max_score_plus_death", ":level_diff"), (assign, ":max_score_plus_death_player_no", ":player_no"), (try_end), (try_end), #t_player2 #here we now have the highest player (try_begin), (eq, ":type", 0), #check if it's shuffle command (ge, ":max_score_plus_death_player_no", 0), (store_add, ":slot_index", ":max_score_plus_death_player_no", multi_data_player_index_list_begin), (troop_get_slot, ":value", "trp_multiplayer_data", ":slot_index"), (assign, reg8, ":value"), (assign, ":value", ":max_score_plus_death"), (assign, reg12, ":value"), (troop_set_slot, "trp_multiplayer_data", ":slot_index", 0), #removed from the loop pool (player_get_team_no, ":curr_team", ":max_score_plus_death_player_no"), (try_begin), (gt, ":new_level_0", ":new_level_1"), (assign, reg9, 1), (val_add, ":new_level_1", ":value"), #checking if he is on the right team (try_begin), (neq, ":curr_team", 1), (call_script, "script_crpg_switch_player_team", ":max_score_plus_death_player_no", 1), (try_end), (else_try), (val_add, ":new_level_0", ":value"), (assign, reg9, 0), #checking if he is on the right team (try_begin), (neq, ":curr_team", 0), (call_script, "script_crpg_switch_player_team", ":max_score_plus_death_player_no", 0), (try_end), (try_end), #(str_store_player_username, s1, ":max_score_plus_death_player_no"), #(assign, reg15, ":new_level_0"), #(assign, reg16, ":new_level_1"), #(assign, reg17, ":curr_team"), #(server_add_message_to_log, "@autobalanceshuffle: player:{s1}, value:{reg12}, checkvalue:{reg8}, team:{reg9}[old:{reg17}], {reg15}:{reg16}"), (try_end), (try_begin), (eq, ":type", 1), #check if it's autobalance command (ge, ":max_score_plus_death_player_no", 0), (store_add, ":slot_index", ":max_score_plus_death_player_no", multi_data_player_index_list_begin), (troop_get_slot, ":value", "trp_multiplayer_data", ":slot_index"), (assign, reg2, ":value"), (str_store_player_username, s1, ":max_score_plus_death_player_no"), #(server_add_message_to_log, "@autobalance: player:{s1}, value:{reg2}"), (troop_set_slot, "trp_multiplayer_data", ":slot_index", 0), #removed from the loop pool (player_get_team_no, ":player_team", ":max_score_plus_death_player_no"), (try_begin), (eq, ":player_team", ":from_team"), (eq, ":player_team", 0), (val_add, ":level_team_1", ":value"), (val_sub, ":level_team_0", ":value"), (call_script, "script_crpg_switch_player_team", ":max_score_plus_death_player_no", 1), (else_try), (eq, ":player_team", ":from_team"), (eq, ":player_team", 1), (val_add, ":level_team_0", ":value"), (val_sub, ":level_team_1", ":value"), (call_script, "script_crpg_switch_player_team", ":max_score_plus_death_player_no", 0), (try_end), (try_end), (try_end), (try_begin), (eq, ":type", 0), (assign, "$ab_score_team_0", ":new_level_0"), (assign, "$ab_score_team_1", ":new_level_1"), (else_try), (assign, "$ab_score_team_0", ":level_team_0"), (assign, "$ab_score_team_1", ":level_team_1"), (try_end), (try_begin), (eq, ":type", -1), #make the teams even by number #disabled #first, check how many are different (store_sub, ":team_diff", ":player_team_0", ":player_team_1"), (val_abs, ":team_diff"), (ge, ":team_diff", 2), #let's see who to move now... (try_begin), (gt, ":player_team_0", ":player_team_1"), (assign, ":move_from", 0), (assign, ":move_to", 1), (store_div, ":average", ":level_team_0", ":player_team_0"), (else_try), (assign, ":move_from", 1), (assign, ":move_to", 0), (store_div, ":average", ":level_team_1", ":player_team_1"), (try_end), #how many? teamdiff/2 #get average from team with more players - done above (get_max_players, ":num_players"), (assign, ":move_total_value", 0), (try_for_range, ":unused", 0, ":team_diff"), #t_player1 (assign, ":move_player_no", -1), (assign, ":move_player_value", -1), (try_for_range, ":player_no", 0, ":num_players"), #t_player2 (player_is_active, ":player_no"), (player_get_team_no, ":team", ":player_no"), (eq, ":team", ":move_from"), #he's on the right team - check if his lvl is above average (call_script, "script_cf_crpg_autobalance_get_level", ":player_no"), (ge, reg0, ":average"), #he is above average - check if we have someone who is lower already (this_or_next|eq, ":move_player_no", -1), (gt, ":move_player_value", reg0), #the guy before has a higher value (assign, ":move_player_no", ":player_no"), (assign, ":move_player_value", reg0), (try_end), #now we should have one guy slightly above average -move him, and add his value (val_add, ":move_total_value", ":move_player_value"), (call_script, "script_crpg_switch_player_team", ":move_player_no", ":move_to"), (try_end), (val_div, ":team_diff", 2), (store_div, ":average", ":move_total_value", ":team_diff"), (try_for_range, ":unused", 0, ":team_diff"), #t_player1 (assign, ":move_player_no", -1), (assign, ":move_player_value", -1), (try_for_range, ":player_no", 0, ":num_players"), #t_player2 (player_is_active, ":player_no"), (player_get_team_no, ":team", ":player_no"), (eq, ":team", ":move_to"), #he's on the right team - check if his lvl is above average (call_script, "script_cf_crpg_autobalance_get_level", ":player_no"), (ge, reg0, ":average"), #he is above average - check if we have someone who is lower already (this_or_next|eq, ":move_player_no", -1), (gt, ":move_player_value", reg0), #the guy before has a higher value (assign, ":move_player_no", ":player_no"), (assign, ":move_player_value", reg0), (try_end), (try_begin), (eq, ":move_player_no", -1), #found no suitable match - take the highest player (try_for_range, ":player_no", 0, ":num_players"), #t_player2 (player_is_active, ":player_no"), (player_get_team_no, ":team", ":player_no"), (eq, ":team", ":move_to"), #he's on the right team - check if his lvl is above average (call_script, "script_cf_crpg_autobalance_get_level", ":player_no"), (this_or_next|eq, ":move_player_no", -1), (gt, reg0, ":move_player_value"), #the guy before has a higher value (assign, ":move_player_no", ":player_no"), (assign, ":move_player_value", reg0), (try_end), (try_end), #now we should have one guy slightly above average -move him, and add his value #(val_add, ":move_total_value", ":move_player_value"), (call_script, "script_crpg_switch_player_team", ":move_player_no", ":move_from"), (try_end), (try_end), #(assign, reg1, ":level_team_0"), #(assign, reg2, ":level_team_1"), #(server_add_message_to_log, "@end of autobalance: team1:{reg1}, team2:{reg2}"), (try_end), (eq, 0, 1), #break script ]), #script_cf_crpg_autobalance_get_level #Input: none #Output: none ("cf_crpg_autobalance_get_level", [ (store_script_param, ":player_no", 1), (try_begin), (store_add, ":troop_no", "trp_player0_multiplayer", ":player_no"), (troop_get_slot, ":level", ":troop_no", slot_troop_crpg_level), (gt, ":level", 0), (val_add, ":level", 5), #add 4 levels to everyone so every player counts higher (try_begin), (eq, "$g_multiplayer_game_type", multiplayer_game_type_rabbit), (val_add, ":level", 25), #in rabbit, people by itself count more (try_end), (player_get_score, ":kill_count", ":player_no"), (player_get_death_count, ":death_count", ":player_no"), #get_death_count (val_div, ":kill_count", 10), (val_sub, ":kill_count", ":death_count"), (val_mul, ":kill_count", 3), (store_mul, ":player_score_plus_death", ":level", 10), (val_add, ":player_score_plus_death", ":kill_count"), #(val_sub, ":player_score_plus_death", ":death_count"), #(val_mul, ":player_score_plus_death", ":player_score_plus_death"), (set_fixed_point_multiplier, 10000), #(val_mul, reg0, 10000), (troop_get_slot, ":kd", ":troop_no", slot_troop_crpg_kd_ratio), (val_div, ":kd", 100), (val_add, ":player_score_plus_death", ":kd"), (val_max, ":player_score_plus_death", 0), (assign, ":power", 1), (convert_to_fixed_point, ":player_score_plus_death"), (convert_to_fixed_point, ":power"), (val_mul, ":power", 11), (val_div, ":power", 10), (store_pow, ":tmp", ":player_score_plus_death", ":power"), (assign, ":player_score_plus_death", ":tmp"), (convert_from_fixed_point, ":player_score_plus_death"), (assign, reg0, ":player_score_plus_death"), (try_begin), (player_get_team_no, ":team", ":player_no"), (is_between, ":team", 0, 2), (team_get_score, ":this_team_score", ":team"), (store_sub, ":enemy_team", ":team", 1), (val_abs, ":enemy_team"), (team_get_score, ":enemy_team_score", ":team"), (val_sub, ":this_team_score", ":enemy_team_score"), (lt, ":this_team_score", 0), (val_mul, ":this_team_score", 30), (val_add, reg0, ":this_team_score"), (try_end), (else_try), (assign, reg0, 1), (try_end), ]), #script_crpg_switch_player_team #Input: none #Output: none ("crpg_switch_player_team", [ (store_script_param, ":player_no", 1), (store_script_param, ":team", 2), #(assign, reg1, ":player_no"), #(assign, reg2, ":team"), #(str_store_player_username, s1, reg1), #(server_add_message_to_log, "@autobalance: moving player:{s1} ({reg1}), team2:{reg2}"), (try_begin), #if player is living add +1 to his kill count because he will get -1 because of team change while living. (player_get_agent_id, ":latest_joined_agent_id", ":player_no"), (ge, ":latest_joined_agent_id", 0), (agent_is_alive, ":latest_joined_agent_id"), (player_get_kill_count, ":player_kill_count", ":player_no"), #adding 1 to his kill count, because he will lose 1 undeserved kill count for dying during team change (val_add, ":player_kill_count", 1), (player_set_kill_count, ":player_no", ":player_kill_count"), (player_get_death_count, ":player_death_count", ":player_no"), #subtracting 1 to his death count, because he will gain 1 undeserved death count for dying during team change (val_sub, ":player_death_count", 1), (player_set_death_count, ":player_no", ":player_death_count"), (player_get_score, ":player_score", ":player_no"), #adding 1 to his score count, because he will lose 1 undeserved score for dying during team change (val_add, ":player_score", 1), (player_set_score, ":player_no", ":player_score"), (get_max_players, ":num_players"), (try_for_range, ":player_send", 1, ":num_players"), #0 is server so starting from 1 (player_is_active, ":player_send"), (multiplayer_send_4_int_to_player, ":player_send", multiplayer_event_set_player_score_kill_death, ":player_no", ":player_score", ":player_kill_count", ":player_death_count"), (try_end), (try_end), (player_set_team_no, ":player_no", ":team"), #(multiplayer_send_message_to_player, ":player_no", multiplayer_event_force_start_team_selection), ]),

Title: Re: Proposed change to team-balance algorithim
Post by: Kafein on February 21, 2014, 11:21:40 am

Quote from: zagibu on February 21, 2014, 10:16:56 am

Here is the current team balance code, feel free to modify it directly:

I'd rather do real time cryptography in Clojure, thanks

Title: Re: Proposed change to team-balance algorithim
Post by: Sniger on February 21, 2014, 02:17:28 pm

24(!) screenshots uploaded

Title: Re: Proposed change to team-balance algorithim
Post by: Elindor on February 21, 2014, 04:28:24 pm

Quote from: Jona on February 21, 2014, 12:46:44 am

I was playing late-night (read: really early morning) battle last night, with only 5v5 or 6v6ish for a while. The balancer put the two top players on the same team after round 1. They each had more score than every player on the entire enemy team combined. The thing is, they weren't even in the same clan, so there was no reason they should be put together. The total score of the two teams after one round was about 16 points vs 60. Makes sense, right?

The thing is, this isn't a problem limited to low-pop servers. It is just far more noticeable and easier to point out the flaws in the system when you can count up the total scores of each team in a matter of seconds.

This is what I'm talking about Jona 100%.
If the server had just moved one of those players to the other team it would have almost completely balanced itself right there.
And in siege it does the same thing and siege can shift players freely every round! But it doesn't do it.

I'm really beginning to think that the balancer has almost no directive to balance overall scores/kdrs of players on each team...

-----

:arrow: I would love for someone (Tydeus, cmp, anyone) who has SOME knowledge of the actual mechanics of the balancer to chime in on one of these many many many topics about how badly the balancer performs and just give us a clue what is going on. Not a demand, but a request which I'm sure the community would be very happy about.

[EDIT] It appears Zagibu has already posted it.... Any chance someone can summarize it's priorities for us though? Paul? Tydeus? :) There is no way I'm gonna understand much of that 500 lines of script :)

...I've said it before and I'll say it again...
Whats wrong with cRPG? Its not this weapon vs this weapon, or this build vs this build ...its HOW BAD THE BALANCER IS.

Title: Re: Proposed change to team-balance algorithim
Post by: Vanthor on February 21, 2014, 04:53:39 pm

Quote from: zagibu on February 21, 2014, 10:16:56 am

Here is the current team balance code, feel free to modify it directly:

Thanks! I'll do exactly that.

Title: Re: Proposed change to team-balance algorithim
Post by: Tydeus on February 21, 2014, 05:46:42 pm

Elindor, I haven't taken an in depth look at how it works, I've only skimmed through it. I've seen it enough to know I don't want to have anything to do with it at the moment. :|

Title: Re: Proposed change to team-balance algorithim
Post by: Utrakil on February 21, 2014, 05:49:53 pm

Quote from: Vanthor on February 21, 2014, 04:53:39 pm

Thanks! I'll do exactly that.

Her comes a +1 for bravery!

Title: Re: Proposed change to team-balance algorithim
Post by: Sniger on February 21, 2014, 06:02:13 pm

vanthor not brave

vanthor is just like:
visitors can't see pics , please register or login

Title: Re: Proposed change to team-balance algorithim
Post by: Elindor on February 21, 2014, 06:52:43 pm

Quote from: Tydeus on February 21, 2014, 05:46:42 pm

Elindor, I haven't taken an in depth look at how it works, I've only skimmed through it. I've seen it enough to know I don't want to have anything to do with it at the moment. :|

Honestly, I cannot blame you. Let's tie a rope around Vanthor so if he tugs on it we can pull him back out...

God speed Vanthor.

Title: Re: Proposed change to team-balance algorithim
Post by: Sniger on February 21, 2014, 11:48:18 pm

since the screenshots ive provided is a little bit old i figured id hop on eu1 and spec for abit.

this is the very first map i spec'ed:

(click to show/hide)

ill keep spec and screen but will .zip the rest and upload

Title: Re: Proposed change to team-balance algorithim
Post by: Paul on February 22, 2014, 10:40:02 am

Afaik the team balance code is a creation of chadz himself and thus considered to be a holy piece of perfection. In other words noone cba to do get started with working on it.

Title: Re: Proposed change to team-balance algorithim
Post by: Sniger on February 22, 2014, 03:21:34 pm

Quote from: Paul on February 22, 2014, 10:40:02 am

Afaik the team balance code is a creation of chadz himself and thus considered to be a holy piece of perfection.

everything make sense now.

but well im sure its awesome code and i guess it works great for what it is! BUT........

:)

Title: Re: Proposed change to team-balance algorithim
Post by: Vanthor on February 24, 2014, 10:22:14 pm

So, this may explain why the auto balancer is awful. This is the power (energy) function it uses. Lets choose two example players Sir_TryHard_CarriesAlot and ArcherWith300Ping.

Its a 30 on 30. Sir_TryHard_CarriesAlot is on blue, and is an old school two-handed hero. He started the match of well, hitting the enemy murderball (massed infantry) like a tidal wave, killing 7 people while taking little damage. ArcherWith300Ping is a strength crutcher with a long bow. He hasn't had a good round so far, hasn't had a clear shot. So he says fuck it, and starts lobbing arrows into the melee at head height from a mile away.

Sir_TryHard_CarriesAlot is on a roll. He going to set a personal record this match. Sir_TryHard turns to fight the next enemy, and suddenly an arrow sprouts from his head. He goes down.

Lets take a look at how our two players did round 1.

P1 Sir_TryHard_CarriesAlot
Level: 30
Overall K/D from all matched: 10:1
Round 1 kills: 7 ( Had a bad round)
Round 1 Deaths: 1
Round 1 Points: 40
On Losing team(Re: Bad round)

P1 ArcherWith300Ping
Level: 31
Overall K/D from all matches: 1:4
Round 1 kills :0
Round 1 Deaths:0
Round 1 Points: 3
On winning team

Some boilerplate:

Player	Original Value	New Value
Sir_TryHard_CarriesAlot	636	100
ArcherWith300Ping	654	29.25

Team	\|	Rounds won	\|	Total Points	\|	New Balance	\|	Old Balance	\|	Old Balance w/o loss modifier
Match 1
Team1	\|	4	\|	852	\|	1307	\|	13,586.69	\|	13,586.69
Team2	\|	1	\|	467	\|	753	\|	11,883.68	\|	13,143.68
Match 2
Team1	\|	4	\|	933	\|	1556	\|	13,731.54	\|	13,731.54
Team2	\|	0	\|	483	\|	802	\|	11,263.54	\|	13,153.54
Match 3
Team1	\|	4	\|	959	\|	1088	\|	13,512.47	\|	13,512.47
Team2	\|	0	\|	951	\|	1048	\|	11,572.27	\|	13,462.27