TechCodeview

Wyszukiwanie kontradyktoryjne to poszukiwanie, podczas którego badamy problem powstający, gdy próbujemy planować z wyprzedzeniem, a inni agenci planują przeciwko nam.

• W poprzednich tematach badaliśmy strategie wyszukiwania, które są powiązane tylko z jednym agentem, którego celem jest znalezienie rozwiązania, które często wyraża się w formie sekwencji działań.
• Mogą jednak zaistnieć sytuacje, w których więcej niż jeden agent szuka rozwiązania w tej samej przestrzeni poszukiwań, a taka sytuacja zwykle ma miejsce podczas grania.
• Środowisko z więcej niż jednym agentem nazywa się środowisko wieloagentowe , w którym każdy agent jest przeciwnikiem innego agenta i gra przeciwko sobie. Każdy agent musi rozważyć działanie innego agenta i wpływ tego działania na jego wydajność.
• Więc, Wyszukiwania, podczas których dwóch lub więcej graczy o sprzecznych celach próbuje eksplorować tę samą przestrzeń poszukiwań w poszukiwaniu rozwiązania, nazywane są wyszukiwaniami kontradyktoryjnymi, często nazywanymi grami. .
• Gry są modelowane jako problem wyszukiwania i funkcja oceny heurystycznej i są to dwa główne czynniki, które pomagają modelować i rozwiązywać gry w sztucznej inteligencji.

Rodzaje gier w AI:

Doskonała informacja:Gra z doskonałymi informacjami to gra, w której agenci mogą zajrzeć do całej planszy. Agenci mają wszystkie informacje na temat gry, mogą także widzieć swoje ruchy. Przykładami są szachy, warcaby, go itp.Niedoskonałe informacje:Jeśli w grze agenci nie mają wszystkich informacji o grze i nie są świadomi, co się dzieje, tego typu gry nazywane są grami z niedoskonałymi informacjami, takimi jak kółko i krzyżyk, pancernik, ślepy, brydż itp.Gry deterministyczne:Gry deterministyczne to te gry, które opierają się na ścisłym schemacie i zestawie reguł gier i nie wiąże się z nimi żadna losowość. Przykładami są szachy, warcaby, go, kółko i krzyżyk itp.Gry niedeterministyczne:Niedeterministyczne to gry, w których występują różne nieprzewidywalne zdarzenia i występuje w nich czynnik przypadku lub szczęścia. Ten czynnik przypadku lub szczęścia wprowadzają kości lub karty. Są one losowe i reakcja na każdą akcję nie jest ustalona. Gry takie nazywane są także grami stochastycznymi.
Przykład: Backgammon, Monopoly, Poker itp.

Uwaga: W tym temacie omówimy gry deterministyczne, w pełni obserwowalne środowisko, grę o sumie zerowej i sytuację, w której każdy agent działa naprzemiennie.

Gra o sumie zerowej

• Gry o sumie zerowej to poszukiwanie kontradyktoryjne, które wiąże się z czystą rywalizacją.
• W grze o sumie zerowej zysk lub utrata użyteczności każdego agenta jest dokładnie równoważona przez straty lub zyski użyteczności innego agenta.
• Jeden z graczy stara się zmaksymalizować jedną wartość, podczas gdy drugi gracz stara się ją zminimalizować.
• Każdy ruch jednego gracza w grze nazywany jest warstwą.
• Szachy i kółko i krzyżyk to przykłady gry o sumie zerowej.

Gra o sumie zerowej: myślenie osadzone

Gra o sumie zerowej wymaga myślenia, w którym jeden agent lub gracz próbuje zrozumieć:

dodaj ciąg Java

• Co robić.
• Jak podjąć decyzję o przeprowadzce
• Musi także myśleć o swoim przeciwniku
• Przeciwnik również myśli, co zrobić

Każdy z graczy stara się poznać reakcję przeciwnika na swoje działania. Wymaga to wbudowanego myślenia lub rozumowania wstecznego, aby rozwiązać problemy z grą w AI.

Formalizacja problemu:

Grę można zdefiniować jako rodzaj wyszukiwania w AI, który można sformalizować z następujących elementów:

Stan początkowy:Określa, jak gra jest skonfigurowana na początku.Gracze):Określa, który gracz poruszył się w przestrzeni stanów.Działania):Zwraca zestaw legalnych ruchów w przestrzeni stanów.Wyniki, a):Jest to model przejścia, który określa wynik ruchów w przestrzeni stanów.Test(y) terminala:Test terminala jest prawdziwy, jeśli gra się skończyła, w przeciwnym razie jest fałszywy w każdym przypadku. Stan, w którym gra się kończy, nazywany jest stanem końcowym.Użyteczność(e, p):Funkcja użyteczności podaje ostateczną wartość liczbową dla gry, która kończy się stanami końcowymi s dla gracza p. Nazywa się ją także funkcją wypłaty. W przypadku szachów wynikiem jest wygrana, przegrana lub remis, a wartości wypłat wynoszą +1, 0, ½. W przypadku gry w kółko i krzyżyk wartości użyteczności wynoszą +1, -1 i 0.

Drzewo gry:

Drzewo gry to drzewo, którego węzły to stany gry, a krawędzie drzewa to ruchy graczy. Drzewo gry obejmuje stan początkowy, funkcję akcji i funkcję wyniku.

Przykład: Drzewo gry Kółko i krzyżyk:

jak przekonwertować ciąg na int w Javie

Poniższy rysunek przedstawia część drzewa gry w kółko i krzyżyk. Oto kilka kluczowych punktów gry:

• Jest dwóch graczy MAX i MIN.
• Gracze mają alternatywną turę i zaczynają od MAX.
• MAX maksymalizuje wynik drzewa gry
• MIN minimalizuje wynik.

Przykładowe wyjaśnienie:

• Ze stanu początkowego MAX ma 9 możliwych ruchów, zaczynając jako pierwszy. MAX miejsce x i MIN miejsce o i obaj gracze grają na zmianę, aż dotrzemy do węzła liścia, w którym jeden z graczy ma trzy w rzędzie lub wszystkie pola są wypełnione.
• Obaj gracze obliczą każdy węzeł, minimax, wartość minimax, która jest najlepszą osiągalną użytecznością w starciu z optymalnym przeciwnikiem.
• Załóżmy, że obaj gracze są świadomi gry w kółko i krzyżyk i grają najlepiej. Każdy gracz robi wszystko, co w jego mocy, aby uniemożliwić innemu wygraną. MIN działa przeciwko Maxowi w grze.
• Zatem w drzewie gry mamy warstwę Max, warstwę MIN, a każda warstwa nazywa się Zagięcie . Max umieść x, następnie MIN stawia o, aby uniemożliwić Maxowi wygraną, a gra toczy się aż do węzła końcowego.
• W tym przypadku albo MIN wygrywa, MAX wygrywa, albo jest remis. To drzewo gry to cała przestrzeń poszukiwań możliwości, w których MIN i MAX grają w kółko i krzyżyk i na zmianę.

Zatem kontradyktoryjne wyszukiwanie procedury minimax działa w następujący sposób:

• Ma na celu znalezienie optymalnej strategii dla MAX, aby wygrać grę.
• Jest to zgodne z podejściem polegającym na przeszukiwaniu w głąb.
• W drzewie gry optymalny węzeł liścia może pojawić się na dowolnej głębokości drzewa.
• Propaguj wartości minimax aż do drzewa, aż do wykrycia węzła końcowego.

W danym drzewie gry optymalną strategię można wyznaczyć na podstawie wartości minimax każdego węzła, którą można zapisać jako MINIMAX(n). MAX woli przejść do stanu wartości maksymalnej, a MIN woli przejść do stanu wartości minimalnej wtedy: