Sokoban 게임 : 자동으로 상자 이동

Question

키퍼가 폭 넓은 첫 번째 검색 알고리즘을 사용하여 자동으로 이동할 때 나는 이미 기능을 구현했습니다. 이제는 상자를 자동으로 이동하려고합니다 (골키퍼가 다른 상자를 이동하지 않고 원본에서 대상으로 상자를 이동할 수있는 경우). 어떻게해야합니까? BFS를 수정하려고했지만 아직 성공하지 못했습니다.

업데이트 : 나는 퍼즐을 풀 필요가 없습니다. 대신 사용자가 마우스로 상자를 이동할 수있는 편리한 사용자 인터페이스를 개발하고 싶습니다. 이를 위해서는 이동 시퀀스를 계산할 수있는 알 고가 필요합니다. 그러나 단 하나의 상자를 움직이는 것과 다른 상자를 움직여서는 안됩니다. Wikipedia - Sokoban에서

Answer 1

이전과 같이 너비 우선 검색을 사용하거나 원하는 경우 A *를 사용하지만 적절한 상태 집합을 검색하십시오.

키퍼 경로를 검색 할 때 상태는 눈금의 사각형에 해당합니다. 그러나 골키퍼가 블록을 이동하는 방법을 검색 할 때 상태는 그리드의 쌍의 (골키퍼의 경우 하나, 블록의 경우 하나)에 해당합니다.

가장 작고 간단한 예입니다. 다음과 같이 우리가 표시된 사각형과 창고지기 수준이 가정 :

그리드가 골키퍼와 한 블록이 포함되어 있습니다.상태 공간은 키퍼와 블록이 차지하는 사각형 쌍으로 구성됩니다. 아래 그림에는 작은 원으로 그려진 56 개의 상태가 있습니다.

줄은 상태 공간 내의 가능한 전이를 나타낸다. 얇은 선은 키퍼의 움직임에 해당합니다 (양방향입니다). 굵은 선은 블록을 밀기위한 것입니다 (따라서 한 방향으로 만 이동). 상태 공간을 검색해야합니다. 그 따라

참고 : 블록 7에서 시작하여 8에서 키퍼 경우

는 예를 들어, 골키퍼가 상태 공간에서 레드 경로를 따라 8로 블록을 밀 수 이 경로는 블록 7-6-5-6-7-8을 통과합니다. 블록이 위치 6과 7을 두 번 통과하기 때문에 블록의 위치 만 고려하면이 경로를 찾을 수 없습니다.

Answer 2

:

창고지기가 계산 복잡도 이론을 사용하여 공부하실 수 있습니다. Sokoban 퍼즐을 푸는 문제는 NP-hard로 증명되었습니다. 3 Sokoban 해결은 창고에서 상자를 움직이는 로봇 로봇을 설계하는 것과 비교할 수 있기 때문에 이는 인공 지능 연구원에게도 흥미 롭습니다. 더 많은 연구 결과에 의하면 Sokoban 문제를 푸는 도 PSPACE-complete라고 나와 있습니다. [4]

Sokoban은 분기점 (체스와 비교할 때 )뿐 아니라 막대한 검색 트리 깊이로 인해 어려울뿐만 아니라, 일부 레벨에는 1000 회 이상의 "푸시"가 필요합니다. 숙련 된 인간 플레이어는 대부분 경험적으로 에 의존합니다. 그들은 일반적으로 쓸데없는 또는 여분의 재생 라인을 빠르게 버리고 패턴과 하위 목표를 인식 할 수 있습니다. 은 검색 량을 대폭 줄입니다.

일부 창고지기 퍼즐

은 도메인 특정 기술을 사용하는 여러 기술들에 의해 강화 이러한 IDA *로서 단일 에이전트 서치 알고리즘을 이용하여 자동적으로 해소 할 수있다. [5] 알버타 GAMES 그룹의 University에서 개발 한 Sokoban 해결사 인 Rolling Stone에서 사용하는 메서드입니다. 그러나 더 복잡한 Sokoban 레벨 은 최상의 자동화 된 솔버에도 도달 할 수 없습니다.

알고 싶습니까?

덧붙여 말하자면 Sokoban 퍼즐을 확실하게 최적의 방법으로 해결하는 것은 NP-hard입니다. 즉, 수행 방법을 알아 내면 $1,000,000 prize을 기다리고 있습니다.