Как машинное обучение и SQL могут помочь вам перехитрить соперника в последовательных командных играх

Будучи заядлым игроком в бильярд с опытом работы в области оптической физики, я часто задавался вопросом, улучшил ли мой опыт моделирования траекторий лазерных лучей мою способность совмещать удары в бильярд или наоборот!

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

Многие национальные пул-лиги ведут хорошо документированную статистику игроков и записи прошлых матчей, что является идеальным ресурсом для построения прогностических моделей. Во время стажировки Insight Data Science я научился использовать Flask в Python для интеграции моделей машинного обучения в удобные веб-приложения. Итак, я задался вопросом: можно ли использовать мощную комбинацию Flask и машинного обучения для создания личного тренера по пулу?

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

  • В Части 1, которую вы сейчас читаете, я представлю проблему более подробно и покажу, как можно применять машинное обучение для прогнозирования результатов игры в бильярд.
  • В Часть 2 я покажу, как SQL-запросы могут помочь улучшить стратегии выбора игроков.
  • В Часть 3 производительность приложения оценивается статистически и сравнивается с реальными стратегиями.

Проблема с пулом

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

В восьмерке на столе 16 шаров:

  • 7 сплошных цветов с номерами 1–7.
  • 7 полосатых цветов с номерами 9–15.
  • Сплошной белый биток.
  • Сплошная черная восьмерка.

Однотонный и полосатый — это два разных костюма; каждому игроку назначается масть (в зависимости от первого забитого шара), и он пытается забить все 7 шаров своей масти, прежде чем забить 8-й шар для победы.

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

В командном пуле возникает совершенно новый тип стратегии: выбор составов игроков. Команда бильярда состоит из когорты игроков/друзей, которые регулярно собираются, чтобы выпустить пар в игровой конкурентной среде. Команды сражаются за то, чтобы набрать наибольшее количество очков и занять первое место в своей местной лиге. Любой капитан команды охотно сообщит вам, что решения, принятые за столом, так же важны, как и решения, принятые за столом. Матчи могут быть выиграны и проиграны исключительно из-за умного (или глупого) выбора состава, сделанного капитанами команд.

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

Прежде чем мы начнем, немного жаргона и определений пула:

– Команда: группа из 5–8 аффилированных игроков в пул.

– Капитан команды: игрок, ответственный за выбор игроков, играющих в каждом раунде.

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

- Раунд: одна встреча между двумя игроками из противоборствующих команд.

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

– Стойка: отдельная «игра» в бильярд, начинающаяся с начального броска и заканчивающаяся, когда шар номер 8 заглубляется. Каждый игрок должен выиграть определенное количество стоек, чтобы выиграть свой раунд.

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

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

Правила соответствия

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

  • Команда А выбирает игрока для первого раунда.
  • Команда Б выбирает игрока для первого раунда.
  • Команда Б выбирает игрока для второго раунда.
  • Команда А выбирает игрока для второго раунда.
  • … и т. д., пока не будут завершены все раунды.

Уравнивающий гандикап

Хотя капитан команды прекрасно знает возможности своих игроков, процесс принятия решений сильно омрачен уравнительной форой. Давайте объясним, как это работает, на примере подбора игроков, который поможет понять контекст некоторых терминов и определений, о которых вы только что прочитали:

Яростный Стив имеет рейтинг навыков 110, что означает, что он игрок-любитель высшего уровня. Тем временем Ambling Ally здесь только для того, чтобы хорошо провести время, а их уровень 50 отражает тот факт, что они не относятся к игре слишком серьезно. Уравнивающий гандикап выравнивает игровое поле, так что, если эти двое столкнутся друг с другом в раунде, у каждого будет примерно 50% шансов на победу. По сути, это формула преобразования, которая использует уровни навыков игроков в качестве входных данных и дает продолжительность гонки для каждого игрока. В лиге, в которой я участвую, Стиву для победы в раунде потребуется 8 стоек, тогда как Элли достаточно выиграть только 2. Однако это не идеальная система, поскольку на исход матча влияет гораздо больше факторов, чем просто уровень мастерства игрока. (например, изношенное оборудование).

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

Решение

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

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

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

Он состоит из следующих компонентов:

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

На рис. 1 показан обзор приложения Magic8Ball. В этой серии я сосредоточусь на наиболее распространенном формате лиги из 5 команд. Это означает, что их 5! = 120 возможных составов матчей, некоторые из которых гораздо чаще приводят к победе одной команды. Результаты каждой очереди прогнозируются алгоритмом машинного обучения и сохраняются в базе данных SQL. В начале каждого раунда на основе этих прогнозов рассчитывается оптимальный выбор игрока. По мере того, как капитан выбирает игроков, которые будут сражаться в следующих четырех раундах, для оценки остается меньше составов, и вероятность победы в матче неуклонно растет.

Выбор функций для прогностической модели

Чтобы предоставить значимые предложения игроков для данного раунда, нам нужен способ количественного сравнения различных пар игроков. Мы построим прогностическую модель, используя результаты 20 000 исторических пар игроков из Североамериканской ассоциации игроков в пул (NAPA).

Чтобы просмотреть любой код, используемый в этом конкретном разделе, см. соответствующий файл в моем репозитории GitHub.

НАПА публикует с точностью до минуты результаты матчей в легко читаемом табличном формате. Статистика матча может быть выражена в виде маржи, т. е. значения этой статистики для игрока B, вычтенного из значения этой статистики для игрока A. Вот некоторые функции, доступные для каждого завершенного матча. круглый:

  • Разница в гонках: разница между количеством стоек, необходимых каждому игроку для победы в раунде.
  • Процент побед: разница между историческими процентами побед каждого игрока в раундах (по сравнению с предыдущими матчами):

  • Граница навыков: разница между уровнями навыков каждого игрока.
  • Игровая маржа: разница между общим количеством раундов, сыгранных каждым игроком за время своего членства в NAPA.
  • Средняя маржа очков за матч (AvgPPM Margin): разница между средним количеством очков за раунд для каждого игрока.

Наконец, и самое главное…

  • Разница в выигрыше: разница в выигрыше (в количестве стоек) для игрока А в текущем раунде. Отрицательные значения означают, что игрок B выиграл раунд. В форме уравнения маржа выигрыша для игрока А определяется как:

Наша цель — использовать первые пять функций для прогнозирования маржи выигрыша для этой пары игроков.

Какие выводы мы можем извлечь из этих исторических результатов? Для начала было бы неплохо изучить распределения данных, представленные на рисунках 2 и 3, и выполнить базовый корреляционный анализ набора данных, чтобы выяснить, демонстрируют ли какие-либо переменные сильные взаимосвязи.

На рис. 4 показана матрица коэффициентов корреляции Пирсона для каждой функции в нашем наборе данных из 20 000 исторических раундов. Некоторые наблюдения, которые сразу бросаются в глаза:

  • Win % Margin и AvgPPM Margin демонстрируют идеальную мультиколлинеарность! Это довольно очевидно, потому что за победу начисляется больше очков, чем за поражение. Однако это плохая новость для таких моделей, как линейная регрессия, поэтому нам нужно будет отказаться от одной из этих функций, прежде чем подгонять модель.
  • Также существует высокий коэффициент корреляции между маржей по навыкам и маржей по расе. Это имеет смысл, так как разница в гонке рассчитывается с использованием уровней навыков игрока. Однако гоночный калькулятор не является непрерывной математической функцией, так что эта корреляция далеко не идеальна.
  • Мы видим только слабую корреляцию с целевой характеристикой Win Margin, причем самый высокий коэффициент составляет 0,2 для Win % Margin. Хотя это хорошая новость для создателей уравнительной форы, она плохо сказывается на наших перспективах разработки высокоинформативной модели. Без гандикапа мы бы ожидали гораздо более сильной корреляции между Уровнем навыков и маржой выигрыша.

Выбор прогнозной модели

Мы хотим обучить модель, которая использует переменные Race Margin, Game Margin, Win % Margin, Skill Margin и AvgPPM Margin, чтобы прогнозировать значение переменной Win Margin.

1. Линейная регрессия

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

Мы уже видели, что переменная AvgPPM Margin была избыточной из-за идеальной корреляции с Win % Margin, и мы также удалим переменную Game Margin. так как величина его влияния настолько мала. Используя оставшиеся функции, данные разбиваются на наборы для обучения и проверки.

Я масштабировал обучающие данные, а затем подгонял обычную модель регрессии наименьших квадратов. Производительность определяется с помощью средней абсолютной ошибки (MAE) и коэффициента корреляции (R в квадрате) между прогнозами и истинными значениями в наборе данных проверки. Регрессионная модель прогнозирует размер выигрыша для игрока А с точки зрения количества стоек.

Прогнозы модели визуализированы на рисунке 5 для наборов обучающих и тестовых данных. Из этих диаграмм рассеяния мы видим, что модель явно имеет большую дисперсию! Средняя абсолютная ошибка для каждого прогноза составляет приблизительно 2 стойки, что довольно неинформативно, учитывая, что из всех результатов в наборе данных 63% были выиграны с разницей в 2 стойки. или менее (см. рис. 3). Таким образом, с этой моделью существует вполне реальная возможность того, что мы можем чаще предсказывать неправильного победителя, чем нет. Не совсем та модель, которой можно доверять.

2. Классификация

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

Мы можем добиться этого, создав новую бинарную переменную выигрыша/проигрыша и преобразовав нашу проблему регрессии в проблему классификации. Модели классификации генерируют вероятность принадлежности выборки к классу, в нашем случае выигрыш или проигрыш игрока А. Мы можем ожидать выигрыша, если прогнозируемая вероятность превышает 0,5, и проигрыша при вероятности менее 0,5. Границе выигрыша больше нуля (выигрыш игрока А) присваивается значение 1, а марже выигрыша меньше нуля (выигрыш игрока Б) присваивается значение 0.

После добавления функции бинарного выигрыша/проигрыша я сравнил три модели классификации для прогнозирования выигрышей игроков: логистическую регрессию, классификатор линейных опорных векторов (SVC) и наивный байесовский классификатор. Некоторые показатели производительности для каждого классификатора показаны ниже.

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

Однако нас больше интересует надежность предсказанных вероятностей, а не просто измерение того, сколько раз предсказанные вероятности приводили к правильному предсказанию выигрыша или проигрыша. Например, во всех раундах, где модель предсказывала 60% шансов на победу игрока А, действительно ли игрок А выигрывал в 60% случаев?

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

Точки данных на рисунке 6 получены путем дискретизации вероятностного интервала [0,1] на 10 интервалов и измерения доли фактических выигрышей игрока А, содержащихся в этом интервале.

Мы видим, что прогнозы вероятности из модели логистической регрессии почти идеально откалиброваны для истинной доли побед игрока А. Среднее абсолютное отклонение от пунктирной линии составляет 0,01 и очень мало меняется в диапазоне вероятностей. Это означает, что мы можем быть уверены в том, что прогнозы вероятности на основе модели логистической регрессии являются реалистичным представлением вероятности того, что игрок выиграет данный раунд. Однако следует учитывать, что изотоническая регрессия может улучшить калибровку SVC и наивных байесовских моделей.

Теперь, когда у нас есть модель, которая достаточно хорошо работает при прогнозировании выигрышей игроков с помощью логистической регрессии, в Части 2 мы увидим, как эта модель логистической регрессии может на самом деле применяться для информирования решений о выборе игроков!

Github-репозиторий для этого проекта.

Иллюстрации предоставил талантливый @stevenfritters.