코딩 어드벤처: 루빅스 큐브 솔버 개선하기

안녕하세요 여러분! 저는 최근에 작은 루빅스 큐브 솔버를 만들었는데, 이 솔버는 약 8초 만에 큐브를 완성할 수 있고 평균적으로 40번의 움직임을 사용합니다. 물론 가끔 막히기도 합니다. 그래서 오늘 더 실험해보고 싶습니다. 바라건대 완벽하게 일관성 있게 그리고 훨씬 더 효율적이 되기를 바랍니다. 주로 지난 영상에서 여러분이 남겨주신 제안들을 활용할 예정이니, 좋은 아이디어들로 부탁드립니다! 한 가지 아이디어는 CFOP를 사용해서 큐브를 푸는 것이고, 이것이 어떻게 비교되는지 보는 것입니다. 이는 4단계 접근법으로, 인간 솔버들에게 인기 있는 방법이며, 모르는 분들을 위해 설명하자면 먼저 크로스(cross)를 만드는 것부터 시작합니다.

빠른 예시로 흰색 크로스를 만들고 싶다고 가정해 봅시다. 예를 들어, 흰색 중앙을 찾은 다음, 이 흰색/파란색 엣지(edge)가 이미 채워져 있는 것을 볼 수 있습니다. 그래서 여기 있는 녹색 것을 잡아서 반대편 파란색에 제자리에 놓을 수 있습니다. 그리고 이 빨간색 엣지도 밀어 넣고 나면 오렌지색만 남는데, 이것을 여기 슬롯에 넣어 크로스를 완성할 수 있습니다. 주변 중앙들과도 정렬되는 것(lines up)을 주목해 주세요. 제가 색깔들을 적절한 위치에 두는 데 주의를 기울였기 때문입니다.

좋습니다. 이 경우 우리가 신경 써야 할 큐브렛(cubelets)은 첫 번째 레이어의 엣지들로, 저희가 번호 매김 체계에서 0부터 3까지 라벨을 붙인 부분입니다. 당연히 시작할 때는 뒤죽박죽일 것이지만, 어떤 엣지들이 그 위치에 있는지 살펴보고 정확한 것들에 점수를 부여할 수 있습니다. 그래서 저는 코드에 이 부분을 구현했습니다. 큐브 상태의 처음 4개 엣지에 대한 작은 루프를 돌면서 각각이 우리가 기대하는 값인지 테스트하고, 그렇다면 점수를 올리는 방식입니다.

각각에 100점을 부여하고 있습니다. 왜냐하면 우리는 또한 사용된 모든 움직임에 대해 점수를 공제하여 더 짧은 솔루션을 장려하고 싶기 때문입니다. 하지만 물론 진전하는 것이 가장 중요합니다. 저는 지난번과 동일한 검색 코드를 이것에도 사용하고 있는데, 이는 처음에는 6수 앞을 내다보며 시작하고, 진행할 방법을 찾지 못하면 7수로 늘리고, 마지막으로 8수까지 늘린 다음 포기합니다. 더 깊이 탐색하는 것은 몇 분 또는 몇 시간이 걸리기 시작하여 기다리기에 재미가 없습니다.

좋습니다. 빠르게 큐브를 섞어보겠습니다... 그리고 어떻게 되는지 봅시다. 저에게는 크로스(cross)처럼 보이네요. 따라서 CFOP의 첫 번째 단계가 완료되었습니다. 다음은 두 번째 레이어(First 2 Layers)입니다. 이것은 단순히 여기와 저기, 그리고 크로스를 따라 올바른 코너 및 엣지 큐브렛을 채우는 것을 의미합니다. 예를 들어, 위쪽에 있는 이 흰색/파란색/빨간색 코너와 그 옆에 속하는 파란색/빨간색 엣지를 볼 수 있으니, 이것들을 이렇게 한 쌍으로 만들고 제자리에 끼울 수 있습니다.

이것을 익히는 데 약간의 연습이 필요하지만, 일단 익숙해지면 기분 좋게 직관적인 과정입니다. 그래서 저는 여기 파란색과 주황색을 끼웠습니다. 다음은 녹색과 주황색을 할 것입니다. 그리고 마지막으로 빨간색과 녹색으로 첫 두 레이어를 완성합니다. 만약 이것을 배우고 싶다면, 훌륭한 커빙 채널(cubing channels)이 많이 있습니다. 특히 JPerm을 보면서 많은 것을 배웠습니다. 하지만 이 지식을 저희 프로그램에 전달하기 위해, 저는 이 단계에 대한 새로운 점수 값을 만들 수 있는데, 이는 크로스보다 낮게 설정하여 진행 상황을 방해하지 않도록 했습니다.

그러면 그 새로운 점수는 두 번째 레이어에서 올바르게 배치된 모든 엣지(edge)나 첫 번째 레이어의 코너(corner)에 대해 부여됩니다. 그래서 제가 무작위로 섞인 큐브를 준비해 봤고, 이제 솔버를 돌려보겠습니다. 오, 잘 작동하네요! 다른 것도 시도해 보고 싶지만, 이번에는 크로스를 바닥에 두고 살펴보겠습니다. 왜냐하면 손으로 풀 때 보통 그렇게 보게 되거든요. 그럼 무작위로 섞어보겠습니다... 그리고 모든 것이 어떻게 조합되는지 볼 수 있도록 X-ray 비전(x-ray vision)도 작동시켜 보겠습니다. 아니면 안 될 수도 있고요.

상황에 따라 다르지만, 우리는 이 두 번째 레이어의 엣지는 해결했지만 그 아래 코너는 뒤틀려 있습니다. 그리고 여기 다른 쪽 끝에서도 실제로 같은 일이 일어났습니다. 이 경우를 자세히 살펴보니... 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11번의 움직임이 필요할 것 같습니다. 하지만 우리의 검색은 깊이(depth) 8까지만 되어 있어서 막힌 것입니다. 하지만 그것이 볼 수 있어야 하는 것은, 만약 코너를 고치는 데만 집중한다면 그게는 대신 1, 2, 3, 4, 5, 6, 7번의 움직임으로 할 수 있다는 것입니다.

하지만 그렇게 할 인센티브가 없습니다. 왜냐하면 올바른 코너나 올바른 엣지에 대한 점수가 동일하기 때문에, 우리는 방금 하나를 다른 것으로 교환했기 때문입니다. 그래서 제가 그것을 빠르게 수정했습니다. 이 단계의 점수를 코너에 대해서는 더 높은 값으로, 엣지에는 더 낮은 값으로 분리하여 사용하고 여기에서 적용해 보겠습니다. 좋습니다. 아까 막혔던 것과 같은 무작위로 섞인 것을 돌려보고 이제 더 똑똑해졌는지 확인해 봅시다. 와, 이게 효과가 있는 것 같습니다!

좀 더 돌려봤더니, 방금 고친 것의 정반대 상황에 빠지곤 했습니다. 즉, 코너는 제자리에 있지만 그 위의 엣지(edge)가 뒤집힌 경우입니다. 그래서 코드에 이 엣지 케이스에 대한 명시적인 페널티를 추가했습니다. 단순히 위치만 정확하게 감지하고 방향은 잘못된 상태, 즉 두 번째 레이어에서 이를 감지하면, 해당 엣지를 두 번째 레이어 밖으로 이동시키도록 하여 다시 올바르게 삽입할 수 있는 충분한 시야를 확보하도록 하는 것입니다.

아니면 더 자주 그랬던 것 같습니다. 이제는 애초에 그런 상황에 놓이는 것을 피합니다. 좋습니다. 이것을 천 번 실행해 봤는데, 이제는 완벽하게 일관성이 있으며 이 첫 두 단계에서는 평균적으로 약 28번의 움직임이 필요합니다. 인간 속도 커브어(speed-cubers)의 경우 보통 35~40회 정도가 일반적이라고 생각하지만, 물론 그들은 몇 번의 움직임을 줄이는 것보다는 손가락으로 얼마나 빠르게 할 수 있는지를 더 신경 씁니다. 어쨌든, 이것이 우리를 세 번째 단계, 즉 마지막 레이어의 방향 맞추기(Orientation of the last layer)로 이끌게 됩니다.

즉, 모든 큐브렛(cubelets)을 돌려서 노란색이 위를 향하도록 만드는 것입니다. 제가 배운 방식은 엣지들을 방향 맞추는 하나의 움직임 시퀀스(sequence of moves)가 필요하고, 그 후 코너들이 어떻게 놓이는지에 따라 그것들을 수정하기 위한 또 다른 시퀀스를 암기하는 것을 포함합니다. 저는 프로그램에게도 엣지를 우선순위로 두는 것이 좋을 것 같다고 생각합니다. 왜냐하면 그렇게 하면 처음부터 전체 솔루션을 볼 수 없을 때를 대비하여 일종의 '중간 목표'가 생기기 때문입니다.

또 다른 접근 방식은 사람들이 이 단계에 대해 알아낸 57가지의 다양한 경우를 단순히 플러그앤플레이(plug & play)하는 것일 수 있습니다. 하지만 프로그램이 스스로 방법을 찾도록 하는 것이 더 재미있다고 생각합니다. 다만, 코드에서 복잡해질 위험이 있어 코너용 루프와 엣지용 루프로 분리했습니다. 먼저 엣지를 살펴보니 약간 리팩토링(refactored)했지만, 새로 추가된 것은 마지막 레이어에서 엣지가 올바르게 방향을 갖도록 보상하는 이 한 줄뿐입니다.

그리고 코너도 마찬가지지만, 방금 논의했듯이 코너는 더 낮은 점수를 받습니다. 첫 두 개의 레이어가 이미 해결된 위치부터 테스트해 보겠습니다. 오… 십자가 모양이 만들어졌다가 막혔습니다. 아마 약간의 추가적인 안내가 필요할 것 같습니다. 저는 십자가 모양을 유지하면서 코너들의 다양한 구성을 순환시키는 짧은 이동 시퀀스(sequence of moves)를 알고 있습니다.

적절한 위치에 적용하면 단 하나의 코너만 올바르게 방향을 갖도록 바로 만들 수 있습니다. 그리고 거기서 다시 적용하면 나머지 코너들도 방향을 맞출 수 있습니다. 따라서, 코너가 하나만 방향이 맞는 것이 두 개일 때보다 실제로 더 좋습니다. 이 점을 염두에 두고 평가를 약간 수정하여, 방향이 맞춰진 코너의 수를 세고 오직 하나 또는 네 개 모두가 정확할 때만 점수를 부여하도록 했습니다. 전에 막혔던 것과 같은 시작 위치로 테스트해 보겠습니다…

그리고 이전에 막혔던 정확한 지점을 무시한 것 같습니다. 그래서 그 까다로운 설정으로 다시 불러와서, 거기부터 진행하도록 강제해 보겠습니다. 실제로 우리가 살펴봤던 동작을 수행합니다 — 먼저 단일 방향의 코너 케이스로 이동하고요. 그리고 거기에서 나머지 부분을 방향 맞추기(orienting)를 합니다. 비록 마지막 단계에 대해서는 다른 접근 방식을 찾았지만요. 좋습니다 — 이제 CFOP의 최종 단계, 즉 마지막 레이어의 순열(Permutation)에 도착했습니다.

이것은 코블렛(cubulets)들을 방향을 망가뜨리지 않고 올바른 위치로 옮기는 것을 의미합니다. 그리고 저는 여기서 두 단계 방법(two-step method)을 배웠습니다. 먼저 코너를 수정하고, 다음으로 엣지(edges)를 수정하는 방식입니다. 하지만 이 단계에서는 나머지 부분을 기본적으로 무작위 탐색(brute force)할 수 있을 만큼 충분히 가까워졌다고 생각합니다. 왜냐하면 모든 것이 세 번째 단계 이후에 방향이 맞춰지기 때문에, 지난번처럼 검색 속도를 높이기 위해 일부 동작을 생략할 수 있다는 의미입니다. 물론 더 깊은 검색도 가능하게 만듭니다. 또한 지난번의 역방향 검색(backwards-search) 조회 기법도 사용할 수 있습니다.

좋습니다, 여기 섞인 큐브가 하나 있는데, 우리의 cfop 솔버가 이것을 풀 수 있는지 봅시다. 크로스(cross)를 수행하면서 동시에 처음 두 레이어에 대한 설정을 합니다 — 적어도 제 눈에는 다소 혼란스러운 방식으로 진행됩니다. 하지만 이제 마지막 레이어의 방향 맞추기 차례입니다. 그리고 마침내 순열까지요. 좋습니다, 이 해결은 성공적이었습니다! 하지만 평소처럼 일관성을 테스트하기 위해 천 번 실행해 보겠습니다. 결과가 나왔습니다 — 100%의 성공률을 달성했습니다. 이는 매우 좋으며, 평균 계산 시간은 5분 반, 동작 수는 56회입니다.

움직임 횟수 분포는 이렇습니다만—참고로 말씀드리자면—드물게는 30대 중반에서, 또 다른 드문 경우에는 해결하는 데 최대 80번의 움직임이 걸리기도 했습니다. 하지만 대부분은 50대 후반 정도였습니다. 그리고 여기서는 움직임 횟수와 계산 시간 모두에 대해 가장 짧고, 가장 길고, 평균적인 풀이 값을 보여주는 간단한 개요도 만들었습니다. 지난번 솔버와 비교해 보면—그것은 명백히 신뢰도가 떨어졌지만, 움직임 측면에서는 훨씬 효율적이어서 평균적으로는 40회 정도였습니다.

CFOP 스타일을 시도해보니 정말 재미있었지만, 이제는 훨씬 더 최적화된 솔버를 만드는 임무에 착수하고 싶습니다. 계속해서 언급되는 용어 중 하나가 '도미노 축소(Domino Reduction)'입니다. 지난번에는 이 개념을 어렴풋이 이해하려고 애썼는데, 몇몇 댓글 작성자들이 제가 이해할 수 있도록 말로 설명해 주었습니다. 이것은 실제로 우리가 전에 멈췄던 부분에 잘 연결됩니다—빠른 복습으로, 여기 있는 흰색과 녹색 같은 모서리(edge)를 위쪽을 향하도록 재배치하고 싶다고 가정해 봅시다.

이를 위해... 앞면 면(front face)을 비틀고, 그리고 오른쪽 면(right face)을 비틀하면 임무가 완료됩니다. 하지만 이제 더 이상 돌아가는 것을 금지할 두 개의 면 쌍—왼쪽과 오른쪽이거나, 아니면 앞면과 뒷면—을 선택한다고 가정해 봅시다. 저는 지난번처럼 앞면과 뒷면으로 하겠습니다. 이렇게 하면 이 모서리를 시작했을 때의 상태로 되돌리는 것이 불가능해집니다. 만약 제가 억지로 해보려고 한다고 해도—음, 여기다 놓아보고, 그리고 이걸 위로 비틀어보면…