Искусственный интеллект и компьютерные игры.

Искусственный интеллект - одно из направлений развития современного программного обеспечения. Мы довольно часто сталкиваемся с ним в повседневной жизни, в том числе и при работе с компьютером. Например: компьютерная программа играет в шахматы, шашки, карты и другие интеллектуальные игры, причем не хуже профессиональных игроков в эти игры. При всем этом эти программы имеют сравнительно небольшой объем. Например,  шахматная программа может занимать объем всего 70-80 килобайт.  При этом  возникает вопрос: каким образом относительно несложной компьютерной программе удается довольно хорошо играть в интеллектуальные игры, причем довольно часто выигрывать? Для того, чтобы ответить на этот вопрос следует поразмыслить над тем, как мы сами играем в шахматы или шашки.

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

        Теперь подумаем, как можно применить эти принципы для написания компьютерной программы, которая могла бы играть в одну из интеллектуальных игр. Современные компьютеры не обладают возможностью самообучения, поэтому  компьютер не может самостоятельно приобретать опыт деятельности в какой-либо сфере. Опыт человека также не может помочь компьютеру, так как его сложно переложить на язык программирования. Понятие "здравый смысл" настолько абстрактно для программирования, что его практически невозможно учесть при написании программы. Соответственно,  "алгоритм" применяемый человеком абсолютно не подходит для компьютера.

        С первого взгляда кажется, что можно внести в компьютер все возможные комбинации игры и ходы для каждой из них, но это абсолютно нереально. Если  для такой несложной игры, как крестики-нолики количество всех комбинаций составляет

"всего" 362 880, то для шахмат это число уже  1 461 501 000 000 000 000 000 000 000 000 000 000 000 000 000 000  комбинаций. Даже для введения трехсот тысяч комбинаций следует потратить очень много времени, а что уж говорить о шахматах с их бесчисленным количеством комбинаций, да и перебор этих комбинаций может занять очень много времени.  

Принципы разработки алгоритмов для интеллектуальных игр.

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

 Как видно из этого сравнения,  алгоритм интеллектуальной игры для реализации его на компьютере должен точно регламентировать выбор того или иного хода. Но как же определить, какой ход является правильным в данной ситуации? Логично, что этот ход должен быть одним из возможных в данное время. То есть для начала нужно определить, какие из ходов возможны в данный момент. Также искомый ход должен быть наиболее выгодным в данной ситуации. Поэтому если вычислить определенный показатель выгодности хода, то из всех ходов можно выбрать наиболее выгодный.  Этот показатель выгодности хода можно выразить числом, но как же его вычислить? Оказывается, это не так сложно.  Он должен вычисляться из нескольких факторов. Например, для шахмат это могут быть возможность взять те или иные фигуры, продвинуться по полю доски в сторону противника. Проанализировав все эти факторы и присвоив различным ситуациям, возникающим при выполнении данного хода различные "оценки" и сложив результаты по нескольким факторам, мы получим тот самый искомый показатель выгодности хода. Затем следует выбрать  ход с наибольшим показателем выгодности и привести его в действие, что с программной точки зрения выполнить абсолютно несложно. Таким образом, мы получили универсальный алгоритм для интеллектуальных игр, причем доступный для его реализации на компьютере. В общей записи этот алгоритм выглядит следующим образом:

Исполнение хода.

Вычисление показателей выгодности для каждого из возможных ходов

Определение самого выгодного хода на основе показателей выгодности.

Определение всех возможных ходов в данной ситуации

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

X>=RND ?

Определение  случайного хода.

Исполнение хода.

Вычисление показателей выгодности для каждого из возможных ходов

Определение самого выгодного хода на основе показателей выгодности.

Определение всех возможных ходов в данной ситуации

Нет

Да

В этом алгоритме введена дополнительная переменная X. Она устанавливает уровень сложности игры алгоритма. Решение о том, насколько выгодным будет следующий ход, принимается на основе сравнения этой переменной со случайным числом (его несложно вычислить с помощью функции RND, входящей практически во все языки программирования). Алгоритм будет играть наиболее сложно при X=0 (Все ходы наиболее выгодные)  и наименее сложно при X=1(все ходы случайные  (случайное число лежит в пределах от 0 до 1)) .

Пример действующего алгоритма.

1.Описание алгоритма.

 Теперь рассмотрим  действующий алгоритм интеллектуальной игры тогызкумалак.

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

Входные данные: текущее состояние игры.

Вычисление хода по вспомогательному алгоритму.

Исполнение хода.

Дополнительная проверка результата хода.

Выбор наиболее выгодного хода.

Подготовка хода для нападения.

Вычисление всех возможных ходов.

Вычисление хода для защиты

Оценка текущей ситуации.

X>= RND?

Да

Нет

Возможность атаки противника.

Возможно нападение на противника через несколько ходов.

Было подготовлено нападение на противника

Угроза.

Ход не подходит для данной ситуации.

Исполнение хода нападения.

Вычисление случайного хода.

Ход действительно выгоден.

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

2.Реализация алгоритма на языке Pascal.

Текст этого алгоритма на языке Pascal занимает примерно 400 строк:

unit movegen;

interface

type

TGroove=array[1..9] of integer;

tmove2=object

              grooves:array[1..2] of TGroove;

              biggrooves:array[1..2] of integer;

              hardlevel:real;

              attack:boolean;

              bonus1,bonus2:boolean;

              bonus1location:integer;

              bonus2location:integer;

              planned:boolean;

              movenum:integer;

              procedure Generate(var groove,num:integer);

              procedure getmaxoddity(var groove:integer;can:integer);

              function getmaxC:integer;

              function getmaxenemyC:integer;

              procedure getparams(need:integer;var gr,nm:integer;pr:integer);

              function getnooddity:integer;

              function getnooddityif(gv,n:integer):integer;

              function getProfit(n,grn:integer):integer;

              function all1:boolean;

              procedure zero(var grv,nmm:integer);

              procedure zero2(var grv,nmm:integer);

              procedure zero3(var grr,mnn:integer);

              procedure zero4(var gr,nm:integer);

              function underattack:boolean;

              function underfault:boolean;

              procedure getbestmove2(var prof:integer;var nn:integer;gr0:integer);

              function noAlg(cn:integer):integer;

end;

implementation

uses grnew,crt;

function min(a,b:integer):integer;

var result:integer;

begin

if a

min:=result;

end;

procedure tmove2.Generate(var groove,num:integer);

var

a,b,c,d:integer;

s,s2:string;

as,c0:integer;

begin

c0:=0;

for as:=1 to 8 do inc(c0,integer(grooves[2][as]=0));

if c0=8 then if biggrooves[2]

if c0<>8 then begin

getmaxoddity(a,getmaxc);

if underattack then if movenum<>1 then begin

  a:=-128;

  end;

if underfault then a:=-128;

if hardlevel>0.050 then if hardlevel>=random then begin

 a:=-128;

end;

if a=-128 then begin

 zero3(groove,num);

 end

  else if b>0 then getparams(a,groove,num,grooves[1][a]-a) else zero3(groove,num);{no2}

str(groove,s);

s2:=s2+s+'  ,  ';

str(num,s);

s2:=s2+s;

end

else begin

groove:=9;

num:=grooves[2][9];

end;

end;

function tmove2.getProfit(n,grn:integer):integer;

begin

getprofit:=n-grn+1;

end;

procedure tmove2.getmaxoddity(var groove:integer;can:integer);

var

gr:TGroove;

as:integer;

mx:integer;

bnsi:integer;

can2:integer;

begin

bnsi:=0;

if can<2 then can2:=can else can2:=2;

for as:=1 to can2 do if grooves[1][as]=2 then if bonus2location=0 then if not planned then begin

 bnsi:=as;

end;

if bnsi<>0 then groove:=bnsi else begin

for as:=1 to 9 do begin

if  odd(grooves[1][as]) then gr[as]:=getprofit(grooves[1][as],as) else gr[as]:=-100;

end;

mx:=-32767;

for as:=1 to can do begin

mx:=max(mx,gr[as]);

end;

for as:=can downto 1 do begin

if gr[as]=mx then groove:=as;

end;

if mx<0 then groove:=-128;

end;

if noalg(can)<>0 then if not planned then groove:=noalg(can);

planned:=false;

end;

function tmove2.getnooddity:integer;

var

result,as:integer;

begin

result:=0;

for as:=1 to 9 do begin

if not odd(grooves[2][as]) then inc(result,11);

getnooddity:=result;

end;

end;

function tmove2.getmaxC:integer;

var

as:integer;

values:array[1..9] of integer;

vl:integer;

mx:integer;

s:string;

begin

for as:=1 to 9 do begin

vl:=(grooves[2][as]-1)-(9-as)+integer(grooves[2][as]=1);

values[as]:=vl;

end;

mx:=0;

for as:=1 to 9 do begin

mx:=max(mx,values[as]);

end;

str(mx,s);

if mx>9 then mx:=9;

getmaxC:=mx;

end;

function tmove2.getmaxenemyC:integer;

var

as:integer;

values:array[1..9] of integer;

vl:integer;

mx:integer;

s:string;

begin

for as:=1 to 9 do begin

vl:=(grooves[1][as]-1)-(9-as)+integer(grooves[1][as]=1);

values[as]:=vl;

end;

mx:=0;

for as:=1 to 9 do begin

mx:=max(mx,values[as]);

end;

str(mx,s);

if mx>9 then mx:=9;

getmaxenemyC:=mx;

end;

function tmove2.UnderAttack:boolean;

var

ec,as:integer;

uat:integer;

rsu:boolean;

begin

ec:=getmaxenemyc;

uat:=0;

for as:=1 to ec do begin

if odd(grooves[2][as]) then begin

uat:=max(uat,grooves[2][as]-as);

end;

end;

if uat>4 then rsu:=true else rsu:=false;

if rsu then begin

end;

underattack:=rsu;

end;

function tmove2.underfault:boolean;

var res:boolean;

as:integer;

cn:integer;

begin

res:=false;

cn:=getmaxenemyc;

if cn>1 then cn:=1;

for as:=1 to cn do if grooves[2][as]=2 then res:=true;

underfault:=res;

end;

procedure tmove2.getparams(need:integer;var gr,nm:integer;pr:integer);

var as:integer;

vl:integer;

tm,tm2:integer;

am:array[1..9] of boolean;

ab:array[1..9] of integer;

mni:integer;

pgg:integer;

begin

for as:=1 to 9 do ab[as]:=100;

for as:=1 to 9 do am[as]:=false;

for as:=9 downto 1 do begin

vl:=(grooves[2][as]-1)-(9-as)+integer(grooves[2][as]=1);

if vl>=need then am[as]:=true;

end;

for as:=1 to 9 do begin

if am[as] then begin

tm:=9-as;

ab[as]:=getnooddityif(as,tm);

end;

end;

mni:=32767;

for as:=1 to 9 do begin

mni:=min(mni,ab[as]);

end;

for as:=9 downto 1 do begin

if mni=ab[as] then tm2:=as;

end;

if movenum=1 then pgg:=10 else pgg:=4;

if getnooddityif(tm2,9-tm2)>pgg then begin

 zero3(gr,nm);

 end

 else begin

gr:=tm2;

nm:=need-tm2+9;

end;

end;

procedure tmove2.zero(var grv,nmm:integer);

var

as:integer;

mx:integer;

begin

mx:=0;

for as:=9 downto 1 do begin

mx:=max(mx,grooves[2][as]);

end;

for as:=9 downto 1 do begin

if grooves[2][as]=mx then grv:=as;

end;

if mx>0 then nmm:=grooves[2][grv] else nmm:=0;

end;

procedure tmove2.zero2(var grv,nmm:integer);

var

as:integer;

mx:integer;

g00:integer;

begin

mx:=0;

for as:=9 downto 1 do begin

mx:=max(mx,grooves[2][as]);

end;

if getnooddity>7 then begin

for as:=1 to 9 do begin

if grooves[2][as]=mx then g00:=as;

end;

end

else begin

for as:=9 downto 1 do begin

if grooves[2][as]=mx then g00:=as;

end;

end;

if (grooves[2][g00])<=(9-g00) then begin

 grv:=g00;

 nmm:=grooves[2][g00];

 end

 else begin

 nmm:=9-g00;

 grv:=g00;

 end;

if nmm=0 then if grv=9 then begin

for as:=1 to 8 do begin

if grooves[2][as]<>0 then g00:=as;

end;

if (grooves[2][g00])<=(9-g00) then begin

 grv:=g00;

 nmm:=grooves[2][g00];

 end

 else begin

 nmm:=9-g00;

 grv:=g00;

 end;

end;

if nmm=0 then begin

 grv:=9;

 nmm:=1;

end;

if grv=9 then if nmm=1 then if grooves[1][1]=2 then begin

for as:=1 to 8 do begin

if grooves[2][as]<>0 then g00:=as;

end;

if (grooves[2][g00])<=(9-g00) then begin

 grv:=g00;

 nmm:=grooves[2][g00];

 end

 else begin

 nmm:=9-g00;

 grv:=g00;

 end;

end;

end;

function tmove2.all1:boolean;

var

as:integer;

result:boolean;

begin

result:=true;

for as:=1 to 9 do

if grooves[2][as]>1 then result:=false;

all1:=result;

end;

function tmove2.getnooddityif(gv,n:integer):integer;

var

barr:array[1..9] of boolean;

bc2:array[1..9] of integer;

as:integer;

result:integer;

tmp:integer;

enc:integer;

mx2:integer;

begin

enc:=getmaxenemyc;

for as:=1 to 9 do barr[as]:=(odd(grooves[2][as]));

tmp:=gv+n;

if grooves[2][gv]=0 then result:=100 else begin

if tmp>14 then result:=100 else begin

if tmp>9 then tmp:=9;

for as:=gv to tmp do barr[as]:=(not barr[as]);

barr[gv]:=odd(grooves[2][gv]-n);

result:=0;

mx2:=0;

for as:=1 to enc do begin

if  barr[as] then bc2[as]:=grooves[2][as]-as else bc2[as]:=-32767;

end;

for as:=1 to enc do mx2:=max(mx2,bc2[as]);

result:=mx2;

end;

end;

if tmp>900 then result:=100;

getnooddityif:=result;

end;

procedure tmove2.getbestmove2(var prof:integer;var nn:integer;gr0:integer);

var

arr1:array[0..162] of integer;

arr2:array[1..9] of integer;

as:integer;

mx:integer;

tgn:integer;

begin

prof:=0;

tgn:=(grooves[2][gr0]-1)+integer(grooves[2][gr0]=1);{gr0;}

if tgn>(1-integer(grooves[2][gr0]=1)) then begin

for as:=1 to tgn do arr1[as]:=getnooddityif(gr0,as);

mx:=32767;

for as:=1 to tgn do mx:=min(mx,arr1[as]);

for as:=1 to tgn do begin

 if arr1[as]=mx then nn:=as;

end;

end

else prof:=100;

if prof<>100 then prof:=getnooddityif(gr0,nn);

end;

procedure tmove2.zero3(var grr,mnn:integer);

var

arrG:array[1..9] of integer;

arrp:array[1..9] of integer;

as:integer;

minimal:integer;

begin

if underfault then begin

zero4(grr,mnn);

end

else begin

for as:=1 to 9 do getbestmove2(arrp[as],arrg[as],as);

minimal:=32767;

for as:=1 to 9 do minimal:=min(minimal,arrp[as]);

for as:=1 to 9 do begin

 if minimal=arrp[as] then grr:=as;

 end;

mnn:=arrg[grr];

if mnn<=0 then zero2(grr,mnn);

if mnn>grooves[2][grr] then zero2(grr,mnn);

end;

end;

function tmove2.noAlg(cn:integer):integer;

var

as,resl,rc,sr:integer;

begin

resl:=0;

if cn>1 then

for as:=cn downto 2 do begin

if not odd(grooves[1][as-1]) then if not odd(grooves[1][as]) then

begin

sr:=0;

for rc:=1 to as-2 do if grooves[1][rc]<>0 then sr:=1;

if sr=0 then resl:=as-1;

end;

end;

if not attack then resl:=0;

noalg:=resl;

end;

procedure tmove2.zero4(var gr,nm:integer);

var

as,r:integer;

begin

for as:=9 downto 1 do if grooves[2][as]=2 then r:=as;

gr:=r;

nm:=1;

if r>1 then if grooves[2][r+1]=1 then if grooves[2][r-1]>0 then begin

gr:=1;

nm:=1;

end;

end;

begin

end.

Полный текст этой программы на языке программирования  занимает примерно 100 страниц и около 4700 строк, поэтому я не стал распечатывать его. Этот текст  и саму программу можно найти на дискете, приложенной к работе.

Тенденции развития искусственного интеллекта.

Дальнейшее развитие подобных алгоритмов искусственного интеллекта для компьютерных игр состоит в том, что в них вводятся некоторые известные ситуации игры и их решения, но для этого требуются очень большие ресурсы памяти и скорости вычислений, поэтому реализовать их удается только на очень мощных компьютерах. И это стоит того: программа F3D, разработанная группой программистов в США проведя несколько партий в шахматы с Гари Каспаровым, выиграла у него одну  партию, одну проиграла и одну свела к ничьей.

Но искусственный интеллект находит применение не только в интеллектуальных играх, его применяют во многих областях деятельности человека: от космических исследований до автомобилей. И во всех этих сферах искусственный интеллект помогает человеку благодаря логике и скорости принятия решений. Теперь компьютерные программы способны даже на копирование интеллекта человека. Недавно в Интернете появился искусственный интеллект Джона Леннона, то есть ему стало возможным задавать ему вопросы, на которые он логично отвечает. Может быть в будущем учитель, готовясь к уроку сможет с помощью компьютера, например, поговорить с Пушкиным, или взять интервью у Вашингтона. Все это, а также многое другое может стать возможным с помощью искусственного интеллекта.