Комментарии 10
С этой статьёй знакомы?
https://slovesnov.users.sourceforge.net/bullscows/bullscows_ru.pdf
а алгоритм-то где? в целом просто достаточно ряда от 0 до 9 — то же самое — чтобы угадать в 5 ходов, если повезет, то и 3-4
Я помню, что детьми мы резались в быков и коров во время долгих часов в поезде - благо планшетов не было, а бумажки и карандаши - были. Позже, уже в школе - я нашел сочетание первых ходов 1234/5234/6734/8904 - из за того, что в ней цифры повторяются "уголком" и используются все - чистым анализом количества быков и коров можно точно определить, является ли 1-4 быком, коровой или ничем, и получить из этого массу полезного про остальные цифры.
Еще позже - уже после института я пришел к выводу, что наши логические алгоритмы - это просто подпорка для нашего несовершенного разума. Машина играет гораздо проще - генерируются все возможные числа загаданные противником, из них выбирается одно (на первом ходу - любое из) - и после получения ответа из множества вычеркиваются все числа, которые ему не соответствуют. Если в какой-то момент множество окажется пустым, значит противник вам хотя бы один раз соврал.
Так глубоко как в статье - я выигрышные стратегии не анализировал. Реально было запрограммировано две стратегии - выбор случайного варианта из множества все еще возможных чисел загаданных противником, и два с оптимизацией: a) при любом ответе противника делит множество заданных чисел в среднем наиболее равномерно; либо б) при наиболее неблагоприятном ответе противника минимизирует максимально возможную мощность множества задагаданных чисел (принцип минимакса - позволяет оптимально играть против "хитрого" противника, который в случае если вы случайно угадали его число - проверяет, не может ли он его изменить так чтобы предыдущие ответы остались корректными, и если да - то меняет его на одну из возможных альтернатив).
Статистически, алгоритм "б" выигрывал у "а" даже когда игра велась по обычным честным правилам. На практике, люди не замечали разницы между "б" и "а" играя с машиной, поэтому дальше и я, играя с людьми, думать и строить логические цепочки перестал - а просто называю любое пришедшее в голову число, которое не противоречит ранее сделанным ходам...
просто называю любое пришедшее в голову число, которое не противоречит ранее сделанным ходам
Условие непротиворечия лишнее, потому что, возможно, отсекает такие запросы, которые в варианте б) дают лучший результат. Правилами не запрещено спрашивать то, что противоречит ранее сделанным ответам.
Я программировал эту игру в начале 90-х, если мне не изменяет память, я реализовывал вариант б) с учётом этого комментария.
Я согласен, но у варианта - "называем любое число не противоречащее сделанным ходам" есть два преимущества: оно дает шанс угадать "на дурачка", а если и нет то гарантированно уменьшает множество оставшихся чисел хотя бы на одно; кроме того это легко реализовать даже "в голове".
Что касается алгоритмов в машине - то тонкую разницу одного относительно другого видно только на статистике машина-машина из сотен игр. При игре с человеком разницы между аналитическим обдумыванием "кто бык, кто корова" (с предложенной ли таблицей, или без таковой), называние любого возможного по предыдущим ходам числа и условно оптимальными стратегиями - не ощущается. Но реализовать последнее в голове - это надо быть гением...
Там может зависеть от цели — мы хотим минимизировать среднее число ходов или минимизировать максимальное число ходов. Но я не исследовал задачу так глубоко, как в статье, ссылку на которую здесь привели в первом комментарии. Даже вариант б) это была некоторая эвристика, строгого доказательства у меня не было.
А может быть все же не "третие", а "третье"??? У грамарнаци аж слезы потекли.
Публикации
Как Выигрывать в Игре Быки и Коровы