title: Sokoban
text: Sokoban (Japans: 倉庫番; Sōkoban; vertaling "magazijnwerker") is een puzzelspel uit 1982 waarbij de speler dozen door een doolhof (gezien van bovenaf) moet verplaatsen, om deze op bepaalde doelen worden te plaatsen.
  
  Gameplay 
  Het is slechts mogelijk een enkele doos tegelijk te verplaatsen, en de dozen kunnen enkel geduwd, niet getrokken worden. De dozen kunnen enkel horizontaal of verticaal verschuiven, niet diagonaal. De uitdaging hierbij is dat men voortdurend moet vermijden om onoplosbare situaties (deadlocks) te creëren, waarin de speler niet meer achter een doos kan komen om die te duwen; bijvoorbeeld een doos die zowel links als boven tegen een muur aan ligt. In dat geval zit er niks anders op dan opnieuw te beginnen. Hiervoor heeft het spel een mogelijkheid om een level te resetten(retry), zodat een nieuwe poging kan worden gedaan om dit level op te lossen. Zelfs op het eerste gezicht eenvoudige spelsituaties kunnen toch moeilijk op te lossen zijn. Een bijkomende uitdaging is de taak in zo weinig mogelijk zetten of in zo kort mogelijke tijd te voltooien.
  
  Geschiedenis 
  Sokoban is in 1982 bedacht door Hiroyuki Imabayashi. Het spel werd ontwikkeld door Thinking Rabbit, een softwarefirma uit Takarazuka, Japan, en uitgegeven door Spectrum Holobyte. Door Thinking Rabbit zijn later nog verschillende vervolgen gemaakt zoals Boxxle (op de Game Boy van Nintendo), Sokoban Perfect en Sokoban Revenge. 
  
  Er zijn diverse klonen van Sokoban op het internet te vinden voor bijna elk computerplatform. Er bestaan ook enkele varianten van het spel Sokoban, zoals Hexoban, Trioban en Multiban. Het spel is ook als app verkrijgbaar in de verschillende app-stores, zodat het ook op smartphones of tablets gespeeld kan worden.
  
  Wiskundige analyse 
  Sokoban kan bestudeerd worden met behulp van de computationele complexiteitstheorie. Het is bewezen dat het oplossen van een spelniveau van Sokoban een probleem is met complexiteitsgraad NP-moeilijk; het is ook bewezen dat Sokoban PSPACE-compleet is.
  
  Het probleem van Sokoban is een planningsprobleem, vergelijkbaar met dat van een robot die dozen in een magazijn moet rangschikken. De vertakkingsfactor van Sokoban is vergelijkbaar met die van schaak, maar de diepte van de zoekboom kan bij Sokoban enorm groot zijn: in sommige niveaus zijn meer dan 1000 bewegingen nodig. Zoekmethoden uit de kunstmatige intelligentie, zoals het A*-algoritme, kunnen aangewend worden om een computerprogramma te maken dat Sokobanniveaus kan oplossen. Maar om efficiënt te zijn moeten die methoden verfijnd worden met domeinspecifieke kennis, net zoals menselijke spelers gebruikmaken van heuristieken bij het spelen van Sokoban. Een voorbeeld van een automatische Sokobanoplosser is Rolling Stone, ontwikkeld door de GAMES-groep aan de Universiteit van Alberta in Canada. Nochtans is dat programma niet in staat om alle 90 standaardniveaus van Sokoban op te lossen.
  
  Platforms
  
  Ontvangst
  
  Trivia 
  Het spel is opgenomen in het boek 1001 Video Games You Must Play Before You Die van Tony Mott.
  Een aantal levels van het computerspel NetHack zijn Sokoban puzzels
  
  Computerspel uit 1982
  Strategiespel
  Puzzelspel
  Apple II-spel
  Commodore 64-spel
  DOS-spel
  Windows Mobile-spel
  Linux-spel
  Mac OS-spel
  MSX-spel
  Windows-spel