Avtomatsko odkrivanje zanimivih šahovskih problemovRizvič, Mitja (Avtor) Guid, Matej (Mentor) reševanje problemovšahšahovski problemhitri matkonstrukcijska nalogapreiskovalni algoritmihevristično preiskovanjealgoritem A*hevristikakombinatorična zahtevnostCilj diplomske naloge je bil razviti računalniški program, s katerim bi si ljudje lahko pomagali pri reševanju in ustvarjanju zanimivih šahovskih problemov. Šahovski problem je uganka na šahovnici, ki reševalcu predstavlja neko nalogo. Tovrstna naloga običajno zahteva premikanje figur na šahovnici z uporabo klasičnih šahovskih pravil in ni nujno povezana z matiranjem nasprotnikovega kralja. Poznamo več vrst šahovskih problemov: probleme direktnega mata, pomožne mate, samomate, serijske probleme, šahovske študije, retrogradno analizo itd. Reševalcu lahko postavimo dodatne zahteve, kot so na primer predpisana zadnja poteza ali pa figura, s katero matiramo. Poseben tip šahovskih problemov so konstrukcijske naloge, ki so lahko brez diagrama in tipično vsebujejo samo nalogo, npr. postavite določeno pozicijo ali konstruirajte igro z določenimi lastnostmi. Primer zanimive konstrukcijske naloge bi bil sestaviti najkrajšo šahovsko partijo, ki se konča z matiranjem nasprotnega kralja s kmetom, ki je ravno promoviral v skakača. Tovrstni problemi so lahko zanimivi ne le za šahiste, ampak tudi za širšo javnost, saj zahtevajo le poznavanje osnovnih šahovskih pravil. Igra šaha je kombinatorično zelo zahtevna, kar pomeni, da imamo pri vsakem premiku figure na voljo veliko različnih možnosti. Posledično je pri več zaporednih potezah število možnih kombinacij premikov lahko ogromno. Za ilustracijo: iz začetne šahovske pozicije lahko le štiripotezno partijo (štiri poteze belega in štiri poteze črnega) odigramo na skoraj 85 milijard različnih načinov. Ravno ta kombinatorična eksplozija je pomemben razlog, da je reševanje šahovskih problemov in še zlasti konstrukcijskih nalog lahko izjemno težavno ne le za človeka, ampak tudi za sodobne računalnike. Pri slednjih se lahko dokaj enostavno prepričamo, da samo preiskovanje s t. i. ``surovo silo`` ne bo obrodilo sadov. Potreben je pametnejši pristop oz. vpeljava algoritmov umetne inteligence. V okviru diplomske naloge smo razvili računalniški program, s katerim je mogoče računalnik usposobiti za premagovanje omenjene kombinatorične kompleksnosti ter ga uporabiti za reševanje različnih neobičajnih šahovskih problemov, še zlasti konstrukcijskih nalog. Program temelji na uporabi hevrističnega preiskovanja in namenskih hevristik, katerih naloga je preiskovanje čim bolj učinkovito usmerjati k danemu cilju. Za spopadanje s kombinatorično eksplozijo smo uporabili dodatne mehanizme, kot so zgoščevalne tabele, možnost omejevanja aktivnosti figur in iskanje več rešitev hkrati. Poleg reševanja že znanih problemov pa program, ki je v odprtokodni različici dostopen na spletu in torej na voljo širši javnosti, lahko služi tudi kot pripomoček za iskanje novih zanimivih šahovskih problemov.20162016-09-19 15:30:01Diplomsko delo/naloga85644VisID: 18282sl