Задача выбора системы проведения чемпионатов

Применение методов искусственного интеллекта в переборных алгоритмах

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

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

- вероятность, с которой побеждает сильнейший;

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

- оценка первой тройки, то есть сумма занятых тремя лучшими игроками мест (из нее удобно вычитать число 6).

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

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

А.В.Мосеев, underwood.narod.ru, 1999 год