Title Primjena strojnog učenja u šahu
Title (english) Data mining for chess
Author Jovan Jokić
Mentor Sanda Martinčić-Ipšić (mentor)
Committee member Marina Ivašić-Kos (predsjednik povjerenstva)
Committee member Sanda Martinčić-Ipšić (član povjerenstva)
Committee member Ivo Ipšić (član povjerenstva)
Granter University of Rijeka (Faculty of Informatics and Digital Technologies) Rijeka
Defense date and country 2018-06-21, Croatia
Scientific / art field, discipline and subdiscipline SOCIAL SCIENCES Information and Communication Sciences
Abstract 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.
Abstract (english) 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.
Keywords
šah
evaluacija pozicija
evaluacijska funkcija
kompleksne mreže
mrežne značajke
klasifikacija pozicija
slučajna stabla
strojno učenje
Python
NetworkX
chess-py
šahovski motori
PGN
Keywords (english)
chess
position evaluation
evaluation function
position classification
random forests
machine learning
Python
NetworkX
chess-py
chess engines
PGN
Language croatian
URN:NBN urn:nbn:hr:195:934683
Study programme Title: Informatics Study programme type: university Study level: graduate Academic / professional title: magistar/magistra informatike (magistar/magistra informatike)
Type of resource Text
File origin Born digital
Access conditions Access restricted to students and staff of home institution
Terms of use
Created on 2018-07-02 11:15:43