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

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

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

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

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

Итак, опишем модель, построенную на основе данного предположения. Параметром данной модели служит дисперсия используемой нормально распределенной случайной величины. Эта величина соответствует отклонению, с которым заполняется таблица личного соотношения сил игроков. В отличие от модели игроков без учета нетранзитивности, теперь вероятность выигрыша игроком i партии у игрока j определяется не разностью показателей их силы, а записью (i, j) в упомянутой таблице. В остальном модель не менялась.

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

В результате работы обновленной программы получены таблицы статистических данных. В них по столбцам перечислены четыре оценки точности системы, а по строкам - использованные значения дисперсии используемой случайной величины. Причем, символ "-" соответствует результатам тестирования без отклонения в личном соотношении сил, то есть когда дисперсия фактически равна 0. Еще раз напомним, что исследована только швейцарская система, как избранная для использования в алгоритме самообучения. Каждая таблица соответствует некоторому числу участников (из набора - 8, 16, 32, 64).

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

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