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

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

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

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

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

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

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

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

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

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

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

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

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

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

Игра

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

Матч

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

Матчмейкинг

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

Участник

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

Отряд

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

Группа

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

Скоринг

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

Роль

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

package utilsimport ("context""errors""fmt""iter""runtime""sync/atomic""time")// Node двусвязный узел конвейераtype Node[T comparable] struct {value   Tnext    atomic.Pointer[Node[T]]prev    atomic.Pointer[Node[T]]locked  atomic.Bool // Захвачен итератором.deleted atomic.Bool // Помечен на удаление.}func (C *Node[T]) Value() T {return C.value}// Conveyor - Конкурентный, конвейерный итератор.//// Границы применимости://// Итерации должны отрабатывать быстрее, чем поступают новые значения в конвейер.// Иначе можно застрять, в цикле, так как итератор никогда не догонит хвост.// Следует избегать использования для слишком больших списков значений.//// Физическое удаление узлов не блокирует итератор, выполняется в отдельной горутине.type Conveyor[T comparable] struct {head  atomic.Pointer[Node[T]]tail  atomic.Pointer[Node[T]]nodes *SyncCache[T, *Node[T]]}// NewConveyor создает пустой конвейер.func NewConveyor[T comparable]() *Conveyor[T] {return &Conveyor[T]{nodes: NewSyncCache[T, *Node[T]](),}}func (c *Conveyor[T]) AddNode(n *Node[T]) {defer c.nodes.Set(n.value, n)for {tail := c.tail.Load()// Если хвоста нет (пустой список)...if tail == nil {// ...попробуем поставить голову.// Если удалось...if c.head.CompareAndSwap(nil, n) {// ...установим хвост тоже.c.tail.Store(n)// Готовоreturn}// Иначе кто-то другой поставил голову. Повторяем.continue}// Если кто-то заблокировал хвост...if !tail.locked.CompareAndSwap(false, true) {// ...попробуем снова, позже.runtime.Gosched()continue}// Если хвост сменился, или к этому моменту был удалён...if c.tail.Load() != tail || tail.deleted.Load() {// ...освобождаем хвост и пробуем сноваtail.locked.Store(false)continue}// Пытаемся привязать новый узел после tail: tail.next == nil -> tail.next = nif tail.next.Load() == nil && tail.next.CompareAndSwap(nil, n) {// Связали узел после tailn.prev.Store(tail)// Попробуем продвинуть tail (best-effort)c.tail.CompareAndSwap(tail, n)tail.locked.Store(false)return}// Не удалось привязать узел...// Освобождаемtail.locked.Store(false)next := tail.next.Load()// Если кто-то уже добавил nextif next != nil {// продвинем tail...c.tail.CompareAndSwap(tail, next)}// Ушли на следующую итерацию}}// BorrowNewNode - append в хвост. Возвращает *Node[T] в заблокированном состоянии.// *Node можно потом передать в DeleteWithContext или в Release, чтобы разблокировать.// Node блокируется до попадания в связный список, так что можно сим что-то сделать, а затем вернуть в Release.func (c *Conveyor[T]) BorrowNewNode(val T) *Node[T] {n := &Node[T]{value: val}e := c.Capture(n)if e != nil {panic("wtf: " + e.Error())}c.AddNode(n)return n}// AddValue - append в хвост. Возвращает *Node[T] в разблокированном состоянии.// *Node можно потом передать в DeleteWithContext.func (c *Conveyor[T]) AddValue(val T) *Node[T] {n := &Node[T]{value: val}c.AddNode(n)return n}func (c *Conveyor[T]) Iterate() {}// 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():returndefault:runtime.Gosched()}}skipped = tryLater}}}// DeleteWithContext помечает узел на удаление, если он захвачен,// и физически удаляет его из списка асинхронно (обновляет prev.next и next.prev).// Нужно передавать именно тот *Node[T], который вернул BorrowNewNode или FindNodeByPredicate.func (c *Conveyor[T]) DeleteWithContext(ctx context.Context, n *Node[T]) {if n == nil {return}// Помечаем узел на удалениеn.deleted.Store(true)defer c.nodes.Delete(n.value)go func(ctx context.Context, n *Node[T]) {// Перед выходом удалим узел из кеша// Ждём, пока Node не будет разблокированfor n.locked.Load() {select {case <-ctx.Done():returncase <-time.After(time.Microsecond): // Не греем камень, попробуем позжеruntime.Gosched()}}// физическое удаление: корректируем prev.next и next.prevfor {prev := n.prev.Load()next := n.next.Load()// если prev == nil - удаляем головуif prev == nil {// пробуем атомарно заменить head (best-effort)if c.head.CompareAndSwap(n, next) {// скорректируем next.prev если естьif next != nil {// попытка установить next.prev = nil (если оно всё ещё указывает на n)next.prev.CompareAndSwap(n, nil) // todo: а что если next.prev уже изменился?}// возможно с tail надо что-то сделать// если мы удалили единственный элемент, tail мог указывать на nc.tail.CompareAndSwap(n, next)return}// head изменился: возможно кто-то другой уже модифицировал список,// просто попробуем снова: обновим prev/next из текущего состояния.continue}// prev != nil// пытаемся установить prev.next = next (заменяем n на next)if prev.next.CompareAndSwap(n, next) {// успешно переключили prev.nextif next != nil {// теперь скорректируем next.prev = prev (если оно всё ещё указывает на n)next.prev.CompareAndSwap(n, prev)} else {// next == nil - значит удаляли хвост; попробуем продвинуть tailc.tail.CompareAndSwap(n, prev)}return}// Если prev.next не равнялся n - возможно prev устарел, попробуем заново:// Обновим prev: берем текущий prev (может измениться из-за конкурентных удалений/вставок)// лучший способ - прочитать снова n.prev,// но если prev стал nil - повторим цикл и обработаем как удаление головы}}(ctx, n)}// FindNodeByPredicate - вспомогательная функция: ищет первый узел, удовлетворяющий predicate.// Возвращает *node[T] или nil.// Полезно чтобы получить node для DeleteWithContext.func (c *Conveyor[T]) FindNodeByPredicate(predicate func(T) bool) *Node[T] {for n := c.head.Load(); n != nil; n = n.next.Load() {// можно попытаться захватить, но нет необходимости - просто читаем значение// и возвращаем ссылку на узел; DeleteWithContext будет корректно работать.if !n.deleted.Load() && predicate(n.value) {return n}}return nil}// Len - некоторая "приближённая" длина списка (не атомарна, может меняться во время подсчёта)func (c *Conveyor[T]) Len() int {cnt := 0for n := c.head.Load(); n != nil; n = n.next.Load() {if !n.deleted.Load() {cnt++}}return cnt}// BorrowNodeByValueWithContext - "берет в долг" (блокирует) узел с заданным значением и возвращает её.// Если ноды с заданным значением нет - вернет nilfunc (c *Conveyor[T]) BorrowNodeByValueWithContext(ctx context.Context, value T) *Node[T] {for n := c.head.Load(); n != nil; n = n.next.Load() {if n.value != value {continue}// Ждём, пока сможем захватить узелfor !n.locked.CompareAndSwap(false, true) {select {case <-ctx.Done():return nildefault:runtime.Gosched()}}if n.deleted.Load() {n.locked.Store(false)return nil}return n}return nil}func (c *Conveyor[T]) TryBorrowNodeByValue(value T) (node *Node[T], tryLater bool) {for n := c.head.Load(); n != nil; n = n.next.Load() {if n.value != value {continue}// Пробуем захватить узел...if !n.locked.CompareAndSwap(false, true) {// Не вышло, возвращаем nilreturn nil, true}if n.deleted.Load() {n.locked.Store(false)return nil, false}return n, false}return nil, false}// Release - возвращает (разблокирует) ранее захваченный узел.func (c *Conveyor[T]) Release(n *Node[T]) error {if n == nil {return errors.New("can not return nil node")}if !n.locked.Load() {return errors.New("can not unlock non-locked node")}n.locked.Store(false)return nil}// Capture пытается синхронно захватить узел.func (c *Conveyor[T]) Capture(n *Node[T]) error {if n == nil {return errors.New("can not borrow nil node")}for n.locked.Load() {runtime.Gosched()}n.locked.Store(true)return nil}func (c *Conveyor[T]) DeleteByValueWithContext(ctx context.Context, value T) error {node, ok := c.nodes.Get(value)if !ok {return fmt.Errorf("can not find node with value %v", value)}c.DeleteWithContext(ctx, node)return nil}func (c *Conveyor[T]) Drain(ctx context.Context) iter.Seq[T] {return func(yield func(T) bool) {for n := c.tail.Load(); n != nil; n = n.prev.Load() {yield(n.value)c.DeleteWithContext(ctx, n)}}}