Метод решета в игре «Быки и коровы»

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

image

Нужно было реализовать хоть какое-то обоснованное поведение компьютера в игре с человеком. Но я пошел дальше и уже через месяц компьютер в большинстве случаев легко обыгрывал моих однокурсников. А по предмету был получен автомат. Программу получите после описания алгоритмов.

Суть игры


Игрок и компьютер загадывают четырехзначные числа, используя цифры от 0 до 9. Игроки пытаются разгадать числа соперника, посылая ему возможные варианты чисел, в ответ получая два числа — число «быков» и число «коров». Что же это за числа такие?
  • «Быки» — правильные цифры на правильных местах. Четыре «быка» — залог победы, мечта каждого фермера.
  • «Коровы» — правильные цифры на неправильных местах.

Для понимания приведу пример:
Загадано число 1622. Если мы предположим 6112, то в ответ придет: 1 бык(четвертая цифра «2» на своем месте), 2 коровы(шестерка и единица не на своих местах).

Оперируя данными о «скоте» противника, нужно угадать число быстрей него.

Первый же тривиальный алгоритм, который так и напрашивается, — это перебирать наборы «1111», «2222», «3333»... до тех пор, пока не будет получен полный набор, а затем генерировать перемещения этого набора.
Например, загадано то же число 1622, мы предполагаем «1111», получаем в ответ «быка», затем «2222» — получаем в ответ уже 2 «быков», «3333» — пусто, «4444» — пусто, «5555» — пусто, «6666»1 бык.
Дальше продолжать не будем, так как набралось уже 4 быка в сумме. Осталось найти нужную комбинацию. Будем генерировать перестановки, пока не получим Та-дааам: «1226», «1262», «1226», «1262», «1622». Все.

Очевидно, что алгоритм не очень хорош, зато понятный и не запутаться. Максимальное число ходов для угадывания — 10(«7890»)+24 перестановки. 34 — это в самом худшем случае. Конечно возможно перебор и перестановки всячески оптимизировать, например перебирать поочередно с двух концов — «1111», «0000», «2222», «9999»... так же оптимизировать генерацию перестановок при наличии одинаковых цифр(как в нашем примере — несколько раз спрашиваем одно и то же).
Но не будем этим заниматься. Пусть данная стратегия будет у нас легким уровнем сложности компьютера.

Много я сидел на парах и играл сам с собой, пытаясь придумать какой то свой крутой алгоритм. Но приходили только единичные идеи, из которой я не мог составить единой стратегии. Начал изучать литературу. Наткнулся на статьи, рода «угадывание за 7 ходов». Они меня не привлекли, поскольку там очень много ветвления. Но прочитав книгу нашего Кировского профессора(но не из нашего университета) С.М. Окулова «Программирование в алгоритмах», я нашел описание довольно простого и достаточно эффективного алгоритма. В нем используется так называемый «метод решета» (примером может служить известное «решето Эрастофена» — классическая задача поиска простых чисел). Мы рассматриваем конечное множество всех возможных чисел и каждый ход исключаем все элементы множества, не представляющие интереса.
Например, для загаданного числа 1234 мы предположили 5678, и получили 0 быков и 0 коров, чего думать — мы исключаем все числа, содержащие 5, 6, 7, 8. Сразу можете прикинуть, сколько отнимется из 10000. Не стоит пугаться множества из 10000 элементов. За 5-6 ходов останется всего несколько чисел.

Начнем со структур данных. Код на паскале:

Const Pmax=10000;
Type Post=string[4];
Var A:array[1..Pmax] of Post; //множество
      B:array[1..Pmax] of boolean; // массив флажков, 1 - значит подходит, 0 - исключено


Инициализация:


t:=1;
 for i:=0 to 9 do
  for j:=0 to 9 do
   for k:=0 to 9 do
    for l:=0 to 9 do begin
     a[t]:=inttostr(i)+inttostr(j)+inttostr(k)+inttostr(l); // формируем множество
     inc(t); end;
 for i:=1 to pmax do  
       b[i]:=true; // по умолчанию все числа подходят


Функция, реализующая анализ элемента множества по значениям переменных (bk,kr — быки и коровы)

function pr(a,b:post;bk,kr:integer):boolean; //b - наш ход, a- элемент "тестируемого" множества
var i,x:integer;
begin
 x:=0;
 for i:=1 to 4 do // проверка по быкам
  if a[i]=b[i] then inc(x);
 if x<>bk then
  begin
   pr:=false;
   exit;
  end;
 x:=0;
 for i:=1 to 4 do // проверка по коровам
  if (a[i]<>b[i]) and (pos(b[i],a)<>0)
   then inc(x);
  if x<kr then
   begin
    pr:=false;
    exit;
   end;
  pr:=true;
end;


таким образом после каждого нашего хода запускаем решето


for i:=1 to Pmax do
if b[i] and not pr(a[i],hod,bk,kr) then  b[i]:=false;


В заключение можно сказать, что алгоритм затратен к памяти и по сравнению со стандартными алгоритмами будет думать «дольше», но насколько же он проще и вполне оптимизируется.
Ну вот и все, совсем не сложно. Первая моя статья, судить строго.

Как и обещал, ссылка на мою игрульку со второго курса, чтоб на себе почувствовать метод «решета»:
Быки и коровы
Share post

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 21

    0
    Очень интересно. Немного не разобрался в функции «pr», но прочитав статью в википедии «метод „Решето Эратосфена“ стало понятней.
    PS а игрушка занятная! Меня компьютер пару раз победил!
      +9
      >не столь известная логическая игра
      угу, учитывая что 99% программистов писали реализацию игры еще в школе=)
        +3
        А алгоритм действительно хорош.
        +3
        1.
        Var A:array[1..Pmax] of Post;
        

        Это лишнее, не нужно хранить в памяти константы, которые легко посчитать:
        function getA(i : integer): Post;
        begin
           result[4] = (i - 1) mod 10;
           result[3] = (i - 1) div 10 mod 10;
           result[2] = (i - 1) div 100 mod 10;
           result[1] = (i - 1) div 1000 mod 10;
        end;
        

        Тут мне пришлось брать (i — 1), потому что вы начинаете с 1, а не с 0, что имхо не очень правильно.

        2. Обязательно прочитайте про то, как должен выглядеть код, про всякие нотации. Ваш код сложно читать.

        3. В самой статье, я так и не понял ничего про применения метода решета. Не хватает формально написанного алгоритма, и примера, который доведет игру до конца.

        P. S. Поздравляю с автоматом.
          0
          вы правы, благодарю за замечания.
          +4
          Подход стандартный.

          Но в нем самое главное — выбор очередного хода. От этого зависит за сколько ходов программа будет угадывать комбинацию. У вас за сколько? И как выбирается очередной ход?
            0
            если ход первый то выбираем случайно 4 разные цифры, разные — чтобы исключить больше.
            если же ход не первый то из невычеркнутых комбинаций так же выбираем числа с 4 разными цифрами, если они есть. ничего лучше я, к сожалению, не смог тогда придумать.
              +1
              И как — наверно за пять-шесть ходов отгадывал?

              Насколько я помню (давненько я не брал в руки шашек) — случайный выбор дает шесть. Кстати вон и ниже так пишут. Но можно получить пять, если выбирать комбинацию, которая как можно сильнее ограничивает множество решений. То есть для разных комбинаций и разных ответов множество возможных решений уменьшается по-разному. И в наших интересах выбрать ход, который уменьшает его как можно больше.
                0
                выбор очередного хода подробно освещен в иностранных статьях, я же, к сожалению, в него не углублялся — там слишком много вариантов нужно разобрать(как вы и сказали «для разных комбинаций и разных ответов множество возможных решений уменьшается по-разному»). это задача намного сложнее чем отсечение заведомо неверных вариантов в методе решета
            0
            Школа, турбо паскаль, 286. Изобретенный алгоритм — это было откровение. Тут же написанный перебор всех вариантов — за сколько ходов будет отгадано. Два варианта выбора — первое допустимое или случайное. Случайное, насколько помню, давало чуть меньшее среднее число попыток, но все равно они оставались на уровне 5-6.
            Недавнее время, fallout 3. Взлом компьютеров по тому же самому алгоритму.
              0
              >Недавнее время, fallout 3.
              Вы тоже писали себе утилиту для взлома компов?=)
                0
                Нет, в голове, но тем самым методом :)
              +2
              Конечно возможно перебор и перестановки всячески оптимизировать, например перебирать поочередно с двух концов — «1111», «0000», «2222», «9999»...

              Какая же это опимизация, если вероятность «выпадения» любого числа одинакова?
                0
                ребенок поиграет с ним два раза и поймет, что он каждый раз начинает с 1,2,3… и загадает например 9876.
                … конечно и с поочередными попытками так же можно догадаться и составить число из средних. вы правы. нужно рандомизировать
                –3
                Меня забавляет объяснение неиспользования алгоритма угадывания за 7 ходов — «слишком много ветвления». Лолшто? И за сколько шагов ваш алгоритм угадывает?
                  0
                  сами поиграйте и увидите. а тот алгоритм не использовал, тк нисколько не интересно переписывать алгоритм из кучи кейзов и условий
                  0
                  Играем иногда в универе в эту игру (правда с несколько модифицированными правилами):) к даному алгоритму приходишь интуитивно игр после пяти;) а вот с выбором максимально эффективного следующего хода уже сложнее…
                    +1
                    Объясните пожалуйста про переменные bk и kr в фунции pr. А именноусловия x
                      0
                      Не совсем по теме, но как забавно смотрится меню «Файл»! Как будто в нём действительно собраны операции для работы с файлами, а не кнопка выход. И это ни в коем случае не упрёк в ваш адрес.
                        0
                        требования преподавателя:) есть еще кнопка «пауза»…
                        0
                        Только что написал программу, используя этот метод решета.
                        Вероятно, я чего-то не понял, но у меня крайне редко случаются ситуации, когда нет ни одного попадания, так что программа работает практически на генераторе случайных чисел.

                        Only users with full accounts can post comments. Log in, please.