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

Algoritem MINIMAX: Razlika med redakcijama


 
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''':
 
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{nochess}
 
\begin{equation*}
 
\begin{equation*}
 
eval_{w}(p) + eval_{b}(p) = 0.
 
eval_{w}(p) + eval_{b}(p) = 0.
Vrstica 10: Vrstica 10:
  
 
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.
 
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.
 +
-->

Redakcija: 07:02, 19. oktober 2006

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 p ovrednotimo za oba igralca (belega - eval_{w}(p), črnega - eval_{b}(p)) in dobimo naslednji izraz oz. ničelno vsoto: