Banner   Фото-рандеву   Majordomo
Специалисты по любому кондиционеру в г. Киеве и киевской области.

Вычисление итогов незавершенных турниров

Особенности алгоритма расчета

Для кого создан сайт www.TurnirLogic.com и написан этот текст, спросите вы. Для болельщиков! Для настоящих футбольных, хоккейных, баскетбольных и других болельщиков. Для тех, кто не только приходит на стадион, орет, свистит, ругает судью, а еще и заполняет турнирные таблицы, анализирует возможные исходы игр, прогнозирует. Его интересует, сможет ли любимая команда занять первое или, скажем, третье место, и как должны закончиться остальные встречи, чтобы это произошло.
Здесь рассказывается об особенностях и ограничениях алгоритма расчета итоговых показателей еще незавершенных турниров. Автор надеется, что читатель сообщит ему об обнаруженных ошибках и недостатках, предложит пути совершенствования расчета.
Ниже описаны алгоритмы расчетов итоговых мест команд при различных вариантах завершения еще не сыгранных игр.

История вопроса, или зачем это надо
Шел чемпионат Европы по футболу. До окончания групповых турниров командам оставалось сыграть последний тур. В группе, где играли Англия, Франция, Украина и Швеция, сложилась сложная ситуация. Могла ли Швеция пробиться в четвертьфинал, а Франция не пробиться? Могла ли Украина занять первое место? Чтобы ответить на эти вопросы , надо было придумывать различные варианты завершения последних игр. И я подумал, что далеко не каждому болельщику это легко сделать. А не написать ли программу, которая бы помогала в этом и показывала бы все возможные варианты распределения итоговых мест команд? На первый взгляд такая программа показалась не очень сложной, но в процессе разработки оказалось, что не все так просто.

Многие болельщики считают, что определять места команд в турнире, зная результаты игр, просто. Во многих случаях это так, но далеко не всегда.
Дело осложняется еще тем, что правила, действующие при розыгрышах турниров Чемпионата Мира, Лиги Чемпионов, Лиги УЕФА, довольно сложны. Не каждый болельщик (и даже спортивный журналист) в состоянии правильно рассчитать занятые командами места.
Рассмотрим следующий пример. Предположим, что в однокруговом турнире участвуют 4 команды. Со счетом 2:0 первая команда выиграла у второй, вторая – у третьей, а четвертая проиграла все 3 матча. Осталось сыграть последнюю игру. Текущая турнирная таблица имеет вид:

команда 1 2 3 4 в н п очки мячи места
Рога   2:0 : 1:0 20 0 6
3
3:0
2:0
1
Копыта 0:2 2:03:0 201 6
0
5:2
0:2
2
Молот : 0:2 7:0 1013 7:2 3
Кувалда 0:10:30:7   0030 0:11 4

Каковы могут быть итоговые результаты турнира? Может ли команда «Копыта» оказаться на 3 месте?
Попробуем разобраться. Понятно, что ничего не может спасти «Кувалду»: она останется на 4 месте, т.к. проиграла все встречи. Если «Молот» сыграет вничью или проиграет, то распределение мест сохранится:

команда 1 2 3 4 в н п очки мячи места
Рога   2:0 0:0 1:0 2017 3:0 1
Копыта 0:2  2:03:0 2016 5:2 2
Молот 0:0 0:2 7:0 1114 7:2 3
Кувалда 0:10:30:7   0030 0:11 4

А вот, если «Молот» выиграет, то распределение мест будут зависеть от того, сколько голов он забъет и пропустит. Чтобы выяснить, какие возможны итоговые результаты, надо перебрать различные варианты забитых и пропущенных голов. На сайте turnirlogic.com для рассматриваемого примера можно увидеть следующие варианты:

- игра закончилась со счетом 1:0 в пользу «Молота»:

команда 1 2 3 4 в н п очки мячи места
Рога   2:0 0:1 1:0 201 6
3
3:1
2:1
1
Копыта 0:2 2:03:0 201 6
3
5:2
2:2
2
Молот 1:00:2 7:0 201 6
3
8:2
1:2
3
Кувалда 0:10:30:7   0030 0:11 4

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

- игра закончилась со счетом 2:0 в пользу «Молота»:

команда 1 2 3 4 в н п очки мячи места
Рога   2:00:21:0 201 6
3
3:2
2:2
3 ?
Копыта 0:2  2:03:0 201 6
3
5:2
2:2
2 ?
Молот 2:00:2  7:0 201 6
3
9:2
2:2
1 ?
Кувалда 0:10:30:7   0030 0:11 4

Получаем неопределенность: три команды набрали одинаковое количество очков и в целом по турниру, и в играх между собой. Более того, в играх между собой каждая забила и пропустила одинаковое количество голов. В этом случае, наверно, придется бить послематчевые пенальти, учитывать рейтинг команд или тянуть жребий.
См. (c) Regulations of the UEFA Champions League 2012-15 Cycle. 2012/13 Season (страница 11, пункт 7.06)
     (c) Regulations of the UEFA Europa League 2012-15 Cycle. 2012/13 Season (страница 17, пункт 7.05)

- игра закончилась со счетом 3:1 в пользу «Молота»:

команда 1 2 3 4 в н п очки мячи места
Рога   2:01:3 1:0 201 6
3
0
4:3
3:3
1:3
2
Копыта 0:2  2:03:0 201 6
3
5:2
2:2
3
Молот 3:10:2  7:0 201 6
3
3
10:3
3:3
3:1
1
Кувалда 0:10:30:7  0030 0:11 4

В этом случае, как и в предыдущем, три команды набрали по 6 очков в целом и по 3 очка в играх между собой. Но «Копыта» забили меньше, чем «Рога» и «Молот», и поэтому опускаются на 3 место. А «Молот» победил «Рога» и поэтому занимает 1 место.

Конечно, можно придумать еще множество возможных результатов последней игры (например, 5:0, 99:85 и т.п.). Сайт turnirlogic.com предъявляет варианты с минимальным количеством забитых и пропущенных голов, но выдает все возможные итоговые распределения мест команд; и этого достаточно для анализа.

Постановка задачи
Для турниров, проводимых по круговой системе, программа должна уметь находить все варианты различных распределений мест команд по итогам турнира. Это могут быть соревнования по многим видам спорта (футбол, хоккей, баскетбол и др.). Программа должна настраиваться на правила конкретного турнира. За основу приняты правила футбольного чемпионата Евро-2012. Но должно предусматриваться изменение правил, например, начисление 2, а не 3 очков за победу, приоритет личных встреч, разницы забитых и пропущенных голов, количества забитых голов и т.п. Посетитель сайта должен иметь возможность задавать исходные данные для расчетов (названия команд, результаты уже сыгранных матчей) и запоминать это, чтобы дополнять сведения о новых играх, а не заново вводить все исходные данные. В качестве входных данных могут указываться также желаемые итоговые места или интервалы мест одной или нескольких участников турнира. Тогда программа должна рассчитывать и показывать только те варианты завершения турнира, которые удовлетворяют указанному запросу. Программа должна использоваться на турнирах, разыгрываемых в один или два круга, с ограниченным количеством участников и на конечных этапах турнира, когда уже известны результаты большинства игр, т.к. в других случаях количество вариантов итоговых результатов оказывается необозримым. Посетитель сайта (непривелигированный) может сохранять сведения об одном турнире, чтобы по ходу турнира дополнять их результатами новых игр. При каждом новом сохранении старые данные стираются.

Варианты итогов без учета количества забитых и пропущенных мячей
Для расчета мест команд нужно прежде всего выяснить, сколько очков они могут набрать. А количество очков не зависят от забитых и пропущенных голов, а только от количества побед, ничьих и поражений. Все равно, с каким счетом заканчивались игры, важно только, это были победы, ничьи или поражения. Поэтому для выяснения, сколько очков наберут команды, достаточно предположить,что игры заканчиваются только со счетом 1:0, 0:0 или 0:1. Если до завершения турнира осталось сыграть единственную игру, то, поскольку она может завершиться тремя результатами, то и возможных итоговых результатов турнира будет три. Если осталось 2 несыгранные игры, то различных итоговых результатов будет 9. Итак, количество различных вариантов итоговых результатов турнира (V) зависит от количества еще несыгранных игр (N) и равно трем в степени количество еще несыгранных игр: V = 3N. Программа перебирает все варианты завершения игр и получает все итоговые варианты завершения турнира. Казалось бы, если в запросе указаны конкретные желаемые итоговые места команд, то количество вариантов будет существенно меньше, однако сначала нужно получить все варианты, и только затем отфильтровать нежелаемые. Поэтому продолжительность расчетов в этом случае не уменьшается, и она при большом количестве вариантов настолько велика (несколько минут), что сервер может прервать вычисления, расценивая это как зацикливание - фатальную ошибку.

Места команд вычисляются следующим образом. Сначала подсчитывается количество побед, ничьих, поражений каждой команды, забитые и пропущенные голы и набранные очки. Составляется служебная таблица с этими данными, которая сортируется по очкам (по убыванию). В результате в первой строке таблицы оказывается команда, занявшая 1 место, во второй строке – 2 место, и т.д. Но это еще не окончательное распределение мест, потому что некоторые команды могут набрать одинаковое количество очков; и тогда надо учитывать результаты личных встреч, разницу и количество забитых голов, результаты матчей на выезде и др. Для каждой подгруппы команд, набравших одинаковое количество очков, производятся дополнительнвые вычисления. Служебная таблица дополняется столбцами, содержащими сумму очков внутри подруппы, разность голов, забитые голы, забитые голы в гостях, общее количество голов и побед в гостях. Строки таблицы, относящиеся к данной подгруппе, сортируются. Вот теперь порядок строк в служебной таблице определяет итоговые места команд.

Сокращение количества вариантов
Даже если не обращать внимание на продолжительность вычислений, само количество вариантов итогов турнира может стать так велико, что практически невозможно будет их анализировать. Один из путей сокращения количества предъявляемых вариантов является ориентировка на показ только вариантов,отличающихся распределением мест команд. Так, например, если найден вариант, при котором Англия занимает первое место, Франция – второе, Украина – третье, Швеция – четвертое, то другие варианты с таким распределением мест можно не показывать. Именно такой способ сокращения количества вариантов понимается под «показом сокращенного списка вариантов». Поскольку вариантов с одинаковым распределением итоговых мест может быть несколько, то нужно выбрать один их них для показа. Если любимая команда займет первое место при выигрыше всех оставшихся игр или, например, при ничьих, то более интересным представляется вариант с ничьими. Чтобы обеспечить показ таких нетривиальных вариантов, выбираются те варианты, у которых сумма среднеквадратичных отклонений очков, набранных командами, минимально. В случае, когда за победу начисляется 2 очка, среднее количество очков за игру равно (0+1+2) : 3 = 1, а когда за победу начисляется 3 очка, то (0+1+3) : 3 = 1.666. Выбор варианта с минимальным отклонением от среднего обеспечивает показ самых неочевидных результатов завершения турнира.
Еще один способ сокращения количества рассчитываемых вариантов при их большом количестве – это просто отказ от расчетов, когда количество вариантов превышает некую критическую величину. Тогда пользователю предъявляются только те варианты, которые программа успела обработать.

Дополнительные варианты для подгрупп с одинаковыми очками Если две команды наберут одинаковое количество очков, а между собой сыграли вничью, то количество забитых и пропущенных мячей определяет занятые ими места. До сих пор предполагалось, что будущие игры могут закончится только со счетом 1:0, 0:0 или 0:1. Но ведь при другом счете могут измениться и места этих команд. Нужно найти такой минимальный счет, при котором это случится. Возможны несколько ситуаций:

А) Разница забитых и пропущенных голов у этих двух команд одинакова. Решающим становится количество забитых командами голов. Нужно сделать так, чтобы количество забитых голов второй команды превысило количество забитых голов первой команды. Для этого надо в любой будущей игре второй (отстающей) команды с другой (не с первой) командой увеличить количество забитых и пропущенных голов на одну и ту же величину. Так, например, если первая команда забила 5 голов, а вторая – 4, то достаточно, чтобы в какой-то игре с третьей командой она выиграла ее не со счетом 1:0, как предполагалось ранее, а со счетом 3:2. Количество забитых голов второй командой окажется больше, чем у первой. И теперь вторая команда превзойдет первую.

В) Разница голов первой команды больше разницы голов второй команды. В этом случае нужно сделать разность мячей второй команды равной разности мячей первой команды, а количество забитых голов увеличить, чтобы оно превысило количество забитых голов первой команды. Для этого надо найти победу второй команды над какой-то третьей и изменить там количество забитых и пропущенных голов. Количество забитых голов надо увеличить на величину, равную R1- R2+S1–S2+2, а количество пропущенных – на S1–S2+1, где R1, R2 – разница забитых и пропущенных голов, а S1, S2 –количество забитых голов первой и второй командами. Если будущих побед не предвидится, то нужно искать будущие поражения первой команды над какой-то третьей и увеличить там количество пропущенных голов на R1- R2+S1–S2+2, а количество забитых – на S1–S2+1. И вторая команда превзойдет первую.

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

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

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


© 2012 Y.Belilovskyi «Вычисление итогов незавершенных турниров» Контакт
О алгоритме расчета

29.12.2012 Футбол на Soccer.ru: Новости футбола России и Европы онлайн, Евро кубки и чемпионаты Live