With the increasing demand for high-performance and compact electronic devices, spatial optimization techniques for the optimal placement of components within restricted areas have become crucial. This paper proposes a Strategic Backtracking and Pruni...
With the increasing demand for high-performance and compact electronic devices, spatial optimization techniques for the optimal placement of components within restricted areas have become crucial. This paper proposes a Strategic Backtracking and Pruning algorithm based on Monte Carlo Tree Search (MCTS) to solve the component placement problem characterized by a vast search space. While conventional MCTS suffers from reduced search efficiency when encountering deadlocks, the proposed algorithm overcomes this limitation through non-sequential backtracking based on an elite candidate pool. Furthermore, an integer grid system and GPU kernel acceleration were implemented to minimize computational overhead. Experimental results demonstrate that the proposed method achieves a 95.3% placement rate within an execution time of 22.9 seconds for 100,000 iterations, proving its superior performance in both search speed and success rate compared to existing methods. Compared to the standard MCTS with large-first strategy, the proposed method reduces execution time by approximately 95% (from 759.3 seconds to 22.9 seconds) while improving the placement success rate from 71.3% to 95.3%, corresponding to an increase of 24.0 percentage points.