TechCodeview

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:

virhe: pääluokkaa ei löytynyt tai ladata

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: