Chess Engine Algorithm in C#

U ovom radu opisani su teorijski principi šaha te je implementiran program koji na temelju aktualne situacije na šahovskoj ploči određuje najbolji potez. Heuristika programa temeljena je na pretpostavci da je svakoj situaciji na ploči moguće odrediti brojčanu vrijednost koja predstavlja kvalitetu poteza za igrača na redu. Tu vrijednost određuje statička funkcija evaluacije koja uzima u obzir broj, poziciju i mobilnost svih figura na ploči. Funkcija pretrage temeljena na minimax algoritmu stvara stablo svih okolnosti koje su moguće na ploči do određene dubine. Zbog eksponencijalne vremenske složenosti nužna je optimizacija pretrage. Objašnjene su implementacije α – β rezanja, sortiranja poteza i transpozicijske tablice koji značajno skraćuju vrijeme izvođenja programa. Testirane su performanse programa te su objašnjeni prisutni nedostaci u programu. Za jednostavnije korištenje programa implementirana je Windows Forms aplikacija s grafičkim korisničkim sučeljem.This paper describes theoretical principles of chess and implements a program which generates the best move based on the current chess board situation. The heuristics of the program are based on the assumption that it is possible to determine a numerical value for each situation on the board, which represents the quality of a situation for the player on the move. That value is determined by the static evaluation function which takes into account the number, position and mobility of all the figures on the board. The search function based on the minimax algorithm creates a tree of all the circumstances that are possible on the board to a certain depth. Due to the exponential time complexity, search engine optimization is necessary. Implementations of α – β pruning, move ordering and transposition table which significantly reduce the program execution time are explained in the paper. The performance of the program is tested and its shortcomings are explained. For easier use of the program, a Windows Forms application with a graphical user interface has been implemented