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.
翻译:我们用单值分解(SVD)来比较Tic-Tac-Toe游戏的评价职能,并调查了近似精度对中标率的影响。我们首先准备了Tic-Tac-Toe的完美评价功能,并将评价功能视为第九阶梯,从而进行了低级近似。我们发现,我们可以将评价功能的信息量减少70%,而不会显著降低性能。适应精确度和得分率密切相关,但并不完全相称。我们还调查了评价职能分解方法如何影响业绩。我们考虑了两种分解方法:将评价功能作为矩阵的简单SVD和由高阶SVD(HOSVD)进行的塔克分解。同样的压缩率,与HOSVD获得的近似评价功能相比,战略的得分率大大高于SVD。这些结果表明,SVD可以有效地压缩游戏策略和取决于游戏的最佳压缩方法。