Студент Рачунарског факултета Марко Матовић је у среду, 8. новембра 2023. године одбранио дипломски рад на тему Генерисање “мат у 3” шаховских позиција генетским алгоритмом пред комисијом коју су чинили ментор др Јелена Васиљевић и члан др Душан Вујошевић.
У уводу свог рада Марко је истакао следеће:
Развој рачунарске технологије непрекидно помера границе проблема које можемо решити, али уједно отвара врата за нове изазове. У том контексту, оптимизација се све више користи као основни алат за решавање тих проблема. На свету постоји безброј проблема који захтевају проналажење најбољег могућег решења или, у неким случајевима, решења која су „довољно добра“. У оваквим ситуацијама, генетски алгоритми често пружају ефикасне методе за проналажење задовољавајућих решења.
Генетски алгоритми, инспирисани природним процесима селекције и еволуције, користе се за решавање разноврсних оптимизационих проблема. Они се ослањају на идеју о преживљавању најјачих како би систематски побољшали решење проблема. Почиње се са скупом потенцијалних решења, а затим користе процеси попут селекције, укрштања и мутације како би итеративно побољшали ова решења.
…
Као једна од најстаријих и најпроучаванијих игара, шах и даље ствара сталну потражњу за новим и иновативним садржајем. Иако већ постојеће базе шаховских проблема нуде мноство материјала, истраживање нових метода стварања ових проблема је и даље значајно.
Примењен је генетски алгоритам, алат инспирисан природним процесима еволуције, с циљем да генерише што оптималније шаховске позиције које воде до мат у три потеза. Овај проблем није нимало наиван, и његово решавање на овај начин има своје препреке. Првенствено, поред дефинисања низа провера за легалност позиције, оно што на самом крају разликује две позиције је лепота и занимљивост, а дефинисање објективних критеријума за то је практично немогуће. Затим, простор претраге, који обухвата све легалне позиције, је изузетно велики, што ограничава ефикасност алгоритма. Поред тога, процес спајања две шаховске позиције у једну нову, док се задржавају неопходни услови фитнес функције, представља значајан изазов. Није пронађен добар начин да се нова табла створи спајањем одвојених делова две постојеће табле. Ако делови садрже исте фигуре, резултујућа позиција је илегална. Вероватноћа добијања легалне табле на овакав или сличан начин је минимална. Као последица, кросовер ретко пружа очекивану вредност комбиновањем две јединке из популације. Другим речима, чини се да нисмо у стању да задржимо најбоље карактеристике оба родитеља, већ се резултати често чине насумичним. – закључио је Марко.
Фотографије са одбране доступне су у галерији.