게임의 승리 상태와 패배 상태

조합 게임에서는 두 플레이어가 번갈아 수를 두고, 모두 최선으로 플레이하며, 둘 수 없는 플레이어가 패배합니다. 여러분의 목표는 승자를 예측하는 것뿐입니다. 🎯

게임의 각 위치를 상태라고 합니다. 해야 할 일은 모든 상태를 다음 차례인 플레이어에게 승리 상태인지 패배 상태인지로 표시하는 것입니다.

다음 차례인 플레이어가 상대방을 패배 상태로 이끄는 수를 하나 이상 둘 수 있다면 그 상태는 승리 상태입니다.

어떤 수를 두더라도 상대방에게 승리 상태를 넘겨주게 된다면 그 상태는 패배 상태입니다. 어떤 선택을 해도 벗어날 수 없습니다.

더 이상 전혀 움직일 수 없는 위치가 기저 사례입니다. 그 위치에 놓인 플레이어는 이미 패배한 것이므로 패배 상태로 표시합니다.

기저 사례에서 시작하여 바깥쪽으로 나아가세요. 새로운 상태의 라벨은 그 상태에서 가능한 수가 도달하는 상태에만 의존합니다.

이기려면 상대방의 패배 상태로 이어지는 하나의 수만 있으면 됩니다. 탈출할 방법을 하나라도 찾으면 충분합니다.

더미에서 돌을 1개 또는 2개 가져가고, 마지막 돌을 가져간 사람이 이기는 게임을 생각해 보세요. 돌 0개인 상태에서는 수를 둘 사람이 패배하므로 패배 상태입니다.

이 재귀는 가능한 모든 수를 시도하고 그 결과에 대해 재귀를 호출하여 상태를 표시합니다. ⚙️

분기마다 같은 상태가 반복되므로 각 결과를 캐시에 저장하세요. 간단한 메모만으로 지수 시간 작업을 선형 시간으로 줄일 수 있습니다.

위치가 완전히 대칭이라면 두 번째 플레이어가 수를 그대로 따라 하여 이기는 경우가 많습니다. 이 대칭 전략을 주의 깊게 살펴보세요.

여러분이 어떤 상태에 놓였다고 합시다. 그 상태가 여러분에게 패배 상태가 되는 때는 언제일까요?

이제 상태를 표시할 수 있습니다. 승리 상태에는 상대방의 패배로 이어지는 수가 하나 있고, 패배 상태에는 그런 수가 없습니다. 기저 사례에서 시작하고 메모이제이션을 사용하세요. 🧠