Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Mahjong solitaire
Résumé
Mahjong solitaire (also known as Shanghai solitaire, electronic or computerized mahjong, solitaire mahjong or simply mahjong) is a single-player matching game that uses a set of mahjong tiles rather than cards. It is more commonly played on a computer than as a physical tabletop game.
Its name comes from the four-player game mahjong, but it is played entirely differently.
The 144 tiles are arranged in a four-layer pattern with their faces upwards. A tile is said to be open or exposed if it can be moved either left or right without disturbing other tiles. The goal is to match open pairs of identical tiles and remove them from the board, exposing the tiles under them for play. The game is won when all pairs of tiles have been removed from the board, and lost if the remaining tiles contain no exposed pairs.
Playing Mahjong solitaire optimally in the sense to maximize the probability of removing all tiles is PSPACE-complete, and the game is NP-complete if looking below tiles is allowed. It has been proven that it is PSPACE-hard to approximate the maximum probability of removing all tiles within a factor of , assuming that there are arbitrarily many quadruples of matching tiles and that the hidden tiles are uniformly distributed. The perfect-information version of this puzzle is where the player knows, before the game starts, the position of every tile. In this case, however, it is NP-complete to decide whether all tiles can be removed.
An analysis of ten million games with the default layout, "the turtle", found that about 3 percent of the turtles cannot be solved even when looking below tiles is allowed.
Mahjong solitaire can be played using genuine tiles and a special wooden frame for set-up. Usually though, it is played in an electronic form as a computer game. This removes the tedium of set-up and the temptation to cheat.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.