Játékfák,
alfa-béta vágás, részlegesen kifejtett
játékfák, heurisztikák
Élgyűjtés játék:
Adott egy gráf, melynek minden éléhez rendelve van
egy-egy érték, továbbá el van helyezve a
két játékosnak, A-nak
illetve B-nek
egy-egy bábuja a gráf egy-egy csúcsán. A
játékosok felváltva
lépnek, minden körben a bábujukat annak aktuális
pozíciójából
valamely szomszédos csúcsra áthelyezve (A
kezd). Ezen lépés következtében az adott
él megszűnik, a játékban
többször már nem használható fel,
viszont az aktuális játékos pontszáma
a felhasznált él értékével nő. A
játék akkor ér véget, amikor
valamelyik játékos már nem tud többet
lépni.
Példa alfa-béta
vágással. Az ábrán egy-egy gráf
alatt az aktuális eredmény is fel van tüntetve [A pontszáma : B pontszáma] formában.
Lehetséges heurisztikák az élgyűjtés
játékhoz:
- h0=PA-PB
- h1=az adott
állásból (mindkét játékos
helyett) a mohó stratégiával folytatva
kialakuló végeredmény
- legyen k=kG
valamely G-től függő
konstans
h2=az adott
állásból (mindkét játékos
esetén) véletlen stratégiát folytatva
kialakuló k
végeredmény átlaga
- . . .
A játékos
stratégiája:
- játékfa kifejtése 2 mélységig
- heurisztika: hA=h1
B játékos
stratégiája:
- játékfa kifejtése 5 mélységig
- heurisztika: hB=h0
A játékos kezd,
kiértékeli az állást:
ami alapján a 3-as csúcsba lép.
Következőként B
értékel:
és mivel minimalizál, ő is a 3-as csúcsra
lép.
Ebben a helyzetben A csak a
2-esre léphet:
B pedig ezután már sehova. Vége a
játéknak, a végeredmény 3:1; azaz B fizet A-nak 2 dollárt.
