Sokoban

Một lời giải đố Sokoban.

Sokoban (倉庫番 ^{(Thương Khố Phiên)}, Sōkoban^?) là trò chơi dạng câu đố trong đó người chơi phải đẩy một số khối vuông vượt qua chướng ngại vật để đến đích.^[1] Trò chơi đã được thiết kế vào năm 1981 bởi Hiroyuki Imabayashi và được ra mắt lần đầu vào tháng 12 năm 1982.^[2][3]

Cách chơi

Trò chơi có dạng bảng ô vuông. Có một số khối vuông được đẩy đến đích (số ô đích đúng bằng số khối vuông). Chỉ có thể đẩy từng khối vuông một, và không thể kéo, cũng như không thể đẩy một dãy hai hay nhiều khối.

Khối vuông bị dính tường nếu như nó bị đẩy sát vào tường mà hai bên tường đều là góc. Vì không thể kéo khối lại được nên coi như khối này bị mất, nó không thể được đưa đến đích trừ phi đích nằm đúng trên cạnh tường đó. Dính tường là một trường hợp cần tránh khi chơi.^[4]

Các phiên bản

Năm	Tựa	Quốc gia	Nền tảng	Nhà phát triển	Phuơng tiện
1982	Sokoban (倉庫番)	Nhật Bản	NEC PC-8801	Thinking Rabbit	Băng cassette
1983	Sokoban [Extra Edition] (倉庫番[番外編])	Nhật Bản	NEC PC-8801	PCマガジン	Nhập chuơng trình
1984	Sokoban 2 (倉庫番2)	Nhật Bản	NEC PC-8801	Thinking Rabbit	Băng cassette
1988	Soko-Ban	Hoa Kỳ	IBM PC và nền tảng tuơng tự	Spectrum HoloByte	Đĩa mềm
1989	Soko-ban Perfect (倉庫番Perfect)	Nhật Bản	NEC PC-9801	Thinking Rabbit	Đĩa mềm
1990	Boxyboy	Nhật Bản Hoa Kỳ	Turbografx-16 và PC Engine	NEC	HuCard
1991	Soko-ban Revenge (倉庫番Revenge)	Nhật Bản	NEC PC-9801	Thinking Rabbit	Đĩa mềm
2016	Sokoban Touch (倉庫番Touch)	Nhật Bản Hoa Kỳ	Android và Apple iOS	Thinking Rabbit	Kỹ thuật số
2019	Minna No Sokoban (みんなの倉庫番)	Nhật Bản	Nintendo Switch và PlayStation 4	Unbalance Corporation	Kỹ thuật số
2021	The Sokoban	Hoa Kỳ	Nintendo Switch và PlayStation 4	Unbalance Corporation	Kỹ thuật số

Trò chơi điện tử
Các nền tảng Trò chơi arcade Trò chơi console Máy console Máy chơi trò chơi điện tử tại gia Máy chơi trò chơi điện tử cầm tay Trò chơi điện tử Trò chơi âm thanh Trò chơi điện tử cầm tay Trò chơi trực tuyến Webgame Trò chơi mạng xã hội Trò chơi di động PC Linux Mac Trò chơi thực tế ảo
Thể loại trò chơi điện tử Trò chơi hành động Beat 'em up Hack and slash Đối kháng Platform Bắn súng Sinh tồn Battle royale Hành động phiêu lưu Lén lút Kinh dị sinh tồn Phiêu lưu Viễn tưởng tương tác Điện ảnh tương tác Visual novel Trò chơi Gacha Nhập vai Hành động nhập vai Chiến thuật nhập vai Mô phỏng Mô phỏng xây dựng và quản lý Mô phỏng cuộc sống Trò chơi thể thao Trò chơi mô phỏng phương tiện Trò chơi điện tử chiến lược 4X Đấu tự động Đấu trường trận chiến trực tuyến nhiều người chơi Chiến lược thời gian thực Chiến thuật thời gian thực Phòng thủ tháp Chiến lược theo lượt Chiến thuật theo lượt Trò chơi trực tuyến nhiều người chơi
Danh sách trò chơi điện tử Danh sách trò chơi arcade Trò chơi bán chạy nhất Loạt bán chạy nhất Sản phẩm chạy nhất Trò chơi có doanh thu cao nhất arcade di động Loạt lâu đời nhất Trò chơi được chơi nhiều nhất điện thoại di động Trò chơi hay nhất Nhạc hay nhất Trò chơi của năm Tiếp nhận tiêu cực
Phát triển trò chơi điện tử Trò chơi điện tử AI Thiết kế trò chơi Thiết kế trò chơi điện tử Thiết kế tương tác Lập trình trò chơi điện tử Mỹ thuật trò chơi điện tử Đồ họa trò chơi điện tử Âm nhạc trò chơi điện tử
x t s

Phát triển

Sokoban được tạo ra vào năm 1981 bởi Hiroyuki Imabayashi và bắt đầu thưong mại lần đầu đầu tiên vào tháng 12 năm 1982 bởi Thinking Rabbit, một công ty phần mềm có trụ sở tại Takarazuka, Nhật Bản.

Năm 1988, Sokoban được Spectrum HoloByte xuất bản tại Mỹ cho dòng Commodore 64, IBM-PC, Unix, Commodore Amiga và Apple II với tên gọi Soko-Ban. Sokoban đã thành công vang dội ở Nhật Bản và đã bán được hơn 400.000 chiếc vào thời điểm Spectrum HoloByte nhập khẩu nó vào Hoa Kỳ.^[5]

Một bài đố trong Sokoban YASC. Có 15 khối vuông cần được đẩy về đích.

Trên máy tính

Sokoban YASC (Yet Another Sokoban Clone)^[6] là một bản phần mềm nguồn mở của trò chơi này, chạy trên Windows. YASC có nhiều tính năng cho người chơi như: lưu lại ván đang chơi giữa chừng, hoãn lại các nước đi sai, thông báo khi không có đường đi, v.v...

Nghiên cứu khoa học

Sokoban có thể nghiên cứu bằng Lý thuyết độ phức tạp tính toán. Bài toán giải trò chơi Sokoban puzzles lúc đầu được chứng minh là NP-khó.^[7][8] Sau nhiều nghiên cứu, bài toán được cho là cực khó so với các bài toán NP khác; nó là PSPACE-đầy đủ.^[9] Điều này có lợi cho nghiên cứu trí tuệ nhân tạo (AI) bởi giải bài toán Sokoban có thể được xem như là việc tự động lập kế hoạch được yêu cầu bởi robot tự hoạt động.

Sokoban khó giải không chỉ vì hệ số rẽ nhánh của nó lớn, mà còn vì độ sâu của cây tìm kiếm của nó. Một số loại màn chơi có thể được mở rộng vô hạn, với mỗi bước lặp tăng trưởng theo cấp số nhân cho mỗi bước đẩy và kéo.^[10] Người chơi có kinh nghiệm dựa chủ yếu vào kỹ thuật tìm kiếm và thường nhanh chóng loại một lượng lớn các nước đi thừa hay nước đi sai lầm bằng việc phát hiện ra quy luật và đích phụ, do đó giảm lượng tìm kiếm đi một cách đáng kể.

Các biến thể khác

Một số trò chơi khác được hình thành trên ý tưởng của Sokoban. Chẳng hạn Chip's Challenge, trong đó các khối có thể đẩy đến vị trí đích là nơi cần bắc cầu hoặc phá bom. Ngoài ra, chướng ngại vật trên đường đi còn có thể là những động vật cần phải tránh.

Liên kết ngoài

• Trang web chính thức của Sokoban. (bằng tiếng Nhật)
• Trang web của Đại học Alberta Sokoban. (bằng tiếng Anh)

Tham khảo

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 (bằng tiếng Anh). Springer Science & Business Media. ISBN 978-3-540-61532-3.
2. “Sokoban History”. www.games4brains.de. Truy cập ngày 12 tháng 11 năm 2022.
3. “Sokoban project”. www.sokobano.de. Truy cập ngày 12 tháng 11 năm 2022.
4. “How to play Sokoban - Sokoban Wiki”. sokobano.de. Truy cập ngày 12 tháng 11 năm 2022.
5. “Wayne Green”, Wikipedia (bằng tiếng Anh), 9 tháng 6 năm 2022, truy cập ngày 12 tháng 11 năm 2022
6. “Sokoban YASC”. SourceForge (bằng tiếng Anh). Truy cập ngày 12 tháng 11 năm 2022.
7. M. Fryers; M. T. Greene (1995). “Sokoban”. Eureka (54).
8. 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.
9. Joseph C. Culberson, Sokoban is PSPACE-complete Lưu trữ 2018-01-15 tại Wayback Machine (PS Lưu trữ 2019-04-22 tại Wayback Machine). Technical Report TR 97-02, Dept. of Computing Science, University of Alberta, 1997.
10. David Holland and Yaron Shoham, "Theoretical analysis on Picokosmos 17".