TechCodeview

Adversarial search je hľadanie, kde skúmame problém, ktorý nastáva, keď sa snažíme plánovať pred svetom a iní agenti plánujú proti nám.

• V predchádzajúcich témach sme študovali stratégie vyhľadávania, ktoré sú spojené iba s jedným agentom, ktorého cieľom je nájsť riešenie, ktoré sa často prejavuje vo forme postupnosti akcií.
• Môžu však nastať situácie, keď viac ako jeden agent hľadá riešenie v rovnakom vyhľadávacom priestore, a táto situácia sa zvyčajne vyskytuje pri hraní hier.
• Prostredie s viac ako jedným agentom sa nazýva multiagentové prostredie , v ktorej je každý agent súperom iného agenta a hrá proti sebe. Každý agent musí zvážiť pôsobenie iného agenta a vplyv tohto pôsobenia na jeho výkon.
• takže, Vyhľadávania, v ktorých sa dvaja alebo viacerí hráči s protichodnými cieľmi snažia preskúmať rovnaký priestor hľadania riešenia, sa nazývajú adversarial searchs, často známe ako hry. .
• Hry sú modelované ako funkcia vyhľadávania a heuristického vyhodnocovania, a to sú dva hlavné faktory, ktoré pomáhajú modelovať a riešiť hry v AI.

Typy hier v AI:

Perfektné informácie:Hra s dokonalými informáciami je tá, v ktorej agenti môžu nahliadnuť do kompletnej dosky. Agenti majú všetky informácie o hre a vidia aj vzájomné pohyby. Príkladmi sú šach, dáma, choď atď.Nedokonalé informácie:Ak agenti v hre nemajú všetky informácie o hre a nevedia, čo sa deje, takýto typ hier sa nazýva hra s nedokonalými informáciami, ako napríklad tic-tac-toe, Battleship, blind, Bridge atď.Deterministické hry:Deterministické hry sú hry, ktoré sa riadia prísnym vzorom a súborom pravidiel pre hry a nie je s nimi spojená žiadna náhodnosť. Príkladmi sú šach, dáma, choď, piškvorky atď.Nedeterministické hry:Nedeterministické sú tie hry, ktoré majú rôzne nepredvídateľné udalosti a majú faktor náhody alebo šťastia. Tento faktor náhody alebo šťastia je predstavený buď kockami alebo kartami. Sú náhodné a každá reakcia na akciu nie je pevná. Takéto hry sa nazývajú aj stochastické hry.
Príklad: Backgammon, Monopoly, Poker atď.

Poznámka: V tejto téme sa budeme zaoberať deterministickými hrami, plne pozorovateľným prostredím, nulovým súčtom a tým, kde každý agent pôsobí alternatívne.

Hra s nulovým súčtom

• Hry s nulovým súčtom sú nepriateľské hľadanie, ktoré zahŕňa čistú súťaž.
• V hre s nulovým súčtom je zisk alebo strata užitočnosti každého agenta presne vyvážená stratami alebo ziskami užitočnosti iného agenta.
• Jeden hráč hry sa snaží maximalizovať jednu hodnotu, zatiaľ čo druhý hráč sa ju snaží minimalizovať.
• Každý ťah jedného hráča v hre sa nazýva ply.
• Šach a piškvorky sú príkladmi hry s nulovým súčtom.

Hra s nulovým súčtom: Vložené myslenie

Hra s nulovým súčtom zahŕňala vložené myslenie, v ktorom sa jeden agent alebo hráč snaží prísť na to:

kruskalov algoritmus

• Čo robiť.
• Ako sa rozhodnúť pre presun
• Musí myslieť aj na súpera
• Súper tiež rozmýšľa, čo má robiť

Každý z hráčov sa snaží zistiť reakciu svojho súpera na ich akcie. To si vyžaduje zabudované myslenie alebo spätné uvažovanie na vyriešenie herných problémov v AI.

Formalizácia problému:

Hru možno definovať ako typ vyhľadávania v AI, ktorý možno formalizovať z nasledujúcich prvkov:

Počiatočný stav:Špecifikuje, ako je hra nastavená na začiatku.Hráči:Určuje, ktorý hráč sa pohyboval v stavovom priestore.Akcie:Vracia množinu legálnych pohybov v stavovom priestore.Výsledok(y, a):Ide o prechodový model, ktorý špecifikuje výsledok pohybov v stavovom priestore.Terminálový test(y):Terminálny test je pravdivý, ak sa hra skončí, inak je v každom prípade nepravdivý. Stav, v ktorom sa hra končí, sa nazýva terminálne stavy.Pomôcka(y, p):Užitočná funkcia dáva konečnú číselnú hodnotu pre hru, ktorá končí v terminálnych stavoch s pre hráča p. Nazýva sa aj výplatná funkcia. V prípade šachu sú výsledkom výhra, prehra alebo remíza a jeho výplatné hodnoty sú +1, 0, ½. A pre tic-tac-toe sú úžitkové hodnoty +1, -1 a 0.

Strom hry:

Strom hry je strom, kde uzly stromu sú stavy hry a okraje stromu sú pohyby hráčov. Strom hry zahŕňa počiatočný stav, funkciu akcií a funkciu výsledku.

Príklad: strom hry Tic-Tac-Toe:

reťazec v porovnaní s

Nasledujúci obrázok zobrazuje časť herného stromu pre hru tic-tac-toe. Nasleduje niekoľko kľúčových bodov hry:

• Hrajú dvaja hráči MAX a MIN.
• Hráči majú striedavý ťah a začínajú s MAX.
• MAX maximalizuje výsledok stromu hry
• MIN minimalizuje výsledok.

Príklad vysvetlenia:

• Z počiatočného stavu má MAX 9 možných ťahov, keďže začína prvý. MAX miesto x a MIN miesto o a obaja hráči hrajú striedavo, kým nedosiahneme listový uzol, kde má jeden hráč tri v rade alebo sú zaplnené všetky políčka.
• Obaja hráči vypočítajú každý uzol, minimax, minimax hodnotu, ktorá je najlepšou dosiahnuteľnou užitočnosťou proti optimálnemu protivníkovi.
• Predpokladajme, že obaja hráči sú si dobre vedomí piškvoriek a hrajú tú najlepšiu hru. Každý hráč robí všetko pre to, aby zabránil inému vyhrať. MIN hrá proti Maxovi v hre.
• Takže v strome hry máme vrstvu Max, vrstvu MIN a každá vrstva sa nazýva ako Ply . Max umiestni x, potom MIN dá o, aby zabránil Maxovi vyhrať, a táto hra pokračuje až do koncového uzla.
• V tomto buď vyhráva MIN, vyhráva MAX, alebo je remíza. Tento herný strom je celým priestorom hľadania možností, ktoré MIN a MAX striedavo hrajú a striedajú.

Preto postup kontradiktórneho vyhľadávania pre minimax funguje nasledovne:

• Jeho cieľom je nájsť optimálnu stratégiu, aby MAX vyhral hru.
• Nasleduje prístup hĺbkového vyhľadávania.
• V strome hry sa optimálny listový uzol môže objaviť v akejkoľvek hĺbke stromu.
• Šírte hodnoty minimax až do stromu, kým sa neobjaví koncový uzol.

V danom hernom strome možno optimálnu stratégiu určiť z minimálnej hodnoty každého uzla, ktorú možno zapísať ako MINIMAX(n). MAX preferuje prechod do stavu maximálnej hodnoty a MIN preferuje prechod do stavu minimálnej hodnoty, potom: