Чёт-нечёт

В данной статье описан метод прогнозирования ходов человека в игре «Чёт-нечёт», реализованный программно в рамках курсовой работы по Информатике.

Суть игры проста: человек загадывает очередное двоичное значение (например, 0 или 1), а компьютер пытается его угадать на основе предыдущих ходов. Оптимальной стратегией для человека было бы использование независимых случайных чисел (непредсказуемых по определению). Но люди, пытаясь «убежать» от компьютера, чаще всего отталкиваются от истории последних ходов – а значит, становятся отчасти предсказуемыми.

Метод прогнозирования

Прогнозирующие модели

Прогноз основывается на анализе предыдущих ходов или других факторов. Основным методом прогнозирования является анализ контекстной зависимости. Взяв за контекст последние n ходов, просматриваем, сколько раз после данной комбинации встречалась единица и сколько всего раз встречалась эта комбинация. Отношение этих величин дает нам оценку вероятности выпадения единицы. Это прогноз контекстной модели n-го порядка.

Смешивание прогнозов

Для расчета результирующей оценки вероятности используется смешивание оценок, обеспеченных моделями.
Результирующая оценка вероятности вычисляется по формуле:
<math>p=pw_1+p_2w_2+...+p_nw_n</math>,
<math>w_1+w_2+...+w_n=1</math>,
где <math>p</math> - результирующая вероятность; <math>p_1, p_2,..., p_n</math> - вероятности даваемые моделями; <math>w_1, w_2,..., w_n</math> - веса моделей.
Т.е. задача прогнозирования сводится не только к разработке моделей, но и к определению весов для смешивания.

Метод смешивания Е.Д. Шелвина

Суть метода смешивания Е.Д. Шелвина заключается в адаптивной корректировке весов после каждого хода на основе скорректерованной результирующей оценки вероятности.

Смешивание двух прогнозов

Пусть есть две прогнозирующие модели прогнозы которых смешиваются с коэффициентами <math>w</math> и <math>(1-w)</math> и дают результатирующую оценку вероятности <math>p=wp_1+(1-w)p_2</math>. Выражается вес:<math>w=(p-p_2)/(p_1-p_2)</math>
На основе <math>p</math> делается прогноз хода человека.
Пусть <math>a</math> - ход человека, <math>a\in\{0,1\}</math>. Е.Д. Шелвин предлагает рассматреть <math>p</math> как статистическую вероятность равную <math>N/M</math>, где <math>M</math> - общее число ходов, <math>N</math> - число ходов с <math>a</math> = 1. Скоректировать <math>p</math> с учетом последнего <math>a</math> можно по формуле:
<math>p=p(1-1/M)+a/M</math>.
Тогда можно скорректировать и значение <math>w</math>:
<math>w=(p-p_2)/(p_1-p_2)</math>.

Смешивание большего числа прогнозов

Для расчитывания большего числа моделей необходимо:

1. разбить вероятности на пары
   
2. вычислить в каждой паре собственную результирующую вероятность и веса
   
3. проделывать шаги до тех пор, пока не останется одна результирующая вероятность.
   

Если же количество моделей не кратно двум, то получается что некоторые вероятности не участвуют в смешивании на определенных шагах. Из-за этого, алгоритм программы становится сложным для написания. Наилучший вариант будет при использовании количества моделей <math>2^n</math>. В нашем случае, этих моделей 16. Изначально веса равны 0,5.

Детали реализации

При разработке программы использовались 16 моделей:

1. Простой контекстный анализ с глубиной 0-7 (глубина 0 означает оценку общего количества единиц и нулей)
   
2. Контекстный анализ с концентрацией. В отличии от простого анализа, порядок нулей и единиц не важен. Глубина 2-6
   
3. Оценка пси. фактора. Оценивается поведение человека на то, как отвечает компьютер на его ход.
   
4. Случайная модель. Данная модель дает случайную вероятность в пределах <math>p\in(0;1)</math>
   
5. Равновероятность. Данная модель добавлена для исключения ситуации нулевой вероятности при оценке качества угадывания[1].
   

Примеры:
История ходов человека: 101001010001011010110
История прогнозов: 001010011001000101010

Простой контекстный анализ

Глубина контекста	0	1	2	3	4	5	6	7
Оценка вероятности выпадения единицы	10/21	7/10	4/6	1/1	1/1	1/1	1/1	0/1

Контекстный анализ с концентрацией

Глубина контекста	2	3	4	5	6
Оценка вероятности выпадения единицы	6/11	2/7	4/9	2/5	1/3

Оценка пси. фактора

Последний ход человека	0	1	0	1
Последний прогноз	0	0	1	1
Оценка вероятности выпадения единицы	4/6	2/10	3/5	0/4

Каждая модель оценивалась на пригодность и было замечено, что модель №1 (глубина контекста 0) всегда плохо угадывала. Было решено проинвертировать (пересчитать вероятность на <math>1 - p</math>) её. Таким образом, получился положительно угадывающая модель.
В первой версии программы в качестве корректировки весов использовалась "бальная" система весов, при которой модели которая угадала и показала большую вероятность прибавляют 1 балл. Для расчета весов баллы всех моделей суммируются и эта сумма делится на количество баллов каждой модели. Таким образом мы получаем нормализованные веса:
<math>w_1+w_2+...+w_n=1</math>.
Во второй версии программы в качестве корректировки весов использовался расмотренный выше метод.

Руководство пользователя

В центре находится таблица, на которой изображены значения советников и их веса, а также результирующая вероятность.

Снизу справа находятся функциональные кнопки:

1. Сохранить игру. Текущая история игры человека сохраняется в файл wes.txt как новая строка.
   
2. Очистить. Все вероятности становятся 1/2, а веса остаются прежними.
   
3. Очистить все. Все вероятности и веса становятся 1/2.
   
4. Запуск. Запускается серия игр из файла wes.txt с сохранением весов предыдущих игр.
   
5. Запуск с очисткой. Запускается серия игр из файла wes.txt. При каждой новой игре происходит полная очистка.
   

Результаты запусков отображаются в виде статистики изображенной в таблице снизу слева.

Результаты

Было сыгранно и сохранено в файл 17 игр. По ним была собранна статистика изображенная на рисунках 1 и 2:

Рис. 1 - Результаты тестирования с очисткой весов

Рис. 2 - Результаты тестирования без очистки весов

Графики отображают отношение угаданных испытаний к их общему числу. На диаграммах изображены отношения обьема сжатых данных на количество данных которое не было сжато.

Как видно из результатов, качество предсказаний очень близко к значению 50%, т.е. практически непредсказуемо. Это вполне обьяснимо, т.к. ход человека, при попытке обмануть компьютер, очень близок к абсолютно слючайному событию.