Использованная модель

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

Из двух шахматистов более сильным считается тот, который чаще у другого выигрывает, чем проигрывает ему. Тем не менее, более сильный шахматист может проиграть менее сильному. Существует подобная вероятность и для игровых программ. Положим, что всем участникам чемпионата можно найти объективные оценки силы их игры, как числа в диапазоне от 0 до 1. Будем обозначать F_n такую оценку силы n-го игрока. Положим также, что эти оценки удовлетворяют следующим условиям. Если игрок n не слабее игрока m, тогда F_n≥F_m, при этом вероятность того, что партия будет выиграна игроком n, равна 0,5, если F_n-F_m=0, равна некоему числу A из отрезка [0,5..1], если F_n-F_m=1, и линейно зависит от разности F_n-F_m на интервале 0..1.

Оценки F_n и число A зависят от набора игроков. Число A характеризует близость по силе игры игроков в группе. При А=1 самый сильный игрок может постоянно выигрывать у самого слабого. При А=0,5 все игроки играют наравне. Распределение оценок F_n по отрезку [0..1] никак не ограничивается, но сами оценки выбираются так, чтобы занять весь отрезок (в реализации использовано равномерное распределение).

Таким образом, мы описали модель группы игроков, участвующих в чемпионате. Эта модель обладает основными свойствами реальной системы, хотя и упрощена. Ее немаловажным преимуществом является легкость в программировании. Аналогом используемых в модели оценок F_n в жизни можно считать рейтинг, который вычисляют для крупных шахматистов. В данном случае группа игроков весьма велика, оценка игрока определяется отношением его рейтинга к самому высокому рейтингу из имеющихся. Остается только правильно подобрать параметр А. Разница заключается в том, что наши оценки F_n мы полагаем абсолютно объективными, в то время как рейтинг шахматистов зависит от их участия и успехов в соревнованиях.

Итак, определена процедура моделирования игроков, партии между двумя из них и нахождения победителя в ней.

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

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