Стратегия / алгоритм разделения честных команд на основе истории

20

Мы группа людей, играющих вместе во флорбол на регулярной основе. Каждый сеанс начинается с сложной задачи разделения команд ...

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

Итак, учитывая историю командных комбинаций и результатов, а также список людей, появляющихся для этой конкретной сессии, что было бы хорошей стратегией для поиска оптимальных команд? Под оптимальным я подразумеваю команды, максимально равные.

Есть идеи?

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

[{ team1: ["playerA", "playerB", "playerC"],
   team2: ["playerD", "playerE", "playerF"],
   goals_team1: 10,
   goals_team2:  8 
 },
 { team1: ["playerD", "playerB", "playerC"],
   team2: ["playerA", "playerE", "playerG"],
   goals_team1:  2,
   goals_team2:  5
 },
 { team1: ["playerD", "playerB", "playerF"],
   team2: ["playerA", "playerE", "playerC"],
   goals_team1:  4,
   goals_team2:  2
 }]
Vegar
источник
4
Что такое флорбол?
Динамичный
1
Я предполагаю, что у вас есть только результаты команды, а не индивидуальный вклад?
Gort the Robot
1
@Dynamic: Я собираюсь догадаться, что это еще одно название для Floor Hockey - хоккей играл на полу спортзала с маленьким резиновым мячом, а не на льду с шайбой (и, конечно, без коньков).
FrustratedWithFormsDesigner
2
Вы можете уточнить, что единственная информация, которая будет использоваться в этом алгоритме, - это количество выигрышных / проигрышных команд каждого игрока.
ТехШрик
2
@TehShrike Для каждого сыгранного матча у меня есть информация о том, кто играл в какой команде и каков был конечный счет. Например. {Team1: ["a", "b", "c"], Team2: ["d", "e", "f"], счет: "10-5"}
Вегар

Ответы:

6

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

Я вспоминаю что-то из того, что у Google был генератор шансов на футбол. Над этим было проделано гораздо больше работы, чем над этим. В поисках ссылки на это я нашел статью в SO и калькулятор True Skill, который Microsoft использует для xbox .

Принимая более упрощенный подход, каждый игрок получает оценку соотношения очков, которые его команда имеет за игру. В игре 1 игрок A получит 1,25 (10/8), а игрок D - 0,8 балла (8/10). Найти среднее значение всех чисел, и это оценка игрока.

Для описанного набора игр это обеспечивает:

  A 1.42
  B 1.22
  C 0.72
  D 1.07
  E 1.27
  F 1.40
  G 2.50

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

Сообщество
источник
То же количество игроков, или как можно ближе, если оно показывает нечетное количество игроков ;-)
Vegar
Спасибо за ссылку на проблему с разделом ! Ты рок, @ user40980
Эрик Гопак
3

Быстрый и грязный подход:

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

Горт Робот
источник
Этот подход может работать, даже если данная комбинация людей совершенно новая.
Вегар
Делать лучше выглядит как вариант проблемы с рюкзаком . Веса тоже могут быть важны - насколько я помню, самый тяжелый игрок (я) всегда выбирался последним.
Steve314
Известно, что этот жадный подход дает 4/3-приближение к оптимальному решению (Википедия)
Радек
3

Если вы не хотите копаться в безумном мире байесовских приоров (pdf) и так далее, интересным подходом будет назначить общий порядок всем игрокам (на основе соотношения выигрышей / проигрышей, кумулятивных очков и т. Д.), А затем разделить на Команды, использующие функцию четности следующим образом.

Возьмите отсортированный список игроков (от лучших к худшим) и разделите их на команды «четные» и «нечетные», основываясь на количестве 1 бита в их индексе (начиная с 0). Это дает следующее распределение:

  • 0000 (лучше всего) - даже
  • 0001 - Нечетный
  • 0010 - Нечетный
  • 0011 - даже
  • 0100 - Нечетный
  • 0101 - даже
  • 0110 - даже
  • 0111 - Нечетный

...и т.д.

Функция четности обеспечит равное количество игроков в каждой команде для любого четного числа игроков. Затем он будет чередоваться, давая преимущество нечетного игрока одной или другой команде таким образом, что со временем эффекты будут уравновешиваться.

Эта функция работает лучше всего, когда распределение навыков игрока является плоским. В действительности, навыки игрока, как правило, следуют распределению «суммы случайных значений», то есть гауссовскому (хотя остерегайтесь применения этого предположения в таких системах, как TruSkill).

Чтобы компенсировать большие пробелы в навыках, вы можете применить перестановки к этому списку. Например, чтобы противостоять очень сильному топ-игроку 0000, вы можете поменять игрока 0011 на нечетного игрока с более низким рейтингом, такого как 0100. Это где вещи становятся волнистыми, но, по крайней мере, это обеспечивает хорошую отправную точку, которая не требует точного измерения абсолютного навыка, но просто упорядочение на основе относительного навыка.

Ричард Нельсон
источник
2

В зависимости от того, сколько у вас есть времени, начните первые несколько сессий, выбрав случайным образом капитанов команд, и перед каждой игрой имейте черновой вариант. Следите за тем, какой игрок выберет. Более ранние выборы получают более высокие оценки:

Round #1 = 8 pts, Round #2 = 6 pts, Round #3 = 4 pts, etc

Winning a game = 5 pts

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

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

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

JeffO
источник
Отличный ответ! Это может работать для средней команды, но некоторые команды являются стратегическими. Например, если вы хотите, чтобы вся ваша команда была защитниками, тогда у вас было бы худшее общее число игроков, идущих в более высокие раунды. Но, я думаю, я не просил канонического: P. Благодарность!
Динамичный
Это отличный способ начать. В первые несколько раундов что-либо, основанное на общем счете команды, не будет применяться индивидуально, так как у вас будут члены команды, которые играют вместе в каждом раунде.
Gort the Robot
1

Самым простым решением будет предоставить оценку / вес оцениваемого навыка и попытаться сбалансировать счет для каждой команды.

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

Как интересный момент с моей стороны: Infer.NET позволяет относительно легко представить и реализовать это, и он может предсказать шансы на победу в данных командных матчах. Infer.NET - это то, что я действительно начинаю понимать в последнее время.

Стивен Эверс
источник
Достаточно ли у вас данных, чтобы иметь смысл, если бы было всего несколько игр?
Gort the Robot
Я надеялся решить эту проблему с помощью javascript или ruby, но в любом случае infer.net выглядит интересно.
Вегар
@StevenBurnap: Зависит от того, насколько хороши / точны ваши первоначальные предположения относительно способностей игрока - что вам придется сделать для большинства или для всех систем. Преимущество использования сети заключается в том, что со временем вы сможете выводить новые оценки для каждого игрока, чтобы повысить это значение.
Стивен Эверс
1

Предположим, что для обсуждения вы можете назначить каждому игроку целое число, и эти значения складываются, то есть игрок с результатом X так же ценен, как и три игрока с показателями A, B и C, если A + B + C = X. Затем цель состоит в том, чтобы разделить группу на две команды, чтобы обе команды имели примерно одинаковое суммарное значение.

Это оптимизационная версия известной задачи PARTITION, которая является NP-полной. Поэтому ваша проблема для всех, кого мы знаем, трудно решить. Тем не менее, PARTITION слабо NP-завершен и допускает некоторые разумные аппроксимационные стратегии.

Одним из примеров является жадный подход, подобный тому, что предлагает Стивен. Это 4/3-приближение, то есть более сильная команда никогда не бывает более чем на 33% сильнее, чем в оптимальном расколе.

Обратите внимание, что у вас, вероятно, есть дополнительные ограничения, например, вам нужно как минимум фиксированное количество игроков на команду. Так что, если вы поместите Майкла Джордана в класс дошкольников, вы не сможете создать почти честные команды с полным числом. Такая (постоянная) нижняя граница размера команды не должна влиять на сложность основной проблемы, но она может разрушить границы аппроксимации, действительные для общей задачи.

Рафаэль
источник
1
Вы не можете разместить очень много игроков на полу спортзала. При 20 игроках, при условии, что вы хотите 10 на стороне, нужно проверить только 92378 комбинаций. Но это не займет много игроков, прежде чем количество комбинаций делает исчерпывающий поиск нецелесообразным.
Кевин Клайн
@kevincline: Верно. Я неявно предположил, что грубая сила не была альтернативой (иначе зачем спрашивать?).
Рафаэль
В каждой команде никогда не будет больше шести человек. Чаще всего четыре.
Вегар
@Vegar: Тогда ваш вопрос больше в том, как использовать результаты команды для моделирования ценности игрока, а не в алгоритмах, верно?
Рафаэль
1
Если вы не можете найти способ по-настоящему оценивать людей по их таланту, точность алгоритма, вероятно, не так важна. Имея под рукой проблему, у нас есть только командный счет и несколько испытаний. Любой рейтинг игрока будет дикой оценкой.
Gort the Robot
0

Насколько нелепым ты хочешь стать? Вы всегда можете использовать множественную линейную регрессию, чтобы сгенерировать коэффициенты для каждого игрока на основе оценок их команд в предыдущих играх. Затем отсортируйте список и выберите.

На самом деле это , вероятно , не будет работать , так как он не моделирует динамику между игроками, но это даст вам повод , чтобы играть вокруг с R . (<- видите, я продолжал программировать)

GrandmasterB
источник
1
Я подумываю о том, чтобы подать заявку, чтобы избежать двухминутной задачи два раза в неделю, и я вынужден тратить примерно столько же времени на запись результатов для будущих вычислений. Я думаю, что это довольно нелепо ...
Вегар
-1

Если вы хотите, чтобы ваш алгоритм был разумным, простые алгоритмы просто не будут его сокращать. Они часто дают вам странные результаты

Вам придется использовать что-то вроде системы ELO или Trueskill (ELO не работает для команд без изменений).

catbert
источник
1
Это не правда Должен быть алгоритм, который бы работал.
Динамичный