Combinatorial Optimization Design of Search Tree Model Based on Hash Storage

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.

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