Теория
Прочитав вот это было решено найти практическое применение механизма гадалки Шеннона. Если рассматривать человека как конечный автомат, то входные данные и исходное состояние полностью определяют текущие состояние и выходные данные. Сразу скажу демо игры и ее исходников нет.
Сама игра состоит в выборе и показе сопернику одного из трех вариантов: колодец(камень), ножницы и бумага. Причем, ножницы тонут в колодце(тупятся о камень), бумагу режут ножницы, колодец накрывается бумагой(камень оборачивается бумагой). Обозначим:
- 0 — колодец(камень)
- 1 — ножницы
- 2 — бумага
Предположим, что игра ведется достаточно долго, чтобы можно было собрать статистику, но не так долго, чтобы человек начал изменять свое поведение, раскусив алгоритм предсказания. Имеем последовательность пар чисел: (0, 1) (0, 2) (2, 2) (2, 0)..., где первое число показал бот, второе — человек. Чтобы определить победителя в паре, сравним числа. (0 — 1) % 3 = 2, значит человек проиграл, (0 — 2) % 3 = 1, значит человек победил, (2 — 2) % 3 = 0, ничья. Обозначим n — длина последовательности чисел из пар. Число возможных последовательностей равно 3^n. При n = 5 получится 243 варианта, что много больше 32 для двух вариантов выбора. Ясно что получить все варианты в течение одной игры маловероятно, поэтому усовершенствуем гадалку. Не каждый выбор человек делает опираясь на все n элементов последовательности чисел, некоторые ее элементы он игнорирует. Назовем такие элементы пустыми.
Итого, входные данные для одного из вариантов предсказания: (0, 1, Ø, 2, 0): 1. Числа в скобках — чередующиеся предыдущие выборы бота и человека, число после двоеточия текущий выбор человека. Опираясь на предположение предсказуемости человека, варианты, например, (0, 1, 2, 2, 0): 1 и (0, 1, 2, 2, 0): 2 с большой вероятностью не будут одинаково вероятны. Подсчитав, какой из них бывает чаще, можно получить более вероятный выбор человека. Но именно такой вариант предпоследовательности на протяжении игры может не повторится, чтобы это учесть и нужны пустые элементы. Запись (Ø, Ø, Ø, 2, 0): 1 означает, что после пары (2, 0) человек выбирает 1, а запись (Ø, 1, Ø, 2, 0): 1 — что после пары (2, 0) человек выбирает 1, если до нее бот выбирал 1. Всего таких записей для каждого рауда игры нужно считать 2^n, перебирая все сочетания чисел в записи, заменяя все не попавшие в него на Ø.
Всего записей будет 3 * (3 + 1)^n. Три записи для текущего выбора человека (колодца, ножниц или бумаги) умножаем на число вариантов предшествующей последовательности с учетом дополнительного варианта — пустого, несущественного выбора.
Массив записей позволяет делать обобщения, например, человек чаще выбирает колодец, то счетчик записи (Ø, Ø, Ø, Ø, Ø): 0 должен содержать большее значение, чем (Ø, Ø, Ø, Ø, Ø): 1 или (Ø, Ø, Ø, Ø, Ø): 2. Решив проблему с обобщением можно взять n значительно больше, его значение ограничивается размером памяти и временем на ход бота.
Каждый раз когда человек делает выбор, бот изменяет 2^n значения, а когда нужно предсказать, просто складывает значения 2^n счетчиков, соответствующих предыстории для каждого из трех возможных текущих вариантов выбора человека, и выбирает больший. Если значений счетчика нет (в начале игры), то выбирает случайный. Затем прибавляет 2 по модулю 3, чтобы получить свое значение для победы.
Интерес представляет не сам бот, а сравнение профилей игры разных людей, как представителей различных социальных групп, какую информацию можно получить о человеке, просто сыграв с ним (хотя и очень долго).
Для расчета степени удаленности профилей друг от друга можно воспользоваться оценкой, похожей на критерий Пирсона. Только нас интересует не вопрос: соответствует ли выборка распределению, а степень или «вероятность» соответствия, если рассматривать один массив счетчиков A1 как данные выборки, а второй A2 как его возможное распределение.
d_j = sum( (A1[x_1, x_2..., x_i,… x_n][x_0] — A2[x_1, x_2..., x_i,… x_n][x_0])^2/A2[x_1, x_2..., x_i,… x_n][x_0] ), сумма берется по всем счетчикам, соответствующим записям с j не пустыми значениями, x_0 — возможный текущий выбор человека(значения от 0 до 2), x_i имеют значения от 0 до 3, так как одно из значений обозначает пустое, пусть это будет 3.
Поскольку расстояние должно быть одинаковым в обе стороны, а также потому что значительная часть массива будет содержать нули, знаменатель лучше заменить на значение счетчика соответствующей записи, будь выбор человека случайным S / 3 ^ j, где S — количество сыгранных игр, j — количество не пустых значений в записи.
Мера дальности будет вероятностью несовпадения распределений А1 и А2. Для распределения хи квадрат важно число степеней свободы, то есть размерность распределения. Поскольку число степеней свободы различно и соответствует нашему j, просто сложим значения соответствующей функции распределения для каждого d_j:
p = sum( F_j(d_j) ), где p — мера дальности, сумма берется по j, F_j — функция распределения хи квадрат для j степеней свободы.
Для проверки алгоритма гадалки Шеннона небольшая демонстрация.
Алгоритм гадалки кажется слишком примитивным, но он быстр, а его видоизменение для игры хорошо параллелится.
Ранее упоминалось в статье Иерархическая Темпоральная Память (НТМ) и алгоритмы ее самообучения, что некоторые нейроны можно представить как элементы, предсказывающие собственную активность.
Был пост Reddwarf для создания Java-сервера на примере онлайн-игры «Камень-ножницы-бумага»: Сервер и Reddwarf на примере онлайн-игры «Камень-ножницы-бумага»: Клиент.
Реализация бота, подобного описанному выше(ссылка из комментариев).
