Tile-matching video game
A tile-matching video game is a type of puzzle video game where the player manipulates tiles in order to make them disappear according to a matching criterion. In many tile-matching games, that 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 these games are called match-three games. The core challenge of tile-matching games is the identification of patterns on a seemingly chaotic board. Their origins lie in puzzle games from the 1980s such as "Tetris", "Chain  Shot!" ("SameGame") and "Puzznic". Tile-matching games were made popular in the 2000s, in the form of casual games distributed or played over the Internet, notably the "Bejeweled" series of games. They have remained popular since, with the game "Candy Crush Saga" becoming the most-played game on Facebook in 2013. Tile-matching games cover a broad range of design elements, mechanics and gameplay experiences. They include purely turn-based games but may also feature arcade-style action elements such as time pressure, shooting or hand-eye coordination. The tile matching mechanic is also a minor feature in some larger  games. Video game researcher Jesper Juul therefore considers tile matching to be a game mechanic, rather than a distinct genre of games. History. The mechanism of matching game pieces to make them disappear is a feature of many non-digital games, including Mahjong solitaire and Solitaire card games. Video game researcher Jesper Juul traces the history of tile-matching video games back to early puzzle "Tetris" and "Chain Shot!" (later known as "SameGame"), published in 1984 and 1985, respectively. While both are puzzle games, they differ in important design points such as time pressure, tile manipulation, and solving criteria. While  there may have been earlier video games with tile-matching mechanics, Juul stated that the commercial success of both "Tetris" and "Chain Shot!" established the popularity of puzzle games, leading to a second generation of influential games – "Puzznic", "Columns", "Dr. Mario" and "Plotting" – which were published in 1989 and 1990. Another early Mahjong-style pair matching game was "Shanghai" (1986). The popularity of the puzzle genre was further boosted when Nintendo bundled the Game Boy version of "Tetris" with the Game Boy handheld system upon its North American and European releases in 1989. The game helped to sell the handheld  system, making it a killer application, and sold over 35 million copies over the Game Boy's lifetime. As it drew in players that normally did not play video games, "Tetris" is considered one of the first casual games. The popularity of the late 1980s puzzle games continued to bring new titles to the market, generally building on ideas introduced in these early games. Games building on "Dr. Mario"'s mechanics include "Puyo Puyo" (1991), "Baku Baku Animal" (1995) and "Puzzle Fighter" (1996). Building on the shooting mechanic introduced in "Plotting", "Dr. Mario" also influenced "Puzzle Bobble" (1994), which in  turn inspired "Puzz Loop" (1998), "Hexic" and "Zuma" (2003), and "Luxor" (2005). "Columns" was the basis of a line of development of tile matching games based on shifting or swapping tiles. It includes "Yoshi's Cookie" (1992) and "Panel de Pon" (1995), which introduced the swapping mechanic. "Magic Jewelry" followed in 1990. "Puzzled" included multiplayer games and was released for the Neo Geo console in the same year. 1994 saw "BreakThru!" and "Gururin" published with "FlipOut!" and "Vid Grid" released the following year. "Hebereke's Popoitto" was released in 1995 containing a two player competitive game. "Sega Swirl" for handheld  devices was released in 1999. Microsoft bundled "Jawbreaker" Windows Mobile 2003. Several multiplayer modes, both local and networked, featured in early tile-matching games such as "Columns" and "Dr. Mario" and later with "TetriNET" (1997) and "Tetris Worlds" (2001). Multiplayer introduced elements of race and competition as players were able to attacks opponents in various ways resulting in more difficult matchmaking for their opponent. The first of what eventually became known as "match-three" games, where the goal is to create clusters of three or more identical items on a grid, was "Shariki" (1994). It led directly to the successful  Bejeweled (2001), which became a series and inspired similar games including "Zoo Keeper" (2003), "Big Kahuna Reef" (2004), "Jewel Quest" (2004), and "Chuzzle" (2005). "Tidalis" (2010) developed the idea further with 20 game modes and the goal of creating the longest possible chain of matching colors. Towards 2010, new trends in tile-matching games appeared. The first was driven by the popularity of mobile games. Prior to 2012, most tile-matching games had no end goal, instead challenging the player to continue as long as possible until the board reached a state where no turn was possible, or, in the  case of "Tetris", where tiles have filled up past a given point on the board. King, which had made similar tile-matching games for browser-based games, explored a different approach with its first mobile app, "Bubble Witch Saga", which had puzzle-oriented gameplay like "Puzzle Bobble", but applied finite restrictions on the number of moves the player could take and setting target goals such as score or clearing the board. This enabled them to create numerous levels that could be completed in a short time, making the game ideal for mobile players, and apply a microtransaction model to provide  players temporary boosts and power-ups for more difficult levels. This approach proved highly successful and King reused it for the tile-matching game "Candy Crush Saga" in 2012, itself which was inspired by "Bejeweled". "Candy Crush Saga" became one of the most financially successful mobile games, and established a new type of tile-matching game based on creating games broken up into levels and establishing goals to reach within a limited number of moves. This "saga" approach also extended to other genres of mobile games. The second innovation in tile-matching games was the incorporation of their mechanic into  other genres. One of the first such games was "" released in 2008. While based on a "Bejeweled"-like tile-matching game, "Puzzle Quest" added elements of a computer role-playing game atop this. The player would take turns against a computer opponent, making matches on a common game board, with the types of tiles matched representing role-playing game elements like attacks, defense, and magic which the player used to battle their current enemy, the larger game component had the player improve their character and obtain gear that improved the value of the tiles they matched or created special effects on  the tile board, such as removing all tiles of a specific type. "Puzzle Quest" was very popular and led to numerous games which uses the tile-matching as part of a battle system. While not directly influenced by "Puzzle Quest", "Puzzle & Dragons" in 2012 was another successful mobile title that used the tile-matching part of the game for combat-related actions. Both "Push Panic" and "Heroes of Kalevala" arrived in 2010. In 2011 "New Puzzle Bobble" was released for iOS while "Bubble Safari", "Ruby Blast", "Gems with Friends" and "Puzzle & Dragons" were first released in 2012. "Juice Cubes", "Tower  of Saviors", "Alien Hive", "Marvel Puzzle Quest", "Jelly Splash" and "" were released for mobile devices from 2013 onwards. In 2015 "", "Ironcast", "HuniePop", "Hex Frvr" and "Sailor Moon Drops" were all released. By 2016 millions of players were logging into titles such as "". The genre continues to appeal to gamers, with numerous titles including "Boost Beast" (2017), "Dr. Mario World", and "Crystal Crisis" (2019) among the more recent. Many casual tile matching games continue to be published. Their development is characterized by gradual evolution, where new games makes only small changes, if any, to a formula known from previous games. In  the highly competitive market for downloadable casual games, new entries must be familiar enough to appeal to players of earlier games, but innovative enough to differentiate the new game from earlier ones. This leads to developers, according to Juul, "simultaneously trying to out-innovate and out-clone each other". A new style of tile-matching game arose from games like "Triple Town" (2010), "2048" (2014), and "Threes" (2014), typically called merge-style games. Here, the player either can place tiles in a limited area, or can manipulate tiles such as sliding all tiles as far as they can move in  one direction. The goal is to match two, three, or more tiles of the same type, which merges those matched tiles into a single tile with a different value that then can be matched further. For example, in "2048", players are given random blocks with numbers 2 or 4 on them, and much match two blocks of the same number as to generate new blocks with values in the multiples of 2, with the goal to try to get a block with the value 2048 (2) or higher. While the merging mechanic had been part of other video games since  as early as "Darwin's Dilemma" in 1990, the genre saw a boost following the success of "Threes" on mobile platforms. Features. Tile-matching games that are set in a fictional background are normally based in a "bright and positive" fiction, as opposed to the warlike background of strategy games or the fantasy background of massively multiplayer games. Tile matching game mechanics have been combined with other mechanics to produce a great variety of puzzle game experiences. This section discusses a number of these mechanics. Gameplay limitations. Early puzzle games like "Tetris" were timed – that is, new tiles are continuously  added and the player is under pressure to make matches before the board fills up. The rate of tile addition often increased as to make for a more difficult challenge in longer games. Untimed (turn-based) games, in which new tiles are added only after the player has made a move, used to be the exception, although the 1985 game "Chain Shot!" already had an untimed mode. In untimed modes, the player is able to continue to make matches until they reach an unplayable state, in which case the game is considered over. The addition of an untimed mode to  Bejeweled! was integral to that game's success, as well as one of its most important influences on subsequent games, as it made the game more accessible to less skilled players. With the introduction of "Candy Crush Saga", games with levels featuring limits on the number of moves were introduced. In this, the player may be challenged to achieve a certain score, or match enough tiles of a specific color before running out of turns, or otherwise would have to complete the level again. Tile arrangement, manipulation, and matching. Tiles may be arranged on a horizontal surface or vertically (that  is, stacked atop one another, and dropping down when tiles below are removed). In the latter case, some games allow moving or rotating new tiles as they fall down from the top of the playing area, as in "Tetris" or "Dr. Mario"; or they may allow only the manipulation of tiles that have already fallen, as in "Yoshi's Cookie". "Panel de Pon" introduced, and "Bejeweled" popularized the mechanism of tile swapping, in which tiles may be moved by exchanging the position of two adjacent tiles. Another frequently used tile manipulation method is having the player shoot the tiles onto  the board, such as in "Plotting" and its descendants including "Zuma". The first method, which allows only moves that create a match, results in a more strategic, thoughtful style of play, whereas the second method requires hand-eye coordination in addition to pattern recognition skills, and makes for a more hectic style of play. Scoring. In most tile-matching games, players obtain points for each match. Higher scores are awarded for more difficult matches, such as those involving a greater number of similar tiles. In some tile games, when tiles are matched and removed, pieces above them fall to fill  the space (as with "Bejeweled" and "Candy Crush Saga"). This creates the potential for additional matches and creating scoring combos, with all subsequent matches scored at higher point values. Victory and loss. Some games drop tiles at random, others according to algorithms. In most tile-matching games, new tiles are randomly added to the board continuously, either turn by turn or in real time. This may continue indefinitely or for a given period of time or number of turns. The player must continuously remove the newly added tiles through matching. The game may end with a loss when the board  is filled with tiles or if there are no more possible matches. It may end with a victory when the player clears the board or reaches a given score. Significance. Among downloadable casual video games, according to a survey referred to by Juul, tile-matching games were the second most popular game type in 2004 and by far the most popular in 2005. After that, their popularity declined: they were the fourth most popular of several genres in 2006 and 2007, and in 2008 a games publisher referred to them as a "niche" genre. But as they became well known  and therefore assumed to be immediately playable by many people, tile-matching games migrated to other, more ubiquitous distribution channels such as cell phones and smartphones. Despite their commercial popularity, tile-matching games are among the games with the lowest status among video game enthusiasts, to the point where reviewers have advised gamers not to be ashamed of playing them. This may be because critics consider that there are too many of these games, which differ only slightly from each other. It may also be because, as casual games, tile-matching games are designed to be easily accessible and easy  to play, which conflicts with a traditional video gaming ethos that demands games to be challenging and punishing. Computational complexity. Match-three games are NP-hard when generalized to an n × n playfield and played such that the player knows in advance all the tiles that will appear, with no random chance involved.