Крестики-нолики> Несколько слов
Алгоритм
Flash вариант
  Скачать

Алгоритм крестиков-ноликов

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


У меня есть только одна просьба к тем, кто будет пользоваться плодами моего труда: если вы отнеслись к процессу творчески и внесли в алгоритм существенные изменения или разработали свой алгоритм, пожалуйста, сообщите мне об этом - мне это интересно.


Все примеры приведены на Паскале. Определим основные массивы, с которыми будем работать:


type
     position=array [1..9] of byte;

var
     Kl : position;
     Ray: position;

Здесь Kl - клетки поля. Принимаемые значения:

0 - для пустой клетки;

1 - для крестика;

4 - для нолика.

Ray - рейтинги клеток. Вычисляются для каждой позиции из массива Kl. Опираясь на рейтинги, компьютер принимает решение о предпочтительности хода на то или иное поле. Собственно,алгоритм вычисления массива Ray и есть главная часть алгоритма крестиков-ноликов. Если известен массив Ray, то выбрать клетку для хода уже легко. Например, так:


procedure SelectCell;
var
  m,r,mr,i: byte;
begin
  ch:=false;
  m:=0;r:=0;
if lvl=0 then begin
  for i:=1 to 9 do 
     r:=r+Ray[i];
  mr:=random(r)+1;
  for i:=1 to 9 do begin
     mr:=mr-Ray[i];
     if mr<=0 then begin
        Kl[i]:=4;
        DrawCell(i);
        break
     end
  end
end
else begin
  for i:=1 to 9 do
    if Ray[i]>r then r:=Ray[i];
  for i:=1 to 9 do
    if Ray[i]=r then m:=m+1;
  mr:=random(m)+1;
  m:=0;
  for i:=1 to 9 do begin
    if Ray[i]=r then begin
      m:=m+1;
      if m=mr then begin
        Kl[i]:=4;
        DrawCell(i);
        break
      end
    end
  end
end
end;

Здесь реализовано два алгоритма выбора клетки для хода в зависимости от глобальной переменной lvl, определяющей уровень игры компьютера. При lvl=0 вероятность хода на данную клетку пропорциональна ее рейтингу, т.е. компьютер с малой вероятностью, но все же может сходить на клетку с низким рейтингом. При ином значении переменной lvl компьютер ходит только на клетку с максимальным рейтингом, а если таких клеток несколько, то среди них нужная клетка выбирается случайно. Естественно, вторая стратегия при правильном определении массива Ray задает более высокий уровень игры компьютера.


Глобальная переменная ch: boolean служит для разрешения/запрещения хода человеком. Не описанная здесь процедура DrawCell(i:byte) перерисовывает нужную клетку на экране монитора.


Другая важная процедура - это функция, определяющая, закончилась игра после данного хода или нет. Эта функция вызывается как после хода человека (до вычисления рейтингов), так и после хода компьютера. Функция анализирует все значащие ряды, т.е. горизонтали, вертикали и диагонали и, если на одном из них оказывается три одинаковых фигуры, то присваивает победу нужной стороне. Если же на всех рядах присутствуют как крестики, так и нолики, то выдается ничейное значение. Если ни одно из этих условий не выполнено, то игра считается неоконченной - выдается ноль. Для анализа рядов функция пользуется массивом-константой lin, который определяется следующим образом:


const
  lin : array[1..8,1..3] of byte =
        ((1,2,3),(4,5,6),(7,8,9),
         (1,4,7),(2,5,8),(3,6,9),
         (1,5,9),(3,5,7));

Вот эта функция:


function Fin(pos: position)
var
   ni,sa,so,i,j,sj,res:byte;
begin
 ni:=5;
 res:=0;
 for i:=1 to 8 do begin
   sa:=5;so:=0;li[i]:=0;
   for j:=1 to 3 do begin
     sj:=pos[lin[i,j]];
     sa := sa and sj;
     so := so or sj;
     li[i] := li[i] + sj
   end;
   res := res or sa;
   ni := ni and so
 end;
 if ni=5 then res:=3;
 Fin:=res
end;

Видно, что выходными значениями этой функции являются:

1 - победа крестиков;

4 - победа ноликов;

3 - ничья;

0 - игра не окончена.


Глобальный массив li: array [1..8] of byte для определения признаков окончания игры не нужен. В нем предварительно готовятся данные (суммы значений фигур по каждому ряду) для дальнейшего определения рейтингов полей.


Анализ ситуации на поле производится после каждого полухода ( т.е. хода человека или компьютера) следующим образом:


procedure Analis;
begin
 case Fin(Kl) of
   0 : if ch then Rayting;
   1 : StopGame("Вы выиграли");
   3 : StopGame("Ничья");
   4 : StopGame("Вы проиграли");
 end
end;

Здесь StopGame - процедура, блокирующая продолжение игры с выводом соответствующего сообщения (подробно здесь не описывается). Процедура Rayting и есть главная подпрограмма, определяющая предпочтительность того или иного хода для компьютера. От ее реализации во многом зависит характер игры компьютера. Ясно, что наивысший рейтинг должен присваиваться полям, ход на которые ведет к немедленному выигрышу (мы дадим им значение 1000000). Следующие по важности - это поля, ход на которые способен предотвратить немедленный проигрыш (рейтинг 100000). Если указанных полей нет, то становятся важными поля, после хода на которые выигрыш неизбежен на следующем ходу (т.е. противнику ставится вилка - рейтинг 10000). Затем идут ходы, способные предотвратить вилку противника (1000). Более низкие рейтинги имеют подготовка вилки (100) и предотвращение подготовки вилки противником (10). И, наконец, просто пустая клетка, ход на которую возможен, имеет рейтинг 1 (в отличие от занятой клетки, рейтинг которой 0).


Для реализации процедуры, присваивающей рейтинги по вышеизложенному принципу, нам понадопится еще один вспомогательный массив-константа:


const
  kle : array [1..9,1..4] of byte =
     ((1,4,7,0),(1,5,0,0),(1,6,0,8),
      (2,4,0,0),(2,5,7,8),(2,6,0,0),
      (3,4,0,8),(3,5,0,0),(3,6,7,0));

Из этого массива легко определить номера рядов, в которые входит данная клетка, т.е. массив выполняет роль, обратную по сравнению с массивом lin.

Сама процедура Rayting имеет вид:


procedure Rayting;
var
 s00,s11,s44: array [0..3] of byte;
 s0,s1,s4,ssj,ii,j,jj,jjj,sj: byte;
begin
  for ii:=1 to 9 do Ray[ii]:=0;
  for ii:=1 to 9 do
   if Kl[ii]=0 then begin
     Ray[ii]:=Ray[ii]+1;
     s0:=0;s1:=0;s4:=0;
     for j:=1 to 4 do begin
       ssj:=kle[ii,j];
       if ssj<>0 then 
         case li[ssj] of
         0 : begin
              s00[s0]:=ssj;
              inc(s0);
              for jj:=0 to s4-1 do
                for jjj:=1 to 3 do begin
                  sj:=lin[ssj,jjj];
                  if sj<>ii then Ray[sj]:=Ray[sj]+100
                end
              for jj:=0 to s1-1 do begin
                for jjj:=1 to 3 do begin
                  sj:=lin[ssj,jjj];
                  Ray[sj]:=Ray[sj]+10;
                end
                for jjj:=1 to 3 do begin
                  sj:=lin[s11[jj],jjj];
                  if (sj<>ii)and(Kl[sj]=0) then
                      Ray[sj]:=Ray[sj]+10
                end
              end
             end; 
         1 : begin
              s11[s1]:=ssj;
              inc(s1);
              if s1>1 then begin
                Ray[ii]:=Ray[ii]+1000;
                for jj:=0 to s1-1 do
                  for jjj:=1 to 3 do begin
                    sj:=lin[s11[jj],jjj];
                    if (sj<>ii)and(Kl[sj]=0) then 
                       Ray[sj]:=Ray[sj]+1000
                  end
              end;         
              for jj:=0 to s0-1 do begin
                for jjj:=1 to 3 do begin
                  sj=lin[ssj,jjj];
                  if Kl[sj]=0 then Ray[sj]:=Ray[sj]+10
                end;
                for jjj:=1 to 3 do begin
                  sj:=lin[s00[jj],jjj];
                  if (sj<>ii)and(Kl[sj]=0) then
                     Ray[sj]:=Ray[sj]+10
                end
              end           
             end; 
         2 : Ray[ii]:=Ray[ii]+100000 
         4 : begin
              s44[s4]:=ssj;
              inc(s4);
              if s4>1 then Ray[ii]:=Ray[ii]+10000;
              for jj:=0 to s0-1 do
                for jjj:=1 to 3 do begin
                  sj:=lin[s00[jj],jjj];
                  if sj<>ii then Ray[sj]:=Ray[sj]+100
                end
             end; 
         5 : ; 
         8 : Ray[ii]:=Ray[ii]+1000000; 
         end
     end
   end
end;

Процедура Rayting позволяет реализовать достаточно сильную игру компьютера, причем "рассуждения" компьютера в данном случае близки к логике человека. Кроме того, несмотря на некоторую громоздкость алгоритма, процедура выполняется достаточно быстро, что позволяет ее использовать на слабых компьютерах или при реализации на интерпретируемых языках программирования. Так, я применил этот алгоритм для Flash-варианта крестиков-ноликов. Недостатком можно считать некоторое однообразие игры (отбрасывание некоторых вполне приемлемых вариантов хода, особенно в самом начале игры). Алгоритм вполне может быть улучшен, однако это я оставляю на усмотрение других разработчиков.


В программе, написанной на Delphi, применен другой вариант процедуры Rayting:


procedure Rayting;
var i: byte;
begin
 for i:=1 to 9 do
  if Kl[i]=0 then Ray[i]:=NextStep(Kl,i,4,0)
  else Ray[i]:=0
end;

Здесь NextStep(pos:position;i,fig,wlo:byte):byte - рекурсивная функция, позволяющая для данной позиции pos оценить рейтинг хода на клетку i фигурой fig при глубине данного хода wlo (в полуходах). Она имеет вид:


function NextStep(pos:position;i,fig,wlo:byte):byte;
var j : byte;
    ra:position;
begin
pos[i]:=fig;
inc(wlo);
if fig=1 then fig:=4 else fig:=1;
Result:=Fin(pos) shl 3;
if Result<>0 then exit;
if wlo<glub then
  begin
    for j:=1 to 9 do
      if pos[j]=0 then
        begin
          ra[j]:=NextStep(pos,j,fig,wlo);
          if ra[j]<16 then inc(ra[j]) else
          if ra[j]>24 then dec(ra[j])
        end;
    if fig=1 then
      begin
        Result:=32;
        for j:=1 to 9 do
          if (pos[j]=0) and (Result>ra[j])
            then Result:=ra[j]
      end
     else
      begin
        Result:=8;
        for j:=1 to 9 do
          if (pos[j]=0) and (Result < ra[j])
            then Result:=ra[j]
      end
  end
else Result:=16
end;

Максимальная глубина расчета задается глобальной переменной glub, что позволяет изменять уровень игры компьютера, изменяя эту переменную, а не переменную lvl. То есть, в процедуре SelectCell можно оставить только вторую половину кода. Кроме того, в этом случае не используются массивы li и kle. К сожалению, данный алгоритм работает медленнее, и его применение, например, в варианте Macromedia Flash очень сильно замедляет работу программы. Однако, при составлении программы на языках, использующих достаточно эффективный компилятор (Pascal, Delphi, C) алгоритм дает очень хорошие результаты.


Процедура Rayting при этом присваивает рейтинги полям по следующей шкале: 25..32 - ходы, приводящие к выигрышу ноликов, причем 32 соответствует немедленному выигрышу, 31 - выигрышу через полуход, 30 - через 2 полухода и т.д.; 24 - ходы, приводящие к гарантированной ничьей; 16 - ходы с непредсказанным результатом (т.е. глубина расчета, заданная переменной glub, оказалась недостаточной, чтобы судить о последствиях данного хода); 8..15 - поля, ход на которые при правильных ходах противника ведет к проигрышу, причем 8 - немедленный проигрыш, 9 - проигрыш через полуход, 10 - через два полухода и т.д.


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


Можно предложить и другие варианты расчета рейтинга. Так, например, можно просто составить таблицу, переводящую все возможные варианты массива Kl в массив Ray. Несмотря на громоздкость такой таблицы и большую трудоемкость ее составления, такой метод может оказаться наиболее быстродействующим. Кроме того, изменение этой таблицы сразу меняет характер игры компьютера.


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

к началу страницы
Rambler's Top100