Использованная модель
Применение методов искусственного интеллекта в переборных алгоритмах
Из двух шахматистов более сильным считается тот, который чаще у другого выигрывает, чем проигрывает ему. Тем не менее, более сильный шахматист может проиграть менее сильному. Существует подобная вероятность и для игровых программ. Положим, что всем участникам чемпионата можно найти объективные оценки силы их игры, как числа в диапазоне от 0 до 1. Будем обозначать Fn такую оценку силы n-го игрока. Положим также, что эти оценки удовлетворяют следующим условиям. Если игрок n не слабее игрока m, тогда Fn≥Fm, при этом вероятность того, что партия будет выиграна игроком n, равна 0,5, если Fn-Fm=0, равна некоему числу A из отрезка [0,5..1], если Fn-Fm=1, и линейно зависит от разности Fn-Fm на интервале 0..1.
Оценки Fn и число A зависят от набора игроков. Число A характеризует близость по силе игры игроков в группе. При А=1 самый сильный игрок может постоянно выигрывать у самого слабого. При А=0,5 все игроки играют наравне. Распределение оценок Fn по отрезку [0..1] никак не ограничивается, но сами оценки выбираются так, чтобы занять весь отрезок (в реализации использовано равномерное распределение).
Таким образом, мы описали модель группы игроков, участвующих в чемпионате. Эта модель обладает основными свойствами реальной системы, хотя и упрощена. Ее немаловажным преимуществом является легкость в программировании. Аналогом используемых в модели оценок Fn в жизни можно считать рейтинг, который вычисляют для крупных шахматистов. В данном случае группа игроков весьма велика, оценка игрока определяется отношением его рейтинга к самому высокому рейтингу из имеющихся. Остается только правильно подобрать параметр А. Разница заключается в том, что наши оценки Fn мы полагаем абсолютно объективными, в то время как рейтинг шахматистов зависит от их участия и успехов в соревнованиях.
Итак, определена процедура моделирования игроков, партии между двумя из них и нахождения победителя в ней.
Теперь рассмотрим вопрос о том, как же получить требуемые оценки систем проведения чемпионатов. Используя описанную выше модель игроков и партий, можно также создать модель чемпионата. В результате появится возможность сравнить, места, которые заняли игроки, с тем порядком, в котором идут их объективные оценки. В силу того, что характеристики модели описываются вероятностно, то результаты единичного чемпионата не будут информативными. Для получения исчерпывающей информации о системе необходимо многократное проведение чемпионата. Такое многократное проведение чемпионата по одной системе будем называть серией. Численные оценки системы в таком случае будем вычислять как среднее арифметическое от оценок всех чемпионатов в одной серии. Точность полученных оценок будет зависеть от количества чемпионатов в серии, поэтому окупит себя простота выбранной нами модели.
А.В.Мосеев, underwood.narod.ru, 1999 год