Make MM map serving abide by gamblers falacy

[GoogleFrog]

The matchmaker map picker is too random for the human concept of randomness. Maps that a player has not played in a while should be more likely to come up for them. Short strings of maps should have fewer repeats than would be expected under pure randomness. Every player should never play the same map twice in a row (this is the easiest and most important part of this ticket).

---

When choosing what map to pick, the matchmaker should, as much as possible, avoid picking a map that any player has played last, possibly also taking into account second or third last, but the idea being to avoid repeats.

Ideally this would work in a cyclic way, where the MM cycles through every map before reshuffling the list and repeating (like how modern tetris chooses blocks) but that's probably too much for a system where separate players will have played a different set of maps prior to the current MM game.

An approach that comes to mind is to store the last to nth last maps played, then try to find a map from the set that excludes maps from last played to nth last played; if that set is empty, try again excluding last to n-1th last, and so on until a non-empty set comes up.

---

Checklist:

• [ ] map can't appear twice in a row
• [ ] maps not played for a long time made more likely
• [ ] a general solution that works for teams as well

[dvr333]

2555 contains a more complete description of the issue, for reference.

[sprunk]

Copied stuff from the other tickets into first post and added a checklist.

[dvr333]

A somewhat clunky way that comes to mind is (assuming player class has a List of maps):

List<Map> NonRepeatMapList(List<Player> players, List<Map> baseMaps, int startingNumOfLastMaps)
{
  List<Map> finalMaps = null;
  int count = startingNumOfLastMaps;
  do
  {
    finalMaps = new List<Map>(baseMaps);
    foreach(Player player in players)
    {
      finalMaps = finalMaps.Subtract(player.LastPlayedMaps.Pick(count)).ToList();
      if (finalMaps.Count == 0)
        break;
    }
    --count;
  } while (finalMaps.Count == 0)
  return finalMaps;
}

So long as every player's LastPlayedMaps field has the currently played map inserted at the start (or added to the end with "Pick" changed to "Skip" and count starting at 0 and going up) it should ensure no one involved in a game has to play the same map twice in a row, unless every one in the group has played every map in totally different orders.

[sprunk]

How about a weighted average?

Map PickMapForPlayerSet(List <Player> players, List<Map> mapPool)
{
  using Weight = long;
  Random rng = new Random();

  Weight total = 0.0;
  var weights = new Dictionary<Map, Weight>();
  for (Map map in mapPool) {
    Weight w = 1;
    for (Player player in players) {
      // 0 for previously played map, effectively banning it
      // more weight the longer since the map was played on
      w *= player.GamesSinceLastPlayedOn(map);
    }
    total += w;
    weights[map] = w;
  }

  if (total == 0) {
    TraceLog("mapfeature more plz");
    return mapPool[rng.Next(mapPool.Count)];
  }

  var rand = rng.Next(0, total);
  for (var weight in weights) {
    rand -= weight.Value;
    if (rand < 0) {
      return weight.Key;
    }
  }

  TraceLog("weighted average failed?");
  return mapPool[0]; // or better "return speedmetal" to bring attention to the problem
}

[dvr333]

I guess? It seems a fair bit more complicated, though maybe more efficient as it isn't doing O(n^2) list subtract operations. Probably could be more easily adjusted than my algorithm to make sure that in the case where every player in the game has a different last played map, such that someone has to get a repeat, that the repeated map happens only for the map most recently played by the fewest players (i.e if there a 6 players and 5 maps, but both p1 and p2 last played map a, while p3 through p6 each last played maps b through e, only maps b through e will be up to be picked. My algorithm wouldn't weight against map a in this case).

If the GamesSinceLastPlayedOn() function has a list of previously played maps backing it, we could also have a way to get the number of times a given map shows up in the list, probably divided by count. So if someone has a list of a, c, b, e, b, f, b, c and we are looking at b, instead of multiplying w by 2 for the position, it would divide that position factor by the number of times the map shows up, multiplying by 2/3 instead. That way it's less likely to keep getting the same map every second or third game.

[Legomenon-gh]

Is this feature still desired? The introduction of map bans has made this behavior both worse and easier to control, so it probably would be nice to prevent map repeats.

Map bans have narrowed the map pool quite a bit since they're distributed relatively evenly across the entire map set, so repeats are more common now (this should be addressed on the map ban side, too). On the other hand, players can now modify their bans to ban the last map or two they've played on, but that's tedious to do manually.