Automatic discovery of interesting chess compositions

Cilj 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.The aim of the thesis was to develop a computer program to help creating and dealing with interesting chess problems. Chess problem, also called a chess composition, is a puzzle on a chessboard, which represents a task to be solved. Task usually requires moving the chess pieces on the chessboard using classic chess rules and is not necessarily related to checkmating the opponent. We know several types of chess problems: directmates, helpmates, selfmates, serialmovers, chess studies, retrograde analysis etc. We can set additional requirements to a player, for instance prescribed last move of the figure to checkmate the opponent. Special type of chess problems are construction tasks, that may be without diagram and typically contain just a task such as ``set a certain position`` or ``construct a game with certain properties``. For example, an interesting construction task would be to construct the shortest game of chess ending with checkmating opponent with a pawn, which was just promoted to a knight. Such problems may be of an interest not only for chess players, but also for the general public, as they require only knowledge of basic chess rules. Chess is a very demanding game in terms of complexity, which means that many different options are available for every chess piece movement. Consequently, in successive moves number of possible combinations can be enormous. For illustration: from starting chess position we can finish a four-move game (four moves by each player) in almost 85 billion different combinations. This combinatorial explosion is the major reason that chess problems and especially construction tasks can be extremely difficult - not only for humans but also for modern computers. We can easily verify with computer that brute force search will not bring results. Smarter approach respectively the introduction of artificial intelligence algorithms is needed. Within the thesis we have developed a computer program by which a computer can overcome this combinatorial complexity and can be used to solve a variety of unusual chess problems, particularly construction tasks. The program is based on the use of heuristic search and advanced heuristics, whose task is to guide the search towards a given goal. We used additional mechanisms, such as hash tables, possibility to deactivate chess pieces and search for several solutions at the same time, to cope with the combinatorial explosion. In addition to solving of already known problems, the program, which is available online in the open source version and therefore to the general public, can also serve as a tool to discover new interesting chess compositions