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

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



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

Суть игры

Игрок и компьютер загадывают четырехзначные числа, используя цифры от 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;

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

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