mindenfele

[Beregnyei Balazs]

On Sun, 24 Aug 2003, VF wrote:

> Ha van a vonalban valaki, aki penge a minimax-ban, megszanhatna nehany
> mondattal. Addig OK, hogy csinalok egy ertekelofuggvenyt, eloallitom az

Ehhez epp ertek, irtam ilyet is :) Remelem nem tul offtopic. Bar ha a
tankolasra es a linux hitvitara sem szol be senki...

> pedig mind olyanok, hogy ha jo helyre tesz, megnyeri, ha rossz helyre
> tesz, elveszti a jatszmat. Az amobaban ez egy eleg tipikus szituacio.
> Ilyenkor ugy tunik megkergul a minimax, nem? Sot, eleg ha kesobb van

Nem kergul meg. Elmondom, miert minimax: a keresesi faban egy adott
melyseben (n) csak a legnagyobb erteku lepessel kell foglalkozni, ha te
vagy soron (MAX), es csak a legkisebb ertekuvel, ha az ellenfel (MIN).
Tehat ha a peldad szerint az ellenfel a kovetkezo lepesben nyerhet is es
benazhat is, akkor azt kell feltetelezni, hogy nyerni fog, ezert a lepes
erteke peldaul -1000 (MIN). Ha te lepsz, nyilvan a legjobb lepest fogod
valasztani (MAX).
Tehat a dontes igy nez ki, ha van egy n melysegu keresesi fa:
- az n. melysegben kiertekelsz minden allast (szamitasz egy erteket, hogy
  peldaul max. milyen hosszu lezaratlan sorok vannak a tablan)
- minden n. melysegu a'gcsoportra MIN-t vagy MAX-ot szamolsz attol
  fuggoen, hogy kinek a lepese
- a fenti erteket beirod az n-1 szintu allasba, ami a szuloje az n. szintu
  a'gdarabnak
- az n-1 szintre (stb.) ugyanezt tovabbviszed, felvaltva MIN es MAX
- ha eljutottal az 1. szintre, akkor maris tudod, hogy mit kell lepned,
  ez egy MAX lesz az 1. szintre :)

Igazabol nem is kell a teljes fa't bejarni, mert kitalaltak az alfa-beta
algoritmust, amivel a fa't jol meg lehet kurtitani anelkul, hogy fontos
esetet eldobnank. Ha erdekelnek a reszletek, szerezd meg a "Szamitogep es
sakk" cimu konyvet, ez egy regi Data Becker kiadvany, mint a C64-es
konyvek. En is onnan tudok mindent :)

Udv,
BB