Author Topic: Proposed change to team-balance algorithim  (Read 7955 times)

0 Members and 1 Guest are viewing this topic.

Offline Vanthor

  • Knight
  • ***
  • Renown: 62
  • Infamy: 3
  • cRPG Player
    • View Profile
  • Faction: Literally
  • Game nicks: Literally_Vanthor,Literally_Locke
Proposed change to team-balance algorithim
« on: February 20, 2014, 07:49:25 pm »
+25
    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.
(click to show/hide)


And here's the algorithm as directly lifted from wikipedia, because its probably implemented right.
(click to show/hide)

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/. 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]
« Last Edit: February 20, 2014, 08:50:38 pm by Vanthor »

Offline Vanthor

  • Knight
  • ***
  • Renown: 62
  • Infamy: 3
  • cRPG Player
    • View Profile
  • Faction: Literally
  • Game nicks: Literally_Vanthor,Literally_Locke
Re: Proposed change to team-balance algorithim
« Reply #1 on: February 20, 2014, 07:50:28 pm »
+1
Class/build
(click to show/hide)

Offline Sniger

  • Marshall
  • ********
  • Renown: 795
  • Infamy: 442
  • cRPG Player
    • View Profile
Re: Proposed change to team-balance algorithim
« Reply #2 on: February 20, 2014, 07:53:39 pm »
+1
hardcore.

will prep a .zip for ya

Offline Kafein

  • King
  • **********
  • Renown: 2203
  • Infamy: 808
  • cRPG Player Sir White Rook A Gentleman and a Scholar
    • View Profile
Re: Proposed change to team-balance algorithim
« Reply #3 on: February 20, 2014, 08:11:57 pm »
-3
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.

Offline Vanthor

  • Knight
  • ***
  • Renown: 62
  • Infamy: 3
  • cRPG Player
    • View Profile
  • Faction: Literally
  • Game nicks: Literally_Vanthor,Literally_Locke
Re: Proposed change to team-balance algorithim
« Reply #4 on: February 20, 2014, 08:32:27 pm »
+4
Thanks for the input Kafein, I'll see what I can do to re-arrange it so the energy function piece more prominent / succinct.
« Last Edit: February 20, 2014, 08:39:54 pm by Vanthor »

Offline Sniger

  • Marshall
  • ********
  • Renown: 795
  • Infamy: 442
  • cRPG Player
    • View Profile
Re: Proposed change to team-balance algorithim
« Reply #5 on: February 20, 2014, 08:33:14 pm »
+2
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:

Offline Elindor

  • King
  • **********
  • Renown: 1178
  • Infamy: 158
  • cRPG Player A Gentleman and a Scholar
  • Caelitus mihi vires
    • View Profile
  • Faction: Order of the Holy Guard
  • Game nicks: Elindor
Re: Proposed change to team-balance algorithim
« Reply #6 on: February 20, 2014, 08:50:05 pm »
+4
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.
« Last Edit: February 20, 2014, 08:54:11 pm by Elindor »
Elindor, Archon of the Holy Guard
Holy Guard Thread :HERE
Banner Shop : HERE // Map Thread : HERE

Offline Vanthor

  • Knight
  • ***
  • Renown: 62
  • Infamy: 3
  • cRPG Player
    • View Profile
  • Faction: Literally
  • Game nicks: Literally_Vanthor,Literally_Locke
Re: Proposed change to team-balance algorithim
« Reply #7 on: February 20, 2014, 08:58:38 pm »
+2

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

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.

Offline Jona

  • Balancer
  • *
  • Renown: 1372
  • Infamy: 376
  • cRPG Player Sir Black Bishop
  • OG Agi Whore
    • View Profile
  • Faction: Hounds of Chulainn
  • Game nicks: Jona, Siegafried
Re: Proposed change to team-balance algorithim
« Reply #8 on: February 21, 2014, 12:46:44 am »
+6
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.
visitors can't see pics , please register or login


"I'll have my lance aimed at Jona's knees and he'll jump up, run up my lance and kill me." -Dalfador

Offline korppis

  • Earl
  • ******
  • Renown: 404
  • Infamy: 51
  • cRPG Player Sir White Knight A Gentleman and a Scholar
    • View Profile
  • Faction: Ninja
Re: Proposed change to team-balance algorithim
« Reply #9 on: February 21, 2014, 08:48:42 am »
+1
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.

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.

Offline zagibu

  • cRPG President
  • King
  • **********
  • Renown: 1436
  • Infamy: 228
  • cRPG Player A Gentleman and a Scholar
    • View Profile
Re: Proposed change to team-balance algorithim
« Reply #10 on: February 21, 2014, 10:16:56 am »
+6
Here is the current team balance code, feel free to modify it directly:

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),
]),
visitors can't see pics , please register or login
 Why am I beswung by sharpe and pointed utensyls?

Offline Kafein

  • King
  • **********
  • Renown: 2203
  • Infamy: 808
  • cRPG Player Sir White Rook A Gentleman and a Scholar
    • View Profile
Re: Proposed change to team-balance algorithim
« Reply #11 on: February 21, 2014, 11:21:40 am »
+2
Here is the current team balance code, feel free to modify it directly:

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

Offline Sniger

  • Marshall
  • ********
  • Renown: 795
  • Infamy: 442
  • cRPG Player
    • View Profile
Re: Proposed change to team-balance algorithim
« Reply #12 on: February 21, 2014, 02:17:28 pm »
+1
24(!) screenshots uploaded

Offline Elindor

  • King
  • **********
  • Renown: 1178
  • Infamy: 158
  • cRPG Player A Gentleman and a Scholar
  • Caelitus mihi vires
    • View Profile
  • Faction: Order of the Holy Guard
  • Game nicks: Elindor
Re: Proposed change to team-balance algorithim
« Reply #13 on: February 21, 2014, 04:28:24 pm »
+1
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.
« Last Edit: February 21, 2014, 05:24:29 pm by Elindor »
Elindor, Archon of the Holy Guard
Holy Guard Thread :HERE
Banner Shop : HERE // Map Thread : HERE

Offline Vanthor

  • Knight
  • ***
  • Renown: 62
  • Infamy: 3
  • cRPG Player
    • View Profile
  • Faction: Literally
  • Game nicks: Literally_Vanthor,Literally_Locke
Re: Proposed change to team-balance algorithim
« Reply #14 on: February 21, 2014, 04:53:39 pm »
+7
Here is the current team balance code, feel free to modify it directly:


Thanks! I'll do exactly that.