Существует старинная народная логическая игра. Называется быки и коровы. Её ещё называют mastermind.
Правила простые:
Ведущий задумывает случайное тайное 4-значное число с неповторяющимися цифрами. Игрок делает попытки отгадать число. Попытка — это 4-значное число с неповторяющимися цифрами, сообщаемое ведущему. Ведущий дает подсказки , сколько цифр угадано без совпадения с их позициями в тайном числе (количество коров) и сколько угадано вплоть до позиции в тайном числе (количество быков). Например:
Задумано тайное число «3219». Попытка: «2310».
Результат: две «коровы» (две цифры: «2» и «3» — угаданы на неверных позициях) и один «бык» (одна цифра «1» угадана вплоть до позиции).
Побеждает тот, кто угадает число за меньшее количество ходов.
В этом тексте я хотел бы представить мой алгоритм для поиска решения в этой игре. Я назвал этот метод: матрица возможных решений.
Для определённости пусть будет вариант игры из трёхразрядного числа. Для четырехзначных чисел суть та же самая. Суть алгоритма покажу в частном виде, то есть на примере.
Подготовка
Первым делом надо расчертить вот такую таблицу вариантов. Это и есть матрица возможных решений. Изначально она пустая. Тут перечислено какие числа могут быть в сотнях, какие в десятках, а какие в единицах.
То есть таблица показывает какие числа могут быть в каждом разряде. Чтобы заполнить таблицу надо делать ходы.
Ход №1: Вариант 123 - подсказка: 2 коровы
Подсказки вида ноль быков и несколько коров - это просто подарок судьбы, так как можно смело замазать в матрице решений аж три ячейки. Сейчас это значит, что 1- это не бык 2-это не бык 3-это не бык
Ход №2: 298 - подсказка: 1 корова
Это значит что 2, 9 и 8 не быки. Замазывает эти ячейки в матрице решений.
Ход №3: 354 подсказка: 2 коровы
Тоже это значит что 3 5 4 не быки. Замазываем эти ячейки в матрице.
Ход №4: 532- подсказка: 2 быка
Когда появляются быки, то замазать в таблице ничего не надо. А надо делать гипотезы исходя из возможной комбинаторики.
В данном случае, присутствует вся информация, чтобы выиграть. Когда есть подсказка 2 быка, то тут надо проверить три гипотезы. Одна останется и две будут опровергнуты.
1.Гипотеза: быки это 53_ (спойлер: ошибочно)
Тогда 2 нет в числе. Тогда 1 3 тоже коровы. То есть в числе должны быть числа 1 3 5. Однако вторая подсказка говорит о том что есть еще четвертое число отличное от 1 3 5. Противоречие. Гипотеза не состоятельная.
3.Гипотеза: быки это 5_2 (спойлер: ошибочно)
Тогда в числе нет 3. На основе хода 3 значит есть 1 2 4 5 . Но это 4 числа! Перебор. Противоречие.
2.Гипотеза: быки это _32 (спойлер: правильно)
Тогда 5 нет в числе. Значит в числе есть ещё и 4. Значит нет 1 ,9, 8 и 5 . Нет ни одной подсказки, которая бы нарушала гипотезу. Получается ответ это 432.
Вот и получается, что ответ найден на пятом шаге.
Ход №5: 432 Победа!
Вот заготовка для того, чтобы заносить в неё развет-данные в игре быки и коровы. Её можно распечатать на A5 для каждой игры.
Вот так может выглядеть один раунд. Победа на 4м ходе.
Итоги
Как видите, удалось выиграть с 5 шагов. Алгоритм работает.
Хорошая это игра быки и коровы. Учит тактике, учит строить гипотезы, доказывать и опровергать их.
Надеюсь этот приём с матрицей поможет другим научиться разгадывать игру быки и коровы.
Ссылки
Метод решета в игре «Быки и коровы»
Загадочное происхождение настольной игры про взлом кодов Mastermind
Комментарии (10)
ruomserg
09.09.2024 21:30+2Я помню, что детьми мы резались в быков и коров во время долгих часов в поезде - благо планшетов не было, а бумажки и карандаши - были. Позже, уже в школе - я нашел сочетание первых ходов 1234/5234/6734/8904 - из за того, что в ней цифры повторяются "уголком" и используются все - чистым анализом количества быков и коров можно точно определить, является ли 1-4 быком, коровой или ничем, и получить из этого массу полезного про остальные цифры.
Еще позже - уже после института я пришел к выводу, что наши логические алгоритмы - это просто подпорка для нашего несовершенного разума. Машина играет гораздо проще - генерируются все возможные числа загаданные противником, из них выбирается одно (на первом ходу - любое из) - и после получения ответа из множества вычеркиваются все числа, которые ему не соответствуют. Если в какой-то момент множество окажется пустым, значит противник вам хотя бы один раз соврал.
Так глубоко как в статье - я выигрышные стратегии не анализировал. Реально было запрограммировано две стратегии - выбор случайного варианта из множества все еще возможных чисел загаданных противником, и два с оптимизацией: a) при любом ответе противника делит множество заданных чисел в среднем наиболее равномерно; либо б) при наиболее неблагоприятном ответе противника минимизирует максимально возможную мощность множества задагаданных чисел (принцип минимакса - позволяет оптимально играть против "хитрого" противника, который в случае если вы случайно угадали его число - проверяет, не может ли он его изменить так чтобы предыдущие ответы остались корректными, и если да - то меняет его на одну из возможных альтернатив).
Статистически, алгоритм "б" выигрывал у "а" даже когда игра велась по обычным честным правилам. На практике, люди не замечали разницы между "б" и "а" играя с машиной, поэтому дальше и я, играя с людьми, думать и строить логические цепочки перестал - а просто называю любое пришедшее в голову число, которое не противоречит ранее сделанным ходам...
askv
09.09.2024 21:30+2просто называю любое пришедшее в голову число, которое не противоречит ранее сделанным ходам
Условие непротиворечия лишнее, потому что, возможно, отсекает такие запросы, которые в варианте б) дают лучший результат. Правилами не запрещено спрашивать то, что противоречит ранее сделанным ответам.
Я программировал эту игру в начале 90-х, если мне не изменяет память, я реализовывал вариант б) с учётом этого комментария.
ruomserg
09.09.2024 21:30Я согласен, но у варианта - "называем любое число не противоречащее сделанным ходам" есть два преимущества: оно дает шанс угадать "на дурачка", а если и нет то гарантированно уменьшает множество оставшихся чисел хотя бы на одно; кроме того это легко реализовать даже "в голове".
Что касается алгоритмов в машине - то тонкую разницу одного относительно другого видно только на статистике машина-машина из сотен игр. При игре с человеком разницы между аналитическим обдумыванием "кто бык, кто корова" (с предложенной ли таблицей, или без таковой), называние любого возможного по предыдущим ходам числа и условно оптимальными стратегиями - не ощущается. Но реализовать последнее в голове - это надо быть гением...
askv
09.09.2024 21:30Там может зависеть от цели — мы хотим минимизировать среднее число ходов или минимизировать максимальное число ходов. Но я не исследовал задачу так глубоко, как в статье, ссылку на которую здесь привели в первом комментарии. Даже вариант б) это была некоторая эвристика, строгого доказательства у меня не было.
Pochemuk
С этой статьёй знакомы?
https://slovesnov.users.sourceforge.net/bullscows/bullscows_ru.pdf
aabzel Автор
Нет. Посмотрю.