Комментарии 12
Респект! Было интересно!
Весьма интересно, но мы играли в другую версию игры "Корова": вместо цифр слова. Эдакая игра виселица. И более интересно подбирать из своего словарного запаса именно существительные с одним и тем же количеством букв, но разным буквенным составом.
Любопытно)) Сейчас подобная игра есть в открытом доступе для 5-буквенных английских слов на платформе The New York Times Games. И клон на русском языке https://wordly.org/ru?
Я по быкам-коровам делал приложеньку ещё в 90-е на Delphi и в алгоритме ориентировался на решение задачи методом минимакса, думаю, это приблизительно то же самое, что и в вашем подходе.
Суть такая. После хода N у нас есть некая информация P(N), исходя из которой мы знаем, что загадано одно из X(N) чисел.
Делаем перебор всех возможных вариантов ходов - их всего 10 * 9 * 8 *7 - N. Для каждого варианта хода внутри устраиваем второй цикл по X(N) - среди всех возможных загаданных чисел, и для каждого числа получаем какой-то ответ в предположении, что загадано оно, на основе которого у нас уже есть информация Px(N+1). Для этой информации вычисляем сколько останется загаданных чисел - X(N+1). Берем максимум из этих чисел во внутреннем цикле. Таким образом для каждого возможного хода мы знаем наихудший в рамках этого алгоритма вариант - сколько останется вероятных кандидатов на верный ответ. Ну и естественно по внешнему циклу выбираем такой ход, для которого это число минимально.
Доказать, что это оптимальная стратегия, я не берусь, но вероятно, очень близко к тому. Вот какой она делала второй ход в ответ на 0б 1к, я за давностью лет позабыл.
Согласен. Интуитивно мне тоже кажется, что алгоритм минимакса близок к теории информации, за исключением "концовки", которую я описал в заметке. Знаний, чтобы доказать это мне не хватает, поэтому попросил ИИ. Ответ мне понравился))
https://baguzin.ru/wp/wp-content/uploads/2025/08/Otvet-na-komment-1.docx
Раз уж упомянута теория информации, то какова вероятность закончить игру за К шагов при оптимальной стратегии?
Зависит ли длина игры от исходной комбинации? Скажем, 0000 и 1234?
Доступна ли общая формула для алфавита размера N и слова длиной M?
Я так и не понял, что за формулы предложил написать чатгпт в Эксель?
>какова вероятность закончить игру за К шагов при оптимальной стратегии?
Для вычисления вероятности, нужно пройтись по огромному числу деревьев решений. Вряд ли это интересно. Мой опыт говорит, что средняя длина игры составляет около 5,3-5,4.
>Зависит ли длина игры от исходной комбинации? Скажем, 0000 и 1234?
Первая комбинация нелегитимна, повтор цифр не допускается. В общем случае, не зависит, если только я не предполагаю, какие-то предпочтения комбинаций у моего оппонента.
>Доступна ли общая формула для алфавита размера N и слова длиной M?
Общая формула чего? "Вероятности закончить игру за К шагов при оптимальной стратегии"? Нет. Если про формулу Шеннона, то она универсальна, но... требуется знать вероятности различных ответов.
>Я так и не понял, что за формулы предложил написать чатгпт в Эксель?
Формулы в приложенном файле Excel. Например такая:
=BYROW(C4#; LAMBDA(y; СУММ(--(BYROW(GenerateUniqueFourDigitNumbers; LAMBDA(x; CountBullsAndCows(x; D1))) = y))))
Для вычисления вероятности, нужно пройтись по огромному числу деревьев решений. Вряд ли это интересно. Мой опыт говорит, что средняя длина игры составляет около 5,3-5,4.
Неужели только брутфорсом решаются статистические задачи?
Если взять длину 6, то даже 20^6 это всего лишь 64 млн.
Интерес в том, что зная эту статистику, можно оценить мастерство игрока. Не сравнительно с кем-то, а в абсолютной шкале.
Первая комбинация нелегитимна, повтор цифр не допускается.
В приведённом вами описании игры этого ограничения нет. Но если повтора нет, то да, вопрос снимается.
Формулы в приложенном файле Excel.
Да, при чтении с телефона был невнимателен. Сейчас увидел, спасибо.
Функции, мягко говоря, нетипичные. :)
При игре в БК я обычно называю 1234, 2345 и так далее, всего 10 комбинаций, а на 11 ходу гарантированно даю правильный ответ. На каком ходу ваш алгоритм обыграет меня?
Мне в среднем нужно 5 ходов, чтобы отгадать число))
Сходу источник не дам, но читал, что доказано математически - максимально необходимое количество ходов - 7. Практически подтверждаю, больше 7 мне не надо. Чтобы угадать быстрее нужна толика удачи.
Кстати, пробовал сыграть с дипсиком. Тупит, путает очередность ходов, сравнивает мои цифры каждый раз с новым набором. Хотя правила как бы "знает". В крестики-нолики у него получается получше :-)
Автору респект! Он ясно показывает, что правильная стратегия - это не случай, а результат понимания сути проблемы. Спасибо, взлянул на задачу под новым углом
Как победить в игре «Быки и коровы» с помощью теории информации