기존 홈즈와 왓슨의 내기의 정해를 구현한 뒤, 그 위에서 SA를 더 정교하게 돌리는 것이 기본 방향이다.
가 수십억 단위가 되면 후보 보드를 한 번 평가하는 데에도 많은 시간이 필요하다. 또한 거울 하나를 바꾸는 작은 변형만으로도 점수가 크게 떨어질 수 있어 지역 최적해에 갇히기 쉽다. 따라서 평가 비용과 탐색의 지역성을 모두 해결해야 한다.
기존 정해의 K구조를 사용하면, 가운데 영역에서 바깥으로 나간 뒤 다시 돌아오는 과정이 일정한 형태를 가진다. 이를 이용하면 모든 이동을 직접 시뮬레이션하지 않고, K구조를 탄 횟수와 K구조에서의 평균 이동 횟수, 그리고 가운데 영역에서의 이동 횟수를 조합하여 후보의 성능을 빠르게 추정할 수 있다.
지역 최적해를 벗어나는 데에는 긴 주기를 가지는 무한 루프 보드도 유용하다. 이런 보드는 일부 칸의 상태를 바꾸는 것만으로 주기를 끊어 유한한 긴 경로로 만들거나, 더 긴 주기로 변형할 수 있다. 단, 단순히 상태의 주기가 긴 것과 서로 다른 칸을 늦게까지 새로 방문하는 것은 구분해야 한다. 긴 주기 동안 같은 칸들을 반복해서 방문한다면 시작점과 도착점을 배치해도 실제 는 기대한 만큼 커지지 않을 수 있다.
따라서 긴 무한 루프 후보를 별도로 관리하고 SA의 재료로 다시 투입하면, 한 지역 최적해에서 빠져나와 새로운 상태 공간으로 이동하는 데 도움이 된다.
기존 문제는 K구조 없이도 단순 SA로 정답 수준에 도달할 수 있었지만, 규칙 없는 내부 보드를 직접 탐색하여 에 도달하는 것은 현실적으로 어렵다. Large 버전에서는 구조를 활용한 평가와 탐색 전략이 모두 중요하다.
Solution written by GPT5.6
