소코반
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, XT 및 AT | 스펙트럼 홀로바이트 | 플로피 | |
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년에 Sokoban은 Spectrum 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에서는 일부 상자와 대상 사각형에 고유 번호가 지정됩니다. 블록-오-매니아에서는 상자의 색상이 다르며, 일치하는 색상으로 사각형 위에 상자를 밀어 넣는 것이 목표입니다.
- 대체 게임 목표: 여러 변형은 전통적인 소코반 게임 플레이와 다른 목표를 특징으로 합니다. 예를 들어, Interlock과 Sokolor에서는 상자의 색상이 다르지만, 비슷한 색상의 상자가 인접하도록 상자를 이동시키는 것이 목적입니다. CyberBox에서 각 레벨에는 지정된 출구 사각형이 있으며, 목표는 박스를 밀어 해당 출구에 도달하는 것이며, 잠재적으로 동시에 둘 이상의 출구에 도달하는 것입니다. Beanstalk라는 변형에서 목표는 수준의 요소를 고정된 순서로 대상 사각형에 밀어 넣는 것입니다.
- 추가 게임 요소: 푸시 크레이트, 소코넥스, Xsok, Cyberbox 및 Block-o-Mania 모두 기본 퍼즐에 새로운 요소를 추가합니다. 예를 들어 구멍, 텔레포트, 이동 블록 및 단방향 통로가 있습니다.
- 캐릭터 액션: 푸코반에서 캐릭터는 상자를 밀기만 하면 상자를 끌 수 있습니다.
- 역방향 모드: 플레이어는 상자를 밀지 않고 당겨서 끝에서 초기 위치까지 퍼즐을 거꾸로 풀어냅니다. 표준 소코반 퍼즐은 리버스 모드로 플레이할 수 있으며 리버스 모드 솔루션은 표준 모드 퍼즐의 솔루션으로 변환할 수 있습니다. 따라서 리버스 모드 게임 플레이는 표준 소코반 퍼즐을 푸는 데에도 중요한 역할을 할 수 있습니다.[18]
참고 항목
외부 링크
- 소코반 공식 사이트(일본어)
- 앨버타 대학교 소코반 페이지
- Virkkala, Timo (2011). Solving Sokoban (PDF) (Master's Thesis). University of Helsinki. Retrieved 24 September 2014.
참고문헌
- ^ 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.
- ^ "今回はこのゲームを開発した 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.
- ^ "題して『倉庫番』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.
- ^ Thinking Rabbit - 1983 개발자 인터뷰.
- ^ 이마바야시 히로유키씨와의 대화
- ^ Low, Lafe (November 1988). "News Line; Made in Japan". inCider (43). 14, 15.
- ^ 오스틴 바, 캘빈 정, 애런 윌리엄스 (2021) "블록 듀드 퍼즐은 NP-하드입니다 (그리고 러그는 정말로 함께 감소를 묶습니다)."
- ^ "CHDK 1.5 User Manual". CHDK Wiki. Retrieved 2023-07-13.
- ^ M. Fryers; M. T. Greene (1995). "Sokoban". Eureka (54).
- ^ 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.
- ^ 조셉씨. 컬버슨, 소코반은 PSPACE-완전체입니다. 기술 보고서 TR 97-02, 1997, 앨버타 대학교 컴퓨팅 과학부.
- ^ Andreas Junghanns, Jonathan Schaeffer (2001) Sokoban: 도메인 지식을 이용한 일반적인 단일 에이전트 검색 방법 강화, 인공지능 129(1–2):220 (인공지능의 휴리스틱 검색에 관한 특별한 이슈)
- ^ 데이비드 홀랜드와 야론 쇼햄, "피코코스모스에 관한 이론적 분석 17"
- ^ Andreas Junghanns, Jonathan Schaeffer (2001) Sokoban: 도메인 지식을 이용한 일반적인 단일 에이전트 검색 방법 강화, 인공지능 129(1–2):219–251 (인공지능의 휴리스틱 검색에 관한 특별한 이슈)
- ^ 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.
- ^ Yaron Shoham, Jonathan Shaeffer (2020) FESS 알고리즘: 단일 에이전트 검색에 대한 특징 기반 접근법 발행일 : 2020 IEEE Conference on Games (CoG)
- ^ "Solver Statistics – Sokoban Wiki". Retrieved 8 February 2013.
- ^ Frank Takes (2008) "소코반: 리버스 솔루션"