Показано с 1 по 11 из 11

Тема: Быки и коровы - оптимальная стратегия игры

  1. #1
    Администратор, Консультант по математике
      За вклад в развитие форума 2006, Лучший знаток физики 2007, Самый активный автор месяца. Август 2007, Лучший консультант 2007, Лучший супермодератор 2007, Народный модератор раздела "Наука и Образование" 2008, Лучший супермодератор 2008, Лучший консультант 2008
    Аватар для Trotil
    Регистрация
    15.12.2005
    Адрес
    град Москва
    Сообщений
    5,890
    Записей в блоге
    26
    Спасибо
    я - 57; мне - 380

    Быки и коровы - оптимальная стратегия игры

    Собственно игра находится вот здесь : http://www.games.look.ru/bc/
    Предлагаю подумать над поиском оптимальной стратегии для игры, а также определить наихудший случай и определить максимальное число ходов для решения этой задачи.
    Ленивый дурак - это полбеды; деятельный дурак - это для всех головная боль, но нет ничего хуже, чем дурак с инициативой, да ещё и при должности.

  2. #2
    Администратор, Консультант по математике
      За вклад в развитие форума 2006, Лучший знаток физики 2007, Самый активный автор месяца. Август 2007, Лучший консультант 2007, Лучший супермодератор 2007, Народный модератор раздела "Наука и Образование" 2008, Лучший супермодератор 2008, Лучший консультант 2008
    Аватар для Trotil
    Регистрация
    15.12.2005
    Адрес
    град Москва
    Сообщений
    5,890
    Записей в блоге
    26
    Спасибо
    я - 57; мне - 380
    У нас есть 13 реакций на введенную комбинацию:

    0 - 0
    1 - 0, 1 - 1
    2 - 0, 2 - 1, 2 - 2
    3 - 0, 3 - 1, 3 - 2, 3 - 3,
    4 - 0, 4 - 1, 4 - 2,
    Цель - дойти до 4 - 4 - т.е. выигрыша.

    Всего возможных комбинаций в игре 10*9*8*7, правильных только одна.

    Пробую решить задачу переборным путем. Для этого надо составить программу, работающую по следующему алгоритму:

    для всех возможных комбинаций (от 1234 до 7890) далаем попытку угадать (начиная с 1234) - получаем ответ - одну из 13-ти ситуаций, указанных выше. Если ответ 4-4 - мы нашли загаданное число. Если нет - выбираем следующее число, и в распоряжении уже 2 реакции компьютера. Существует какая-то минимальная цепочка, по котором можно однозначно определить, какая комбинация будет правильной. Необходимо ее найти.

    Есть интересная характеристика - количество информации, или энтропия. Например, если мы получили f(1234)=00, то ход N2 - 4321 нам новой информации не даст. Математически это можно вычислить через условную энтропию, а можно пойти другим путем: Пусть у нас известны отклики на k различных комбинаций - тогда Мы можем заведомо вычитать отклики для некоторых других комбинаций (например f(1234)=00 будет давать f(1243)=00, f(2431)=00 и т.д.) - тем самым снижая число вариантов следующего хода.
    Ленивый дурак - это полбеды; деятельный дурак - это для всех головная боль, но нет ничего хуже, чем дурак с инициативой, да ещё и при должности.

  3. #3
    Питерский миХеевец Аватар для elek
    Регистрация
    08.12.2005
    Адрес
    Санкт-Петербург
    Сообщений
    699
    Спасибо
    я - 0; мне - 1
    отгадала число за 7 ходов.
    Алгоритма решения сказать не могу, т.к. я все-таки не математик. При решении просто анализирую результаты, сравниваю их, исключаю какие-то цифры, замечаю угаданные и цифры и места (угаданных быков) и таким образом пытаюсь вычислить правильный ответ.
    Самое главное - то, чего не увидишь глазами... (с) "Маленький принц"


  4. #4
    Участник Аватар для Дарида
    Регистрация
    25.08.2005
    Адрес
    Белоруссия, Минск
    Сообщений
    379
    Спасибо
    я - 3; мне - 82
    Моя любимая игра


    Цитата Сообщение от Trotil Посмотреть сообщение
    Существует какая-то минимальная цепочка, по котором можно однозначно определить, какая комбинация будет правильной. Необходимо ее найти.
    после не одного потраченого на эту игру урока истории, биологии и географии... пришла к выводу, что наубыстрый способ, это

    1. определить какие именно эти 4 числа.
    2. при этом по возможности одну и туже цифру не ставить в одну и туже позицию.

  5. #5
    Участник Аватар для Дарида
    Регистрация
    25.08.2005
    Адрес
    Белоруссия, Минск
    Сообщений
    379
    Спасибо
    я - 3; мне - 82
    честно сказать, меня эта хадача задела за живое) до сих пор покоя не даёт =)
    недавно натолкнулась на алгоритм реализации её решения на с++

  6. #6
    Футбольный болельщик
      Самый полезный участник раздела "Спорт" 2007
    Аватар для JuliaR
    Регистрация
    12.02.2005
    Адрес
    w
    Сообщений
    805
    Записей в блоге
    2
    Спасибо
    я - 17; мне - 2
    Интересная игра . Пока лучший результат - 7 ходов.

  7. #7
    partizan
    Гость
    Вот тут: http://igrun.com/?7210 можно в эту игру на деньги играть
    Там она называется "Сейф", нужно угадать за 5 ходов - выиграл (чем раньше угадал - тем больше выиграл).

    Моя программа угадывает всреднем за 5.4 ходов, этого мало, чтоб деньги зарабатывать

    Завтра буду думать над улучшением алгоритма

  8. #8
    bulca
    Гость

    уупс!

    Цитата Сообщение от partizan Посмотреть сообщение
    Завтра буду думать над улучшением алгоритма
    Что скажете об этом?
    bulca.h18.ru

    Тут можно заставить комп играть самого против себя!

  9. #9
    Bars
    Гость

    Моя стратегия

    Открыл технологию угадывания 4-значного числа! Абсолютная безотказность. Количество необходимых попыток - 5-6, ну в случае фатального невезения может потребоваться 7.
    Такая технология, правда, требует от Вас хорошей сообразительности и достаточно большого промежутка времени для отгадывания чисел (у меня уходило от 70 до 160 секунд). Если для Вас это - пустяки, можете смело прибегать к этой технологии)
    Принцип такой.
    Первые 4 попытки пишем следующие числа:
    1234
    4567
    3480
    6043

    И смотрим на результаты.
    В частности нас интересует СУММА всех быков и коров за эти 4 попытки.
    Вы спросите в чем дело, почему именно эти числа? Можно и другие, на самом деле, но обязательно условие такое:
    ОДНА цифра должна повторяться ЧЕТЫРЕ раза (в данном случае это 4) и желательно стоять во всех числах на разных позициях;
    ОДНА цифра - ТРИ раза (в данном случае это 3);
    ДВЕ цифры - по ДВА раза (6 и 0);
    и ОДНА цифра - отсутствовать вовсе (9).
    При этом пять цифр будут повторяться по одному разу - это 1, 2, 5, 7 и 8.
    Еще одна особенность: в числе 6043, которое мы ввели 4-ой попыткой, присутствуют все цифры, которые повторяются в данной комбинации более чем один раз (это 4, 3, 6 и 0) - и ТОЛЬКО они. Это сыграет также важную роль. Зачем это надо - потом скажу.
    Итак, теперь считаем сумму полученных быков и коров. Их может быть от 3 до 11. Это нам надо для того, чтобы определить, какие из повторяющихся цифр встречаются в загаданном числе.
    Например, если в итоге получилось 3 быка и коровы - ясное дело, что загаданное число содержит три цифры, которые повторяются в комбинации один раз, и цифру, которая отсутствует. Другого варианта быть не может.
    Для тех, кто хочет сэкономить время, приводу шпаргалку:
    Сумма БК/Повторения
    3 = 1110
    4 = 2110 или 1111.
    5 = 3110/2210/2111
    6 = 4110/3210/3111/2211
    7 = 4210/4111/3220/3211
    8 = 4310/4220/4211/3221
    9 = 4320/4311/4221
    10 = 4321
    11 = 4322

    Если сумма равна от 4 до 9, то вариантов, как вы видите, несколько.
    В этом случае на помощь приходит число 6043 (то самое, где встречаются только повторяющиеся цифры). Смотрим сумму быков и коров именно у него.
    Например, если общая сумма равна 7, а у четвертой попытки только один бык, то ясное дело - иначе как 4111 вариантов быть не может.

    Вот например:

    1234 - 1б, 1к
    4567 - 1б, 1к
    3480 - 0б, 2к
    6043 - 1б, 0к.


    Подставляем и получаем следующее:
    Цифра 4 - ТОЧНО есть, причем стоит она на 3-ей позиции.
    Цифр 3, 6, 9, 0 - ТОЧНО нет.
    Подставляем результаты в третью попытку: Цифра 8 - точно есть.
    И еще есть одна из цифр 12, и одна из цифр 57. Обе - стоят на своих позициях (так как в обоих случаях 4 - это корова).
    Возможные варианты: 1847, 1548, 8247.
    Более точно мы определить число пока не можем, но заметьте - уже свели количество возможных вариантов к трем (при том что всего их ни много ни мало 4536, при условии что число не начинается с нуля). Вероятность того, что мы угадаем с 5-ой попытки, равна 33%. Вопрос - что вводить 5-ой попыткой?
    Посмотрим варианты.
    Если мы введем 1847, то:
    Если загадано число 1548, результат будет - 2 быка 1 корова.
    Если загадано число 8247, результат будет - 2 быка 1 корова.
    Вывод: число 1847 вводить не стоит, если только Ваши экстрасенсорные способности не подсказывают Вам, что загадано именно оно.
    Если мы введем 1548, то:
    Если загадано 1847, результат будет - 2 быка 1 корова.
    Если загадано 8247, результат будет - 1 бык 1 корова.
    Уже лучше! Делаем пятую попытку. С вероятностью 33% - она оказывается удачной, если же нет - то шестая попытка уже точно будет последней. =)))

    Если жа и после такой проверки вариантов все равно осталось несколько (например, общая сумма = 8, сумма у 4-го числа = 2, варианты - 4310 и 4211) тогда уже анализируйте дальше, исходя из кол-ва быков и коров на каждой попытке.

    Еще один пример:
    1234 - 1б, 1к
    4567 - 0б, 2к
    3480 - 2б, 0к
    6043 - 0б, 2к


    Сумма = 8. 8 = 4310/4220/4211/3221.
    После проверки 4-ой попыткой возможные варианты: 4211, 4310.
    Проверим сначала 4310. Может быть такое? Может. Это означает, что цифры 3 и 4 - есть, 6 и 0 - нет, 9 - есть. Все подходит.
    Теперь определим местоположение. Третья попытка - два быка, и кроме как 3 и 4 вариантов быть не может. СТО-о-оп! А где же тогда бык в первой попытке? Согласно ей, цифр 1 и 2 быть не может, а 3 и 4 уже заняты... Не получается!
    ЗНАЧИТ - 3 все-таки нет, а единственный вариант оставшийся - 4211.
    То есть: 4 есть, также есть 6 или 0, 9 нет. 3 - тоже нет.
    Если предположить, что есть 4 и 6, тогда есть еще 8, а также 1 или 2.
    Если же предположить, что есть 4 и 0, то есть еще 5/7 или 1/2.
    Еще один момент: В первой попытке остался неиспользованным один бык. Причем это точно цифра 1, так как на второй позиции стоит цифра 4 (согласно 3-ей попытке), а цифры 3 вообще нет.
    Итак, первые две цифры числа 14.
    Варианты: 1450, 1470, 1486.
    И опять с вероятностью 33% мы угадываем с пятой попытки, с вероятностью 67% - с шестой.

    Конечно, значительную роль в игре играют быки. В третьей попытке получилось два быка - и в итоге мы сэкономили один ход. Но на самом деле бывает так, что мне удалось выиграть с пятой попытки (и даже без угадывания в конце!!!) имея лишь одного быка.

    Например:

    1234 - 0б, 2к
    4567 - 1б, 0к
    3480 - 0б, 3к
    6043 - 0б, 3к.


    Сумма = 9. 9 = 4320/4311/4221.
    6043 = 3 коровы
    Остаются варианты 4320 и 4221.
    Пробуем оба этих варианта. Согласно первому:
    Есть цифры 4, 3 и 9, также есть 6 или 0.
    Или:
    Есть 4, 6 и 0, а также еще одна цифра из неповторяющихся - 1, 2, 5, 7 или 8.
    Какая? Смотрим по быкам. И натыкаемся на несоответствие - во второй попытке 4567 имеем только одного быка, а согласно этому варианту есть 4 и 6. Не подходит.
    Следовательно, подходит только первый вариант, причем как мы только что выяснили, цифры 6 нет, значит есть 3, 4, 9 и 0.
    Теперь вычислим местоположение этих цифр. 4 - единственный бык во второй попытке, значит, она на первой позиции.
    Цифра 3 может находиться только на 2-ой позиции, так как она была использована в первой и в четвертой попытке на 3-ей и 4-ой позиции, и нигде нет ни одного быка. Значит, у нас два варианта: 4390 и 4309. 4390 - быть не может, так как в третьей попытке у нас тоже нет быков. Остается единственный ваариант - 4309, который мы и вводим 5-ой попыткой и выигрываем!

    Но могут изредка возникать ситуации, когда четырех попыток маловато, чтобы свести дальнейший процесс к тупо угадыванию.

    1234 - 0б, 1к
    4567 - 1б, 0к
    3480 - 0б, 1к
    6043 - 0б, 1к.


    Итого - 4 в сумме. 4 = 2110 или 1111.
    На 4-ой попытке - одна корова. Это означает, что вариант 1111 нам не подходит - только 2110.
    Из этого делаем вывод следующий:
    9 - есть
    Есть также 6 или 0
    Есть также 1 или 2 (исходя из первого числа)
    И еще одна цифра. Это может быть 5 или 7, но если есть одна из этих цифр, значит 6 нет, а есть 0. Или же если есть 6, то есть 8 обязательно.
    Проще говоря, варианты цифр: 1/2 - 6 - 8 - 9, или 1/2 - 5/7 - 9 - 0.
    О местоположении цифр догадываться мы пока не можем - маловато быков.
    Возможных вариантов пока много. Делаем пятую попытку. Лучше первым проверять тот вариант, где меньше точно известных цифр. Пусть это будет число 2907.
    Получилось: 1 бык, 1 корова.
    Что это означает?
    1: Цифры 9 и 0 - верны, а 2 и 7 надо заменить на 1 и 5.
    2: Вариант неверен, и совпали цифры 2 и 9, а оставшиеся две - 6 и 8.
    То есть набор цифр получается следующий: либо 1-5-9-0, либо 2-6-8-9.
    Рассмотрим сначала первый вариант. Мы имеем следующее:
    5 может быть только на второй позиции;
    0 - не на четвертой, значит на третьей позиции (в начале числа он не может стоять). Это и есть бык;
    1 - не на первой позиции.
    Единственный вариант - 9501. Пока не спешим его вводить...
    Теперь второй вариант - с набором 2-6-8-9:
    6 - на третьей позиции;
    2 - не на второй позиции.
    Варианты: 2869, 2968, 8962, 9862
    Варианты 2968 и 9862 - не подходят, так как в первом случае получается 2 быка, а во втором - ни одного.
    Остается три варианта: 9501, 2869, 8962. Тут уже - только вопрос везения. Мне не повезло, я ввел 8962 и получил 1 корову и только) оказалось как раз 9501((( получилось 7 попыток.

    Конечно, выглядит сложно на первый раз. Но нужно просто попрактиковаться, и все будет хорошо). А главное - это РАБОТАЕТ! Реально, я только что 40 раз сыграл с компьютером, в 52,5% случаев (21 из 40) угадал с 5 попыток, в 42,5% (17 из 40) - с 6-ти, и лишь дважды (5%) мне не повезло и пришлось использовать седьмую.

    Хотя бывают, конечно, и исключительные случаи. С вероятностью 1 к 1134 компьютер может загадать одно из чисел 1234, 4567, 3480, 6043. Однажды он загадал число 4576, которое я благополучно угадал с трех попыток) А может оказаться так, что после ввода, к примеру, 3480 Вы получите 0 быков 0 коров, что делает почти бессмысленным ввод числа 6043. Но факт есть факт - при использовании этой стратегии вероятность отгадывания с 4 попыток равна 0.09%
    не более чем с 5 попыток = около 50%
    не более чем с 6 попыток = около 90%
    не более чем с 7 попыток = 100%!
    Может быть конечно я и ошибаюсь, но на мой взгляд - это самая оптимальная стратегия отгадывания четырехзначного числа.
    В настоящее время я еще думаю над стратегией отгадывания 5-значных, 6-значных и даже 9-значных чисел. Как додумаюсь - поделюсь, если конечно это будет интересно.

    В завершении даю ссылку на мою версию программы, которую я написал за 1,5 часа на Delphi 7. Ее особенность - возможность отгадывать числа как четырехзначые, так и других разрядностей, а также возможность проходить Чемпионаты, т.е. последовательность раундов с отгадыванием чисел разных разрядностей с ограничением по кол-ву попыток и времени (мой рекорд по прохождению чемпионата на 8 раундов - 58 попыток и 590 секунд, уровень Экстрасенс).
    Вот она - http://depositfiles.com/files/ma1i1gsiw

    УДАЧИ!!!
    Последний раз редактировалось Bars; 10.10.2012 в 20:14.

  10. #10
    Новый участник
    Регистрация
    06.11.2016
    Сообщений
    1
    Спасибо
    я - 0; мне - 0
    Цитата Сообщение от Bars Посмотреть сообщение
    В завершении даю ссылку на мою версию программы, которую я написал за 1,5 часа на Delphi 7. Ее особенность - возможность отгадывать числа как четырехзначые, так и других разрядностей, а также возможность проходить Чемпионаты, т.е. последовательность раундов с отгадыванием чисел разных разрядностей с ограничением по кол-ву попыток и времени (мой рекорд по прохождению чемпионата на 8 раундов - 58 попыток и 590 секунд, уровень Экстрасенс).
    Вот она - http://depositfiles.com/files/ma1i1gsiw

    УДАЧИ!!!
    Ссылка уже мертвая. Может кто успел скачать ? Или автор еще тут - очень нужен код.
    Киньте живой ссылочкой или на почту shroomz@mail.ru.

    Заранее спасибо.

  11. #11
    Новый участник
    Регистрация
    27.01.2018
    Адрес
    Москва
    Сообщений
    1
    Спасибо
    я - 0; мне - 0
    Цитата Сообщение от Trotil Посмотреть сообщение
    Собственно игра находится вот здесь : http://www.games.look.ru/bc/
    Предлагаю подумать над поиском оптимальной стратегии для игры, а также определить наихудший случай и определить максимальное число ходов для решения этой задачи.
    Круто круто))

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •