[Solomonov Seminar] 143. Solomonov seminar

[Marko Grobelnik]

Vabim vas na 143. Solomonov seminar, ki bo v torek,
16. marca 2004 ob 13:00 uri v Veliki predavalnici IJS.

Na seminarju bosta Mitja Lustrek in Matjaz Gams predstavila
analizo iskalnega prostora, ki se pojavi pri algoritmih za igranje iger.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mitja Lustrek in Matjaz Gams (IJS):
  PATOLOGIJA MINIMAKSA

Skoraj vsi programi za igranje iger temeljijo na preiskovanju 
drevesa igre in nacelu minimaksa. Praksa kaze, da se z vecanjem 
globine preiskovanja igranje izboljsuje. Iz tega bi bilo moc sklepati, 
da minimanks zmanjsa napako, ki jo naredimo, ko hevristicno 
ocenimo stanja igre v listih. Ze pred 20 leti pa so na videz smiselni 
teoreticni modeli pokazali prav nasprotno. Poizkusov razlage je bilo 
precej, dokoncnega odgovora pa se do danes ni.
 
Poizkusila bova nekoliko osvetliti opisani problem in predstaviti najine 
ugotovitve. Pokazala bova, kaksne razultate dobimo, ce se omejimo manj 
kot v preteklih raziskavah, in kaksne implikacije ima to za programe za 
igranje iger. Opisala bova tudi algoritem, ki omogoca analizo vseh dreves 
igre izbrane globine (ki jih je lahko 10 na vec 1000), in kaj nam pove 
o podobnosti med bliznjimi stanji igre - lastnosti, ki najverjetneje pojasnjuje, 
zakaj se minimaks v praksi obnese. Pokazala bova tudi spodbudne rezultate, 
ki jih dobimo, ce za ocene stanj igre namesto zmag in porazov, kot se je 
to pocelo do sedaj, uporabimo realna stevila.