Alfa-béta vágás
A Wikipédiából, a szabad enciklopédiából.
 |
Ez a szócikk (vagy szakasz) nem tünteti fel a forrásokat, melyek segítségével készült. Segíts megbízható forrásokat találni, hogy alátámaszthassuk, ami a lapon olvasható! |
Az alfa-béta vágás egy játékelméleti keresési algoritmus, amellyel csökkenthető a játékfában lévő kiértékelendő állások száma a minimax algoritmus által szükséges kiértékelésekhez képest. Az algoritmust az olyan kétszemélyes játékoknál mint pl. az amőba, sakk, go stb. lehet eredményesen használni gépi játékos készítésére. Az algoritmus alapötlete azon nyugszik, hogy ha a játékfában az éppen vizsgált lépésünkre az ellenfélnek van egy olyan erős lépése ami miatt ezt a lépést úgyse választanánk (mivel a vizsgálat korábbi részéből már van jobb választásunk), akkor az erre a lépésre az ellenfél által adható további lépéseket nem szükséges megvizsgálni. (Más szóval: ha ez ellenfél válaszlépése túl jó, akkor úgyse fogjuk meglépni az azt lehetővé tévő lépésünket.) Az algoritmusban ezen részjátékfák fölösleges vizsgálatának kihagyását hívjuk alfa illetve béta vágásnak. A minimax algoritmus ilyetén történő optimalizálása nem változtatja meg a kapott végeredményt.
[szerkesztés] Az algoritmus
Az algoritmus a játékfa bejárása közben két értéket tart karban, az ún. alfa és béta értéket, az alfa azt a minimum értéket jelenti, amit az ún. 'maximalizáló' játékos már biztosított magának, illetve a béta azt a maximum értéket, amit a 'minimalizáló' játékos biztosított magának. Az algoritmus induláskor a két értéket mínusz végtelen illetve plusz végtelenre inicializálja, majd a fa rekurzív vizsgálata közben folyamatosan állítgatja értéküket a két játékos által garantáltan elérhető értékekre. Ezáltal folyamatosan szűkül ez az alfa-béta ablak. Amint a béta kisebbé válik az alfánál, az azt jelenti, hogy ez az állás – ha mind a két játékos részéről a legjobb játékot tételezzük fel – nem állhat elő, így nincs is értelme tovább vizsgálni.
Az algoritmus pszeudo kódja:
evaluate (node, alpha, beta)
if node_is_a_leaf()
return the_heuristic_value_of_node
if node_is_a_maximizing_node()
for each child of node
beta = min (beta, evaluate (child, alpha, beta))
if beta <= alpha
return alpha
return beta
if node_is_a_minimizing_node()
for each child of node
alpha = max (alpha, evaluate (child, alpha, beta))
if beta <= alpha
return beta
return alpha
[szerkesztés] Hatékonyság a minimax-szal szemben
Az alfa-béta algoritmus előnye abból származik, hogy a játékfa bizonyos ágainak vizsgálatát megspórolja. Ezáltal a játékfa gyorsabb vagy mélyebb vizsgálatát teszi lehetővé. A vágások által realizálható előny sok tényezőtől függ, de a gyakorlati életben közelítőleg a vizsgálati mélység megduplázása érhető el vele. A vágások mértéke nagyon függ a játékfa 'szélességétől', amely paraméter leginkább az adott játék sajátossága, illetve attól hogy milyen sorrendben értékeljük ki a lépéseket, egészen pontosan attól, hogy mennyire hamar értékeljük ki a mindenkori adott álláshoz tartozó legerősebb lépés(eke)t. Ezt elősegítendő célszerű erősorrendben megvizsgálni a lehetséges lépéseket, amely erősorrendet heurisztikus algoritmusokkal lehet megbecsülni. Ezek közül az egyik legegyszerűbb a gyilkos lépés heurisztikája, amely az előző vizsgált lépésre adott legjobb választ próbálja ki először az aktuálisan vizsgált lépésre adható válaszok közül.
Egy képzeletbeli játékfa estében aminek minden csomópontjában konstans b lehetséges lépés van és d a mélysége, legkedvezőtlenebb esetben az alfa-béta algoritmus műveletigénye egyenlő a minimax algoritmus műveletigényével = O(bd). A legkedvezőbb esetben, amikor minden csomópontban a legjobb lépéssel kezdjük a vizsgálatot = 
. Azaz ugyanannak a fának a megvizsgálása négyzetgyöknyi levél csomópont kiértékelését igényli, vagy más nézőpontból megközelítve: ugyanannyi levél csomópont kiértékelése esetén kétszer olyan mély fát tudunk megvizsgálni.
