Khác biệt giữa bản sửa đổi của “Sokoban”

Bách khoa toàn thư mở Wikipedia
Duyệt lịch sử tương tác
← Thay đổi trướcThay đổi sau →
Nội dung được xóa Nội dung được thêm vào
Trực quanMã wiki
Không có tóm lược sửa đổi
Dòng 1: Dòng 1:
{{thiếu nguồn gốc}}
{{thiếu nguồn gốc}}
[[Hình:Sokoban_ani.gif|frame|right|Một lời giải đố Sokoban.]]
[[Hình:Sokoban_ani.gif|right|Một lời giải đố Sokoban.|nhỏ|241x241px]]
{{nihongo|'''Sokoban'''|倉庫番|Sōkoban|hanviet=Thương Khố Phiên}} là [[trò chơi đố|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.<ref>{{Chú thích sách|url=https://books.google.com/books?id=j2QrFVEd2GUC&newbks=0&printsec=frontcover&pg=PA592&dq=sokoban+meaning+warehouse&hl=en|title=PRICAI '96: Topics in Artificial Intelligence: 4th Pacific Rim International Conference on Artificial Intelligence, Cairns, Australia, August 26 - 30, 1996, Proceedings|last=Foo|first=Norman|last2=Goebel|first2=Randy|date=1996|publisher=Springer Science & Business Media|isbn=978-3-540-61532-3|language=en}}</ref> 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.
⚫
[[Tập tin:Sokoban YASC screenshot.jpg|300px|nhỏ|phải|Một bài đố trong Sokoban YASC. Có 15 khối vuông cần được đẩy về đích.]]
{{nihongo|'''Sokoban'''|倉庫番|Sōkoban|hanviet=Thương Khố Phiên}} là [[trò chơi đố|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.


==Cách chơi==
==Cách chơi==
Dòng 8: Dòng 7:


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.
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.

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


==Trên máy tính==
==Trên máy tính==
Dòng 15: Dòng 94:


===Nghiên cứu khoa học===
===Nghiên cứu khoa học===
⚫
[[Tập tin:Sokoban YASC screenshot.jpg|300px|nhỏ|phải|Một bài đố trong Sokoban YASC. Có 15 khối vuông cần được đẩy về đích.]]
''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ó]].<ref>{{chú thích tạp chí |author1=M. Fryers |author2=M. T. Greene |title= Sokoban |journal= Eureka |issue= 54 |year= 1995}}</ref><ref name="DorZwick1999">{{chú thích tạp chí |last1=Dor |first1=Dorit |last2=Zwick |first2=Uri |title=SOKOBAN and other motion planning problems |journal=Computational Geometry |volume=13 |issue=4 |year=1999 |pages=215–228 |issn=09257721 |doi=10.1016/S0925-7721(99)00017-6}}</ref> <!--as it is part of a more general class of motion planning problems where the porter is allowed to push and/or pull one or more boxes at a time. --> 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 (độ phức tạp)|NP]] khác; nó là [[PSPACE-đầy đủ]].<ref>Joseph C. Culberson, [http://cl-informatik.uibk.ac.at/teaching/ss07/alth/material/culberson97sokoban.pdf Sokoban is PSPACE-complete] ([https://webdocs.cs.ualberta.ca/~joe/TR/TR97-02.ps PS]). Technical Report TR 97-02, Dept. of Computing Science, University of Alberta, 1997.</ref> Đ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'' 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ó]].<ref>{{chú thích tạp chí |author1=M. Fryers |author2=M. T. Greene |title= Sokoban |journal= Eureka |issue= 54 |year= 1995}}</ref><ref name="DorZwick1999">{{chú thích tạp chí |last1=Dor |first1=Dorit |last2=Zwick |first2=Uri |title=SOKOBAN and other motion planning problems |journal=Computational Geometry |volume=13 |issue=4 |year=1999 |pages=215–228 |issn=09257721 |doi=10.1016/S0925-7721(99)00017-6}}</ref> <!--as it is part of a more general class of motion planning problems where the porter is allowed to push and/or pull one or more boxes at a time. --> 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 (độ phức tạp)|NP]] khác; nó là [[PSPACE-đầy đủ]].<ref>Joseph C. Culberson, [http://cl-informatik.uibk.ac.at/teaching/ss07/alth/material/culberson97sokoban.pdf Sokoban is PSPACE-complete] ([https://webdocs.cs.ualberta.ca/~joe/TR/TR97-02.ps PS]). Technical Report TR 97-02, Dept. of Computing Science, University of Alberta, 1997.</ref> Đ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]].


Phiên bản lúc 07:27, ngày 12 tháng 11 năm 2022

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.

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.

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ên máy tính

Sokoban YASC (Yet Another Sokoban Clone)[1] 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

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

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ó.[2][3] 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 đủ.[4] Đ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.[5] 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.

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. ^ M. Fryers; M. T. Greene (1995). “Sokoban”. Eureka (54).
  3. ^ 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.
  4. ^ Joseph C. Culberson, Sokoban is PSPACE-complete (PS). Technical Report TR 97-02, Dept. of Computing Science, University of Alberta, 1997.
  5. ^ David Holland and Yaron Shoham, "Theoretical analysis on Picokosmos 17".
Lấy từ “https://vi.wikipedia.org/w/index.php?title=Sokoban&oldid=69304900”