TechCodeview

Състезателното търсене е търсене, при което изследваме проблема, който възниква, когато се опитваме да планираме пред света и други агенти планират срещу нас.

• В предишни теми проучихме стратегиите за търсене, които са свързани само с един агент, чиято цел е да намери решението, което често се изразява под формата на последователност от действия.
• Но може да има ситуации, при които повече от един агент търси решението в едно и също пространство за търсене и тази ситуация обикновено се случва по време на игра.
• Средата с повече от един агент се нарича като мултиагентна среда , в който всеки агент е опонент на друг агент и играе един срещу друг. Всеки агент трябва да вземе предвид действието на друг агент и ефекта от това действие върху тяхното представяне.
• Така, Търсенията, при които двама или повече играчи с противоречиви цели се опитват да изследват едно и също пространство за търсене на решението, се наричат ​​състезателни търсения, често известни като игри .
• Игрите се моделират като проблем за търсене и функция за евристична оценка и това са двата основни фактора, които помагат за моделиране и решаване на игри в AI.

Видове игри в AI:

Перфектна информация:Игра с перфектната информация е тази, в която агентите могат да разгледат цялата дъска. Агентите разполагат с цялата информация за играта и могат да виждат ходовете си. Примери за това са шах, дама, го и др.Несъвършена информация:Ако в дадена игра агентите нямат цялата информация за играта и не са наясно какво се случва, такъв тип игри се наричат ​​игри с несъвършена информация, като tic-tac-toe, Battleship, blind, Bridge и др.Детерминистични игри:Детерминистичните игри са тези игри, които следват строг модел и набор от правила за игрите и няма произволност, свързана с тях. Примери за това са шах, дама, го, тик-так и др.Недетерминистични игри:Недетерминирани са тези игри, които имат различни непредсказуеми събития и имат фактор шанс или късмет. Този фактор шанс или късмет се въвежда или от зарове, или от карти. Те са произволни и всеки отговор на действие не е фиксиран. Такива игри се наричат ​​още стохастични игри.
Пример: табла, монопол, покер и др.

Забележка: В тази тема ще обсъдим детерминистични игри, напълно видима среда, нулева сума и къде всеки агент действа алтернативно.

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

• Игрите с нулева сума са състезателно търсене, което включва чиста конкуренция.
• В играта с нулева сума печалбата или загубата на полезност на всеки агент е точно балансирана от загубите или печалбите на полезността на друг агент.
• Един играч в играта се опитва да максимизира една единствена стойност, докато друг играч се опитва да я минимизира.
• Всеки ход на един играч в играта се нарича слой.
• Шахът и тик-так са примери за игра с нулева сума.

Игра с нулева сума: Вградено мислене

Играта с нулева сума включва вградено мислене, в което един агент или играч се опитва да разбере:

софтуерно тестване и видове

• Какво да правя.
• Как да решим хода
• Трябва да мисли и за противника си
• Противникът също мисли какво да прави

Всеки от играчите се опитва да разбере отговора на опонента си на техните действия. Това изисква вградено мислене или мислене назад, за да се решат проблемите на играта в AI.

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

Една игра може да се дефинира като вид търсене в AI, което може да бъде формализирано от следните елементи:

Първоначално състояние:Той определя как е настроена играта в началото.Играч(и):Той определя кой играч се е преместил в пространството на състоянието.Действие(я):Той връща набора от законни ходове в пространството на състоянието.Резултат(и, а):Това е моделът на прехода, който определя резултата от движенията в пространството на състоянието.Терминален тест(ове):Терминалният тест е верен, ако играта е свършила, в противен случай е фалшив във всеки случай. Състоянието, в което играта завършва, се нарича терминално състояние.Полезност(и, p):Функция за полезност дава крайната числена стойност за игра, която завършва в терминални състояния s за играч p. Нарича се още функция на изплащане. За шаха резултатите са победа, загуба или равенство и стойностите на изплащане са +1, 0, ½. А за tic-tac-toe стойностите на полезност са +1, -1 и 0.

Дърво на играта:

Дървото на играта е дърво, в което възлите на дървото са състоянията на играта, а ръбовете на дървото са ходовете на играчите. Дървото на играта включва първоначално състояние, функция за действия и функция за резултат.

Пример: дърво на играта Tic-Tac-Toe:

безкраен цикъл

Следващата фигура показва част от дървото на играта за играта tic-tac-toe. Следват някои ключови моменти от играта:

• Има двама играчи MAX и MIN.
• Играчите имат алтернативен ход и започват с MAX.
• MAX максимизира резултата от дървото на играта
• MIN минимизира резултата.

Примерно обяснение:

• От първоначалното състояние MAX има 9 възможни хода, тъй като започва първи. MAX поставя x и MIN поставя o и двамата играчи играят алтернативно, докато стигнем до листов възел, където един играч има три подред или всички квадратчета са запълнени.
• И двамата играчи ще изчислят всеки възел, минимакс, минимаксната стойност, която е най-добрата постижима полезност срещу оптимален противник.
• Да предположим, че и двамата играчи са добре запознати с тик-так-палеца и играят най-добрата игра. Всеки играч прави всичко възможно, за да попречи на друг да спечели. MIN действа срещу Max в играта.
• Така че в дървото на играта имаме слой от Max, слой от MIN и всеки слой се нарича като пластове . Max поставя x, след това MIN поставя o, за да попречи на Max да спечели и тази игра продължава до терминалния възел.
• В това или MIN печели, MAX печели, или е равенство. Това дърво на играта е цялото пространство за търсене на възможности, които MIN и MAX играят на тик-так и се редуват последователно.

Следователно състезателното търсене на процедурата minimax работи по следния начин:

linux стартирайте cmd

• Има за цел да намери оптималната стратегия за MAX да спечели играта.
• Той следва подхода на първо търсене в дълбочина.
• В дървото на играта оптималният листов възел може да се появи на всяка дълбочина на дървото.
• Разпространете минимаксните стойности до дървото, докато бъде открит терминалният възел.

В дадено дърво на играта оптималната стратегия може да се определи от минимаксната стойност на всеки възел, която може да бъде записана като MINIMAX(n). MAX предпочита да премине към състояние на максимална стойност, а MIN предпочита да премине към състояние на минимална стойност, след което: