기하 제약을 인식하는 몬테카를로 트리 탐색(Geometry-Aware MCTS)으로 조합기하학 극값 문제의 신기록을 세운 연구다. n×n 격자에서 전역 기하 제약을 만족하는 점 배치를 찾는 문제에서, 실행 가능 행동 공간의 증분 갱신으로 제약 검사 복잡도를 O(n³)에서 O(n²)로 낮추고, 대칭성 기반 가지치기와 배치 전이로 탐색 효율을 높였다. 6개 문제 중 5개에서 기존 최고 계산 결과를 경신했으며, 대표적으로 No-Three-in-Line 문제에서 82≤n≤119 격자에 약 1.8n 크기 배치를, 최소 완전 집합 문제에서 약 0.95n 크기의 새 상한을 찾았다. 정밀 해법과 표준 강화학습이 모두 막히는 희소 보상·조합 폭발 문제에 MCTS가 실용적 대안임을 보여준다.

• •실행 가능 행동 공간의 증분 갱신으로 공선점 제약 검사 복잡도를 O(n³)→O(n²)로 감축
• •기하 대칭성을 활용한 정규형 가지치기와 대칭 배치 전이로 탐색 효율 향상
• •검토한 6개 극값 문제 중 5개에서 기존 최고 계산 결과 경신
• •No-Three-in-Line 문제에서 82≤n≤119 격자에 약 1.8n 크기 배치 발견, 최소 완전 집합은 약 0.95n의 새 상한 제시
• •희소 보상 '유효성 절벽'에 막히는 RL·트랜스포머 대비 MCTS의 실용성 입증