Арпад Эло

Днем физик, ночью шахматист

Нет, Арпад Эло не придумал матчмейкинг. Он придумал рейтинговую систему. Да и вообще, его больше шахматы занимали, хотя везде и пишут, что он физик. Вот, кстати, его формула расчета мат. ожидания исхода партии:

$E_{A} = \frac{1}{1 + 10^{(R_{B} - R_{A})/400}}$

Из неё следует, что при разрыве в четрыреста пунктов рейтинга, шанс у андердога примерно один к десяти. А если увеличивать разрыв, то уже на шестистах пунктах - шансов примерно нет. Ну… это если оба трезвые.

Несколько занимательных историй из детства

История первая

Из того, что я помню, в первый раз с подбором игроков я столкнулся в начальной школе. Учитель физкультуры, которого все называли просто по отчеству — Борисыч, вывел нас на улицу и объявил, что мы будем играть в пионербол. Он поделил нас на две группы — пацанов и девчонок. Так как площадка с сеткой была одна, сначала играли пацаны, а девчонки прыгали на скакалках. Затем наоборот. А когда мы вышли на площадку, Борисыч выбрал двух самых высоких из нас и назначил капитанами, которые будут набирать себе команды. Я не был самым высоким.

Когда капитаны стали набирать команды, я быстро заметил что критерии у них различались кардинально. Один из них старался выбрать самых высоких и ловких. А второй — тех, с кем играл в «Денди» после школы. Я очень любил «Денди».

Мы сражались как львы. Но эта мужская битва в пионербол получилась, мягко говоря, с гандикапом. Была одна проблема: вся наша геймерская команда (кроме нашего капитана — Славика) могла запросто, не нагибаясь, ходить под парту. Славик, конечно, старался… но когда Роман (мой тёзка) сломал очки, притом что мяч ни разу даже в его сторону не летел, стало ясно: мы из тех, кто в стратегию, а не в тактику. Вот в «Черепашек-ниндзя» мы бы их отодрали…

История вторая

Помню как старшие ребята с нашего двора притащили два листа ДСП и пару дужек от пружинной кровати. Из этого они ловко собрали стол для тенниса. Сетку сделали из ластичного бинта и пары струбцин. А вот ракетки были очень хорошие. Где они их взяли - я не знаю. Еще сколько-то времени ушло на приготовления… и понеслась битва!

Стол был сантиметров на пять шире и длиннее стандартного. Но нас это совсем не беспокоило, так как мы настоящий теннисный стол никогда не видели. Да и какая разница, когда весело!

Мы пропадали у этого стола всё лето с утра и до самой темноты — когда уже и шарик-то не видно. Была одна проблема: мы играли «на победителя» — это когда победивший игрок остаётся за столом, а проигравшего заменяет следующий по очереди.

В нашей компании быстро вырисовались лидеры. Они научились играть чуть быстрее — а значит, играли больше и лучше. Бывали дни, когда я просто смотрел, как играют другие, так и не прикоснувшись к ракетке, просто потому, что до меня не доходила очередь. Я помню, как специально ставил будильник на семь утра (это на каникулах-то!), чтобы пойти поиграть с моим другом в теннис, пока никого нет. Как позже выяснилось в техникуме, я отлично научился играть в теннис. Хотя было очень сложно переучиваться на стол меньшего размера.

История третья

Я был классе в седьмом или восьмом, когда девочка из нашей дворовой компании, вернувшись из летнего лагеря, с горящими глазами рассказала нам про игру в «Мафию». Было довольно сложно собрать десять человек вместе, чтобы у всех было на это время, но она была очень мотивирована и как-то с этим справилась.

Сначала получалось как-то криво и косо. То кто-то просыпался не вовремя, то вообще забывал свою роль. В общем, царил полный сумбур. Всё пошло лучше, когда мы стали вести записи и отыгрывать каждую партию до конца, даже если какой-то игрок удалялся за нарушение. А ещё мы стали записывать очки за отыгрыш. Игрок получал тем больше очков, чем дольше он жил за столом. Плюс дополнительные очки за победу. Мне очень нравилась эта игра. Была одна проблема: я до дрожи в коленях боялся вытянуть чёрную карту.

Я очень любил вести расследование за красный город. Но быстро плыл, когда мне приходилось врать людям в глаза, играя за мафию. Я очень не хотел играть за мафию. Под давлением красного города я нервничал и часто промахивался. А однажды даже сделал случайный самострел, когда остался один. Зато на шерифе я просто сиял. За что меня часто убивали в первую же ночь — на всякий случай.

Мне не удалось достоверно выяснить, кто первым придумал автоматизированную систему подбора игроков в современном виде. Очень похоже, что это были люди создавшие DWANGO - Ки Кимбрэлл и Боб Хантли. Но это не точно. Они делали матчмейкинг для Doom и других игр того времени (1994 год). Не знаю, была ли у них рейтинговая система.

Роберт Хантли

Основал DWANGO. Ту, что из США. Не из Японии

Я попытался представить себе как мог бы выглядеть универсальный матчмейкер. Этакий демон, которому можно объяснить правила игры и он лихо разгребёт поток участников, зная кого и куда пристроить. Где-то в этот момент, я понял что дело вообще не в вакансии. Меня занимает сама проблема.

Проблематика

О чем пойдет речь:

честный подбор игроков

О чем не пойдёт речь:

рейтинговая система
подкрутка
патент В. Кислого

Виктор Кислый

Запатентовал кумулятивное пробитие стульев множества игроков

Глоссарий

Игра

Здесь в тексте, я буду иметь в виду некую абстрактную игру, для проведения сеанса которой необходим матч. Иногда я буду приводить конкретные примеры игр, для наглядности.

Матч

Некоторый набор групп участников.

Матчмейкинг

Процесс подбора участников, целью которого является формирование матча.

Участник

Если не сказано иное, я буду иметь в виду участника подбора. Можно представлять его, как конкретного игрока.

Отряд

Отрядом я буду называть то, что в английском языке называется premade squad. Набор игроков сформировавшийся до начала матчмейкинга. Например, друзья решившие вместе поиграть в выбранную игру. Я буду предполагать, что они должны попасть в одну группу.

Группа

Разметка участников внутри матча. Качественный и количественный состав участников группы определяется правилами игры. Можно представлять себе группу как команду (но это не обязательно так).

Скоринг

Рейтинг Эло, MMR, прокачка, или любой другой способ оценить расстояние между игроками в пространстве этой оценки.

Роль

Качественная позиция участника в разметке матча количественно обусловленная правилами игры. Например, голкипер в футболе, мирный житель в “мафии”, игрок третьей позиции в DotA.

При изучении этой задачи я решил сосредоточиться на самом формировании матча, оставив за скобками систему скоринга. Я буду предполагать, что такая система существует, но не буду ее моделировать. Цель: организовать честный подбор по ролям и отрядами согласно правил абстрактной игры, с учетом выданного внешней системой скоринга. Подбор будет именно честным, а не справедливым. Меня устроят хорошие решения за приемлемое время. Мы не будем искать глобальный оптимум по двум причинам:

Поиск глобального оптимума это NP-полная задача
Система динамическая и в неё постоянно поступают новые участники

Но… как река начинается с ручья, нам тоже нужно начать с чего-то малого.

Минимальный пример

Я подумал, что мне нужно взять какую-то простую модель и усложнять её постепенно. Так я решил максимально упростить подбор до вырожденного случая:

Все участники имеют одинаковый скоринг
Состав матча полностью симметричен. Нет команд, нет ролей.
Участники присоединяются к матчмейкину по одиночке

Я легко могу представить себе такую игру. Матч может быть как “все против всех”(ffa), так и “все против среды”(pve) - это ничего не меняет. Здесь всё понятно. Блок-схема для такого решения очень простая:

В один момент времени существует только один открытый матч. Когда он заполняется участниками, он закрывается. При этом, абстрактная внешняя система получает уведомление о том, что матч был сформирован, о составе участников, дате создания и тому подобное.

Усложнение первое

~~Участники присоединяются к матчмейкину по одиночке~~
Участники присоединяются к матчмейкингу отрядами

Уже интереснее. Предположим, есть некоторая игра на 7 участников. К матчмейкингу последовательно присоединяются отряды размеров 5, 4, 3. Если мы сразу создали матч для первого отряда, то когда поступит второй отряд, он не поместится в этот матч. Тогда нам нужно создать еще один матч. То есть, появляется список открытых матчей. Когда придет третий отряд он не поместится в первый матч, но поместится во второй туда его и добавим. В целом не плохо. Есть конечно проблема с тем, что список блокируется и в один момент времени мы можем проверять только один отряд. Но мы вернёмся к этому позже.

Усложнение второе

Всё-таки, без рейтингового подбора сегодня никуда. Многие люди хотят соревноваться и светить своими циферками, но не очень многие хотят быть побиты слишком крутыми оппонентами.

~~Все участники имеют одинаковый скоринг~~
Все участники имеют некоторый скоринг

На этом моменте я немного поплыл. Как я буду высчитывать скоринг отряда? Просто взять среднее? Нужно ли сделать поправку на то, что они играют вместе? Может они сыграны? Они первый раз играют вместе? Двадцатый?

Потом мне в голову пришла простая мысль - я не должен думать о том как вычислять скоринг для отряда. Внешняя система предоставит мне скоринг для всего отряда, а не для каждого участника в отдельности. Как именно она это сделает - не та проблема которую я решаю.

Теперь, создавая матч для отряда, мы будем считать, что скоринг первого добавленного в матч отряда и есть скоринг матча. Так же мы добавим некоторое допустимое окно, в пределах которого скоринг нового отряда будет считаться подходящим для матча.

Кроме того, существует две основные стратегии для ведения скоринга матча. Первая: скоринг матча остаётся неизменным при добавлении новых отрядов в матч. Так как в матче есть окно, то скорниг добавляемого отряда может отличаться от скоринга матча. Отсюда вытекает вторая стратегия: мы можем пересчитывать скоринг матча каждый раз при добавлении нового отряда.

Однако, со второй стратегией (хотя она и выглядит интересной) все не так просто. Тесты (на случайной выборке из нормального распределения рейтингов) показали, что если мы будем наивно пересчитывать среднее значение скоринга, то сокоринг матча может дрейфовать так, что изначальный отряд оказывается за пределами окна скоринга матча. И отклонение скоринга отряда внутри матча, от среднего скоринга матча становится неприемлемым. Я думаю, что вернусь к этой идее позже, и посмотрю что можно сделать. А сейчас буду придерживаться статичного скоринга для матча и буду двигаться дальше.

Усложнение третье

Есть огромное множество командных игр. А среди компьютерных мультиплеерных игр, кажется что командные - самые популярные.

~~Состав матча полностью симметричен. Нет команд,~~ нет ролей.
В матче могу быть команды.

В целом кажется, что ничего особенного - просто в матче появляются группы участников. Но когда я подумал о скоринге…

Здесь появляется первый трейдофф. Дело в том, что между командами может быть отклонение по скорингу. Возможно, что это не так существенно, учитывая что все отряды вписываются в допустимое окно скоринга матча. Однако, если вдруг это критично - задача о балансировке отрядов между командами является NP-полной и сводится к Теореме Ока. Есть некоторые эвристики которые предлагают в среднем хорошие решения для больших входных данных. Я собрал небольшую табличку, чтобы понять, где живут решения этой проблемы различными способами:

По горизонтали отложено количество команд, а по вертикали количество отрядов

Тривиальный случай понятен. Перебор (с бэктрекингом и отсечением) и динамическое программирование (DP) - дают лучшее решение. Метод локального поиска (LS) даёт в среднем хорошие решения. Жадный - что найдёт. На больших входных данных, при запуске жадного алгоритма, мы могли бы выделить некоторый бюджет времени, и забрать лучшее решение, что он нашел за отведённое время. Еще стоит отметить, что DP алгоритм очень сильно отличается для случаев с двумя и тремя командами. Не буду утомлять вас кодом этих алгоритмов - в сети полно примеров, и LLM-ки отлично с этим справляются.

У меня уже начала болеть голова, от мысли, что мне придется как-то встраивать эти балансировщики в свой код. И тут я снова подумал, что это не моя задача. Матч сформирован. Как именно его сбалансировать? Пусть какая-то внешняя система принимает это решение. Сейчас будем просто считать, что в Матче есть какие-то команды (далее я буду называть их группы). Будем двигаться дальше.

Усложнение четвертое

~~Состав матча полностью симметричен. Нет команд, нет ролей~~.
У участников есть роли.

Я начал представлять себе ролевой подбор с самого понятного мне примера: DOTA2. Я немалое время провёл в этой игре, и мне вполне понятна её ролевая проблематика. Всё довольно несложно. Роли в DOTA2 просто пронумерованы. Они, конечно, имеют какие-то названия, но чаще всего вы можете слышать “игрок n-ной позиции”. И так, мы имеем пять игроков в команде и пять ролей. На этом этапе, будем считать, что каждый участник отряда указал какую-то роль. И не забываем, что отряд может состоять из любого количества игроков от 1 до 5.

Когда отряд присоединяется к матчмейкингу, мы сначала отфильтровываем все матчи, что не подходят по скорингу (MMR) - то есть, не вписываются в окно скоринга матча. Затем проверяем, есть ли в матче группы в которых достаточно места под наш отряд, после этого проверяем ролевой состав группы - свободны ли в группе роли для этого отряда. И если всё хорошо, то добавляем отряд в группу. Если не удалось найти подходящий для отряда матч, то создаём новый матч на основе отряда.

В целом всё ок, но меня немного смущал этот перебор ролей отряда, затем перебор доступных ролей группы. Была какая-то чуйка, что всё должно быть сильно проще. И оказалось, что да.

Мы можем представить состав ролей отряда как битовую маску, в которой указано, какие именно роли заняты:

10001 // Те кто играл в DOTA2, уже поняли, что это дуо на легкую линию

И делая бинарное умножение с ролями группы, мы легко понимаем что они совместимы:

10001 & 01110 = 00000 // получили ноль - совместимы
10001 & 11100 = 10000 // больше ноля - не совместимы

Кроме того, теперь нам даже не нужно проверять группу на вместимость. Профит.

Но здесь я вспомнил, про другую игру. Когда-то давно, я играл в WoW. Там можно было вставать очередь на поиск группы в подземелье. Группа так же состояла из пяти человек. Однако, распределение ролей там было иным: 3 damage dealer (DD), 1 Tank, 1 Heal. Такая разметка битами не очень работала:

11001 // 2*DD и 1*Heal встали в очередь
10010 // В группе есть 1*DD и 1*Tank

10001 & 10010  = 10000 // больше ноля - не совместимы

И мне пришла в голову интересная идея. Мы можем разметить битовую маску участками, и в отряде вести наполнение участка битами в прямом порядке, а группе - в обратном.

DD   T  H
_________
110  0  1   // 2*DD и 1*Heal встали в очередь
001  1  0   // В группе есть 1*DD и 1*Tank
000  0  0   // ноль - совместимы

Когда тебя посещают такие маленькие озарения, даже кофе становится вкуснее! Одна бинарная операция проверяет и вместимость и ролевой состав.

Усложнение пятое

Вообще-то, как в DOTA2, так и в WOW можно указать не одну роль для поиска, а несколько. Но я решил пойти дальше, и посчитать еще и приоритеты.

~~У участников есть роли~~
Участники могут указать список желаемых ролей в порядке приоритета

Решение для количества ролей 1 и 2 тривиальны. Из них вряд ли можно что-то понять. Первый сложный пример открывается на группе с тремя ролями.

Пусть есть некоторая игра, с такой разметкой: {1:1, 2:1, 3:1}. То есть в группе есть 3 роли. Каждая в количестве 1. И пусть есть некоторый отряд, со списком приоритетов:

1, 2, 3
3, 1, 2
1, 3, 2

Что мы можем об этом сказать? Такой отряд покрывает всю группу. Количество возможных перестановок элементов составляет n!. Но мы быстро можем заметить, что не все эти перестановки одинаково хороши. Стоит учесть, что роли указаны в порядке приоритета. А это значит, что некоторые перестановки могут быть лучше других. Давайте попробуем дать оценку этим перестановкам. Пусть чем выше позиция роли, тем меньше оценку она получает, начиная с нуля для самой приоритетной роли. В итоговом подсчете меньше - лучше:

 1  3  2
 0  0  2  = 2
 
 1  2  3
 0  2  1  = 3
 
 2  3  1
 1  0  0  = 1

 2  1  3
 1  1  1  = 3 

 3  2  1
 2  2  0  = 4
 
 3  1  2
 2  1  2  = 5

Как мы видим, перестановка [2, 3, 1] самая приоритетная. Но так как мы работаем с вырожденным случаем (все роли заняты отрядом), все эти перестановки имеют общую маску 111 и мы можем их схлопнуть до одной лучшей перестановки. В общем (не вырожденном) случае, это не обязательно так. Некоторые перестановки будут схлопываться в одну, другие - нет. Но что точно понятно: перестановки с одинаковой маской должны схлопываться до лучших перестановок с такой маской.

Так или иначе, мы теперь можем оценить такие перестановки и упорядочить по приоритету. А затем, проверять на совместимость с группами в порядке убывающего приоритета. На что еще я хотел бы обратить внимание: в зависимости от того как мы генерируем список перестановок, их порядок на одном уровне приоритета может зависеть от того, в каком порядке участники находятся в отряде. Это значит, что находясь на определённой позиции в отряде, участник может чаще получать более приоритетную роль, чем другие участники этого же отряда. Чтобы это не происходило, все перестановки на одном уровне приоритета нужно перемешивать в случайном порядке.

Суперпозиция матча

Так как теперь за одной маской может скрываться несколько перестановок, мне было не очень понятно, какую именно из перестановок выбрать при создании матча на основе отряда. Ведь может оказаться, что в отряде не одна, а несколько лучших перестановок. Я принял решение, хранить все лучшие перестановки при добавлении отряда в матч. Кроме того, все добавляемые отряды будут так же добавлять все свои лучшие перестановки для маски, с которой они были добавлены. Финальная композиция перестановок будет складываться из всех перестановок всех отрядов группы. Перестановки будут заново отсортированы, как если бы все участники группы были участниками одного отряда. Из лучших таких перестановок будет выбрана случайная. Фактически, финальная перестановка не будет известна до того, как матч будет сформирован.

Конкурентность

Когда я делал самое первое усложнение, и впервые появился список матчей, меня уже смущала блокировка списка. Даже если мы не будем блокировать весь список матчей, а повешаем мьютекс на матче - проблема не уйдет.

Представим, что два отряда почти одновременно поступили в очередь.

Первый отряд проходится по списку матчей, блокирует первый матч. Выполняет свои проверки.
Второй отряд проходится по списку матчей, доходит до первого матча и ждёт пока его отпустит первый отряд.

Не дело…

Я не знаю, существует ли для этого специальный термин, или это какой-то паттерн. Для решения этой задачи я написал неблокирующий итератор. Логика такая:

Первый итератор проходится по списку матчей.
- Блокирует первый матч.
- Выполняет свои проверки.
Второй итератор проходится по списку матчей.
- Видит, что первый матч заблокирован.
- Запоминает это и идет дальше по списку.
- Закончив с общим списком, он возвращается к списку виденных заблокированных и крутит его в CAS-цикле.

Если интересно, то вот код. С комментариями для вас.

Шучу. Комментарии для меня.


// IterateWithContext возвращает iter.Seq[T] - генератор, который проходит по текущему списку
// и для каждого узла пытается "взять его в руки" (locked CAS).
// Если узел помечен deleted итератор его пропускает.
// Если узел занят, итератор тоже его пропускает, но запоминает. Первый проход похож на skip locked в базах данных.
// Затем пытается обойти пропущенные узлы, пока не обойдёт все
func (c *Conveyor[T]) IterateWithContext(ctx context.Context) iter.Seq[T] {
	return func(yield func(T) bool) {
		// Здесь будем хранить пропущенные узлы
		skipped := make([]*Node[T], 0)

		for n := c.head.Load(); n != nil; {
			current := n

			// Если узел помечен на удаление...
			if current.deleted.Load() {
				//  ...пропускаем его
				n = current.next.Load()
				continue
			}

			// Пытаемся захватить узел...
			if !current.locked.CompareAndSwap(false, true) {
				// ...занят кем-то, то запоминаем...
				skipped = append(skipped, current)

				// ...и пропускаем его.
				n = current.next.Load()
				continue
			}

			// Отдаем значение наружу.
			_continue := yield(current.Value())

			// Освобождаем узел.
			current.locked.Store(false)

			// Если yield вернул false (break/return) - прекращаем.
			if !_continue {
				return
			}

			// Переходим к следующему узлу.
			n = current.next.Load()
		}

		// Продолжаем бегать по пропущенным, пока они не опустеют
		for len(skipped) > 0 {
			tryLater := make([]*Node[T], 0, len(skipped))
			for _, current := range skipped {
				if current.deleted.Load() {
					continue
				}

				if !current.locked.CompareAndSwap(false, true) {
					// ...занят кем-то - запоминаем, и пропускаем.
					tryLater = append(tryLater, current)
					continue
				}

				_continue := yield(current.Value())

				// Освобождаем узел.
				current.locked.Store(false)

				// Если yield вернул false (break/return) - прекращаем.
				if !_continue {
					return
				}
			}

			if len(skipped) == len(tryLater) {
				select {
				case <-ctx.Done():
					return
				default:
					runtime.Gosched()
				}
			}
			skipped = tryLater
		}
	}
}

Это далеко не всё. Есть еще система событий, подписок, метрики, логи и куча всякой возни… Об этом всём в другой раз (если кому-то вообще интересна эта тема).

Так что я знаю о матчмейкинге? Ну… кое-что знаю. Только никто не спрашивает.

О подборе игроков