본 논문은 그래프 알고리즘에서 가장 많이 연구된 문제 중 하나인 그래프 컬러링 문제에 대한 효율적인 몬테카를로 탐색 기법을 제시하고 기존 기법들과 비교 분석합니다. 정확한 방법들은 수백 개가 넘는 정점을 가진 인스턴스를 해결하는 데 실패하기 때문에 많은 휴리스틱 기법들이 제안되어 왔습니다. 본 논문에서는 싱글 플레이어 게임을 위한 몬테카를로 탐색 알고리즘인 Nested Monte Carlo Search (NMCS)와 Nested Rollout Policy Adaptation (NRPA)를 그래프 컬러링 문제에 적용하는 방법을 제시하고, 기존 기법들과의 성능을 비교합니다. 몬테카를로 탐색 알고리즘을 조합 그래프 문제에 적용한 연구는 놀랍게도 거의 없었습니다.
