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

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

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

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

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

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, который определяется следующим образом:

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;

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

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

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

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

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

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

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:

Здесь 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. Несмотря на громоздкость такой таблицы и большую трудоемкость ее составления, такой метод может оказаться наиболее быстродействующим. Кроме того, изменение этой таблицы сразу меняет характер игры компьютера.

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