Vastakkainen haku on etsintä, jossa tutkimme ongelmaa, joka syntyy, kun yritämme suunnitella maailmaa edellä ja muut agentit suunnittelevat meitä vastaan.

• Aiemmissa aiheissa olemme tutkineet hakustrategioita, jotka liittyvät vain yhteen agenttiin, joka pyrkii löytämään ratkaisun, joka usein ilmaistaan ​​toimintosarjan muodossa.
• Mutta voi olla tilanteita, joissa useampi kuin yksi agentti etsii ratkaisua samassa hakutilassa, ja tämä tilanne tapahtuu yleensä pelien pelaamisessa.
• Ympäristöä, jossa on useampi kuin yksi tekijä, kutsutaan nimellä monen agentin ympäristö , jossa jokainen agentti on toisen agentin vastustaja ja pelaa toisiaan vastaan. Jokaisen edustajan on otettava huomioon toisen toimijan toiminta ja sen vaikutus heidän suoritukseensa.
• Niin, Hakuja, joissa kaksi tai useampi pelaaja, joilla on ristiriitaiset tavoitteet, yrittää tutkia samaa hakualuetta ratkaisua varten, kutsutaan kontradiktorisiksi hauiksi, joita kutsutaan usein peleiksi. .
• Pelit on mallinnettu hakuongelmana ja heuristisena arviointifunktiona, ja nämä ovat kaksi päätekijää, jotka auttavat mallintamaan ja ratkaisemaan pelejä tekoälyssä.

Pelityypit tekoälyssä:

Täydellistä tietoa: Täydellistä tietoa sisältävä peli on se, jossa agentit voivat tarkastella koko lautaa. Agenteilla on kaikki tiedot pelistä, ja he näkevät myös toistensa liikkeet. Esimerkkejä ovat shakki, tammi, go jne. Epätäydellinen tieto: Jos pelissä agenteilla ei ole kaikkea tietoa pelistä ja he eivät ole tietoisia siitä, mitä tapahtuu, tämäntyyppisiä pelejä kutsutaan peliksi, jossa on epätäydellinen tieto, kuten tic-tac-toe, Battleship, blind, Bridge jne. Deterministiset pelit: Deterministiset pelit ovat pelejä, jotka noudattavat tiukkaa kaavaa ja pelien sääntöjä, eikä niihin liity satunnaisuutta. Esimerkkejä ovat shakki, tammi, go, tic-tac-toe jne. Epädeterministiset pelit: Epädeterministisiä ovat pelejä, joissa on erilaisia ​​arvaamattomia tapahtumia ja joissa on sattuman tai onnen tekijä. Tämä sattuman tai onnentekijä esitellään joko noppalla tai korteilla. Nämä ovat satunnaisia, ja jokainen toimintavaste ei ole kiinteä. Tällaisia ​​pelejä kutsutaan myös stokastisiksi peleiksi.
Esimerkki: Backgammon, Monopoli, Pokeri jne.

Huomautus: Tässä aiheessa käsitellään deterministisiä pelejä, täysin havaittavissa olevaa ympäristöä, nollasummaa ja sitä, missä kukin agentti toimii vuorotellen.

Nollasummapeli

• Nollasummapelit ovat kontradiktorista hakua, johon liittyy puhdasta kilpailua.
• Nollasummapelissä jokaisen agentin hyöty tai menetys on täsmälleen tasapainotettu toisen agentin hyötyjen tai hyötyjen kanssa.
• Yksi pelin pelaaja yrittää maksimoida yhden arvon, kun taas toinen pelaaja yrittää minimoida sen.
• Jokaista yhden pelaajan siirtoa pelissä kutsutaan plyksi.
• Shakki ja tic-tac-toe ovat esimerkkejä nollasummapeleistä.

Nollasummapeli: sulautettu ajattelu

Nollasummapeli sisälsi sulautetun ajattelun, jossa yksi agentti tai pelaaja yrittää selvittää:

• Mitä tehdä.
• Kuinka päättää muutto
• Pitää ajatella myös vastustajaansa
• Vastustaja miettii myös mitä tehdä

Jokainen pelaaja yrittää selvittää vastustajansa vastauksen heidän toimintaansa. Tämä vaatii sulautettua ajattelua tai taaksepäin ajattelua peliongelmien ratkaisemiseksi tekoälyssä.

Ongelman virallistaminen:

Peli voidaan määritellä tekoälyn haun tyypiksi, joka voidaan muotoilla seuraavista elementeistä:

Alkutila: Se määrittää, kuinka peli on asetettu alussa. Pelaaja(t): Se määrittää, mikä pelaaja on liikkunut tila-avaruudessa. Toiminnot): Se palauttaa joukon laillisia liikkeitä tila-avaruudessa. Tulokset, a: Se on siirtymämalli, joka määrittää tila-avaruuden liikkeiden tuloksen. Päätetesti(t): Päätetesti on tosi, jos peli on ohi, muuten se on epätosi joka tapauksessa. Tilaa, johon peli päättyy, kutsutaan terminaalitiloiksi. Apuohjelma(t, p): Aputoiminto antaa lopullisen numeerisen arvon pelille, joka päättyy päätetiloihin s pelaajalle p. Sitä kutsutaan myös maksufunktioksi. Shakissa lopputulokset ovat voitto, tappio tai tasapeli ja sen voittoarvot ovat +1, 0, ½. Ja tic-tac-toe:n hyötyarvot ovat +1, -1 ja 0.

Pelipuu:

Pelipuu on puu, jossa puun solmut ovat pelin tiloja ja puun reunat ovat pelaajien liikkeet. Pelipuu sisältää alkutilan, toimintatoiminnon ja tulosfunktion.

Esimerkki: Tic-Tac-Toe pelipuu:

Seuraava kuva esittää osaa tic-tac-toe-pelin pelipuusta. Seuraavassa on joitain pelin avainkohtia:

• Pelaajia on kaksi MAX ja MIN.
• Pelaajilla on vaihtoehtoinen vuoro, ja he aloittavat MAX:lla.
• MAX maksimoi pelipuun tuloksen
• MIN minimoi tuloksen.

Esimerkki selitys:

• Alkutilasta lähtien MAXilla on 9 mahdollista liikettä, kun hän aloittaa ensimmäisenä. MAX paikka x ja MIN paikka o, ja molemmat pelaajat pelaavat vuorotellen, kunnes saavutamme lehtisolmun, jossa yhdellä pelaajalla on kolme peräkkäin tai kaikki ruudut ovat täynnä.
• Molemmat pelaajat laskevat kunkin solmun, minimaxin, minimax-arvon, joka on paras saavutettavissa oleva apuohjelma optimaalista vastustajaa vastaan.
• Oletetaan, että molemmat pelaajat ovat hyvin tietoisia tic-tac-toe-pelistä ja pelaavat parasta peliä. Jokainen pelaaja tekee parhaansa estääkseen toista voittamasta. MIN toimii Maxia vastaan ​​pelissä.
• Joten pelipuussa meillä on kerros Max, kerros MIN, ja jokaista kerrosta kutsutaan nimellä Ply . Max paikka x, sitten MIN laittaa o:n estääkseen Maxia voittamasta, ja tämä peli jatkuu terminaalisolmuun asti.
• Tässä joko MIN voittaa, MAX voittaa tai se on tasapeli. Tämä pelipuu on koko mahdollisuuksien hakuavaruus, jossa MIN ja MAX pelaavat tiikkiä vuorotellen.

Tästä syystä minimax-menettelyn kontradiktorinen haku toimii seuraavasti:

• Sen tavoitteena on löytää optimaalinen strategia, jolla MAX voi voittaa pelin.
• Se noudattaa Depth-first-haun lähestymistapaa.
• Pelipuussa optimaalinen lehtisolmu voi esiintyä missä tahansa puun syvyydessä.
• Levitä minimax-arvoja puuhun, kunnes päätesolmu havaitaan.

Tietyssä pelipuussa optimaalinen strategia voidaan määrittää kunkin solmun minimax-arvosta, joka voidaan kirjoittaa muodossa MINIMAX(n). MAX mieluummin siirtyy maksimiarvon tilaan ja MIN mieluummin pienimmän arvon tilaan, sitten: