Как составить расписание матчей по футболу

Руководитель направления систем бизнес-аналитики BIA Technologies Станислав Воронин рассказывает, как математическая модель решает кому, когда и с кем играть в следующем сезоне, и размышляет о дивном новом будущем спорта.

Математическая оптимизация расписаний

«Ну кто додумался поставить в сетку выездную встречу с «Ювентусом» на этот вторник?! Ребята только отыграли сложнейший матч на домашнем поле!» — восклицаете вы в гневе. И напрасно: расписание составил не человек, а компьютер, и сделал он это на основе сложнейшей математической модели. Как? Сейчас расскажу.

Разумеется, речь пойдёт не о любительских соревнованиях между студенческими командами, а о составлении расписаний для высших спортивных лиг (Российская премьер-лига, итальянская Серия А, НБА, КХЛ и т.д.). Сетка для матчей такого уровня должна учитывать столько ограничений, что составить расписание вручную просто невозможно, поэтому лиги поручают это ответственное дело компьютеру.

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

1. Предпочтительно, чтобы матчи проводились по выходным или в будни по вечерам (так их увидит больше зрителей); самые зрелищные — в телевизионный прайм-тайм.

2. Нежелательно, чтобы в одно и то же время параллельно проходило несколько популярных матчей самых титулованных команд (болельщикам придётся переключаться между телеканалами).

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

4. Домашние и выездные матчи должны чередоваться; нельзя проводить все домашние игры скопом в начале сезона (так как играть на родном стадионе традиционно легче, это создаст ложное ощущение превосходства).

5. Необходимо учитывать часовые пояса, джетлаги и время на переезд спортсменов из одного города/страны в другую.

6. Домашняя и выездная игры между двумя соперниками должны быть разнесены как можно дальше в расписании.

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

8. Желательно не сводить явных фаворитов в первые две недели сезона (это сведёт на нет всю интригу).

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

10. Сетка должна учитывать доступность стадионов под другие мероприятия.

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

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

За календарь Российской футбольной премьер-лиги с 2019 года отвечает алгоритм, разработанный НИУ ВШЭ. Если вам интересны детали, в интервью изданию «Спорт-Экспресс» сотрудники лаборатории исследований спорта рассказали о своей методологии и российской специфике. Так, например, нежелательно проводить пять матчей в одном туре в Москве, поскольку это создаст сложности для МВД. Кроме того, в большинстве регионов страны зимой не поиграешь в футбол на открытом поле.

Искусственный интеллект vs. магия спорта

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

Во многих случаях компьютер действительно может заметить неочевидные взаимосвязи и предложить оптимальное решение. Вот интересный пример: защитник «Арсенала» Эктор Бельерин в начале сезона 2021/2022 перешёл на правах аренды в испанский клуб «Реал Бетис». Чтобы выбрать идеальный для себя вариант (по слухам, среди них были такие тяжеловесы как «Барселона», «Интер» и «ПСЖ») Бельерин обратился за помощью в консалтинговую фирму Analytics FC. Эксперты компании создали математическую модель специально под футболиста.

Алгоритм проанализировал множество факторов и подсказал, что текущая схема 4-3-2-1, которую предпочитает тренер «Реал Бетис», лучше всего сочетается со стилем игры Бельерина. Кроме того, данные показали, что команда нуждается в крайнем защитнике после трансфера Эмерсона, что точно не позволит Бельерину скучать на скамейке запасных. Наконец, игра в испанском клубе должна увеличить шансы футболиста на попадание в национальную сборную Испании к ближайшему Чемпионату мира. Эксперты говорят, что это первый случай в истории, когда игрок принял решение о трансфере при помощи аналитики.

Но есть и обратная сторона медали. Действительно ли мы готовы отдать на откуп ИИ принятие абсолютно всех решений? Дал бы он шанс, скажем, юному Лионелю Месси с его небольшим ростом и проблемным здоровьем, или сходу посчитал бы его бесперспективным форвардом? А хороший тренер — это просто «оптимизатор», который сравнивает статистику сутками напролёт, или харизматичный тактик, психолог и родитель в одном лице? Может ли условного Теда Лассо полностью заменить компьютер?

В 2018 году вышел документальный фильм «В поисках величия», который задавался примерно такими вопросами. Авторы поговорили с такими легендами спорта как Пеле, Уэйн Гретцки и Джерри Райс, и пришли к выводу, что искусственный интеллект лишил бы нас многих «неочевидных» звёзд. Один из примеров, приводимых в фильме, — чемпион мира по боксу Рокки Марчиано. Он был ниже большинства соперников и не обладал большим размахом рук. Но эти «недостатки» помогли ему найти свой собственный подход: он наклонялся ниже и бил в упор на короткой дистанции. Марчиано не проиграл ни одного поединка в своей карьере и считается одним из лучших боксёров в истории.

Тем не менее сейчас спорт движется в направлении всё большей автоматизации в принятии решений. Насколько это рационально — покажет время. Но мне бы всё-таки хотелось, чтобы часть решений осталась за людьми. В конце концов, мы любим спорт за человеческие моменты, красивую игру, командный дух, эпизоды невероятной удачи и «руку Бога». Если оставить выбор за компьютером, спорт перестанет быть искусством. А вы что думаете?

Можно еще методом грубой силы. Случайно выбирая пары и проверяя, что они еще не играли.

Т.е. цикл по турам. Выбираем пару. Упорядочиваем ее по номеру команд. Смотрим (в хэше), если их нет там, то добавляем в хэш, в расписание и уменьшаем счетчик игр в туре (его начальное значение известно). Как счетчик обнулится переходим к новому туру.

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

UPDATE

Другой вариант просто посчитать по турам. Я сделал на C. Судя по результатам работы алгоритм не оптимален для количества команд не равным степени 2-х. Но он работает

/*
  avp 2012

  Таблица чемпионата (один круг) 
  n команд (аргумент командной строки)

  Составление расписания по турам
  Количество туров вычисляется в программе

  В stdout выводится список туров с парами команд 
  и квалратная таблица номеров туров для команд
 */

#include <stdio.h>
#include <stdlib.h>

struct cmd {  // данные каждой команды
  int ic,     // номер команды (с нуля)
    ng;       // количество уже проведенных игр (init 0)
};

/*
  Сортировать команды по возрастанию проведенных игр
  (у кого меньше в начало списка)
  n - размер списка команд
 */
void
sort (struct cmd a[], // список команд
      int n)
{
  int i, j;

  for (i = 1; i < n; i++) {
    struct cmd tt = a[i];
    for (j = i; j > 0; j--) {
      if (a[j].ng >= a[j-1].ng)
        break;
      a[j] = a[j-1];
    } 
    if (j < i)
      a[j] = tt;
  }

}

main (int ac, char *av[])
{
  int n = 10;  // количество команд в чемпионате
  if (ac > 1)
    if ((n = atoi(av[1])) < 2)
      n = 10;

  int game[n][n];    // в каком туре играют j,k (туры с 1, номера команд с 0)
  int tot = (n*(n-1))/2; // общее количество игр в круге
  int cal[tot][n];   // с кем в туре i играет команда j (все индексы с 0)

  int i,j,k, jc, kc, // разные индексы
    ng, // количество уже проведенных игр в круге
    nt; // количество туров (вычисляетя в ходе составления расписания)

  // инициализация таблицы игр в круге
  for (i = 0; i < n; i++) { 
    for (j = 0; j < n; j++) {
      game[i][j] = 0;  // здесь будет в каком туре играют команды i,j
    }
    game[i][i] = -1;
  }
  // инициализация таблицы по турам (количество туров с большим запасом)
  for (i = 0; i < tot; i++) 
    for (j = 0; j < n; j++)
      cal[i][j] = 0; /* здесь будет с какой командой (номер с 1)
                        в туре i (индекс с 0) играет команда j (индекс с 0)
                     */

  struct cmd a[n]; // список команд
  for (i = 0; i < n; i++) {
    a[i].ic = i;
    a[i].ng = 0;
  }

  // собственно вычисления
  for (i = ng = 0; ng < tot; i++) { // увеличиваем туры (i) пока не сыграли
                                    // все матчи круга (ng)
    sort(a,n); // это для равномерности (?) по турам
    for (j = 0; j < n; j++) { // перебираем команды из списка
      jc = a[j].ic;
      if (cal[i][jc])
         continue;   // уже играла в этом туре
      for (k = 0; k < n; k++) { // перебираем команды из списка
         kc = a[k].ic;
         if (kc == jc)
            continue; // сама с собой
         if (cal[i][kc] || game[jc][kc])
            continue; // kc уже играла в туре или играла раньше с jc
         /*
           kc и jc еще не играли. Пусть сыграют в этом туре
           увеличим количество проведенных игр и заполним таблицы
         */
         ng++;
         a[jc].ng++;
         a[kc].ng++;
         cal[i][kc] = jc+1;
         cal[i][jc] = kc+1;
         game[jc][kc] = i+1;
         game[kc][jc] = i+1;
         break;
      }
    }
  }
  nt = i; // это сколько туров получилось.

  // печать игр по турам
  printf ("ntours %dn",nt);
  for (i = 0; i < nt; i++) {
    printf ("tour %dn",i+1);
    int t[n];
    for (j = 0; j < n; j++)
      t[j] = 0;
    for (j = 0; j < n; j++) {
      if (k = cal[i][j]) {
        if (!t[k-1]) {
        // printf ("%2d:%2d ",j+1,k);
           printf (" %c : %c  ",'A'+j,'A'+k-1);
           t[j] = t[k-1] = 1;
        }
      }
    }
    printf ("n");
  }

  // печать квадратной таблицы туров для команд
  printf ("ntours tablen");
  printf ("    ");
  for (i = 0; i < n; i++)
    //    printf ("%2d ",i+1);
    printf (" %c ",'A'+i);
  printf ("n");
  for (i = 0; i < n; i++) {
    //    printf (" %2d ",i+1);
    printf (" %c  ",'A'+i);
    for (j = 0; j < n; j++) {
      printf ("%2d ",game[i][j]);
    }
    printf ("n");
  }
  printf ("n");
}

Уважаемый @namak, Вы уж извините меня за программу на Си. Я понимаю, что Вы спрашивали PHP с SQL, но Си я владею значительно лучше, а алгоритм надеюсь будет понятен.

Алгоритм (операторы) собственно находится между комментариями

// собственно вычисления

и

// печать игр по турам

UPDATE 2

Функция перемешивающая команды (вместо sort())

void
shuffle (struct cmd a[], int n)
{
  int i, j;
  static int first = 1;
  if (first) {
    first = 0;
    srand(time(0));
  }

  for (i = 0; i < n; i++) {
    struct cmd tt;
    j = rand()%n;
    tt = a[j];
    a[j] = a[i];
    a[i] = tt;
  }

}

Алгоритм составления расписания матчей

27.03.2015, 12:50. Показов 2942. Ответов 5

0