Alfa Beta-karsinta tekoälyssä

Alpha beta-karsinta on minimax-algoritmin optimointitekniikka. Tämän blogin aikana keskustelemme siitä, mitä alpha beta karsinta tarkoittaa, keskustelemme minimax-algoritmista, säännöistä hyvän tilauksen löytämiseksi ja paljon muuta.

1. Johdanto
2. Minimax-algoritmi
3. alfa-beeta-karsinnan avainkohdat
4. alfa-beeta-karsinnan työskentely
5. siirrä karsinnan Järjestys
6. säännöt hyvän järjestyksen löytämiseksi
7. koodit Pythonilla

johdanto

sana ”karsiminen” tarkoittaa oksien ja lehtien leikkaamista. Datatieteessä karsinta on paljon käytetty termi, jolla viitataan jälki-ja esikarsintaan ratkaisupuissa ja satunnaismetsissä. Alfa-beta-karsinta ei ole mitään muuta kuin hyödyttömien oksien karsimista ratkaisupuissa. Tämän alfa-beeta-karsimisalgoritmin löysivät itsenäisesti tutkijat 1900-luvulla.

alfa-beeta-karsinta on minimax-algoritmin optimointitekniikka, jota käsitellään seuraavassa jaksossa. Karsimistarve tuli siitä, että joissakin tapauksissa ratkaisupuista tulee hyvin monimutkaisia. Siinä puussa muutamat turhat oksat lisäävät mallin monimutkaisuutta. Tämän välttämiseksi Alfa-Beta-karsinta tulee siis pelaamaan niin, ettei tietokoneen tarvitse katsoa koko puuta. Nämä epätavalliset solmut tekevät algoritmista hitaan. Siksi poistamalla nämä solmut algoritmi tulee nopeasti.

Opi a * – algoritmista.

Minimax-algoritmi

Minimax on klassinen syvyysetsintätekniikka peräkkäisessä kahden pelaajan pelissä. Kaksi pelaajaa ovat nimeltään MAX ja MIN. Minimax-algoritmi on suunniteltu löytämään optimaalinen liike Maxille, pelaajalle juurisolmussa. Hakupuu luodaan laajentamalla rekursiivisesti kaikkia solmuja juuresta syvyys ensin – tavalla, kunnes joko pelin loppu tai hakusyvyys on saavutettu. Tutkikaamme tätä algoritmia yksityiskohtaisesti.

kuten jo mainittiin, pelissä on kaksi pelaajaa, viz – Max ja Min. Max pelaa ensimmäistä askelta. Maxin tehtävänä on maksimoida palkkionsa, kun taas Minin tehtävänä on minimoida Maxin palkkio kasvattaen samalla omaa palkkiotaan. Oletetaan, että Max voi toimia A, b tai C. kumpi heistä antaa Maxille parhaan palkinnon, kun peli päättyy? Jotta voimme vastata tähän kysymykseen, meidän täytyy tutkia pelipuuta riittävän perusteellisesti ja olettaa, että Min pelaa optimaalisesti minimoidakseen Maxin palkitsemisen.

tässä on esimerkki. Neljä kolikkoa ovat peräkkäin ja jokainen pelaaja voi poimia yhden kolikon tai kaksi kolikkoa hänen/hänen vuorollaan. Pelaaja, joka nostaa viimeisen kolikon, voittaa. Olettaen, että Max pelaa ensin, mitä liikkua pitäisi Max tehdä voittaa?

jos Max valitsee kaksi kolikkoa, jäljelle jää vain kaksi kolikkoa ja Min voi valita kaksi kolikkoa ja voittaa. Näin poimien 1 kolikon maksimoida Max palkkio.

kuten olet saattanut huomata, alla olevan kuvan puun solmuihin on kaiverrettu joitakin arvoja, joita kutsutaan minimax-arvoiksi. Solmun minimax-arvo on solmun hyödyllisyys, jos se on päätepiste.



jos solmu on ei-terminaalinen Max-solmu, solmun minimax-arvo on suurin kaikista solmun seuraajien minimax-arvoista. Toisaalta, jos solmu on ei-terminaalinen min-solmu, solmun minimax-arvo on pienin kaikkien solmun seuraajien minimax-arvoista.

nyt keskustellaan alfa beta-karsinnan ideasta. Jos käytämme alfa-beeta-karsintaa standardimax-algoritmiin, se antaa saman päätöksen kuin standardialgoritmi, mutta se karsii tai leikkaa solmut, jotka ovat epätavallisia ratkaisupuussa eli jotka eivät vaikuta algoritmin tekemään lopulliseen päätökseen. Tämä auttaa välttämään monimutkaisten puiden tulkinnan monimutkaisuutta.

Katso, miten KNN-algoritmi toimii.

nyt keskustellaan intuitiosta tämän tekniikan takana. Yritetään löytää minimax päätös alla puu :



tässä tapauksessa,

Minimax-päätös = MAX {MIN {3, 5, 10}, MIN {2, A, b}, MIN {2, 7, 3}}

= MAX {3, c, 2} = 3

täällä edellä tulos sinun täytyy olla epäilystäkään mielessäsi, että miten voimme löytää enintään puuttuu arvo. Joten tässä on ratkaisu myös epäilykseesi:

toisessa solmussa valitsemme minimiarvoksi c, joka on pienempi tai yhtä suuri kuin 2 eli C <= 2. Nyt jos c < = 3 ja meidän on valittava max 3, c, 2, maksimiarvo on 3.

olemme tehneet päätöksen katsomatta noita solmuja. Tässä kohtaa alpha-beta-karsinta tulee mukaan näytelmään.

avainkohdat Alfa-beta-karsinnassa

• Alpha: Alpha on paras valinta tai korkein arvo, jonka olemme löytäneet missään vaiheessa Maksimoijan polulta. Alfan alkuarvo on -∞.

• Beta: Beta on paras valinta tai alin arvo, että olemme löytäneet missään vaiheessa polun Minimizer. Alfan alkuarvo on+∞.

• ehtona alfa-beeta-karsinnalle on, että α >= β.

• jokaisen solmun on seurattava alfa-ja beeta-arvojaan. Alpha voidaan päivittää vain, kun on Maxin vuoro, ja vastaavasti beta voidaan päivittää vain, kun se on Minin mahdollisuus.

• MAX päivittää vain alfa-arvot ja MIN player päivittää vain beta-arvot.

• solmun arvot siirretään Ylempiin solmuihin alfa-ja beta-arvojen sijaan puun kääntöpuolelle siirtymisen aikana.

• Alfa-ja beeta-arvot siirtyvät vain lapsisolmuihin.

alfa-beeta-karsinnan työstäminen

1. aloitetaan ensin alkuliikkeellä. Määrittelemme aluksi alfa-ja beeta-arvot huonoimmiksi tapauksiksi eli α = – ∞ ja β= +∞. Me karsimme solmun vasta, kun alfa on suurempi tai yhtä suuri kuin beta.

2. Alfan alkuarvo on pienempi kuin beetan, joten emme karsineet sitä. Nyt on Maxin vuoro. Solmussa d lasketaan alfan arvo. Alfan arvo solmussa D on max (2, 3). Alfan arvo solmussa D on siis 3.

3. Nyt seuraava siirto on solmu B ja sen vuoro min Nyt. Solmussa B alfa beetan arvo on siis min (3,∞). Solmussa B arvot ovat siis alfa= – ∞ ja beta on 3.

seuraavassa vaiheessa algoritmit kulkevat solmun B seuraavan seuraajan, joka on solmu E, ja myös arvot α= – ∞ ja β= 3 ohitetaan.

4. Nyt on Maxin vuoro. E-solmussa etsimme Maxin. Alfan nykyinen arvo E: ssä on – ∞ ja sitä verrataan arvoon 5. Eli MAX ( – ∞ , 5) on 5. E-solmussa alfa = 5, Beta = 5. Nyt voimme nähdä, että alfa on suurempi kuin beta, joka täyttää karsinta ehto, joten voimme karsia oikea seuraaja solmu E ja algoritmi ei kuljeta ja arvo solmu E on 5.

6. Seuraavassa vaiheessa algoritmi tulee jälleen solmuun a solmusta B. solmussa a alfa muuttuu maksimiarvoksi MAX ( – ∞ , 3). Joten nyt alfan ja beetan arvo solmussa A on vastaavasti (3,+∞) ja se siirretään solmuun C. Nämä samat arvot siirretään solmuun F.

7. Solmussa F alfan arvoa verrataan vasempaan haaraan, joka on 0. Joten MAX (0, 3) on 3 ja sitten verrattuna oikeaan lapseen, joka on 1, ja MAX (3,1) = 3 edelleen α pysyy 3, mutta solmun arvo F tulee 1.

8. Nyt solmu F palauttaa solmun arvon 1 C: ksi ja vertaa beta-arvoon C: ssä.nyt sen vuoro on MIN. Eli MIN ( + ∞ , 1) on 1. Nyt solmussa C α= 3, ja β= 1 ja alfa on suurempi kuin beta, joka jälleen täyttää karsinta ehto. Joten, seuraava seuraaja solmu C so. G karsitaan, eikä algoritmi laskenut koko alaluokkaa G.

nyt C palauttaa solmun arvon A: ksi ja A: n paras arvo on MAX (1, 3) on 3.

edellä esitetty puu on lopullinen puu, joka osoittaa solmut, jotka on laskettu ja solmut, joita ei ole laskettu. Niin, tässä esimerkissä maksimointilaitteen optimaalinen arvo on 3.

Katso avoimen lähdekoodin Python-kirjastoja.

siirtojärjestys karsinnassa

alfa-beeta-karsinnan tehokkuus perustuu siihen, missä järjestyksessä solmu tutkitaan. Move-käskytyksellä on tärkeä rooli alpha beta-karsinnassa.

Alpha beta-karsinnassa on kahdenlaisia siirtojärjestyksiä:

1. huonoin tilaus: joissakin tapauksissa alpha beta karsiminen mikään solmu karsitaan algoritmin ja toimii kuten standardi minimax algoritmi. Tämä kuluttaa paljon aikaa, koska alfa-ja beetakertoimet ja myös ei anna mitään tehokkaita tuloksia. Tätä kutsutaan huonoimmaksi tilaukseksi karsimisessa. Tällöin paras liike tapahtuu puun oikealla puolella.
2. ideaali Järjestys: joissain tapauksissa algoritmin karsimien solmujen alfa beta-karsintaerä. Tätä kutsutaan ihanteelliseksi tilaamiseksi karsimisessa. Tällöin paras liike tapahtuu puun vasemmalla puolella. Sovellamme DFS siten se ensin etsiä vasemmalle puusta ja mennä syvälle kaksi kertaa minimax algoritmi samassa ajassa.

säännöt hyvän järjestyksen löytämiseksi

• paras siirto tapahtuu alimmasta solmusta
• käytä domain knowledge ja löydä paras siirto
• solmujen Järjestys tulisi olla siten, että parhaat solmut lasketaan ensin

Katso tämä Python-opetusohjelma aloittelijoille

codes in python

class MinimaxABAgent: """ Minimax agent """ def __init__(self, max_depth, player_color): """ Initiation Parameters ---------- max_depth : int The max depth of the tree player_color : int The player's index as MAX in minimax algorithm """ self.max_depth = max_depth self.player_color = player_color self.node_expanded = 0 def choose_action(self, state): """ Predict the move using minimax algorithm Parameters ---------- state : State Returns ------- float, str: The evaluation or utility and the action key name """ self.node_expanded = 0 start_time = time.time() print("MINIMAX AB : Wait AI is choosing") list_action = AIElements.get_possible_action(state) eval_score, selected_key_action = self._minimax(0,state,True,float('-inf'),float('inf')) print("MINIMAX : Done, eval = %d, expanded %d" % (eval_score, self.node_expanded)) print("--- %s seconds ---" % (time.time() - start_time)) return (selected_key_action,list_action) def _minimax(self, current_depth, state, is_max_turn, alpha, beta): if current_depth == self.max_depth or state.is_terminal(): return AIElements.evaluation_function(state, self.player_color), "" self.node_expanded += 1 possible_action = AIElements.get_possible_action(state) key_of_actions = list(possible_action.keys()) shuffle(key_of_actions) #randomness best_value = float('-inf') if is_max_turn else float('inf') action_target = "" for action_key in key_of_actions: new_state = AIElements.result_function(state,possible_action) eval_child, action_child = self._minimax(current_depth+1,new_state,not is_max_turn, alpha, beta) if is_max_turn and best_value < eval_child: best_value = eval_child action_target = action_key alpha = max(alpha, best_value) if beta <= alpha: break elif (not is_max_turn) and best_value > eval_child: best_value = eval_child action_target = action_key beta = min(beta, best_value) if beta <= alpha: break return best_value, action_target

tässä dokumentissa on nähty tärkeä osa peliteoriaa. Vaikka minimax algoritmin suorituskyky on hyvä, mutta algoritmi on hidas. Jotta se olisi nopea, käytämme alfa-beeta-karsinta-algoritmia, joka kaataa epätavallisia solmuja päätöksentekopuusta suorituskyvyn parantamiseksi. Nykyään nopea ja hyvin suoritettu algoritmi on laajalti käytössä.

Tsekkaa nämä tekoäly – ja Koneoppimiskurssit loistavasta oppimisesta alan taitoon ja master Alpha Beta-karsintaan ja muihin vastaaviin algoritmeihin.

lisäluku

1. a * hakualgoritmi tekoälyssä (AI)
2. Ratkaisupuun algoritmi selitettynä esimerkeillä
3. paras ensimmäinen hakualgoritmi tekoälyssä | käsitteessä, toteutuksessa, hyödyissä, haitoissa
4. mikä on tekoäly? Miten tekoäly toimii, tyypit ja tulevaisuus?