Misplaced Pages

#878121

48-446: Sokoban ( 倉庫番 , Sōko-ban , lit.   ' warehouse keeper ' ) is a puzzle video game in which the player pushes boxes around in a warehouse , trying to get them to storage locations. The game was designed in 1981 by Hiroyuki Imabayashi, and first published in December 1982. The warehouse is depicted as a grid of squares , each one representing either a floor section or

96-670: A nim-playing computer which was displayed at the Festival of Britain in 1951. In 1952, Herbert Koppel, Eugene Grant and Howard Bailer, engineers from the W. L. Maxson Corporation, developed a machine weighing 23 kilograms (50 lb) which played nim against a human opponent and regularly won. A nim playing machine has been described made from tinkertoys . The game of nim was the subject of Martin Gardner 's February 1958 Mathematical Games column in Scientific American . A version of nim

144-479: A challenging testbed for developing and evaluating planning techniques. The first documented automated solver was Rolling Stone , developed at the University of Alberta . Its core principles laid the groundwork for many newer solvers. It employed a conventional search algorithm enhanced with domain-specific knowledge. Festival , utilizing its FESS algorithm, was the first automatic solver to complete all 90 puzzles in

192-401: A misère game are the same until the number of heaps with at least two objects is exactly equal to one. At that point, the next player removes either all objects (or all but one) from the heap that has two or more, so no heaps will have more than one object (in other words, so all remaining heaps have exactly one object each), so the players are forced to alternate removing exactly one object until

240-414: A normal nim game, the player making the first move has a winning strategy if and only if the nim-sum of the sizes of the heaps is not zero. Otherwise, the second player has a winning strategy. Proof: Notice that the nim-sum (⊕) obeys the usual associative and commutative laws of addition (+) and also satisfies an additional property, x  ⊕  x  = 0. Let x 1 , ..., x n be

288-534: A player must remove at least one object, and may remove any number of objects provided they all come from the same heap or pile. Depending on the version being played, the goal of the game is either to avoid taking the last object or to take the last object. Nim is fundamental to the Sprague–Grundy theorem , which essentially says that every impartial game is equivalent to a nim game with a single pile. Variants of nim have been played since ancient times. The game

336-406: A position s ≠ 0, and therefore this situation has to arise when it is the turn of the player following the winning strategy. The normal play strategy is for the player to reduce this to size 0 or 1, leaving an even number of heaps with size 1, and the misère strategy is to do the opposite. From that point on, all moves are forced. In another game which is commonly known as nim (but is better called

384-497: A series of creatures walk into deadly situations, and a player assigns jobs to specific lemmings to guide the swarm to a safe destination. The 1994 MS-DOS game Shariki , by Eugene Alemzhin, introduced the mechanic of swapping adjacent elements to tile matching games. It was little known at the time, but later had a major influence on the genre. Interest in Mahjong video games from Japan began to grow in 1994. When Minesweeper

432-492: A single heap, one is permitted to remove the same number of objects from each heap. Yet another variation of nim is "circular nim", wherein any number of objects are placed in a circle and two players alternately remove one, two or three adjacent objects. For example, starting with a circle of ten objects, three objects are taken in the first move then another three then one but then three objects cannot be taken out in one move. In Grundy's game , another variation of nim,

480-483: A wall section. Some floor squares contain boxes and some are marked as storage locations. The player, often represented as a worker character, can move one square at a time horizontally or vertically onto empty floor squares, but cannot pass through walls or boxes. To move a box, the player walks up to it and pushes it to an empty square directly beyond the box. Boxes cannot be pushed to squares with walls or other boxes, and they cannot be pulled. The number of boxes matches

528-693: Is a precursor to puzzle-platform games such as Lode Runner (1983), Door Door (1983), and Doki Doki Penguin Land (1985). Blockbuster , by Alan Griesemer and Stephen Bradshaw (Atari 8-bit, 1981), is a computerized version of the Rubik's Cube puzzle. Snark Hunt (Atari 8-bit, 1982) is a single-player game of logical deduction, a clone of the 1970s Black Box board game. Elements of Konami 's tile-sliding Loco-Motion (1982) were later seen in Pipe Mania from LucasArts (1989). In Boulder Dash (1984),

SECTION 10

#1733115099879

576-518: Is a special case of a poset game where the poset consists of disjoint chains (the heaps). The evolution graph of the game of nim with three heaps is the same as three branches of the evolution graph of the Ulam–Warburton automaton . Nim has been mathematically solved for any number of initial heaps and objects, and there is an easily calculated way to determine which player will win and which winning moves are open to that player. The key to

624-499: Is between two players and is played with three heaps of any number of objects. The two players alternate taking any number of objects from any one of the heaps. The goal is to be the last to take an object. In misère play, the goal is instead to ensure that the opponent is forced to take the last remaining object. The following example of a normal game is played between fictional players Bob and Alice , who start with heaps of three, four and five objects. The practical strategy to win at

672-548: Is played—and has symbolic importance—in the French New Wave film Last Year at Marienbad (1961). Nim is typically played as a misère game , in which the player to take the last object loses. Nim can also be played as a "normal play" game whereby the player taking the last object wins. In either normal play or a misère game, when there is exactly one heap with at least two objects, the player who takes next can easily win. If this removes either all or all but one objects from

720-424: Is possible to make a move so that t = 0. Proof: Let d be the position of the leftmost (most significant) nonzero bit in the binary representation of s , and choose k such that the d th bit of x k is also nonzero. (Such a k must exist, since otherwise the d th bit of s would be 0.) Then letting y k  =  s  ⊕  x k , we claim that y k  <  x k : all bits to

768-570: Is said to have originated in China —it closely resembles the Chinese game of jiǎn-shízi ( 捡石子 ), or "picking stones" —but the origin is uncertain; the earliest European references to nim are from the beginning of the 16th century. Its current name was coined by Charles L. Bouton of Harvard University , who also developed the complete theory of the game in 1901, but the origins of the name were never fully explained. The Oxford English Dictionary derives

816-435: Is that the player must experiment with mechanisms in each level before they can solve them. Exploration games include Myst , Limbo , and The Dig . Escape room games such as The Room involve detailed exploration of a single location. Sokoban games, such as its namesake title, or block-pushing puzzle games, involve pushing or pulling blocks on a grid-like space to move them into designated positions without blocking

864-505: Is the "100 game": Two players start from 0 and alternately add a number from 1 to 10 to the sum. The player who reaches 100 wins. The winning strategy is to reach a number in which the digits are subsequent (e.g., 01, 12, 23, 34,...) and control the game by jumping through all the numbers of this sequence. Once a player reaches 89, the opponent can only choose numbers from 90 to 99, and the next answer can in any case be 100. In another variation of nim, besides removing any number of objects from

912-436: The Sprague–Grundy theorem , which essentially says that in normal play every impartial game is equivalent to a nim heap that yields the same outcome when played in parallel with other normal play impartial games (see disjunctive sum ). While all normal-play impartial games can be assigned a nim value, that is not the case under the misère convention. Only tame games can be played using the same strategy as misère nim. Nim

960-423: The subtraction game ), an upper bound is imposed on the number of objects that can be removed in a turn. Instead of removing arbitrarily many objects, a player can only remove 1 or 2 or ... or k at a time. This game is commonly played in practice with only one heap. Bouton's analysis carries over easily to the general multiple-heap version of this game. The only difference is that as a first step, before computing

1008-674: The Rope , as well as projectile collision games such as Angry Birds , Peggle , Monster Strike , and Crush the Castle . Programming games require writing code, either as text or using a visual system, to solve puzzles. Examples include Rocky's Boots (1982), Robot Odyssey (1984), SpaceChem (2011), and Infinifactory (2015). This sub-genre includes point-and-click games that often overlap with adventure games and walking simulators . Unlike logical puzzle games, these games generally require inductive reasoning to solve. The defining trait

SECTION 20

#1733115099879

1056-634: The U.S. for the IBM PC , Commodore 64 , and Apple II as Soko-Ban . In 2001, the Japanese software company Falcon acquired the trademarks for Sokoban and Thinking Rabbit. Since then, Falcon has continued to develop and license official Sokoban games. Sokoban has been implemented for almost all home computers , personal computers , video game consoles and even some TVs . Versions also exist for mobile phones , graphing calculators , digital cameras and electronic organizers . Sokoban has been studied using

1104-485: The board such as Zuma . Puzzle games based on Tetris include tile-matching games where the matching criterion is to place a given number of tiles of the same type so that they adjoin each other. That number is often three, and the corresponding subset of tile-matching games is referred to as match-three games. Nim Nim is a mathematical game of strategy in which two players take turns removing (or "nimming") objects from distinct heaps or piles. On each turn,

1152-405: The example above, taking the nim-sum of the sizes is X = 3 ⊕ 4 ⊕ 5 = 2 . The nim-sums of the heap sizes A=3, B=4, and C=5 with X=2 are The only heap that is reduced is heap A, so the winning move is to reduce the size of heap A to 1 (by removing two objects). As a particular simple case, if there are only two heaps left, the strategy is to reduce the number of objects in the bigger heap to make

1200-417: The game ends. In normal play, the player leaves an even number of non-zero heaps, so the same player takes last; in misère play, the player leaves an odd number of non-zero heaps, so the other player takes last. In a misère game with heaps of sizes three, four and five, the strategy would be applied like this: The soundness of the optimal strategy described above was demonstrated by C. Bouton. Theorem . In

1248-414: The game of nim is for a player to get the other into one of the following positions, and every successive turn afterwards they should be able to make one of the smaller positions. Only the last move changes between misère and normal play. For the generalisations, n and m can be any value > 0, and they may be the same. Normal-play nim (or more precisely the system of nimbers ) is fundamental to

1296-500: The goal is to collect diamonds while avoiding or exploiting rocks that fall when the dirt beneath them is removed. Chain Shot! (1985) introduced removing groups of the same color tiles on a grid, causing the remaining tiles to fall into the gap. Uncle Henry's Nuclear Waste Dump (1986) involves dropping colored shapes into a pit, but the goal is to keep the same color tiles from touching. Tetris (1985) revolutionized and popularized

1344-419: The heap that has two or more, then no heaps will have more than one object, so the players are forced to alternate removing exactly one object until the game ends. If the player leaves an even number of non-zero heaps (as the player would do in normal play), the player takes last; if the player leaves an odd number of heaps (as the player would do in misère play), then the other player takes last. The normal game

1392-491: The heaps equal. After that, no matter what move the opponent makes, the player can make the same move on the other heap, guaranteeing that they take the last object. When played as a misère game, nim strategy is different only when the normal play move would leave only heaps of size one. In that case, the correct move is to leave an odd number of heaps of size one (in normal play, the correct move would be to leave an even number of such heaps). These strategies for normal play and

1440-458: The left of d are the same in x k and y k , bit d decreases from 1 to 0 (decreasing the value by 2 ), and any change in the remaining bits will amount to at most 2 −1. The first player can thus make a move by taking x k  −  y k objects from heap k , then The modification for misère play is demonstrated by noting that the modification first arises in a position that has only one heap of size 2 or more. Notice that in such

1488-443: The length of the game from these two lemmas. Lemma 1 . If s = 0, then t ≠ 0 no matter what move is made. Proof: If there is no possible move, then the lemma is vacuously true (and the first player loses the normal play game by definition). Otherwise, any move in heap k will produce t  =  x k  ⊕  y k from (*). This number is nonzero, since x k  ≠  y k . Lemma 2 . If s ≠ 0, it

Sokoban - Misplaced Pages Continue

1536-399: The movement of other blocks. Similar games include Baba is You and Patrick's Parabox . A hidden object game, sometimes called hidden picture or hidden object puzzle adventure (HOPA), is a genre of puzzle video game in which the player must find items from a list that are hidden within a scene. Hidden object games are a popular trend in casual gaming . In tile-matching video games,

1584-533: The name from the German verb nimm , meaning "take". At the 1939 New York World's Fair Westinghouse displayed a machine, the Nimatron , that played nim. From May 11 to October 27, 1940, only a few people were able to beat the machine in that six-month period; if they did, they were presented with a coin that said "Nim Champ". It was also one of the first-ever electronic computerized games. Ferranti built

1632-407: The nim-sum is not zero before the move. If the nim-sum is zero, then the next player will lose if the other player does not make a mistake. To find out which move to make, let X be the nim-sum of all the heap sizes. Find a heap where the nim-sum of X and heap-size is less than the heap-size; the winning strategy is to play in such a heap, reducing that heap to the nim-sum of its original size with X. In

1680-671: The nim-sums we must reduce the sizes of the heaps modulo k  + 1. If this makes all the heaps of size zero (in misère play), the winning move is to take k objects from one of the heaps. In particular, in ideal play from a single heap of n objects, the second player can win if and only if This follows from calculating the nim-sequence of S (1, 2, ..., k ), 0.123 … k 0123 … k 0123 … = 0 ˙ .123 … k ˙ , {\displaystyle 0.123\ldots k0123\ldots k0123\ldots ={\dot {0}}.123\ldots {\dot {k}},} from which

1728-406: The number of storage locations. The puzzle is solved when all boxes occupy the storage locations. Progressing through the game requires careful planning and precise maneuvering. A single mistake, such as pushing a box into a corner or obstructing the path of others, can render the puzzle unsolvable, forcing the player to backtrack or restart. Anticipating the consequences of each push and considering

1776-408: The ordinary sum, x + y . An example of the calculation with heaps of size 3, 4, and 5 is as follows: An equivalent procedure, which is often easier to perform mentally, is to express the heap sizes as sums of distinct powers of 2, cancel pairs of equal powers, and then add what is left: In normal play, the winning strategy is to finish every move with a nim-sum of 0. This is always possible if

1824-591: The overall layout of the puzzle are crucial to avoid deadlocks and complete the puzzle successfully. Sokoban was created in 1981 by Hiroyuki Imabayashi. The first commercial game was published in December 1982 by his company, Thinking Rabbit , based in Takarazuka , Japan . Sokoban was a hit in Japan, selling over 400,000 copies before being released in the United States. In 1988, Spectrum HoloByte published Sokoban in

1872-431: The player manipulates tiles in order to make them disappear according to a matching criterion. The genre began with 1985's Chain Shot! and has similarities to falling-block games such as Tetris. This genre includes games that require pieces to be swapped such as Bejeweled or Candy Crush Saga , games that adapt the classic tile-based game Mahjong such as Mahjong Trails , and games in which pieces are shot on

1920-474: The puzzle game genre. The game was created by Soviet game designer Alexey Pajitnov for the Electronika 60 . Pajitnov was inspired by a traditional puzzle game named Pentominos in which players arrange blocks into lines without any gaps. The game was released by Spectrum Holobyte for MS-DOS in 1987, Atari Games in arcades in 1988, and sold 30 million copies for Game Boy . In Lemmings (1991),

1968-1867: The sizes of the heaps before a move, and y 1 , ...,  y n the corresponding sizes after a move. Let s  =  x 1  ⊕ ... ⊕  x n and t  =  y 1  ⊕ ... ⊕  y n . If the move was in heap k , we have x i  =  y i for all i ≠ k , and x k  >  y k . By the properties of ⊕ mentioned above, we have t = 0 ⊕ t = s ⊕ s ⊕ t = s ⊕ ( x 1 ⊕ ⋯ ⊕ x n ) ⊕ ( y 1 ⊕ ⋯ ⊕ y n ) = s ⊕ ( x 1 ⊕ y 1 ) ⊕ ⋯ ⊕ ( x n ⊕ y n ) = s ⊕ 0 ⊕ ⋯ ⊕ 0 ⊕ ( x k ⊕ y k ) ⊕ 0 ⊕ ⋯ ⊕ 0 = s ⊕ x k ⊕ y k ( ∗ ) t = s ⊕ x k ⊕ y k {\displaystyle {\begin{aligned}t&=0\oplus t\\&=s\oplus s\oplus t\\&=s\oplus (x_{1}\oplus \cdots \oplus x_{n})\oplus (y_{1}\oplus \cdots \oplus y_{n})\\&=s\oplus (x_{1}\oplus y_{1})\oplus \cdots \oplus (x_{n}\oplus y_{n})\\&=s\oplus 0\oplus \cdots \oplus 0\oplus (x_{k}\oplus y_{k})\oplus 0\oplus \cdots \oplus 0\\&=s\oplus x_{k}\oplus y_{k}\\[10pt](*)\quad t&=s\oplus x_{k}\oplus y_{k}\end{aligned}}} The theorem follows by induction on

Sokoban - Misplaced Pages Continue

2016-409: The strategy above follows by the Sprague–Grundy theorem . The game "21" is played as a misère game with any number of players who take turns saying a number. The first player says "1" and each player in turn increases the number by 1, 2, or 3, but may not exceed 21; the player forced to say "21" loses. This can be modeled as a subtraction game with a heap of 21 − n objects. The winning strategy for

2064-467: The theory of computational complexity . The computational problem of solving Sokoban puzzles was first shown to be NP-hard . Further work proved it is also PSPACE-complete . Solving non-trivial Sokoban puzzles is difficult for computers because of the high branching factor (many legal pushes at each turn) and the large search depth (many pushes needed to reach a solution). Even small puzzles can require lengthy solutions. The Sokoban game provides

2112-432: The theory of the game is the binary digital sum of the heap sizes, i.e., the sum (in binary), neglecting all carries from one digit to another. This operation is also known as " bitwise xor " or "vector addition over GF (2) " (bitwise addition modulo 2). Within combinatorial game theory it is usually called the nim-sum , as it will be called here. The nim-sum of x and y is written x ⊕ y to distinguish it from

2160-436: The two-player version of this game is to always say a multiple of 4; it is then guaranteed that the other player will ultimately have to say 21; so in the standard version, wherein the first player opens with "1", they start with a losing move. The 21 game can also be played with different numbers, e.g., "Add at most 5; lose on 34". A sample game of 21 in which the second player follows the winning strategy: A similar version

2208-936: The widely used XSokoban test suite. However, even the best automated solvers cannot solve many of the more challenging puzzles that humans can solve with time and effort. Several puzzles can be considered variants of the original Sokoban game in the sense that they all make use of a controllable character pushing boxes around in a maze . This table lists some prominent official Sokoban releases that mark milestones, such as expanding to new platforms or achieving widespread popularity. They are organized by release date. Puzzle video game Puzzle video games owe their origins to brain teasers and puzzles throughout human history. The mathematical strategy game Nim , and other traditional thinking games such as Hangman and Bulls and Cows (commercialized as Mastermind ), were popular targets for computer implementation. Universal Entertainment 's Space Panic , released in arcades in 1980,

2256-558: Was followed by other physics-based puzzle games. A physics game is a type of logical puzzle video game wherein the player must use the game's physics and environment to complete each puzzle. Physics games use consistent physics to make games more challenging. The genre is popular in online flash games and mobile games . Educators have used these games to demonstrate principles of physics. Physics-based logic puzzle games include The Incredible Machine , Portal , The Talos Principle , Braid , Fez , World of Goo , and Cut

2304-515: Was released with Windows 95 , players began using a mouse to play puzzle games. In 2000, PopCap Games released Bejeweled , a direct clone of the 1994 tile-matching game Shariki with improved visuals. It sparked interest in the match-three mechanic which became the foundation for other popular games, including Puzzle Quest: Challenge of the Warlords (2007), Candy Crush Saga (2012), and Puzzle & Dragons (2012). Portal (2007)

#878121