You'll have to write a mutator that performs
the balancing, both at the start of the game as
players are swapped, and during the game as
players come and go, and evening out the
remaining imbalance. This mutator needs to be
able to find out the weighting of any player
taking part, for the current game type and
mutator set.
Devise a simple protocol so the mutator can
talk over TCP to a server that has access to the
weightings. (We had trouble getting our mutator
to reread a local file after it had been
updated, so we opted for a network interaction.)
Because we only had a handful of players (maybe
20 at most), our protocol was a single
interaction. After connection, the mutator sent
one line to identify the game type, one line for
each mutator, and a terminating line. The server
then looked up the weightings for that game, and
sent them all in response. If you are writing for
a public server, you should probably support a
few distinct commands:

GAME gameType — A
new game has started, and this is its type.
The server should not respond.

MUTATOR mutatorName
— The specified mutator is active in the
game. The balancer should send all mutators,
and let the server decide which affect
gameplay and which do not. The server should
not respond.

PLAYER playerId —
Ask the server for the weight of the
identified player. Use the strong identities
if they are available to the mutator. The
server should respond with a single line of
the form PLAYER playerId
decimalWeight, or with
PLAYER playerId if
the server has no information about the
player.

BOT botName — Ask
the server for the weight of the identified
bot. The server should respond with a single
line of the form BOT botName
decimalWeight.

MEANBOT — Ask the server for
the average weight of all bots. The server
should respond with a single line of the form
MEANBOT decimalWeight
botCount.
If there are no weightings for a given player,
the mutator will have to use a configured
default. Normalizing the weightings between (say)
0 and 100 ensures that the default always has the
same meaning.
Here's the pseudocode for the balancer.
Documentation on UnrealScript seems hard to find, so
I've made some assumptions about the environment.
For example, Game
is taken to hold
all details of the current game, and the mutator
is told when a new game is created, and when play
actually starts. I assume that all players,
manual and automatic (bots), have a distinct
number during the game, but the mutator also uses
its own index, only for real players. I assume
that each bot has a name, while a player has an
id.
config int minPlayers = 6;
config real defaultWeighting = 50;
int levelRecMin;
int levelRecMax;
Game game;
real meanBotWeight;
// By 'pawn', I mean real player or bot. This array is
// indexed by the game's own bot/player number, which I'm
// calling a 'pawn' number. If there is no such number,
// this needs a rethink.
real pawnWeight[32];
// This is a list of real players who have been assigned a team
// based on our decisions. New players are added at the end. A
// player is removed by replacing it with the player at the end.
// It is essential that there are no gaps in the array, so this is
// indexed by the mutator's own internal numbering, which excludes
// bots.
int playerNumber[32];
int placedPlayers = 0;
// Place a player (specified by pawn number) into our array. If
// it's already there, return false. Update the player's weight
// in either case.
function bool placePlayer(int num, real weight) {
pawnWeight[num] = weight;
for (int index = 0; index < placedPlayers; index++) {
if (playerNumber[index] != num) continue;
return false;
}
playerNumber[placedPlayers] = num;
placedPlayers++;
return true;
}
function void removePlayer(int num) {
for (int index = 0; index < placedPlayers; index++) {
if (playerNumber[index] != num) continue;
placedPlayers;
playerNumber[index] = playerNumber[placedPlayers];
}
}
event newGame(Game game) {
this.game = game;
// No players are placed yet.
placedPlayers = 0;
// Get ideal player range for this level.
parseRange(game.level.recommendedPlayers,
levelRecMin, levelRecMax);
send game type to server;
send list of mutators to server;
request mean bot weight from server;
}
event newManualPlayer(int num) {
PlayerId id = game.players[num];
request weight of player id from server;
}
event newAutomaticPlayer(int num) {
string name = game.players[num].name;
request weight of bot called 'name' from server;
}
event manualPlayerRemoved(int num) {
removePlayer(num);
updateBots();
updateBalancer();
}
event automaticPlayerRemoved() {
updateBots(); // Should be a noop, so it won't loop.
updateBalancer();
}
function void updateBots() {
if (game.type.isTeamGame()) {
int teamSize[] = { 0, 0 };
for (int i = 0; i < placedPlayers; i++)
teamSize[player[playerNumber[i]].team]++;
largestTeamSize = max(teamSize[0..3]);
teamCount = 2;
} else {
// Every player is on his own team.
largestTeamSize = 1;
teamCount = game.playerCount;
}
int clamped = clamp(minPlayers, leveRecMin, levelRecMax);
clamped = roundUp(clamped, teamCount);
game.setMinPlayers(max(clamped, largestTeamSize * teamCount));
}
// This deals with late changes and the unpredictability of bot
// weights, by working out the relative weights of all team
// players, including bots, and delegating the action to take,
// e.g. varying firing rates, altering initial health.
function void updateBalancer() {
real teamWeight[4] = { 0, ... };
for (Pawn p : game.pawns)
teamWeight[p.teamNumber] += pawnWeight[p.num];
// This is a black box, and needs further thought.
game.applyBalance(teamWeight);
}
event newMeanBotWeight(real weight) {
meanBotWeight = weight;
updateBalancer();
}
event newManualWeight(PlayerId id, real weight) {
if (weight < 0)
weight = defaultWeighting;
int num = findPlayer(id);
if (num < 0) return;
if (placePlayer(num, weight)) {
if (game.hasStarted()) {
choose a side for #num;
move #num to that side;
updateBots();
}
} else if (game.hasStarted()) {
updateBalancer();
}
}
event newAutomaticWeight(string name, real weight) {
if (weight < 0)
weight = meanBotWeight;
int num = findBot(name);
pawnWeight[num] = weight;
if (game.hasStarted())
updateBalancer();
}
function int roundUp(int input, int period) {
return (input + period  1) / period * period;
}
real bestRat[5];
uint32_t bestComb[5];
function void resetCombinations() {
for (int i = 0; i < 5; i++) {
bestRat[i] = 0;
bestComb[i] = 0;
}
}
function void recordCombination(uint32_t comb, real ratio) {
// Keep track of the best 5 ratios and the
// combinations that generated them.
for (int i = 0; i < 5; i++) {
if (ratio < bestRat[i]) continue;
for (int j = i + 1; j < 5; j++) {
bestRat[j] = bestRat[j  1];
bestComb[j] = bestComb[j  1];
}
bestRat[i] = ratio;
bestComb[i] = comb;
break;
}
}
event gameStarts() {
if (!game.type.isTeamGame()) {
updateBots();
break;
}
// Create a cache of player weights.
real weight[placedPlayers] = { 0... };
for (int p = 0; p < placedPlayers; p++)
weight[p] = pawnWeight[playerNumber[p]];
// The bitshifting and masking only works with 2 teams.
const int teamCount = 2;
// Go through all combinations of placed players, looking
// for the best 5 combinations.
if (placedPlayers > 20) {
// An alternative algorithm might be better when
// the number of players is high.
} else {
const int limit = teamCount ** (placedPlayers  1);
for (uint32_t comb = 0; comb < limit; comb++) {
// The weight of each team
real sum[teamCount] = { 0, 0 };
// The number of manual players in each time
int count[teamCount] = { 0, 0 };
// Work out the weight of manual players in each team.
for (int p = 0; p < placedPlayers; p++) {
int team = (comb >> p) & 1;
sum[team] += weight[p];
count[team]++;
}
// Add in the weight of any extra bots, assuming the
// mean bot weight.
int maxTeam = max(count);
int clamped = clamp(minPlayers, leveRecMin, levelRecMax);
clamped = roundUp(clamped, teamCount);
int size =
max(clamped, largestTeamSize * teamCount) / teamCount;
for (int i = 0; i < teamCount; i++)
sum[i] += meanBotWeight * (size  count[i]);
// Work out how balanced this combination is.
real ratio = min(sum) / max(sum);
recordCombination(comb, ratio);
}
}
// Pick one of the best combinations, and
// move players into the correct teams.
int i = random(0, 4); // inclusive
uint32_t comb = bestComb[i];
for (int p = 0; p < placedPlayers; p++)
game.pawn[playerNumber[p]] = (comb >> p) & 1;
updateBots();
updateBalancer();
}
Here's a complete C program for inspiration.
You need to give it a text file containing one
line per player, giving the player's weighting
followed by his name.
#include <stdio.h>
#include <inttypes.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <stdbool.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
typedef uint_least32_t comb_t;
#define COMB_C(V) UINT32_C(V)
struct cand {
double ratio;
comb_t comb;
};
static void reset_cands(struct cand *cands, size_t lim)
{
for (size_t i = 0; i < lim; i++)
cands[i].ratio = 0.0;
}
static void merge_cand(struct cand *cands, size_t lim,
comb_t comb, double ratio)
{
for (size_t i = 0; i < lim; i++) {
if (ratio < cands[i].ratio) continue;
for (size_t j = lim  1; j > i; j)
cands[j] = cands[j  1];
cands[i].ratio = ratio;
cands[i].comb = comb;
return;
}
}
static const struct cand *select_cand(struct cand *cands, size_t lim)
{
double power = 1.0;
double sum = 0.0;
for (size_t i = 0; i < lim; i++)
sum += pow(cands[i].ratio, power);
for (size_t i = 0; i < lim; i++) {
double val = pow(cands[i].ratio, power);
#if 0
printf("Option %zu: %g = %g%% %08" PRIxLEAST32 "\n",
i + 1, val, 100.0 * val / sum, cands[i].comb);
#endif
}
double chosen = rand() / (double) RAND_MAX * sum;
#if 0
printf("Chosen %g/%g\n", chosen, sum);
#endif
for (size_t i = 0; i < lim; i++) {
chosen = pow(cands[i].ratio, power);
if (chosen < 0.0)
return &cands[i];
}
assert(false);
}
static size_t max(const size_t *ptr, size_t len)
{
size_t val = ptr[0];
for (size_t i = 1; i < len; i++)
if (ptr[i] > val) val = ptr[i];
return val;
}
static size_t max2(size_t a, size_t b)
{
return a > b ? a : b;
}
static size_t min2(size_t a, size_t b)
{
return a < b ? a : b;
}
static size_t min(const size_t *ptr, size_t len)
{
size_t val = ptr[0];
for (size_t i = 1; i < len; i++)
if (ptr[i] < val) val = ptr[i];
return val;
}
static double maxd(const double *ptr, size_t len)
{
double val = ptr[0];
for (size_t i = 1; i < len; i++)
if (ptr[i] > val) val = ptr[i];
return val;
}
static double mind(const double *ptr, size_t len)
{
double val = ptr[0];
for (size_t i = 1; i < len; i++)
if (ptr[i] < val) val = ptr[i];
return val;
}
static size_t clamp(size_t input, size_t min, size_t max)
{
if (input < min) return min;
if (input > max) return max;
return input;
}
static size_t roundUp(size_t input, size_t factor)
{
return (input + factor  1) / factor * factor;
}
struct player {
char name[32];
double weight;
};
static int dblcmp(const void *av, const void *bv)
{
const struct player *a = av;
const struct player *b = bv;
if (a>weight > b>weight) return +1;
if (a>weight < b>weight) return 1;
return 0;
}
int main(int argc, const char *const *argv)
{
const size_t teams = 2;
double meanBotWeight = 20.0;
size_t targetPlayers = 8;
size_t minRecPlayers = 6;
size_t maxRecPlayers = 12;
for (int argi = 1; argi < argc; argi++) {
if (!strcmp(argv[argi], "min")) {
minRecPlayers = atoi(argv[++argi]);
} else if (!strcmp(argv[argi], "max")) {
maxRecPlayers = atoi(argv[++argi]);
} else if (!strcmp(argv[argi], "target")) {
targetPlayers = atoi(argv[++argi]);
} else if (!strcmp(argv[argi], "bot")) {
meanBotWeight = atof(argv[++argi]);
} else {
fprintf(stderr, "%s: Unknown argument: %s\n", argv[0], argv[argi]);
exit(EXIT_FAILURE);
}
}
/* Load in player weightings from standard input. */
struct player weightings[32];
size_t players = 0;
char line[100];
while (players < sizeof weightings / sizeof weightings[0] &&
fgets(line, sizeof line, stdin)) {
line[strlen(line)  1] = '\0';
char *end;
weightings[players].weight = strtod(line, &end);
while (*end && isspace(*end))
end++;
strncpy(weightings[players].name, end, sizeof weightings[players].name);
weightings[players].name[sizeof weightings[players].name] = '\0';
players++;
}
srand(time(NULL));
/* Try all combinations and record the best few. */
struct cand cands[20];
reset_cands(cands, sizeof cands / sizeof cands[0]);
comb_t lim, preset;
const size_t player_threshold = 16;
if (players > player_threshold) {
/* Fix the positions of the top N players. First, sort the
players by increasing weight. */
qsort(weightings, players, sizeof weightings[0], dblcmp);
preset = 0x99999999u >> (32  players);
preset &= 1 << player_threshold;
lim = COMB_C(1) << player_threshold;
} else {
/* Just go through every possible combination. */
lim = COMB_C(1) << (players  1);
preset = 0;
}
printf("Range %08" PRIxLEAST32 "%08" PRIxLEAST32
" preset %08" PRIxLEAST32 "\n", (comb_t) 0, lim  1u, preset);
for (comb_t index = 0; index < lim; index++) {
comb_t comb = index  preset;
/* Prepare to weigh up the teams for this combination. */
double score[teams];
size_t count[teams];
for (size_t i = 0; i < teams; i++) {
score[i] = 0.0;
count[i] = 0;
}
/* Add the weights of each player on each team. */
bool exceeded = false;
size_t excess = min2(32 / teams, 18 * players / 32);
for (size_t p = 0; p < players; p++) {
size_t team = (comb >> p) & 1u;
score[team] += weightings[p].weight;
count[team]++;
if (count[team] > excess) {
exceeded = true;
break;
}
}
if (exceeded) continue;
/* Add the weights of bots on each team. */
const size_t largestTeamSize = max(count, teams);
const size_t minPlayers =
max2(roundUp(clamp(targetPlayers,
minRecPlayers,
maxRecPlayers), teams),
largestTeamSize * teams);
assert(minPlayers % teams == 0);
const size_t playersPerTeam = minPlayers / teams;
for (size_t t = 0; t < teams; t++)
score[t] += meanBotWeight * (playersPerTeam  count[t]);
/* Work out the quality of this combination, and record it. */
double ratio = mind(score, teams) / maxd(score, teams);
merge_cand(cands, sizeof cands / sizeof cands[0], comb, ratio);
#if 0
for (size_t t = 0; t < teams; t++)
printf("%zu ", count[t]);
printf("= %g\n", ratio);
#endif
}
/* Choose from the best combinations, and apply it. */
const struct cand *chosen =
select_cand(cands, sizeof cands / sizeof cands[0]);
size_t team_list[teams][players];
size_t team_count[teams];
size_t playersPerTeam;
{
for (size_t t = 0; t < teams; t++)
team_count[t] = 0;
for (size_t p = 0; p < players; p++) {
size_t team = (chosen>comb >> p) & 1u;
team_list[team][team_count[team]] = p;
team_count[team]++;
}
const size_t largestTeamSize = max(team_count, teams);
const size_t minPlayers =
max2(roundUp(clamp(targetPlayers,
minRecPlayers,
maxRecPlayers), teams),
largestTeamSize * teams);
assert(minPlayers % teams == 0);
playersPerTeam = minPlayers / teams;
}
printf("%zu players across %zu teams:\n", players, teams);
printf("\tMap for %zu%zu players (target %zu)\n",
minRecPlayers, maxRecPlayers, targetPlayers);
for (size_t t = 0; t < teams; t++) {
size_t bot_count = playersPerTeam  team_count[t];
printf("\nTeam %zu: (%zu players + %zu bots)\n",
t + 1, team_count[t], bot_count);
double sum = 0.0;
for (size_t i = 0; i < team_count[t]; i++) {
struct player *player = &weightings[team_list[t][i]];
double weight = player>weight;
sum += weight;
printf("\t%3g %s\n", weight, player>name);
}
double bot_weight = bot_count * meanBotWeight;
printf("\t+ %zu * %g = %g\n", bot_count,
meanBotWeight, bot_weight);
sum += bot_weight;
printf("\t=%g\n", sum);
}
return EXIT_SUCCESS;
}
Here's an example input file:
5 Boring John
3 Silly Billy
2 Slartibartfast
7 Chewbacca
23 Ignoramus
92 Riddick
93 Luke Skywalker
95 Darth Vader
27 Peter Griffin
56 Roger
28 Annoying Git
99 Cheat
1 Lame
23 Twonk
83 Foogilicious
41 Flunk Basket
49 Jack O'Neill