Описание алгоритма игры heshby

Описание игры

На каждом ходе человек задумывает один из двух вариантов (чет/нечет) и сообщает о своем выборе программе путем нажатия одной из двух клавиш (+/-). Одновременно с этим программа формирует собственный прогноз хода человека на основе статистики его предшествующих действий. Задача программы — наиболее эффективно предсказывать действия человека; задача человека — эффективно противодействовать предикции. В зависимости от результата хода точка на экране смещается на одну позицию влево (успех программы) или вправо (успех человека). Победой одного из противников (программы или человека) считается достижение точкой края экрана (левого или правого соответственно).

Основой программы является популяция «демонов», каждый из которых является простейшим адаптирующимся стохастическим автоматом. Популяция демонов управляется «супервизором».

Описание демона

Структура демона определяется двумя числами — (m,n). (m,n)-демон использует для прогноза m последних ходов человека и n последних ходов программы. Демон представляет собой (m+n+1)-мерный массив D вещественных чисел. Пусть последние m ходов человека образуют вектор (h_0, \ldots, h_{m-1}), а последние n ходов программы образуют вектор (p_0, \ldots, p_{n-1}). Каждый ход представляется числами 0 (чет) или 1 (нечет). Пусть теперь

a_j = (p_0, \ldots, p_{n-1}, h_0, \ldots, h_{m-1}, j),

d_j = D[a_j],

где j принимает значения из множества \{ 0, 1 \}. Если d_0 > d_1, то считается, что демон рекомендует программе ход 0, если же d_1 > d_0, то рекомендуемым ходом считается 1. Если d_0 = d_1, то выбирается ход 0. Первоначально элементы массива D установлены в ноль. После получения информации об истинном ходе h_m человека демон корректирует массив D, добавляя к элементу

D[p_0, \ldots, p_{n-1}, h_0, \ldots, h_{m-1}, h_m]

величину

(1+e_1)^k,

где e_1 — наперед заданное небольшое число, а k — номер хода.

Описание супервизора.

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

(1+e_2)^k,

где e_2 — наперед заданное небольшое число, а k — номер хода.

page_revision: 10, last_edited: 1248112508|%e %b %Y, %H:%M %Z (%O ago)
EditTags History Files Print Site tools+ Options
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License