|
|
| (Vmesna redakcija istega uporabnika ni prikazana) |
| Vrstica 1: |
Vrstica 1: |
| − | 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 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 <math>p</math> ovrednotimo za oba igralca (belega - <math>eval_{w}(p)</math>, črnega - <math>eval_{b}(p)</math>) in dobimo naslednji izraz oz. '''ničelno vsoto''':
| |
| | | | |
| − | <!-- \begin{nochess}
| |
| − | \begin{equation*}
| |
| − | eval_{w}(p) + eval_{b}(p) = 0.
| |
| − | \end{equation*}
| |
| − | \end{nochess}
| |
| − |
| |
| − | 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.
| |
| − |
| |
| − | Igralca v šahovski igri izmenjujeta poteze in oba poskušata izbrati najboljšo svojo potezo oz. maksimirati svojo vrednost, posledično pa minimizirati nasprotnikovo. Tako glede na trenutno pozicijo identificiramo igralca MIN in MAX. V začetni poziciji igralca MAX predstavlja beli igralec, ki je na potezi. Igralca MIN pa predstavlja črni igralec. Na osnovi opisanega lahko formuliramo algoritem za igranje iger med dvema nasprotnikoma s popolno informacijo in ničelno vsoto. To naredimo tako, da simuliramo obnašanje igralcev MIN in MAX oz. ti. načela MINIMAX.
| |
| − | -->
| |