Adversarial search je hledání, kde zkoumáme problém, který nastává, když se snažíme plánovat dopředu před světem a ostatní agenti plánují proti nám.

• V předchozích tématech jsme studovali vyhledávací strategie, které jsou spojeny pouze s jediným agentem, jehož cílem je najít řešení, které se často projevuje ve formě sledu akcí.
• Mohou však nastat situace, kdy více než jeden agent hledá řešení ve stejném vyhledávacím prostoru, a tato situace obvykle nastává při hraní her.
• Prostředí s více než jedním agentem se nazývá multiagentní prostředí , ve kterém je každý agent protivníkem jiného agenta a hraje proti sobě. Každý agent musí zvážit akci jiného agenta a vliv této akce na jeho výkon.
• Tak, Vyhledávání, ve kterých se dva nebo více hráčů s protichůdnými cíli snaží prozkoumat stejný prostor pro hledání řešení, se nazývají adversarial searches, často známé jako hry. .
• Hry jsou modelovány jako vyhledávací problém a funkce heuristického hodnocení, a to jsou dva hlavní faktory, které pomáhají modelovat a řešit hry v AI.

Typy her v AI:

Perfektní informace:Hra s dokonalými informacemi je ta, ve které mohou agenti nahlédnout do kompletní desky. Agenti mají všechny informace o hře a také mohou vidět vzájemné pohyby. Příklady jsou šachy, dáma, jděte atd.Nedokonalé informace:Pokud ve hře agenti nemají všechny informace o hře a nevědí, co se děje, takový typ her se nazývá hra s nedokonalými informacemi, jako je tic-tac-toe, Battleship, blind, Bridge atd.Deterministické hry:Deterministické hry jsou takové hry, které se řídí přísným vzorem a souborem pravidel pro hry a není s nimi spojena žádná náhodnost. Příklady jsou šachy, dáma, jít, piškvorky atd.Nedeterministické hry:Nedeterministické jsou ty hry, které mají různé nepředvídatelné události a mají faktor náhody nebo štěstí. Tento faktor náhody nebo štěstí je zaveden buď kostkami nebo kartami. Ty jsou náhodné a každá reakce na akci není pevná. Takové hry se také nazývají stochastické hry.
Příklad: Backgammon, Monopoly, Poker atd.

Poznámka: V tomto tématu probereme deterministické hry, plně pozorovatelné prostředí, nulový součet a kde každý agent působí alternativně.

Hra s nulovým součtem

• Hry s nulovým součtem jsou hledáním protivníků, které zahrnuje čistou soutěž.
• Ve hře s nulovým součtem je zisk nebo ztráta užitku každého agenta přesně vyvážena ztrátami nebo zisky užitku jiného agenta.
• Jeden hráč hry se snaží maximalizovat jednu hodnotu, zatímco druhý hráč se ji snaží minimalizovat.
• Každý tah jednoho hráče ve hře se nazývá ply.
• Šachy a tic-tac-toe jsou příklady hry s nulovým součtem.

Hra s nulovým součtem: Vestavěné myšlení

Hra s nulovým součtem zahrnovala vložené myšlení, ve kterém se jeden agent nebo hráč snaží přijít na to:

• Co dělat.
• Jak se rozhodnout o přesunu
• Musí myslet i na soupeře
• Soupeř také přemýšlí, co dělat

Každý z hráčů se snaží zjistit odezvu soupeře na jejich akce. To vyžaduje vestavěné myšlení nebo zpětné uvažování k vyřešení herních problémů v AI.

Formalizace problému:

Hru lze definovat jako typ vyhledávání v AI, který může být formalizován z následujících prvků:

Počáteční stav:Specifikuje, jak je hra nastavena na začátku.Hráči:Určuje, který hráč se ve stavovém prostoru pohyboval.Akce:Vrací sadu legálních tahů ve stavovém prostoru.Výsledek(y, a):Je to přechodový model, který specifikuje výsledek pohybů ve stavovém prostoru.Terminálový test(y):Terminálový test je pravdivý, pokud hra skončila, jinak je v každém případě nepravdivý. Stav, kdy hra končí, se nazývá terminální stavy.Utility, p):Užitná funkce udává konečnou číselnou hodnotu pro hru, která končí v terminálních stavech s pro hráče p. Říká se jí také výplatní funkce. U šachů je výsledkem výhra, prohra nebo remíza a jejich výplatní hodnoty jsou +1, 0, ½. A pro tic-tac-toe jsou užitečné hodnoty +1, -1 a 0.

Herní strom:

Herní strom je strom, kde uzly stromu jsou stavy hry a okraje stromu jsou pohyby hráčů. Strom hry zahrnuje počáteční stav, funkci akcí a funkci výsledku.

Příklad: strom hry Tic-Tac-Toe:

Následující obrázek ukazuje část herního stromu pro hru tic-tac-toe. Níže jsou uvedeny některé klíčové body hry:

• Hrají dva hráči MAX a MIN.
• Hráči mají alternativní tah a začínají s MAX.
• MAX maximalizuje výsledek stromu hry
• MIN minimalizuje výsledek.

Příklad vysvětlení:

• Z počátečního stavu má MAX 9 možných tahů, protože začíná jako první. MAX místo x a MIN místo o a oba hráči hrají střídavě, dokud nedosáhneme listového uzlu, kde má jeden hráč tři v řadě nebo jsou všechna políčka vyplněna.
• Oba hráči spočítají každý uzel, minimax, hodnotu minimax, což je nejlepší dosažitelná užitečnost proti optimálnímu protivníkovi.
• Předpokládejme, že oba hráči jsou si dobře vědomi piškvorek a hrají tu nejlepší hru. Každý hráč dělá, co může, aby zabránil dalšímu ve výhře. MIN ve hře jedná proti Maxovi.
• Takže ve stromu hry máme vrstvu Max, vrstvu MIN a každá vrstva se nazývá jako Vrstva . Max umístí x, poté MIN položí o, aby zabránil Maxovi ve výhře, a tato hra pokračuje až do koncového uzlu.
• V tomto buď vyhraje MIN, vyhraje MAX, nebo je to remíza. Tento herní strom je celým prostorem pro hledání možností, které MIN a MAX hrají jako piškvorky a střídavě se střídají.

Adversarial Search pro postup minimax tedy funguje následovně:

• Jeho cílem je najít optimální strategii, aby MAX vyhrál hru.
• Sleduje přístup hloubkového vyhledávání.
• Ve stromu hry se optimální listový uzel může objevit v jakékoli hloubce stromu.
• Šířte hodnoty minimax až do stromu, dokud nebude objeven terminálový uzel.

V daném herním stromu lze optimální strategii určit z minimální hodnoty každého uzlu, kterou lze zapsat jako MINIMAX(n). MAX preferuje přechod do stavu maximální hodnoty a MIN preferuje přechod do stavu minimální hodnoty, pak: