더 나은 역 추적 시스템 찾기

Question

나는 이것을 간단한 설명으로 설명하려고합니다. 코드를 게시하는 것보다 더 짧을 것이기 때문입니다. 나는 올바른 "이동 명령"을 선택하여 게임을 완료해야하는 재귀 적 솔루션의 일부를 만들었으며, 그것이 처참한 상황에 빠지면 되돌아 가야합니다. 나의 현재 시스템은 작동하지 않은 이동에 식별자를 설정하여 새로운 경로/이동 명령이 발견 될 때까지 역 추적 중에 다시 사용할 수 없도록합니다.

그러나 문제가 발생했습니다. 게임은 두 가지 움직임 만 남았고 둘 중 어느 것도 게임을 풀 수없는 상태에 도달 할 수 있습니다. 나의 현재 시스템은 기본적으로이 두 가지 움직임이 서로를 끊임없이 바꿔 놓을 것입니다. 왜냐하면 그 해결책은 움직이려고 시도하고, 그것이 작동하지 않는 것을보고, 다음 시도를 시도하기 때문입니다. 내 문제는 내가 이동을 할 때마다 이동을 사용하지 않도록 솔루션을 알려주는 내 식별자를 재설정한다는 것이지만, 어떻게 설정해야할지 모르겠다 고 생각합니다.

추가 정보가 필요하거나 통찰력이 있으면 알려주십시오. 감사!

Answer 1

설명하는 게임의 성격에 대해 확신이 없으며 따라야 할 더 좋은 방법을 결정하는 데 도움이되는 몇 가지 정보가 있습니다. 나는 새로운 움직임이 발견 된 후에이 색인이 다시 설정된다고 말하는 주제에 대한 귀하의 의견을 보았습니다. 이것은 아주 좋은 것으로 들리지 않습니다. 나는 당신이 당신의 예제에서 보았 듯이 실패 할 경우가 있고 조건 적으로 만 작동하는 알고리즘을 가질 수 없기 때문에 이것을 고쳐야한다고 믿습니다.

당신이 묘사하는 문제는 게임 트리처럼 들립니다. 옳은? 그렇다면 문제에 대한 설명을 게임 트리로 변경하고 Alpha-Beta Pruning과 같은 증명 된 게임 트리 검색 알고리즘 중 하나를 사용하여 게임이 적대적이라고 가정합니다.