论文标题
使用单数值分解的TIC-TAC评估功能的信息压缩和性能评估
Information Compression and Performance Evaluation of Tic-Tac-Toe's Evaluation Function Using Singular Value Decomposition
论文作者
论文摘要
我们通过单数值分解（SVD）近似游戏TIC-TAC-TAC的评估函数，并研究了近似准确性对获胜率的影响。我们首先准备了TIC-TAC-TOE的完美评估功能，并通过将评估函数视为第九阶张量来进行低级近似。我们发现，我们可以将评估功能的信息量减少70％，而不会显着降低性能。近似准确性和获胜率密切相关，但不完全成比例。我们还研究了评估功能的分解方法如何影响性能。我们考虑了两种分解方法：关于评估函数的简单SVD作为矩阵和高阶SVD（HOSVD）的Tucker分解。在相同的压缩比下，通过HOSVD获得的近似评估函数的策略表现出明显高于SVD获得的策略。这些结果表明，SVD可以有效地压缩棋盘游戏策略，以及取决于游戏的最佳压缩方法。
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.
