Tegenstrijdig zoeken is een zoektocht waarbij we het probleem onderzoeken dat zich voordoet wanneer we proberen vooruit te plannen op de wereld en andere actoren plannen tegen ons maken.

• In eerdere onderwerpen hebben we de zoekstrategieën bestudeerd die alleen verband houden met één enkele agent die tot doel heeft de oplossing te vinden, die vaak wordt uitgedrukt in de vorm van een reeks acties.
• Maar er kunnen situaties zijn waarin meer dan één agent in dezelfde zoekruimte naar de oplossing zoekt, en deze situatie doet zich meestal voor tijdens het spelen van games.
• De omgeving met meer dan één agent wordt genoemd als omgeving met meerdere agenten , waarin elke agent een tegenstander is van een andere agent en tegen elkaar speelt. Elke agent moet rekening houden met de actie van een andere agent en het effect van die actie op zijn of haar prestaties.
• Dus, Zoekopdrachten waarbij twee of meer spelers met tegenstrijdige doelen dezelfde zoekruimte voor de oplossing proberen te verkennen, worden vijandige zoekopdrachten genoemd, ook wel bekend als Games. .
• Games worden gemodelleerd als een zoekprobleem en een heuristische evaluatiefunctie, en dit zijn de twee belangrijkste factoren die helpen bij het modelleren en oplossen van games in AI.

Soorten games in AI:

Perfecte informatie:Een spel met de perfecte informatie is dat waarbij agenten het volledige bord kunnen inkijken. Agenten hebben alle informatie over het spel en kunnen elkaars bewegingen ook zien. Voorbeelden zijn schaken, dammen, go, enz.Onvolmaakte informatie:Als agenten in een spel niet over alle informatie over het spel beschikken en zich niet bewust zijn van wat er aan de hand is, worden dergelijke spellen het spel met imperfecte informatie genoemd, zoals boter-kaas-en-eieren, slagschip, blind, bridge, enz.Deterministische spellen:Deterministische spellen zijn spellen die een strikt patroon en een reeks regels voor de spellen volgen, en er is geen willekeur aan verbonden. Voorbeelden zijn schaken, dammen, Go, boter-kaas-en-eieren, enz.Niet-deterministische spellen:Niet-deterministisch zijn spellen met verschillende onvoorspelbare gebeurtenissen en een factor toeval of geluk. Deze factor van toeval of geluk wordt geïntroduceerd door dobbelstenen of kaarten. Deze zijn willekeurig en elke actiereactie staat niet vast. Dergelijke spellen worden ook wel stochastische spellen genoemd.
Voorbeeld: Backgammon, Monopoly, Poker, enz.

Opmerking: in dit onderwerp bespreken we deterministische spellen, een volledig waarneembare omgeving, nulsom en waar elke agent afwisselend handelt.

Nulsomspel

• Zero-sum games zijn vijandige zoektochten waarbij sprake is van pure concurrentie.
• In het nulsomspel wordt de winst of het verlies aan nut van elke agent precies gecompenseerd door het verlies of de winst aan nut van een andere agent.
• De ene speler van het spel probeert één enkele waarde te maximaliseren, terwijl de andere speler deze probeert te minimaliseren.
• Elke zet van één speler in het spel wordt een ply genoemd.
• Schaken en boter-kaas-en-eieren zijn voorbeelden van een nulsomspel.

Zero-sum game: ingebed denken

Het Zero-sum-spel omvatte ingebed denken waarbij één agent of speler probeert uit te vinden:

• Wat moeten we doen.
• Hoe de zet te beslissen
• Hij moet ook aan zijn tegenstander denken
• De tegenstander denkt ook na over wat hij moet doen

Elk van de spelers probeert de reactie van zijn tegenstander op zijn acties te achterhalen. Dit vereist ingebed denken of achterwaarts redeneren om de spelproblemen in AI op te lossen.

Formalisering van het probleem:

Een game kan worden gedefinieerd als een soort zoekopdracht in AI die kan worden geformaliseerd uit de volgende elementen:

Oorspronkelijke toestand:Hierin wordt aangegeven hoe het spel in het begin is opgezet.Speler(s):Het geeft aan welke speler zich in het toestandsveld heeft verplaatst.Actie(s):Het retourneert de reeks legale zetten in de toestandsruimte.Resultaat(en, a):Het is het transitiemodel, dat het resultaat van bewegingen in de toestandsruimte specificeert.Terminal-test(en):De terminaltest is waar als het spel voorbij is, anders is hij in ieder geval onwaar. De staat waar het spel eindigt, wordt terminalstaten genoemd.Hulpprogramma('s, p):Een nutsfunctie geeft de uiteindelijke numerieke waarde voor een spel dat eindigt in eindtoestanden s voor speler p. Het wordt ook wel de uitbetalingsfunctie genoemd. Voor schaken zijn de uitkomsten winst, verlies of gelijkspel en de uitbetalingswaarden zijn +1, 0, ½. En voor boter-kaas-en-eieren zijn de nutswaarden +1, -1 en 0.

Spelboom:

Een spelboom is een boom waarbij de knooppunten van de boom de spelstatussen zijn en de randen van de boom de bewegingen van spelers. De spelboom omvat de beginstatus, de actiefunctie en de resultaatfunctie.

Voorbeeld: Tic-Tac-Toe-spelboom:

De volgende afbeelding toont een deel van de spelboom voor het boter-kaas-en-eieren-spel. Hieronder volgen enkele belangrijke punten van het spel:

• Er zijn twee spelers MAX en MIN.
• Spelers hebben een afwisselende beurt en beginnen met MAX.
• MAX maximaliseert het resultaat van de spelboom
• MIN minimaliseert het resultaat.

Voorbeeld uitleg:

• Vanaf de begintoestand heeft MAX 9 mogelijke zetten als hij als eerste begint. MAX plaats x en MIN plaats o, en beide spelers spelen afwisselend totdat we een bladknooppunt bereiken waar een speler er drie op een rij heeft of alle vierkanten gevuld zijn.
• Beide spelers berekenen elk knooppunt, minimax, de minimax-waarde die het best haalbare nut is tegen een optimale tegenstander.
• Stel dat beide spelers goed op de hoogte zijn van de boter-kaas-en-eieren en het beste spel spelen. Elke speler doet zijn best om te voorkomen dat een andere speler wint. MIN treedt in het spel op tegen Max.
• Dus in de spelboom hebben we een laag Max, een laag MIN, en elke laag heet as Laag . Max plaatst x, daarna zet MIN o om te voorkomen dat Max wint, en dit spel gaat door tot het eindknooppunt.
• Hierin wint MIN, MAX wint, of het is gelijkspel. Deze spelboom is de hele zoekruimte van mogelijkheden waarin MIN en MAX afwisselend boter-kaas-en-eieren spelen en om de beurt spelen.

Daarom werkt de vijandige zoektocht naar de minimax-procedure als volgt:

• Het doel is om de optimale strategie voor MAX te vinden om het spel te winnen.
• Het volgt de aanpak van Diepte-eerst zoeken.
• In de spelboom kan een optimaal bladknooppunt op elke diepte van de boom verschijnen.
• Verspreid de minimax-waarden naar de boom totdat het terminalknooppunt wordt ontdekt.

In een gegeven spelboom kan de optimale strategie worden bepaald op basis van de minimax-waarde van elk knooppunt, die kan worden geschreven als MINIMAX(n). MAX gaat het liefst naar een staat van maximale waarde en MIN gaat liever naar een staat van minimale waarde, en dan: