Дружественная для человека стратегия

Агниашвили Даниил Владиславович

Иванова Елизавета Федоровна

Математический подход к игре «Быки и коровы»

Аннотация

В этой статье описывается и исследуется игра «Быки и коровы». Затем обсуждается упрощенный алгоритм, который может быть использован людьми во время игры. Расширенная версия алгоритма, использующая вычислительную мощность компьютера, помогает решить задачу быстрее и эффективнее. Наконец, были проведенынебольшие испытания на людях для изучения эффективностиалгоритма.

Введение

В игре «Быки и коровы» играют 2 игрока, один из которых загадывает секретный код, а другой –угадывает за наименьшее количество попыток.После каждой попытки задумавший игрок выставляет «оценку», указывая количество угаданного без совпадения с их позициями (количество «коров») и полных совпадений (количество «быков»).

История

«Быки и коровы» - это логическая игравыпущенная в игре Mastermind. Первая компьютерная программа, была написана Франком Кингом в Университете Кембриджа[3], ибыла реализована Дж. М. Гроховым в Массачусетском технологическом институте. Пользователю приходилось вводить значения, а в программе использовался простой алгоритм, разработанный доктором Лармутом для определения значений.Обычно определяемая и решаемая проблема исследования включает в себя максимум 5 ячеек, которые нужно угадать.

Предыдущие исследования

Методы оптимизации, применяемые к любым дедуктивным играм с двумя игроками, имеют две цели:

1. Сведение к минимуму максимального количества догадок, которое может потребоваться для завершенияигры.

2. Сведение к минимуму среднего количества догадок, которое потребуется, чтобы угадать случайным образом назначенный номер.

Известные теоретические результаты для стандартной игры на 4 ячейки:

• Минимальная ожидаемая длина игры составляет 5.213, доказал ТетсуроТанака в 1996 году [4].

• Максимальное количество догадок, в которых число может быть правильновыведено 7, доказано несколькими исследователями [2].

В первую очередь мы используем две стратегии, простую и расширенную. Простую стратегию можно легко объяснить и использовать людям, расширенная же стратегия требует вычислительной мощности.Здесь мы используем концепцию обрезки. Обрезанный набор - это тот, где используетсярезультаты угадывания, невозможные комбинации устранены. Например,если код 026, и мы догадываемся, что 602, мы получаем ответ <0b, 3c>, авозможности обрезаны только {026, 260}.

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

Начальный объект создается с помощью <0b, 0c>. Каждая цифра угадывания повторяется и проверяется на наличие в коде. Если цифра присутствует, мы проверяем, находится ли она в правильном месте. Если он находится в правильном месте, количество быков увеличивается, в противном случае количество коровы увеличивается.

Идея ответа может быть понята как хеш-функция, аналогичная MD5 / SHA2, но менее сложная, так как это односторонняя функция. Следовательно, мы используем простой подход грубой силы для отсечения набора. Мы тестируем все ответы от всех возможных перестановок и сравниваем их с фактическим ответом. Мы добавляем все перестановки, которые дают соответствующий ответ новому набору, который мы доставляем как завершенный набор. Кодописанниже

Дружественная для человека стратегия

Важно то, что необходимо предположить такие наборы, которые исключат наибольшее количество возможных значений. Например, угадывая номер 798, выбирается set {098, 198, 298, 398, 498, 598, 698, 798}. Если выбраны номера из набораи предположили, что до окончательного ответа может потребоваться максимум 8 попыток. А выбор 012 приведет к ответу <0b, 0c> и обрезке до {398, 498, 598, 698, 798}. Формализуя алгоритм математически,мы обнаруживаем, что для этого требуются следующие шаги:

1. Заказывайте цифры по частоте, как они встречаются в обрезке.

2. Выберите цифры, которые встречаются наименее часто и формируют угадывание с ними.

Эта стратегия, конечно, рудиментарна. Однако, исходя из нашего человеческогоисследования, мы смогли найти хорошие показатели успеха после объяснения этого алгоритма.Мы написали программу JavaScript для имитации этой стратегии. Каждая цифра,представленная как объект, которая перечисляет значение, положение и частоту цифры.Функция getHashTable преобразует данный набор в указанное числовое представление.Функция searchInHash выполняет поиск существующих записей, чтобы проверить, чтоцифра уже представлена, и если это так, увеличить частоту на 1. В противном случае,создается новая запись.Затем записи сортируются в порядке возрастания частот цифр и передаютсяк функции makeGuess, которая создает правильное предположение без повторов изотсортированных записей.Мы наблюдаем, что человеческая стратегия пытается определить число, котороеспособно устранить максимальное количество догадок, но грубым способом. Усиливаявычислительнуюмощность, алгоритм может проверять все возможные перестановки.Он проверяет, какой ответ найден,если все номера существующего обрезного набора считаются «кодами» и верны. Ответы хранятся и сравниваются друг с другом. Перестановка может действовать как уникальное предположение, когда все элементы обрезкинабор считаются кодами, он считается «уникальной перестановкой» изначение используется, чтобы сделать реальную догадку.

Заключение

Программирование стратегийдоказали свою жизнеспособность.Примитивный алгоритм и расширенный алгоритм имеют небольшую, но важнуюразницу, которую нельзя игнорировать. Однако необходимо увеличить объем вычислительной мощности для расширенного подхода из-заNP-проблемы.Огромное количество подходов и стратегий для игры по-прежнему остается нерешенным.Тем не менее, благодаря краткости еёправил, «Быки и Коровы»- это очень интересная задача для математиков, компьютерных инженерови психологов.

Список литературы

1. Implementation of described algorithms http://projects.namanyayg.com/moo

2. John Francis, Strategies for playing MOO, or “Bulls and Cows”, http://slovesnov.users.sourceforge.net/bullscows/bulls and cows.pdf

3. John Wiley & Sons, Ltd., MOO in Multics, http://www.multicians.org/moo-in-multics-1972.pdf

4. Tetsuro Tanaka, An optimal MOO strategy, http://dell.tanaka.ecc.u-tokyo.ac.jp/~ktanaka/papers/gpw96.pdf