Data mining for chess

Cilj ovog diplomskog rada je izgraditi model evaluacije šahovskih pozicija koji upošljava isključivo informacije esktrahirane iz mrežnih značajki pozicija šahovskih figura na ploči. Međusobni odnosi figura na šahovskoj ploči, kao i odnosi figura i polja koja okupiraju, koji opisuju određene taktičke i strateške elemente koje tipično nalazimo u tijeku šahovske partije, će se modelirati kompleksnom mrežom. Ideja je pokazati da koristeći samo određene mjere koje opisuju strukturu kompleksne mreže, u kojoj su prikazane sve pozicije u igri, možemo naučiti klasifikator pozicija koji može bolje predvidjeti krajnji ishod partije od klasične Shannonove evaluacijske funkcije. Shannonova evaluacijska funkcija kvantificira materijalno stanje na ploči obje strane, mobilnost figura, sigurnost kralja, te kvalitetu pješačke strukture. Klasifikator kao ulaz ima vektore značajki određene iz 4 tipa mreža (mreža podrške, mreža mobilnosti, pozicijska mreža, mreža praćenja) konstruiranih iz baze majstorskih partija, od kojih svaka modelira određeni aspekt igre. Vektor značajki sadrži značajke dobivene različitim mjerama strukture mreže. Postupci strojnog učenja se primjenjuju za određivanje značajki koje imaju najveću prediktivnu moć po pitanju krajnjeg ishoda partije. Za testiranje mogućih značajki koriste se slučajna stabla. Također, eksperimentalno se, pomoću Python skripte, određuju osnovne evaluacije statičkih pozicija u šahovskim partijama pomoću Stockfish šahovskog programa. Nakon toga se značajke od interesa, te pripadne evaluacijske ciljne klase (pobjeda bijelog ili crnog igrača ili remi), udružuju u ulazne vektore za finalni klasifikator pozicija čiji rezultati se uspoređuju sa Shannonovom evaluacijskom funkcijom. Pokazano je kako ovakva evaluacijska metoda daje bolje rezultate (75% točnost) od klasične Shannon evaluacijske funkcije (52% točnost) za testnu bazu partija, s naknadnom interpretacijom i diskusijom dobivenih rezultata. Za potrebe parsiranja PGN (engl. „Portable Game Notation”) formata, reprezentacije statičkih pozicija u šahu, te kreiranja mreža/ grafova koji sadrže notirane poteze u tijeku šahovske partije iz baze majstorskih partija se koristi odgovarajući Python program i moduli poput NetworkX i chess-py.The purpose of this master's thesis is to build a static chess position evaluation model which utilizes only information extracted from complex networks' features of positions of chess pieces on the board. The mutual relations of chess pieces, as well as complex relations of pieces and their occupied and attacked squares, which describe certain tactical and strategic elemens of the chess game, are modeled by a complex network. The main idea of this is to demonstrate that it is possible to train a classifier which has a better prediction of the final game result, utilizing only a few network features which describe a complex network representing all game positions, than Shannon's evaluation function. Shannon's evaluation function quantifies material state of both players on the board, mobility of the pieces, king safety and pawn structure quality . Classification input consists of feature vectors defined by 4 network types („support”, „mobility”, „position”, „tracking”) constructed from static game positions from the games database, each of which models a different aspect of the game. Feature vector contains different complex network's computed features. Machine-learning techniques and algorithms are used in order to decide upon the features which have the greatest game evaluation predictive power and are, thus, included in the final classificator. Random forests are used for discovery and testing of such features. Experimentally, with the custom Python script employing the chess engine Stockfish for analysis, a baseline fixed-depth evaluation of the static positions in analyzed games is generated. as the target classification class (win for white, win for black or draw). Then, selected network features of choice and the related evaluation class variable are combined together as input vectors which are fed as input to the final position classifier and its' results are compared to the classic Shannon's evaluation function (52% precision). This evaluation method's results (75% precision) proved to be better than the classic Shannon's evaluation function for the test game database, the result which is afterwards interpreted and discussed. PGN database („Portable Game Notation”) reading and parsing of games from the games database, representation of static positions from the games, and generation of networks/graphs is done with suitable Python tools, namely chess library „chess-py” and „NetworkX” Python module