Amikor felesleges tovább nézni
A minimax minden lehetőséget végiggondol, de a valóságban ennek nagy része felesleges. Képzeljünk el egy hétköznapi döntést. Már találtunk egy jó ajánlatot, mondjuk egy termékre, és most egy másik boltot nézünk. Ha az első árcédula, amit ott meglátunk, már drágább, mint az eddigi legjobb ajánlatunk, akkor a bolt többi polcát felesleges végignézni. Bármit is találnánk, a döntésünkön már nem változtatna. Pontosan ez az alfa-béta vágás alapötlete.
A minimax fában sok olyan ág van, amelyről menet közben kiderül, hogy nem befolyásolhatja a végső döntést. Ha ezt idejében észrevesszük, akkor az egész ágat átugorhatjuk anélkül, hogy a végét megnéznénk. A lényeg, hogy ez nem közelítés, nem becslés. A vágás pontosan azokat az ágakat metszi el, amelyek biztosan nem számítanak, így a végeredmény ugyanaz marad, mint a teljes minimaxé.
Két korlát, amit magunkkal viszünk
A módszer nevében szereplő két görög betű két korlátot jelöl, amelyeket a gép a keresés közben magával cipel. Az egyik azt tartja számon, mi a legjobb eredmény, amit a mi oldalunk eddig biztosan el tud érni. A másik azt, mi a legjobb, amit az ellenfél eddig biztosítani tud magának. Ez a két szám egyfajta ablakot feszít ki, amelyen belül még értelme van keresni. Amint egy ág kilóg ebből az ablakból, vagyis kiderül, hogy az egyik fél már úgysem engedné ezt az utat, a keresés ott azonnal leáll.
Fontos, hogy a levágott ágakról nem azt mondjuk, hogy rosszak. Csak azt, hogy a döntés szempontjából már közömbösek. Az ellenfél sosem hagyná, hogy ide jussunk, vagy mi sosem választanánk ezt az irányt, ezért mindegy, pontosan mi lenne a végén. A gép így a figyelmét arra összpontosítja, ami valóban eldönti a lépést.
Ugyanaz az eredmény, kevesebb munka
Az alfa-béta vágás legszebb tulajdonsága, hogy semmit nem áldoz fel a pontosságból. A lépés, amit ajánl, pontosan ugyanaz, mint amit a teljes minimax adna. A különbség csak annyi, hogy sokkal kevesebb állást kellett hozzá megvizsgálni. Ez a gyakorlatban óriási különbség. Egy jó vágással a gép ugyanannyi idő alatt jóval mélyebbre tud előre gondolkodni, ami erősebb játékot jelent.
A megtakarítás mértéke azonban nagyban függ attól, milyen sorrendben nézzük a lépéseket. Ha a gép szerencsés, vagy okosan a legígéretesebb lépéseket veszi előre, akkor korán talál egy jó eredményt, és utána nagyon sok ágat le tud vágni. Ha viszont a rosszabb lépésekkel kezd, kevesebbet nyer. Ezért a játékprogramok sok energiát fektetnek abba, hogy a lépéseket jó sorrendbe rakják, mielőtt keresni kezdenek.
Miért fontos ez az elv
Az alfa-béta vágás egy sokkal általánosabb gondolat egyik példája. Nem kell mindent kiszámolni ahhoz, hogy jó döntést hozzunk. Elég annyit kiszámolni, amennyi a döntéshez szükséges, a többi felesleges munka. Ez az elv a klasszikus MI-ben újra és újra visszaköszön. A cél nem az, hogy a gép a lehető legtöbbet dolgozzon, hanem hogy a lehető legkevesebb munkával jusson el a biztosan helyes válaszhoz.
Ezzel lezárul a keresés és a játékok blokkja. Eddig mindig egy megoldáshoz vezető utat, vagy a legjobb lépést kerestük. A következő leckében más típusú problémákra váltunk, ahol nem út a kérdés, hanem az, hogyan adjunk értékeket úgy, hogy közben egy csomó feltétel egyszerre teljesüljön.
Nulla pontosság vész el a vágással. Az alfa-béta ugyanazt a lépést adja, mint a teljes minimax, csak a döntés szempontjából közömbös ágakat hagyja ki. Nem gyorsabb sejtés, hanem ugyanaz a biztos válasz, kevesebb munkából.
Workshop
AI Transformation Day
Egésznapos, vezetőknek szóló program. Feltérképezzük, hol tart a szervezet, mi az első reális lépés, és milyen belső feltételek szükségesek a sikerhez. A nap végén konkrét, prioritizált cselekvési lista.
Érdekel a program →