TechCodeview

Адверсариал сеарцх је потрага, где испитујемо проблем који настаје када покушавамо да планирамо испред света, а други агенти планирају против нас.

• У претходним темама проучавали смо стратегије претраживања које су повезане само са једним агентом који има за циљ да пронађе решење које се често изражава у облику низа акција.
• Али, могу постојати неке ситуације у којима више од једног агента тражи решење у истом простору за претрагу, а ова ситуација се обично дешава током играња игрица.
• Окружење са више од једног агента се назива као окружење са више агената , у којој је сваки агент противник другог агента и игра један против другог. Сваки агент треба да размотри деловање другог агента и ефекат те акције на њихов учинак.
• Тако, Претраге у којима два или више играча са супротстављеним циљевима покушавају да истраже исти простор за претрагу за решење, називају се супротстављеним претрагама, често познатим као игре .
• Игре су моделоване као проблем претраге и функција хеуристичке евалуације, а ово су два главна фактора који помажу у моделирању и решавању игара у АИ.

Врсте игара у АИ:

Савршене информације:Игра са савршеним информацијама је она у којој агенти могу погледати у комплетну таблу. Агенти имају све информације о игри, а могу и да виде једни друге потезе. Примери су шах, даме, го итд.Несавршене информације:Ако у игри агенти немају све информације о игри и нису свесни шта се дешава, такве игре се називају играма са несавршеним информацијама, као што су тиц-тац-тое, Баттлесхип, блинд, Бридге, итд.Детерминистичке игре:Детерминистичке игре су оне игре које прате стриктан образац и скуп правила за игре и с њима не постоји случајност. Примери су шах, даме, Го, тиц-тац-тое итд.Недетерминистичке игре:Недетерминистичке су оне игре које имају различите непредвидиве догађаје и имају фактор случајности или среће. Овај фактор случајности или среће се уводи или коцкицама или картама. Они су насумични и сваки одговор на акцију није фиксан. Такве игре се називају и стохастичким играма.
Пример: Бацкгаммон, Монопол, Покер, итд.

Напомена: У овој теми ћемо разговарати о детерминистичким играма, потпуно видљивом окружењу, нултом збиру и где сваки агент делује алтернативно.

Игра нулте суме

• Игре са нултим сумом су супротстављена претрага која укључује чисто такмичење.
• У игри са нултим сумом добитак или губитак корисности сваког агента је тачно избалансиран губицима или добицима од корисности другог агента.
• Један играч игре покушава да максимизира једну једину вредност, док други играч покушава да је минимизира.
• Сваки потез једног играча у игри назива се играње.
• Шах и тиц-тац-тое су примери игре са нултом сумом.

Игра са нултим сумом: Уграђено размишљање

Игра са нултим сумом укључивала је уграђено размишљање у којем један агент или играч покушава да схвати:

• Шта да радим.
• Како одлучити о потезу
• Треба мислити и на свог противника
• Противник такође размишља шта да ради

Сваки од играча покушава да сазна одговор свог противника на њихове акције. Ово захтева уграђено размишљање или резоновање уназад да би се решили проблеми игре у АИ.

Формализација проблема:

Игра се може дефинисати као врста претраге у АИ која се може формализовати од следећих елемената:

Почетно стање:Одређује како је игра постављена на почетку.Играч(и):Одређује који играч се померио у простору стања.Радња(е):Враћа скуп легалних потеза у државном простору.Резултат(и, а):То је модел транзиције, који специфицира резултат кретања у простору стања.Терминални тест(и):Терминални тест је истинит ако је игра готова, у супротном је у сваком случају нетачан. Стање у којем се игра завршава назива се терминалним стањима.Помоћ(и, п):Функција корисности даје коначну нумеричку вредност за игру која се завршава у терминалним стањима с за играча п. Такође се зове функција исплате. За шах, исходи су победа, пораз или реми, а његове исплатне вредности су +1, 0, ½. А за тиц-тац-тое, корисне вредности су +1, -1 и 0.

Стабло игре:

Стабло игре је дрво где су чворови стабла стања игре, а ивице стабла су потези играча. Стабло игре укључује почетно стање, функцију радњи и функцију резултата.

Пример: дрво игре Тиц-Тац-Тое:

јсон фајл

Следећа слика приказује део стабла игре за тиц-тац-тое игру. Следе неке кључне тачке игре:

• Постоје два играча МАКС и МИН.
• Играчи имају алтернативни окрет и почињу са МАКС.
• МАКС максимизира резултат стабла игре
• МИН минимизира резултат.

Пример објашњења:

• Од почетног стања, МАКС има 9 могућих потеза док први крене. МАКС место к и МИН место о, и оба играча играју наизменично све док не дођемо до листног чвора где један играч има три у низу или су сва поља попуњена.
• Оба играча ће израчунати сваки чвор, минимак, минималну вредност која је најбољи могући алат против оптималног противника.
• Претпоставимо да су оба играча добро свесна тиц-тац-тое и да играју најбољу игру. Сваки играч даје све од себе да спречи још једног да победи. МИН делује против Мака у игри.
• Дакле, у стаблу игре имамо слој од Мак, слој од МИН, а сваки слој се зове као Пли . Максимално место к, затим МИН ставља о да би се спречило да Мак победи, и ова игра се наставља до терминалног чвора.
• У овом случају или МИН побеђује, МАКС побеђује или је нерешено. Ово стабло игре је читав простор претраживања могућности које МИН и МАКС играју тик-так-тое и смењују се наизменично.

Према томе, контрадикторна претрага минимакс процедуре функционише на следећи начин:

• Циљ му је да пронађе оптималну стратегију за МАКС-а да победи у игри.
• Следи приступ претраге у дубину.
• У стаблу игре, оптимални листни чвор може се појавити на било којој дубини дрвета.
• Пропагирајте минималне вредности до стабла док се не открије терминални чвор.

У датом стаблу игре, оптимална стратегија се може одредити из минималне вредности сваког чвора, која се може написати као МИНИМАКС(н). МАКС преферира да пређе у стање максималне вредности, а МИН преферира да пређе у стање минималне вредности тада: