Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


√лава 22. ¬едение игры






3. ѕерейти вниз к позиции й.

4. ¬ыбрать максимальное значение дл€ одного из преемников d, что приводит к получению V(d) = 4.

5. ¬ыполнить возврат к позиции №, а затем спуститьс€ вниз к позиции е.

6. –ассмотреть первого преемника е, значение которого равно 5. ¬ данный мо≠мент дл€ игрока ћ ј ’ (который должен сделать ход в позиции е) гарантирова≠но, по меньшей мере, значение 5 в позиции е, если даже не учитывать того, что из позиции е исход€т другие (возможно лучшие) альтернативы. Ёта оценка €вл€етс€ достаточной дл€ игрока MIM, чтобы пон€ть, что в узле № альтернатива е хуже, чем d, даже не зна€ точного значени€ е,

Ќа этом основании можно пренебречь вторым преемником позиции е и присвоить позиции е ориентировочное значение 5. Ќо така€ замена точного значени€ прибли≠зительным не вли€ет на расчетное значение b и, следовательно, на значение а.

Ќа этой идее основан знаменитый алъфа-бста-алгоритм (называемый также алго≠ритмом альфа-бета-отсечсни€), примен€емый дл€ эффективной реализации прин≠ципа минимакса. Ќа рис. 22.3 показано действие альфа-бета-алгоритм а на примере дерева, приведенного на рис. 22.2,  ак показано на рис. 22.3, некоторые из зафик≠сированных значений €вл€ютс€ приблизительными. Ќо, несмотр€ на такую замену точных значений приблизительными, дерево содержит достаточно информации дл€ точного определени€ значени€ корневого узла, ¬ примере, показанном на рис. 22.3, применение альф а-б era-алгоритма позвол€ет сократить сложность поиска с восьми ста≠тических оценок (как было первоначально на рис, 22.2) до п€ти статических оценок.


’ол игрока ћј’

с ’од игрока MIN

ћј’

Х i Х)

–ис. 22.3. ƒерево, приведенное на рис. 22.2, поиск в котором осуществл€етс€ с по≠мощью алъфабстаалгоритма. ѕри этот поиске отсекаютс€ узлы, обозначенные штриховыми лини€ми, поэтому общий объем поиска уменьшаетс€. ¬ результате некоторые из зафиксированных значений станов€тс€ неточными (в частности, это характерно дл€ узлов с, е, f; см рис. 22.2). Ќо, несмотр€ на такое снижение точности, дерево содержит достаточно информации дл€ правильного определени€ значении корневого узла и поиска основного варианта

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

как Alpha и Beta. Ёти ограничени€ имеют следующее значение: Alpha Ч это мини≠мальное значение, достижение которого уже гарантировано дл€ игра MAX, a Beta Ч максимальное значение, которого может наде€тьс€ достичь игрок ћј’ ≈сли позици€ рассматриваетс€ с точки зрени€ игрока W I N, то ¬еса Ч это наихудшее значение дл€



„асть It. ѕрименение €зыка Prolog а области искусственного интеллекта


M I K, достижение которого гарантировано дл€ игрока M I H. ѕоэтому фактическое зна≠чение (которое должно быть найдено) лежит в пределах от P.lpha до Beta. ≈сли ока≠залось, что некотора€ позици€ имеет значение, лежащее за пределами интервала Alpha-Beta, то этого достаточно, чтобы определить, что данна€ позици€ не относит≠с€ к основному варианту, даже не зна€ точного значени€ этой позиции. “очное значе≠ние позиции необходимо знать только в том случае, если оно находитс€ между Alpha и Beta. ѕон€тие достаточно хорошего зафиксированного значени€ V(P, Alpha, Beta) позиции – по отношению к ограничени€м Alpha и Beta можно определить фор≠мально как любое значение, которое удовлетвор€ет следующим требовани€м:

Vt P, Alpha, Beta) < Alpha, если V(P> < Alpha V<P,Alpha,Beta) = v(p), если Alpha < V[P) < Beta V(P, Alpha, Beta) > Beta, еслк V(P) > Beta

Ѕезусловно, мы можем всегда вычислить точное значение V(P) корневой позиции –, задава€ дл€ нее пределы следующим образом: V(P, -бесконечность, +оесконечность} = V(P)

¬ листинге 22,3 приведена реализаци€ альфа-бета-ал го ритма на €зыке Prolog. ќс≠новным отношением в этой программе €вл€етс€ следующее: alphabets [ Pos, Alpha, Beta, GoodPos, Val)

где GoodPos - достаточно хороший преемник –оз, поэтому его значение Val соот≠ветствует требовани€м, указанным выше, следующим образом: Val = V(Pos, Alpha, Beta)

Ћистинг 22.3. –еализаци€ альфа-бета-алгоритма

% јльфа-бета-алгоритм

alpbabeta(Pos, Alpha, Beta, GoodPos, Val):-moves(Pos, PcsList),!,

boundedbeat(PosList, Alpha, Beta, GoodPos, Val);
Staticval(Pos, Val). % —татическое значение позиции Pcs

boundedbestf [Pos 1 PosList], Alpha, Beta, GoodPos, GoodVal):-alphabeta{ Pos, Alpha, Beta, _, Val), goodenougH PosList, Alpha, Beta, Pos, Val, GoodPcs, Good val].

goodenough([], _, _, Pos, Val, Pos, Val):-!. % ƒругой кандидат отсутствует

goodenoughl _, Alpha, Beta, –оз, Val, Pos, Val):-

min to move (Pos), Val > Beta,! $ ¬ерхн€€ граница, достигнута€

~~ ~~ % максимизирующим оператором

max_to moue (Pos), Val < Alpha,!, * Ќижн€€ граница, достигнута€

% минимизирующим оператором

goodenoughi PosList, Alpha, Beta, –оз, Val, GoodPos, GoodVal):-

neutrounds(Alpha, Beta, Pos, Val, NewAlpha, MewBeta), % ”точнить границы boundedbest[ PosList, NewAlpha, MewBeta, Posl, Vail), betterofl Pos, Val, Posl, Vail, GoodPos, GoodVal).

newbounds(Alpha, Beta, Pos, Val, Val, Beta):-

min_to_move'{ Pos), Val > Alpha,!. * ћаксимизирующий оператор

2 увеличил нижнюю границу

newbounds(Alpha, Beta, Pos, Val, Alpha, Val):-

max to move! Pos), Val < Beta,!. I ћинимизирующий оператор

% уменьши верхнюю границу

newbounds(Alpha, Beta, _, _, Alpha, Beta). I ¬ противном случае границы

% не изменились


√лава 22. ¬едение игры



betteroft Pos, Val, Posl, Vail, Pos, Val):- % ѕозици€ Eos лучше, чем Posl min_to_itLove! Pos), Val > Vail,!

max_to_move(Pos), Val < Vail,!.

betteroft _, _, Posl, Vail, Posl, Vail). % ¬ противном случае лучше

% позици€ Posl

ѕроцедура baundedbest(PosList, Alpha, Beta, GbodPos, Val)

находит достаточно хорошую позицию GoodPos в списке PosList таким образом, что зафиксированное значение Val позиции GoodPos €вл€етс€ достаточно хорошим при≠ближением по отношению к Alpha и Beta.

јльф а-бета-интервал может стать более узким (но ни в коем случае не более ши≠роким!) при больших по глубине рекурсивных вызовах альфа-бета-процедуры. ќтно≠шение newbounds[ Alpha, Beta, Pos, Val, NewAlpha, NewBeta)

определ€ет новый интервал (NewAlpha, NewBeta), который всегда меньше или ра≠вен старому интервалу [ Alpha, Beta). ѕоэтому по мере перехода на более глубо≠кие уровни дерева поиска пределы Alpha-Beta сужаютс€ и позиции этих глубоких уровней оцениваютс€ в более узких пределах. »з-за сужени€ интервалов количество приближенных оценок увеличиваетс€ и поэтому отсечение поддеревьев в дереве ста≠новитс€ все более интенсивным. ¬ св€зи с этим возникает интересный вопрос: " акой объем работы позвол€ет сэкономить альфа-бета-алгоритм по сравнению с про≠граммой исчерпывающего поиска по принципу минимакса, приведенной в листин≠ге 22.2?" Ёффективность поиска с использованием альфа-бет а-алгоритм а зависит от того, в каком пор€дке происходит перебор позиций. ¬ыгоднее всего в первую очередь рассматривать самые сильные ходы дл€ каждого из игроков. ћожно легко показать на примерах, что если пор€док перебора окажетс€ неудачным, то альфа-бета-процедуре потребуетс€ перебрать все позиции, рассматриваемые при исчерпывающем минимаксном поиске. Ёто означает, что з худшем случае альфа-бета-ал го ритм не имеет преимуществ над исчерпывающим поиском по принципу минимакса. Ќо если пор€док €вл€етс€ благопри€тным, экономи€ усилий может оказатьс€ весьма значи≠тельной. ѕредположим, что N - количество заключительных позиций поиска, ста≠тически оцениваемых с помощью исчерпывающего минимаксного алгоритма. Ѕыло доказано, что в наилучшем случае, когда вначале всегда рассматриваетс€ самый сильный ход, альфа-бет а-алгоритм требует статической оценки лишь %/N ѕќ«»÷»….

ƒобавим к этому, что данный результат подтвержден на практике при проведении шахматных турниров. Ќа соревновани€х шахматной программе обычно даетс€ опре≠деленное количество времени дл€ вычислени€ следующего хода в игре, а глубина, на которую программа может выполнить поиск, зависит от этого количества времени. ¬ наилучшем случае альфа-бета-алгоритм оказалс€ способным выполн€ть поиск на глубину, в два раза большую по сравнению с исчерпывающим минимаксным поис≠ком. Ёксперименты показали, что одна и та же функци€ оценки, примен€ема€ на большей глубине дерева, обычно позвол€ет обеспечить более сильную игру.

–езультаты экономии усилий при использовании альфа-бета-алгоритма можно также выразить в терминах эффективного коэффициента ветвлени€ (среднего ко≠личества ветвей, отход€щих от каждого внутреннего узла) дерева поиска. ѕредполо≠жим, что дерево игры имеет единообразный коэффициент ветвлени€ №, ¬ результате отсечени€ альфа-бета-алгоритм требует поиска лишь в некоторых из ветвей, что фак≠тически приводит к уменьшению коэффициента ветвлени€. ¬ наилучшем случае та≠кое сокращение находитс€ в пределах от b до ^№. ¬ программах игры в шахматы фактический коэффициент ветвлени€ в результате альфа-бета-отсечени€ становитс€ приблизительно равным 6 по сравнению с общим количеством допустимых ходов, примерно равным 30. ћенее оптимистические оценки этого результата показывают,



„асть ». ѕрименение €зыка Prolog в области искусственного интеллекта


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

ѕроект

–ассмотрите игру с двум€ участниками (например, некоторую нетривиальную версию игры в крестики и нолики). Ќапишите отношени€ с определением игры (допустимых ходов и заключительных игровых позиций) и предложите статическую функцию оценки, примен€емую дл€ ведени€ этой игры с помощью альфа-бета-процедуры.

22.4. ѕрограммы, основанные на принципе минимакса: усовершенствовани€ и ограничени€

ѕринцип минимакса, нар€ду с альфа-бета-алгоритмом, €вл€етс€ основой многих удачных программ ведени€ игр; наиболее известными из них €вл€ютс€ шахматные программы. ќбща€ схема такой программы состоит в следующем: выполнить альфа-бста-лоиск в текущей позиции игры, вплоть до некоторой фиксированной предельной глубины (котора€ определ€етс€ временными ограничени€ми, налагаемыми правила≠ми соревнований), использу€ характерную дл€ данной игры функцию оценки дл€ определени€ значений заключительных позиций поиска; после этого выполнить на игровой доске наилучший ход (в соответствии с альфа-бета-алгоритмом), прин€ть от≠вет противника и снова приступить к выполнению того же цикла.

ѕоэтому двум€ основными компонентами подобной программы €вл€ютс€ альфа-бета-алгоритм и эвристическа€ функци€ оценки. ƒл€ создани€ качественной про≠граммы ведени€ такой сложной игры, как шахматы, необходимо ввести р€д усовер≠шенствований в эту основную схему. ¬ данном разделе рассматриваютс€ некоторые стандартные методы.

ћногое зависит от функции оценки. ≈сли бы у нас была идеальна€ функци€ оценки, то достаточно было бы рассмотреть только непосредственных преемников те≠кущей позиции, фактически устранив при этом поиск. Ќо в таких играх, как шах≠маты, люба€ функци€ оценки с практически приемлемой вычислительной сложно≠стью об€зательно должна быть просто эвристической функцией оценки. Ёта оценка основана на "статических" свойствах позиции (в частности, числа фигур на доске) и поэтому в некоторых позици€х €вл€етс€ более надежной, чем в других. Ќапример, рассмотрим подобную функцию оценки дл€ шахмат, основанную на учете количества фигур (как прин€то называть их в шахматах Ч материала) и представим себе пози≠цию, в которой белые имеют лишнего кон€. Ѕезусловно, что эта функци€ оценит по≠зицию белых как более благопри€тную. –азумеетс€, така€ оценка €вл€етс€ вполне приемлемой, если игра развиваетс€ спокойно и черные не имеют в своем распор€же≠нии внезапных угроз, — другой стороны, если на следующем ходе черные могут вз€ть ферз€ белых, то така€ оценка может привести к роковой ошибке, поскольку она не позвол€ет оценить позицию динамически. Ѕезусловно, что статической оценке можно скорее довер€ть в спокойной игре, а не в резко измен€ющихс€ позици€х острой борьбы, когда кажда€ из сторон непосредственно угрожает вз€ть фигуры противни≠ка. ќчевидно, что статическа€ оценка может использоватьс€ только в спокойных по≠зици€х. ѕоэтому стандартный прием состоит в том, что поиск в опасных позици€х должен продлеватьс€ за пределы глубины до тех пор, пока не будет достигнута спо≠койна€ позици€. ¬ частности, дл€ применени€ этого расширени€ необходимо запро≠граммировать последовательности вз€ти€ фигур с обеих сторон (обмена фигурами) в шахматах.

≈ще одним усовершенствованием €вл€етс€ эвристическое отсечение. ќно предна≠значено дл€ достижени€ большего предела глубины благодар€ исключению из рас-


√лава 22. ¬едение игры



смотрени€ некоторых менее перспективных продолжений. Ётот метод позвол€ет от≠секать некоторые ветви дерева игры в дополнение к тем, которые были отсечены с помощью самого альф а-бета-алгоритма. ѕоэтому он св€зан с тем риском, что некото≠рые удачные продолжени€ не будут обнаружены, а значение минимакса вычислено неправильно.

≈ще одним важным методом €вл€етс€ последовательное углубление. ѕрограмма повторно выполн€ет альфа-бета-поиск, вначале осуществл€€ поиск на некоторую не≠большую глубину, а затем увеличива€ предел глубины после каждой итерации. Ётот процесс останавливаетс€ после достижени€ определенного предела времени. «атем выполн€етс€ ход, который оказалс€ наилучшим в соответствии с результатами наи≠более глубокого поиска. “акой метод имеет следующие преимущества.

Х ѕозвол€ет учитывать контроль времени; после достижени€ предела времени всегда имеетс€ в запасе некоторый наилучший ход, найденный до сих пор.

Х ћинимаксные значени€ предыдущей итерации могут использоватьс€ дл€ предварительного упор€дочени€ позиций в следующей итерации, что позвол€≠ет в альфа-бета-алторитме в первую очередь выполн€ть поиск среди самых сильных ходов.

ѕри последовательном углублении возникают определенные дополнительные из≠держки (св€занные с повторным поиском в верхних част€х дерева игры), но они €вл€≠етс€ довольно незначительными по сравнению с общим положительным результатом.

»звестным недостатком программ, реализованных по этой общей схеме, €вл€етс€ эффект горизонта. ѕредположим, что рассматриваетс€ шахматна€ позици€, в кото≠рой игрок, за которого выступает программа, неизбежно тер€ет кон€. Ќо потерю ко≠н€ можно отдалить, пожертвовав менее ценную фигуру, скажем, пешку. “ака€ про≠межуточна€ жертва может отодвинуть фактическую потерю кон€ за пределы поиска (за "горизонт", куда не может загл€нуть программа), ¬ таком случае, не вид€, что конь в конечном итоге все равно будет потер€н, программа выбирает этот вариант, а не такое продолжение, в котором потер€ кон€ произойдет быстрее, но без ненужных жертв. ѕоэтому программа в конечном итоге потер€ет и пешку (без необходимости), и кон€. Ёффект горизонта может быть устранен путем продлени€ поиска вплоть до спокойной позиции.

Ќо программы, основанные на использовании принципа минимакса, имеют более фундаментальное ограничение, св€занное с тем, что в них примен€ютс€ лишь огра≠ниченна€ форма знаний, характерных дл€ данной проблемной области. Ёто стано≠витс€ особенно заметным при сравнении лучших шахматных программ с опытными шахматистами. ћощные программы часто выполн€ют поиск среди миллионов {и да≠же большего числа) позиций, прежде чем выбрать очередной ход. ј психологические исследовани€ показывают, что шахматисты обычно выполн€ют поиск лишь среди нескольких дес€тков позиций, самое большее среди нескольких сотен. Ќесмотр€ на такую "низкую производительность" поиска, шахматист все еще может выиграть у программы. ѕреимущество шахматных мастеров заключаетс€ в их знани€х, которые намного превосход€т все, что содержатс€ в программах. —оревновани€ между ком≠пьютерами и сильными шахматистами показывают, что неверо€тное превосходство в вычислительной мощности не всегда может полностью компенсировать нехватку знаний.

«нани€, которые могут быть введены в программы, основанные на принципе ми≠нимакса, принимают следующие основные формы.

Х ‘ункци€ оценки.

Х Ёвристические методы отсечени€ поддеревьев дерева.

Х Ёвристические методы поиска спокойных позиций.

‘ункци€ оценки сводит многочисленные аспекты игровой ситуации к единствен≠ному числу, и такое сокращение может иметь отрицательный эффект. ¬ отличие от этого, понимание игровой позиции хорошим игроком €вл€етс€ многомерным. –ас≠смотрим пример из шахмат: некотора€ функци€ оценки может оценить позицию как

542 „асть II. ѕрименение €зыка Prolog в области искусственного интеллекта


равную, просто указав, что ее значение равно 0. ј оценка той же позиции шахмати≠стов может быть гораздо более содержательной и указывать на то, как дальше долж≠на развиватьс€ игра. Ќапример, у черных есть лишн€€ пешка, но белые имеют хо≠рошую атакующую инициативу, котора€ компенсирует материал, поэтому шансы равны.

¬ шахматах программы, основанные на принципе минимакса, обычно играют лучше в жестких тактических битвах, когда решающим становитс€ точный расчет форсированных вариантов. »х слабости с большей веро€тностью про€вл€ютс€ в спо≠койных позици€х, когда игра этих программ характеризуетс€ отсутствием долговре≠менных планов, играющих решающую роль в медленных, стратегических играх. »з-за отсутстви€ плана создаетс€ впечатление, что на прот€жении всей игры программа случайным образом переходит от одной шахматной идеи к другой.

¬ остальной части этой главы рассмотрим еще один подход к ведению игр, осно≠ванный на использовании в программе типовых знаний, которые представлены в ви≠де советов. Ёто позвол€ет реализовывать в игровой программе целенаправленное плановое поведение.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-10-01; ћы поможем в написании ваших работ!; просмотров: 418 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ќаглость Ц это ругатьс€ с преподавателем по поводу четверки, хот€ перед экзаменом уверен, что не знаешь даже на два. © Ќеизвестно
==> читать все изречени€...

1835 - | 1485 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.035 с.