az alfa-béta metszés a minimax algoritmus optimalizálási technikája. A blog folyamán megvitatjuk, hogy mit jelent az alfa-béta metszés, megvitatjuk a minimax algoritmust, a jó megrendelés megtalálásának szabályait és így tovább.
- Bevezetés
- Minimax algoritmus
- kulcsfontosságú pontok alfa-béta metszés
- munka alfa-béta metszés
- lépés rendelés metszés
- szabályokat találni jó rendelés
- kódok Python
bevezetés
a ‘metszés’ szó ágak és levelek levágását jelenti. Az adattudományban a metszés egy sokat használt kifejezés, amely a döntési fák és a véletlenszerű erdők utáni és előtti metszésére utal. Az alfa-béta metszés nem más, mint a haszontalan ágak metszése a döntési fákban. Ezt az alfa-béta metszési algoritmust a kutatók önállóan fedezték fel az 1900-as években.
az alfa-béta metszés a minimax algoritmus optimalizálási technikája, amelyet a következő szakaszban tárgyalunk. A metszés szükségessége abból adódott, hogy egyes esetekben a döntési fák nagyon összetetté válnak. Ebben a fában néhány haszontalan ág növeli a modell összetettségét. Tehát ennek elkerülése érdekében az alfa-béta metszés jön létre, hogy a számítógépnek ne kelljen az egész fát néznie. Ezek a szokatlan csomópontok lassúvá teszik az algoritmust. Ezért eltávolításával ezek a csomópontok algoritmus lesz gyors.
Tudjon meg többet az a* algoritmusról.
Minimax algoritmus
a Minimax egy klasszikus mélység-első keresési technika egy szekvenciális kétjátékos játékhoz. A két játékos neve MAX és min. A minimax algoritmus célja, hogy megtalálja az optimális lépés MAX, A Játékos a gyökér csomópont. A keresési fa úgy jön létre, hogy rekurzív módon bővíti az összes csomópontot a gyökérből mélység-első módon a játék végéig vagy a maximális keresési mélység eléréséig. Vizsgáljuk meg részletesen ezt az algoritmust.
mint már említettük, két játékos van a játékban, viz – Max és Min. Max játssza az első lépést. Max feladata, hogy maximalizálja jutalmát, míg Min feladata, hogy minimalizálja Max jutalmát, ugyanakkor növelje saját jutalmát. Tegyük fel, hogy Max lépéseket tehet a, b, vagy c. melyikük adja Maxnek a legjobb jutalmat, amikor a játék véget ér? A kérdés megválaszolásához meg kell vizsgálnunk a játékfát megfelelő mélységben, és feltételeznünk kell, hogy Min optimálisan játszik, hogy minimalizálja Max jutalmát.
íme egy példa. Négy érme van egymás után, és minden játékos felvehet egy érmét vagy két érmét a fordulóján. Az a játékos nyer, aki felveszi az utolsó érmét. Feltételezve, hogy Max játszik először, milyen lépést kell tennie Maxnek a győzelemhez?
ha Max két érmét választ, akkor csak két érme marad, és Min két érmét választhat és nyerhet. Így 1 érme felvétele maximalizálja Max jutalmát.
mint észrevehette, az alábbi ábrán látható fa csomópontjain néhány érték szerepel, ezeket minimax értéknek nevezzük. A csomópont minimax értéke a csomópont hasznossága, ha terminálcsomópont.
ha a csomópont nem terminális Max csomópont, akkor a csomópont minimax értéke a csomópont összes utódjának minimax értékeinek maximuma. Másrészt, ha a csomópont nem terminális min csomópont,akkor a csomópont minimax értéke a csomópont összes utódjának minimax értékeinek Minimax értéke.
most megvitatjuk az alfa-béta metszés ötletét. Ha alfa-béta metszést alkalmazunk a standard minimax algoritmusra, akkor ugyanazt a döntést hozza, mint a standard algoritmusé, de szilva vagy levágja azokat a csomópontokat, amelyek szokatlanok a döntési fában, azaz amelyek nem befolyásolják az algoritmus végső döntését. Ez segít elkerülni a komplex fák értelmezésének összetettségét.
nézze meg, hogyan működik a KNN algoritmus.
most beszéljünk a technika mögötti intuícióról. Próbáljuk megtalálni minimax döntés az alábbi fa :
ebben az esetben,
Minimax döntés = MAX {MIN {3, 5, 10}, MIN {2, a, b}, MIN {2, 7, 3}}
= MAX {3, c, 2} = 3
itt a fenti eredményben kétségei vannak a fejedben, hogy hogyan találjuk meg a maximumot a hiányzó értékből. Tehát itt van a kétség megoldása is:
a második csomópontban a minimális értéket választjuk c-nek, amely kisebb vagy egyenlő 2-vel, azaz c <= 2. Ha c < = 3 és ki kell választanunk a 3, c, 2 maximális értékét, akkor a maximális érték 3 lesz.
úgy döntöttünk, hogy nem vizsgáljuk meg ezeket a csomópontokat. És itt jön be a játékba az alfa-béta metszés.
az alfa-béta metszés legfontosabb pontjai
- Alpha: Az Alpha a legjobb választás vagy a legmagasabb érték, amelyet a Maximizer útja mentén találtunk. Az alfa kezdeti értéke -++.
- béta: a béta a legjobb választás vagy a legalacsonyabb érték, amelyet a Minimizer útján bármely esetben találtunk. Az alfa kezdeti értéke+++.
- A feltétele, hogy az Alfa-béta Metszés, hogy α >= β.
- minden csomópontnak nyomon kell követnie az alfa és béta értékeit. Az Alpha csak akkor frissíthető, ha MAX a sor, és hasonlóképpen, a béta csak akkor frissíthető, ha MIN esélye van.
- a MAX csak az alfa értékeket, a MIN player pedig csak a béta értékeket frissíti.
- a csomópont értékei a felső csomópontoknak kerülnek átadásra az alfa és a béta értékek helyett a fa hátoldalán.
- az alfa és béta értékeket csak a gyermekcsomópontokhoz lehet továbbítani.
az alfa-béta metszés munkája
- először a kezdeti lépéssel kezdjük. Kezdetben az alfa-és béta-értékeket fogjuk a legrosszabb esetként definiálni, pl. Csak akkor fogjuk metszeni a csomópontot, ha az alfa nagyobb vagy egyenlő lesz a bétával.
2. Mivel az alfa kezdeti értéke kisebb, mint a béta, ezért nem metszettük meg. Most MAX következik. Tehát a D csomópontnál az alfa értéke kiszámításra kerül. Az alfa értéke a D csomópontban max (2, 3) lesz. Tehát az alfa értéke a D csomópontban 3 lesz.
3. Most a következő lépés a B csomóponton lesz, most pedig min. Tehát a B csomópontnál az alfa-béta értéke min (3, 6) lesz. Tehát a B csomópontnál az értékek alpha= – xhamsternek, a béta pedig 3 – nak felelnek meg.
a következő lépésben az algoritmusok áthaladnak a B csomópont következő utódján, amely az E csomópont, és a következők értékei is átadásra kerülnek.
4. Most MAX következik. Tehát az e csomópontnál keressük max. Az alfa jelenlegi értéke E-nél-6, és összehasonlítjuk 5-tel. Tehát MAX (- 6, 5) 5 lesz. Tehát az e csomópontnál alfa = 5, béta = 5. Most, amint láthatjuk, hogy az alfa nagyobb, mint a béta, amely kielégíti a metszési feltételt, így meg tudjuk metszeni az e csomópont megfelelő utódját, és az algoritmus nem fog áthaladni, és az e csomópont értéke 5 lesz.
6. A következő lépésben az algoritmus ismét az a csomóponthoz érkezik a B csomópontból. Tehát most az alfa és a béta értéke az a csomópontban (3, + 6) lesz, és átkerül a C csomópontba. ugyanezek az értékek átkerülnek az F csomópontba.
7. Az F csomópontnál az alfa értékét összehasonlítjuk a bal ággal, amely 0. Tehát MAX (0, 3) 3 lesz, majd összehasonlítjuk a megfelelő gyermekkel, amely 1, és Max (3,1) = 3 továbbra is 3 marad, de az F csomópont értéke 1 lesz.
8. Most az F csomópont visszaadja az 1-es csomópont értékét C-nek, és összehasonlítja a C Béta értékével. Tehát MIN (+6, 1) lesz 1. Most a C csomópontnál, a (C) csomópontnál, a (C) csomópontnál, a (C) csomópontnál, és a (C) csomópontnál az alfa nagyobb, mint a (Z) béta, ami szintén kielégíti a metszési feltételt. Tehát a C csomópont következő utódja, azaz. G lesz metszeni, és az algoritmus nem számította ki a teljes részfa G.
most, C visszaadja a csomópont értékét A-nak, és a legjobb értéke MAX (1, 3) lesz 3.
a fent ábrázolt fa az utolsó fa, amely megmutatja a kiszámított csomópontokat és a nem kiszámított csomópontokat. Tehát ebben a példában a maximalizáló optimális értéke 3 lesz.
nézd meg a nyílt forráskódú Python könyvtárakat.
Mozgásrendezés metszés közben
az alfa – béta metszés hatékonysága a csomópont vizsgálatának sorrendjén alapul. A mozgásrendelés fontos szerepet játszik az alfa-béta metszésben.
kétféle lépésrendezés létezik az alfa-béta metszésben:
- legrosszabb Rendezés: egyes esetekben az alfa-béta metszés egyik csomópont metszeni az algoritmus működik, mint a standard minimax algoritmus. Ez fogyaszt sok időt, mert az alfa-és béta-tényezők, és nem ad semmilyen hatékony eredményt. Ezt a metszés legrosszabb megrendelésének nevezik. Ebben az esetben a legjobb lépés a fa jobb oldalán történik.
- ideális Rendezés: egyes esetekben az alfa-béta metszés sok a csomópontok metszeni az algoritmus. Ezt nevezik a metszés ideális megrendelésének. Ebben az esetben a legjobb lépés a fa bal oldalán történik. A DFS-t alkalmazzuk, így először a fától balra keres, és kétszer olyan mélyre megy, mint a minimax algoritmus ugyanannyi idő alatt.
szabályok A jó sorrend megtalálásához
- a legjobb lépés a legalacsonyabb csomópontból történik
- használja a domain tudást, miközben megtalálja a legjobb lépést
- a csomópontok sorrendjének úgy kell lennie, hogy a legjobb csomópontok először kiszámításra kerüljenek
nézze meg ezt a Python oktatóanyagot kezdőknek
kódok a Pythonban
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
ebben a dokumentumban a játékelmélet fontos elemét láttuk. Bár a minimax algoritmus teljesítménye jó, de az algoritmus lassú. Tehát, hogy gyors legyen, alfa-béta metszési algoritmust használunk, amely a teljesítmény javítása érdekében levágja a szokatlan csomópontokat a döntési fáról. Manapság széles körben használják a gyors és jól végrehajtott algoritmust.
nézze meg ezeket a mesterséges intelligencia és gépi tanulási tanfolyamokat a nagyszerű tanulástól a továbbképzésig a tartományban, és elsajátítsa az alfa-béta metszést és más ilyen algoritmusokat.
további olvasmányok
- a * keresési algoritmus a mesterséges intelligenciában (AI)
- döntési fa algoritmus példákkal magyarázva
- legjobb első keresési algoritmus az AI-ben | koncepció, megvalósítás, előnyök, hátrányok
- mi a mesterséges intelligencia? Hogyan működik az AI, típusai és jövője?