Information Compression and Performance Evaluation of Tic-Tac-Toe's Evaluation Function Using Singular Value Decomposition
We approximated the evaluation function for the game Tic-Tac-Toe by singular
value decomposition (SVD) and investigated the effect of approximation accuracy
on winning rate. We first prepared the perfect evaluation function of
Tic-Tac-Toe and performed low-rank approximation by considering the evaluation
function as a ninth-order tensor. We found that we can reduce the amount of
information of the evaluation function by 70% without significantly degrading
the performance. Approximation accuracy and winning rate were strongly
correlated but not perfectly proportional. We also investigated how the
decomposition method of the evaluation function affects the performance. We
considered two decomposition methods: simple SVD regarding the evaluation
function as a matrix and the Tucker decomposition by higher-order SVD (HOSVD).
At the same compression ratio, the strategy with the approximated evaluation
function obtained by HOSVD exhibited a significantly higher winning rate than
that obtained by SVD. These results suggest that SVD can effectively compress
board game strategies and an optimal compression method that depends on the
game exists.