Sokoban
Sokoban (倉庫番 Sōkoban, "magazynwurker" yn it Japansk) is in puzel dêr't de spiler doazen troch in doalhôf (fan boppen sjoen) fersette moat, sadat dy op bepaalde doelen setten wurde. Der kin mar ien doaze tagelyk fersetten wurde, en de doazen kinne allinnich treaun, en net lutsen wurde. De doazen kinne allinnich horizontaal of fertikaal ferskowe, net diagonaal. De útdaging hjirby is dat allegeduerigen mijd wurde moat om ûnoplosbre sitaasjes ('deadlocks') te meitsjen, wêryn de spiler net mear efter in doaze komme kin om dy te triuwen; bygelyks in doaze dy't én links én boppe tsjin in muorre oanleit. Sels yn it earste oankommen maklike spulsituaasjes kinne dochs min op te lossen wêze. In bykommende útdaging is de taak yn sa min mooglik setten of yn sa koart mooglike tiid dien te krijen.
Omdat de puzel net ienfâldich fysyk makke wurde kin, wurdt it meast as kompjûterspul oanbean.
Sokoban is yn 1982 útfûn troch Hiroyuki Imabayashi, en it spul is doe útjûn troch Thinking Rabbit, in softwarefirma út Takarazuka, Japan. Troch Thinking Rabbit binne letter moch ferskate ferfolgen útjûn lykas Boxxle, Sokoban Perfect en Sokoban Revenge.
Op ynternet binne ûntelbere kloanen fan Sokoban te finen, foar hast elk kompjûterplatform.
Der besteane ek inkele farianten fan it spul Sokoban, lykas Hexoban, Trioban en Multiban.
Wiskundige analyze
[bewurkje seksje | boarne bewurkje]Sokoban kin bestudearre wurde middels de kompjûtasjonele kompleksiteitsteory. It is bewiisd dat it oplossen fan in spulnivo fan Sokoban in probleem is mei kompleksiteitsgraad NP-slim[1]; it is ek bewiisd dat Sokoban PSPACE-kompleet is.[2]
It probleem fan Sokoban is in planningsprobleem, fergelykber mei dat fan in robot dy't doazen yn in magazyn oarderje moat. De fertakkingsfaktor fan Sokoban is te fergelykjen mei dy fan skaak, mar de djipte fan de sykbeam kin by Sokoban enoarm grut wêze: yn guon niveaus binne mear as 1000 bewegingen nedich. Sykmetoaden út de keunstmjittige yntelliginsje, lykas it A*-algoritme, kinne brûkt wurde om in kompjûterprogramma te meitsjen dat Sokobanniveaus oplosse kin. Mar om effisjint te wêzen moatte dy metoaden ferfine wurde mei domeinspesifike kennis, krektas minsklike spilers heuristiken brûke en by it spyljen fan Sokoban. In foarbyldd fan in automatyske Sokobanoplosser is Rolling Stone, ûntwikkele troch de GAMES-groep oan de Universiteit fan Alberta yn Kanada. En dôchs is dat programma net by steat om alle 90 standertniveaus fan Sokoban op te lossen.[3][4]
| Boarnen, noaten en/as referinsjes: |
|