Alfa-béta vágás
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 például 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 az 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.
Az algoritmus
szerkesztésAz 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:
alphabeta(node)
return evaluate(node, -infinity, +infinity, true)
evaluate(node, alpha, beta, is_maximizing_node)
if node_is_a_leaf()
return the_heuristic_value_of_node
if node_is_a_maximizing_node()
for each child of node
alpha = max(alpha, evaluate (child, alpha, beta))
if beta <= alpha
break
return alpha
if node_is_a_minimizing_node()
for each child of node
beta = min(beta, evaluate (child, alpha, beta))
if beta <= alpha
break
return beta
Hatékonyság a minimaxszal szemben
szerkesztésAz 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 aktuálisan vizsgált lépésre adható válaszok közül az előző vizsgált lépésre adott legjobb választ próbálja ki először.
Egy képzeletbeli játékfa esetében, amelynek minden csomópontjában konstans b lehetséges lépés van és d a mélysége, az alfa-béta algoritmus műveletigénye a legkedvezőtlenebb esetben egyenlő a minimax algoritmus műveletigényével, azaz . A legkedvezőbb esetben, amikor minden csomópontban a legjobb lépéssel kezdjük a vizsgálatot, ez . Azaz ugyanannak a fának a megvizsgálása négyzetgyöknyi levélcsomópont kiértékelését igényli, vagy más nézőpontból megközelítve: ugyanannyi levélcsomópont kiértékelése esetén kétszer olyan mély fát tudunk megvizsgálni.
