Abstract: The game search tree model usually does not consider the state information of similar nodes, which results in searching a huge state space, and there are problems such as the size of the game tree and the long solution time. In view of this, the article proposes a scheme using the idea of combinatorial optimization algorithm, which has an important application in solving the decision problem in the tree graph model. First, the special graph-theoretic structure of the point-grid game is analyzed, and the storage and search of states are optimized by designing hash functions; then, the branch delimitation algorithm is used to search the state space, and the evaluation value of repeated nodes is calculated by dynamic programming; finally, the state space is greatly reduced by combining the two-way detection search strategy. The results show that the algorithm improves decision-making efficiency and has achieved 37% and 42% final winning rate, respectively. The design provides new ideas for computational complexity problems in the field of game search and also proposes new solutions for the field of combinatorial optimization.

Yun Liu, Jiajun Li and Jingjing Chen, “Combinatorial Optimization Design of Search Tree Model Based on Hash Storage” International Journal of Advanced Computer Science and Applications(IJACSA), 14(5), 2023. http://dx.doi.org/10.14569/IJACSA.2023.0140574

@article{Liu2023,
title = {Combinatorial Optimization Design of Search Tree Model Based on Hash Storage},
journal = {International Journal of Advanced Computer Science and Applications},
doi = {10.14569/IJACSA.2023.0140574},
url = {http://dx.doi.org/10.14569/IJACSA.2023.0140574},
year = {2023},
publisher = {The Science and Information Organization},
volume = {14},
number = {5},
author = {Yun Liu and Jiajun Li and Jingjing Chen}
}