Moskva, 1978.
******************
Unaprijeđeni Grinblatov program učestvovao je i na Svjetskom prvenstvu mašinskih šahovskih programa 1974. godine.
Naša „Kaissa“ razvijena je 1967. godine u grupi moskovskih matematičara G. M. Adelsona-Veljskog, V. L. Arlazarova, A. V. Uskova i drugih. U razvoju je učestvovao i majstor A. R. Bitman. Uspješno je nastupila protiv programa Dž. Makartija, a nakon usavršavanja učestvovala je i na turniru šahovskih računara u Stokholmu 1974. godine.
Slika 13. Grafički prikaz algoritma u obliku stabla igre. Bijelim kružićima označene su pozicije u kojima su na potezu bijeli, crnim — pozicije u kojima su na potezu crni, dok brojevi predstavljaju procjene pozicija.
Principi ugrađeni u algoritam „Kaisse“ nisu naročito složeni, međutim, njihova programska realizacija povezana je s mnogim teškoćama.
Predstavimo algoritam u obliku stabla igre (vidi sliku 13). Početna pozicija P₀ smatra se korijenom stabla. Upravo za P₀ traži se najbolji potez. Za to je dovoljno procijeniti sve pozicije koje se iz P₀ dobijaju u jednom potezu. Cilj bijelih je, prirodno, da dođu do završne pozicije s najvećom procjenom, dok je cilj crnih — do one s najnižom procjenom.
Ako je najveći rang pozicija u stablu jednak l (rang vrha predstavlja udaljenost od početnog vrha), tada su sve pozicije tog ranga završne. Na osnovu procjena tih pozicija mogu se pronaći procjene za sve pozicije rangova l − 1, l − 2 i tako dalje, sve do pozicija prvog i nultog ranga, čime se određuje najbolji potez u poziciji P₀.
Procjena pozicije Pᵢ bira se, u zavisnosti od toga ko je na potezu, na osnovu maksimalne odnosno minimalne procjene pozicija Pᵢ₊₁. U ovoj šemi razmatranje svake pozicije izgleda isto: pretraživanjem poteza određuje se procjena pozicije.
Blok-dijagram takvog algoritma pretraživanja prikazan je na slici 14. U njemu blok „ispisivanje poteza“ određuje moguće poteze u poziciji koja se razmatra i upisuje ih na spisak neistraženih poteza. Blok „ima li poteza?“ provjerava da li postoji makar jedan neistraženi potez.
Blok „potez“ vrši prelazak iz posmatrane pozicije Pᵢ ranga l u poziciju Pᵢ₊₁ ranga l + 1. Ako je pozicija Pᵢ₊₁ završna, ovaj blok određuje njenu procjenu. Ako nije završna, počinje kretanje nagore kroz stablo.
Posljednji blok na desnoj grani blok-dijagrama algoritma određuje procjenu pozicije Pᵢ nakon što su svi potezi iz te pozicije istraženi u granicama pretraživanja. Ovakva organizacija algoritma po principu „odozgo-nadole i odozdo-nagore“ omogućava smanjenje količine informacija potrebne za sprovođenje pretraživanja.
Slika 14. Blok-dijagram algoritma kretanja kroz stablo pretraživanja.
U algoritmu naše „Kaisse“ primijenjena je još jedna važna pojedinost koja omogućava da se skrati vrijeme potrebno za pretraživanje pozicija. U njemu se ne razmatraju, odnosno odbacuju, pozicije od kojih procjena pozicije P₀ ne zavisi.
Neka je Pₐ pozicija u kojoj su na potezu bijeli, Pᵦ pozicija u kojoj su na potezu crni, a djelimična procjena Pᵦ veća od djelimične procjene Pₐ. Tada se neistraženi potezi iz pozicije Pᵦ mogu zanemariti, jer oni mogu samo smanjiti procjenu Pᵦ, dok procjena Pₐ može samo da se poveća. Na osnovu teorije granica i procjena A. L. Brudnog, koja predstavlja uopštavanje ovog razmišljanja, izgrađen je mehanizam odsijecanja.
Odsijecanje navedenih pozicija predstavlja svojevrsnu „službu najboljih poteza“. Drugim riječima, prilikom odsijecanja vrši se sortiranje poteza prema njihovoj unaprijed utvrđenoj vrijednosti. Prirodno, ako su potezi „poređani“ odgovarajućim redosljedom, postiže se smanjenje obima pretraživanja.
Posebnost programa sastoji se u tome što se postupak izbora poteza svojevrsno „odigrava“ na grubom modelu igre — na takvom modelu šaha u kojem se prednost daje „aktivnim“ potezima. Može se pretpostaviti da ti aktivni potezi uopšte nisu loši.
To su prije svega forsirani potezi, odnosno potezi nakon kojih se osvaja materijal (na primjer, uzimanjem figure) ili se stvara prijetnja da će materijal biti osvojen, kao i šahovi i odgovori na njih.
Izdvajanje aktivnih poteza omogućava da se ograniči dubina pretraživanja svih ostalih „mirnih“ šahovskih poteza, na primjer na pet polupoteza, dok se forsirani potezi razmatraju do znatno veće dubine, praktično do kraja.
Uostalom, ni čovjek gotovo nijednu varijantu ne računa sve do mata i gotovo ni u jednoj poziciji ne razmatra baš sve moguće poteze.
U praksi se dobro pokazao sljedeći redosljed prioriteta kriterijuma prema kojima se potezi sortiraju:
a) u poziciji sa osvojenim materijalom — povlačenje na polja koja nisu napadnuta, iz napada protivničke figure koja je odigrala prethodni potez;
b) pretvaranja pješaka, povoljna uzimanja i uzimanja na polju na koje je protivnik upravo odigrao prethodni potez;
c) najbolji potezi i najbolji odgovori — opovrgavanja, zabilježeni u posebnoj „referentnoj“ bazi u skladu s izračunatim procjenama;
d) povlačenje iz napada protivničke figure koja je odigrala prethodni potez;
e) rokada i uzimanje u prolazu;
f) uzimanje zaštićene figure jednake vrijednosti;
g) šahovi na nenapadnuta polja;
h) potezi na nenapadnuta polja;
i) potezi kraljem iz šaha, ako je izgubljeno pravo na rokadu;
j) šahovi na napadnuta polja;
k) potezi na napadnuta polja;
l) potezi kraljem iz šaha, ako pravo na rokadu nije izgubljeno.
(Nastaviće se)