Cookies help us deliver our services. By using our services, you agree to our use of cookies.

Šahovski iskalni algoritmi


Iskalni algoritem je osrednji del šahovskih programov. Le ta na določen način preiskuje iskalno drevo s pomočjo ocenitvene funkcije, na koncu pa poda potezo za nadaljevanje igre. Z matematičnega stališča lahko igro šah opišemo kot igro med dvema nasprotnikoma s popolno informacijo in ničelno vsoto. Kot vemo je šah igra med dvema igralcema in sicer med belim in črnim. Oba igralca imata popoln pregled nad celotno igro (pozicijo in potezami), zato takim igram pravimo tudi igre s popolno informacijo. Dodatno lastnost šahovske igre pa predstavlja ničelna vsota. Določa jo strukturno ravnotežje v tekmovalni naravi igre. Igra poteka z izmenjavo potez med igralcema. Vsaka od legalnih potez prinaša določeno prednost oz. slabost za igralca na potezi oz. njegovega nasprotnika. Tako lahko npr. potezo p ovrednotimo za oba igralca (belega - eval_{w}(p), črnega - eval_{b}(p)) in dobimo naslednji izraz oz. ničelno vsoto:

eval_{w}(p) + eval_{b}(p) = 0.

Na osnovi tega matematičnega opisa lahko zgradimo drevo igre. To je drevo, ki v korenu drevesa vsebuje začetno pozicijo, v listih drevesa pa se nahajajo končne pozicije. Problem tega drevesa pri šahovski igri je njegova ogromna velikost. Drevo igre vsebuje približno w^d vozlišč, kjer w predstavlja povprečno število potez na eno pozicijo, d pa povprečno število potez na partijo. Tako iskalno drevo praktično ni mogoče preiskati. Zato šahovski programi uporabljajo algoritme, ki preiskujejo samo del drevesa igre. Ta del drevesa imenujemo tudi iskalno drevo. To drevo v korenu vsebuje trenutno pozicijo igre, v listih pa vozlišča, ki zadoščajo določenemu pogoju. Ta pogoj je lahko npr. določen z globino iskanja.

Algoritmi s pomočjo katerih šahovski programi preiskujejo iskalno drevo so: