Student Računarskog fakulteta Marko Matović je u sredu, 8. novembra 2023. godine odbranio diplomski rad na temu Generisanje “mat u 3” šahovskih pozicija genetskim algoritmom pred komisijom koju su činili mentor dr Jelena Vasiljević i član dr Dušan Vujošević.
U uvodu svog rada Marko je istakao sledeće:
Razvoj računarske tehnologije neprekidno pomera granice problema koje možemo rešiti, ali ujedno otvara vrata za nove izazove. U tom kontekstu, optimizacija se sve više koristi kao osnovni alat za rešavanje tih problema. Na svetu postoji bezbroj problema koji zahtevaju pronalaženje najboljeg mogućeg rešenja ili, u nekim slučajevima, rešenja koja su „dovoljno dobra“. U ovakvim situacijama, genetski algoritmi često pružaju efikasne metode za pronalaženje zadovoljavajućih rešenja.
Genetski algoritmi, inspirisani prirodnim procesima selekcije i evolucije, koriste se za rešavanje raznovrsnih optimizacionih problema. Oni se oslanjaju na ideju o preživljavanju najjačih kako bi sistematski poboljšali rešenje problema. Počinje se sa skupom potencijalnih rešenja, a zatim koriste procesi poput selekcije, ukrštanja i mutacije kako bi iterativno poboljšali ova rešenja.
…
Kao jedna od najstarijih i najproučavanijih igara, šah i dalje stvara stalnu potražnju za novim i inovativnim sadržajem. Iako već postojeće baze šahovskih problema nude mnostvo materijala, istraživanje novih metoda stvaranja ovih problema je i dalje značajno.
Primenjen je genetski algoritam, alat inspirisan prirodnim procesima evolucije, s ciljem da generiše što optimalnije šahovske pozicije koje vode do mat u tri poteza. Ovaj problem nije nimalo naivan, i njegovo rešavanje na ovaj način ima svoje prepreke. Prvenstveno, pored definisanja niza provera za legalnost pozicije, ono što na samom kraju razlikuje dve pozicije je lepota i zanimljivost, a definisanje objektivnih kriterijuma za to je praktično nemoguće. Zatim, prostor pretrage, koji obuhvata sve legalne pozicije, je izuzetno veliki, što ograničava efikasnost algoritma. Pored toga, proces spajanja dve šahovske pozicije u jednu novu, dok se zadržavaju neophodni uslovi fitnes funkcije, predstavlja značajan izazov. Nije pronađen dobar način da se nova tabla stvori spajanjem odvojenih delova dve postojeće table. Ako delovi sadrže iste figure, rezultujuća pozicija je ilegalna. Verovatnoća dobijanja legalne table na ovakav ili sličan način je minimalna. Kao posledica, krosover retko pruža očekivanu vrednost kombinovanjem dve jedinke iz populacije. Drugim rečima, čini se da nismo u stanju da zadržimo najbolje karakteristike oba roditelja, već se rezultati često čine nasumičnim. – zaključio je Marko.
Fotografije sa odbrane dostupne su u galeriji.