Naslov
Primjena šume slučajnih stabala za predviđanje ishoda šahovske partije reprezentirane kompleksnom mrežom
(Predicting the Outcome of the Chess Game Represented as Complex Network with Random Forest Classifier)

Autori
Jokić, Jovan ; Martinčić-Ipšić, Sanda

Izvornik
Zbornik Veleučilišta u Rijeci / Journal of the Polytechnic of Rijeka (1848-1299) 7 (2019), 1; 31-52

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
evaluacijska funkcija u šahu ; kompleksne mreže ; mrežne značajke ; šuma slučajnih stabala ; predviđanje ishoda šahovske igre
(chess ; position evaluation ; evaluation function ; position classification ; random forests ; machine learning ; Python ; NetworkX ; chess-py ; chess engines ; PGN)

Sažetak
This work addresses the problem of construction of 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 figures, complex relations of figures and the positions on the chess board, as well as the information on which fields are attacked, describing tactical and strategic elements of the chess game, are modeled by a complex network formalism. The goal of this work is to demonstrate that it is possible to train a classifier which has better prediction results of the game outcome, utilizing only selected measurements of the complex network’s features than corresponding Shannon's evaluation function. Shannon's evaluation function quantifies the material state of both players on the board, the mobility of the figures, king safety and pawn structure quality. The input to the classification model consists of feature vectors defined by four types of networks (support, mobility, position, tracking) constructed from static game positions. Game information is obtained from the available chess games database in a Portable Game Notation format. Features vector contains different complex network's measures that quantify the structural properties of the network. The machine-learning algorithm of random forest is used for the training of the classification model and for selecting the most important features which have the highest impact on the prediction results. Experimentally, with the custom Python script employing the chess engine Stockfish for analysis, a baseline fixed-depth evaluation of the static positions in chess games are extracted for determining the target classification classes – labels - win for white, win for black or draw. Next, selected network measurements and the corresponding class labels are forming the input features vectors. Features vectors are used to train the Random Forest classifier: the results of the trained classification model (75% correctly predicted outcomes are compared to the baseline obtained by standard Shannon's evaluation function (52% correctly classified outcomes)). 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.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo, Informacijske i komunikacijske znanosti

POVEZANOST RADA