소코반

Sokoban
소코반 퍼즐이 풀리고 있습니다.

소코반(倉庫番, 소코반, '창고지기')은 플레이어가 창고에 있는 상자들을 밀어서 보관 장소로 이동시키는 퍼즐 비디오 게임입니다. 이 게임은 1981년 이마바야시 히로유키에 의해 디자인되었으며 1982년 12월에 처음 출시되었습니다.

게임플레이

창고는 바닥 섹션 또는 벽 섹션을 나타내는 정사각형 격자로 묘사됩니다. 일부 바닥 사각형에는 상자가 들어 있고 일부는 보관 장소로 표시되어 있습니다. 종종 작업자 캐릭터로 표현되는 플레이어는 한 번에 하나의 정사각형을 빈 바닥 정사각형에 수평 또는 수직으로 이동할 수 있지만 벽이나 상자를 통과할 수는 없습니다.

상자를 옮기기 위해 플레이어는 상자로 걸어가서 상자를 너머 광장으로 밀어냅니다. 상자는 벽이 있는 사각형이나 다른 상자로 밀 수 없으며 끌 수 없습니다. 상자의 수는 저장 위치의 수와 같습니다. 모든 상자가 보관 장소에 있을 때 퍼즐이 해결됩니다.

과제 및 전략

게임을 진행하려면 종종 세심한 계획과 전략적인 조작이 필요합니다. 상자를 구석으로 밀어 넣거나 다른 사람을 차단하는 것과 같은 한 번의 실수로 해결할 수 없는 시나리오가 생성되어 플레이어가 퍼즐을 역추적하거나 다시 시작해야 할 수 있습니다. 이러한 데드락을 방지하려면 각 푸시의 결과를 예측하고 퍼즐의 전체 레이아웃을 고려하는 것이 중요합니다.

선택한 공식 릴리스

연도 제목 나라 플랫폼 출판인 미디어 메모들
1982 소코반 (倉庫番) 일본 NEC PC-8801 생각하는 토끼 카세트테이프
1983 소코반 [엑스트라 에디션] (倉庫番[番外編][2][3]) 일본 NEC PC-8801 PCマガジン 입력 프로그램
1984 소코반2 (倉庫番2) 일본 NEC PC-8801 생각하는 토끼 카세트테이프
1986 나미다노소코반 스페셜 (涙の倉庫番スペシャル) 일본 패미컴 디스크 시스템 ASCII 주식회사 플로피
1988 소코반 미국 IBM PC, XTAT 스펙트럼 홀로바이트 플로피
1989 소코반 퍼펙트 (倉庫番 완벽) 일본 NEC PC-9801 생각하는 토끼 플로피
1990 박시보이 일본, 미국 터보그라프x-16/PC 엔진 선관위 후카드
1990 밀어!창고 게임 일본, 미국 세가 제네시스/메가 드라이브 마사야 게임스 ROM 카트리지
1991 소코반 리벤지 (倉庫番복수) 일본 NEC PC-9801 생각하는 토끼 플로피
2016 소코반 터치 (倉庫番 터치) 일본, 미국 안드로이드애플 iOS 생각하는 토끼 디지털 유통
2019 민나노소코반 (みんなの倉庫番) 일본 닌텐도 스위치와 플레이스테이션 4 언밸런스 주식회사 디지털 유통
2021 소코반 미국 닌텐도 스위치와 플레이스테이션 4 언밸런스 주식회사 디지털 유통

발전

소코반은 1981년 이마바야시 히로유키에 의해 만들어졌습니다.[4][5] 최초의 상업용 게임은 1982년 12월 일본 다카라즈카에 본사를 둔 소프트웨어 회사Thinking Rabbit에 의해 출판되었습니다. 소코반은 미국에서 발매되기 전에 40만 부 이상 팔린 일본에서 히트를 쳤습니다.[6] 1988년에 SokobanSpectrum HoloByte에 의해 IBM PC, Commodore 64, Apple II용으로 Soko-Ban으로 미국에서 출판되었습니다.[7]

구현

Sokoban의 구현은 거의 모든 가정용 컴퓨터개인용 컴퓨터 시스템을 포함한 수많은 컴퓨터 플랫폼을 위해 작성되었습니다. 비디오 게임 콘솔, 휴대폰, 그래프 계산기, 디지털 카메라[8]전자 정리기에도 다양한 버전이 존재합니다.

과학연구

소코반계산 복잡도 이론을 사용하여 연구할 수 있습니다. 소코반 퍼즐을 푸는 문제는 NP-hard로 처음 증명되었습니다.[9][10] 추가 작업을 통해 NP 문제보다 훨씬 더 어려웠습니다. PSPACE-완전입니다.[11] 이는 소코반을 해결하는 것이 일부 자율 로봇에서 필요로 하는 자동화된 계획과 비교될 수 있기 때문에 인공지능(AI) 연구에 관심이 있습니다.[12]

소코반분기인자가 클 뿐만 아니라 검색 나무 깊이가 커서 어렵습니다. 일부 레벨 유형은 무한 확장될 수도 있으며, 각 반복기하급수적으로 증가하는 이동 수와 푸시 수를 필요로 합니다.[13] 숙련된 인간 플레이어는 대부분 휴리스틱에 의존하며 일반적으로 패턴과 하위 목표를 인식하여 많은 허무하거나 중복된 플레이 라인을 빠르게 폐기할 수 있으므로 검색 노력을 크게 줄일 수 있습니다.

일부 소코반 퍼즐은 IDA*와 같은 단일 에이전트 검색 알고리즘을 사용하여 도메인별 지식을 활용하는 여러 기술을 통해 자동으로 해결할 수 있습니다.[14] 이것은 앨버타 대학에서 개발한 소코반 솔버인 [15]롤링 스톤이 사용한 방법입니다. Festival[16] 널리 사용되는 XSokoban 테스트 스위트에서 90레벨을 모두 해결한 최초의 자동 해결기였지만, 더 복잡한 Sokoban 레벨은 최고의 자동화된 해결기에도 도달할 수 없습니다.[17]

변종

여러 퍼즐은 원래 소코반 게임의 변형으로 간주될 수 있는데, 이는 모든 퍼즐이 미로에서 상자를 밀고 다니는 통제 가능한 캐릭터를 사용한다는 점에서 그렇습니다.

  • 대체 타일: 표준 게임에서는 미로가 정사각형 격자 위에 놓여 있습니다. 여러 변형은 다른 타일에 배치된 미로에 소코반의 규칙을 적용합니다. 헥소반정육각형을, 트라이오반정삼각형을 사용합니다.
  • Multiple Pusher(다중 푸셔): Multiban(다중반)이라는 변형에서 퍼즐에 하나 이상의 푸셔가 포함되어 있으며 종종 필요합니다. 소코박스 듀오라는 게임에서 퍼즐을 풀기 위해서는 엄격하게 두 명의 캐릭터가 필요한데, 이들은 돌아가면서 또는 함께 작업할 수 있습니다.
  • 지정된 보관 장소: Sokomind Plus에서는 일부 상자와 대상 사각형에 고유 번호가 지정됩니다. 블록-오-매니아에서는 상자의 색상이 다르며, 일치하는 색상으로 사각형 위에 상자를 밀어 넣는 것이 목표입니다.
  • 대체 게임 목표: 여러 변형은 전통적인 소코반 게임 플레이와 다른 목표를 특징으로 합니다. 예를 들어, InterlockSokolor에서는 상자의 색상이 다르지만, 비슷한 색상의 상자가 인접하도록 상자를 이동시키는 것이 목적입니다. CyberBox에서 각 레벨에는 지정된 출구 사각형이 있으며, 목표는 박스를 밀어 해당 출구에 도달하는 것이며, 잠재적으로 동시에 둘 이상의 출구에 도달하는 것입니다. Beanstalk라는 변형에서 목표는 수준의 요소를 고정된 순서로 대상 사각형에 밀어 넣는 것입니다.
  • 추가 게임 요소: 푸시 크레이트, 소코넥스, Xsok, CyberboxBlock-o-Mania 모두 기본 퍼즐에 새로운 요소를 추가합니다. 예를 들어 구멍, 텔레포트, 이동 블록 및 단방향 통로가 있습니다.
  • 캐릭터 액션: 푸코반에서 캐릭터는 상자를 밀기만 하면 상자를 끌 수 있습니다.
  • 역방향 모드: 플레이어는 상자를 밀지 않고 당겨서 끝에서 초기 위치까지 퍼즐을 거꾸로 풀어냅니다. 표준 소코반 퍼즐은 리버스 모드로 플레이할 수 있으며 리버스 모드 솔루션은 표준 모드 퍼즐의 솔루션으로 변환할 수 있습니다. 따라서 리버스 모드 게임 플레이는 표준 소코반 퍼즐을 푸는 데에도 중요한 역할을 할 수 있습니다.[18]

참고 항목

외부 링크

  • 소코반 공식 사이트(일본어)
  • 앨버타 대학교 소코반 페이지
  • Virkkala, Timo (2011). Solving Sokoban (PDF) (Master's Thesis). University of Helsinki. Retrieved 24 September 2014.

참고문헌

  1. ^ Foo, Norman; Goebel, Randy (1996). PRICAI '96: Topics in Artificial Intelligence: 4th Pacific Rim International Conference on Artificial Intelligence, Cairns, Australia, August 26 - 30, 1996, Proceedings. Springer Science & Business Media. p. 592. ISBN 978-3-540-61532-3.
  2. ^ "今回はこのゲームを開発した THINKING RABBIT さんにお願いして, 市販品とは別に10の倉庫をつくってもらいましたので" [This time, we asked THINKING RABBIT, who developed this game, to build 10 warehouses separately from commercial products]. PCマガジン (in Japanese). August 1983. pp. 52–56.
  3. ^ "題して『倉庫番』PCマガジン番外編 (このプログラムは, PC-8801/9801 で使えます)" [Titled "Sokoban" PC Magazine Extra Edition (this program can be used with PC-8801 / 9801)]. PCマガジン (in Japanese). August 1983. pp. 52–56.
  4. ^ Thinking Rabbit - 1983 개발자 인터뷰.
  5. ^ 이마바야시 히로유키씨와의 대화
  6. ^ Low, Lafe (November 1988). "News Line; Made in Japan". inCider (43). 14, 15.
  7. ^ 오스틴 바, 캘빈 정, 애런 윌리엄스 (2021) "블록 듀드 퍼즐은 NP-하드입니다 (그리고 러그는 정말로 함께 감소를 묶습니다)."
  8. ^ "CHDK 1.5 User Manual". CHDK Wiki. Retrieved 2023-07-13.
  9. ^ M. Fryers; M. T. Greene (1995). "Sokoban". Eureka (54).
  10. ^ Dor, Dorit; Zwick, Uri (1999). "SOKOBAN and other motion planning problems". Computational Geometry. 13 (4): 215–228. doi:10.1016/S0925-7721(99)00017-6. ISSN 0925-7721.
  11. ^ 조셉씨. 컬버슨, 소코반PSPACE-완전체입니다. 기술 보고서 TR 97-02, 1997, 앨버타 대학교 컴퓨팅 과학부.
  12. ^ Andreas Junghanns, Jonathan Schaeffer (2001) Sokoban: 도메인 지식을 이용한 일반적인 단일 에이전트 검색 방법 강화, 인공지능 129(1–2):220 (인공지능의 휴리스틱 검색에 관한 특별한 이슈)
  13. ^ 데이비드 홀랜드와 야론 쇼햄, "피코코스모스에 관한 이론적 분석 17"
  14. ^ Andreas Junghanns, Jonathan Schaeffer (2001) Sokoban: 도메인 지식을 이용한 일반적인 단일 에이전트 검색 방법 강화, 인공지능 129(1–2):219–251 (인공지능의 휴리스틱 검색에 관한 특별한 이슈)
  15. ^ Junghanns, Andreas; Schaeffer, Jonathan (1997). "Sokoban: A Challenging Single-Agent Search Problem" (PDF). In IJCAI Workshop on Using Games as an Experimental Testbed for AI Research. University of Alberta. pp. 27–36.
  16. ^ Yaron Shoham, Jonathan Shaeffer (2020) FESS 알고리즘: 단일 에이전트 검색에 대한 특징 기반 접근법 발행일 : 2020 IEEE Conference on Games (CoG)
  17. ^ "Solver Statistics – Sokoban Wiki". Retrieved 8 February 2013.
  18. ^ Frank Takes (2008) "소코반: 리버스 솔루션"