Balancing tools for Unreal Tournament

Adjust bots automatically


This is supposed to be some mutators and other software to help balance team games in UT2004, though there's only one mutator at the moment. The rest of the page is just an opportunity to describe a balancing system I helped to implement for CUT, and which might still be applicable to UT2004, and might inspire someone else to try it.

Ideal Bot Counter

Firstly, the mutator JoolsWorks.IdealBotCounter does a very simple job of automating the number of bots in a game, as you switch between maps with various ideal numbers of players. To install, unzip the joolsworks-bin file into the System folder of your server, and engage the Ideal Bot Count mutator.

You might want to set your preferred MinPlayers value in this mutator's configuration:


The job of the mutator is to watch the number of human players taking part in a game, and adjust the game's own MinPlayers so that there are enough bots to balance both teams, but no more than necessary. First, it takes its own MinPlayers setting, and clamps it within the map's ideal range, then it ensures that the number is at least the number of teams times the number of humans on the largest team.

As a result, you get the minimum number of bots to balance the teams, changing as a modest number of human players travels across maps of diverse sizes.

On non-team games, the mutator simply clamps the number of players to the map's ideal range.

Team balancing

Here's the plan to provide full team balancing. Note that something like this has already been implemented for CUT, but I don't think I've still got the code. Nevertheless, read on, and some keen programmer with time on his hands might have a go.

Computing player weights

Ideally, you need a system of weights for different players. Also keep weights for each bot, and their average. You might be able to get them off a website showing game statistics, but we built our own using the log files of each game. You need to be able to update them after each game so that new players' skills are quickly determined, but they also have to be fairly stable, or the variability will just annoy players.

In CUT, we only had players' names for identity, which meant that someone could discard their weighting, if they thought they were ranked too high, just by changing their name. In UT2004, identities might be stronger, more expensive to renew, and I hope that mutator code has access to them. If strong identities are available (e.g., as hashes of the key codes; see GetPlayerIDHash in PlayerController?), use them as the primary identifier of a player, but also keep the last name they appeared under, so you can generate statistics pages too.

In CUT, you could set your game server to run an external program to process the log of the last game. We tried using events like kills to determine a player's skill, but number of kills is not directly relevant to certain game types, like Capture The Flag. For that, we settled on simple presence on a team as it scores. Your log processor should adapt to the game type, and choose an appropriate method of evaluating skill. It should also consider the effects of various mutators, such as InstaGib or low gravity, and keep separate sets of weightings per game type per mutator set. Even if you only run one game type on a public server where you intend to deploy your balancer, keeping so many different sets of weightings might help if you publish your code for others, whose servers allow players to choose different configurations as well as different maps.

Consider only mutators that affect the gameplay — you don't want the addition of (say) an anti-cheating mutator to invalidate all the old weightings.

Accumulate weightings from the logs of the last 30 or so games, giving more significance to the more recent ones. Keep those logs around so you can rebuild those weightings from scratch if something goes wrong, or you adjust the algorithms. Make your log processor work almost idempotently, so that you can give it either a single log from a just-finished game (plus current weightings), or the last 30 logs, and it will still yield similar weightings.

Our log processors were written in Java, and ran sufficiently fast to update the weightings before the next game.

Choosing teams at the start of a game

You need to be able to choose team composition just as a game is starting. We tried putting players on a team as they joined during the pause at the start, but you can get better teams if you wait until the game is just about to start, and swap everyone as necessary. (This is a bit disturbing for the players, though.) As you determine teams, you might consider one team having more humans than the other, and bots make up the numbers. Since you don't know which bots will take part, use the average bot weight mentioned earlier.

To choose team composition, you need to consider 2N combinations. Give each player an index from 0 to N−1, and count from 0 to 2N−1. For each value, each bit corrsponds to a player, 0 meaning Red, and 1 meaning Blue. (For games that support more than two teams, you just need to work in a different base than two.) Note that half of these combinations are identical to the other half, but with the teams totally swapped. No need to go through them twice, just go from 0 to 2N−1−1.

For each combination, work out the total weights for each team, and then a level of balance by dividing the smaller sum by the larger. Keep the best ones (closest to one), and choose one when you've gone through them all. You might choose the very best every time, or choose randomly, with those being closer to one having the greater probabilities.

Late changes

Don't recompose teams during the game as players join and leave — that's extremely annoying. To deal with late arrivals and departures, you can do two things. First, add the new player to a team such that the balance is better. To do this, you must consider not just the new player's weight and the teams' weights, but also the fact that adding the player might cause a bot to be removed, or one to be added. You don't know which one will be removed, so use the average of those present on that team. You don't know which one will be added, so use the over-all average of bots, possibly adjusted to account for those already present.

Furthermore, keep track of both teams' total weights (using specific bot weights, not averages), and find out what advantage one team has over the other. If it's possible, you should try to give the weaker team a little advantage, or make it harder for the stronger team. Adjusting the strength of weapons or shields is quite universal across game types, but not very effective with InstaGib. Increasing respawn time is also universal, but depends on members of the stronger team being fragged. Adjusting running speed might simply not be effective. Nevertheless, see if you can think of something, and implement it.

I would ask that game developers put hooks into their game types so that a third party can arbitrarily specify balancing for a running game. The third party would simply say Give Red a 1.1 advantage over Blue, and the game type would decide how to do that.

Getting the data into the game server

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 re-read 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 pseudo-code 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;
  return true;

function void removePlayer(int num) {
  for (int index = 0; index < placedPlayers; index++) {
    if (playerNumber[index] != num) continue;
    playerNumber[index] = playerNumber[placedPlayers];

event newGame(Game game) { = game;

  // No players are placed yet.
  placedPlayers = 0;

  // Get ideal player range for this level.
             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) {

event automaticPlayerRemoved() {
  updateBots(); // Should be a no-op, so it won't loop.

function void updateBots() {
  if (game.type.isTeamGame()) {
    int teamSize[] = { 0, 0 };
    for (int i = 0; i < placedPlayers; i++)
    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.

event newMeanBotWeight(real weight) {
  meanBotWeight = weight;

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;
  } else if (game.hasStarted()) {

event newAutomaticWeight(string name, real weight) {
  if (weight < 0)
    weight = meanBotWeight;
  int num = findBot(name);
  pawnWeight[num] = weight;

  if (game.hasStarted())

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;

event gameStarts() {
  if (!game.type.isTeamGame()) {

  // Create a cache of player weights.
  real weight[placedPlayers] = { 0... };
  for (int p = 0; p < placedPlayers; p++)
    weight[p] = pawnWeight[playerNumber[p]];

  // The bit-shifting 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];
      // 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;


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;

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);
  double chosen = rand() / (double) RAND_MAX * sum;
#if 0
  printf("Chosen %g/%g\n", chosen, sum);
  for (size_t i = 0; i < lim; i++) {
    chosen -= pow(cands[i].ratio, power);
    if (chosen < 0.0)
      return &cands[i];

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]);

  /* 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))
    strncpy(weightings[players].name, end, sizeof weightings[players].name);
    weightings[players].name[sizeof weightings[players].name] = '\0';


  /* 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;
      if (count[team] > excess) {
        exceeded = true;
    if (exceeded) continue;

    /* Add the weights of bots on each team. */
    const size_t largestTeamSize = max(count, teams);
    const size_t minPlayers =
                         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);

  /* 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;

    const size_t largestTeamSize = max(team_count, teams);
    const size_t minPlayers =
                         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


We didn't really keep our numbers up high enough to really test the balancing system once it was up. Our best players tended to be annoyed at such high weightings that they ended up on teams by themselves sometimes, with no hope of winning alongside useless bots. We needed a balancer much more than a public server, with so few players, and eventually the gaming petered out as people moved on and their availability diminished.

However, the balancer did do its job, and could be seen to be trying its best. We also got some pretty graphs of our performance over time.


File Size Last modified Description Requirements and recommendations
5KiB 2010-06-26 Bot balancer
3¼KiB 2010-06-26 Bot-balancer source