Ghost Leg
Encyclopedia
Ghost Leg known in Japan as Amidakuji (阿弥陀籤) or in Korea as 사다리타기 (literally translated as "ladder climbing"), is a method of lottery designed to create random pairings between two sets of any number of things, as long as the number of elements in each set is the same. This is often used to distribute things among people, where the number of things distributed is the same as the number of people. For instance, chores or prizes could be assigned fairly and randomly this way.
It consists of vertical lines with horizontal lines connecting two adjacent vertical lines scattered randomly along their length; the horizontal lines are called "legs". The number of vertical lines equals the number of people playing, and at the bottom of each line there is an item - a thing that will be paired with a player. The general rule for playing this game is: choose a line on the top, and follow this line downwards. When a horizontal line is encountered, follow it to get to another vertical line and continue downwards. Repeat this procedure until reaching the end of the vertical line. Then the player is given the thing written at the bottom of the line.
If the elements written above the Ghost Leg are treated as a sequence
, and after the Ghost Leg is used, the same elements are written at the bottom, then the starting sequence
has been transformed to another permutation
. Hence, Ghost Leg can be treated as a kind of permuting operator.
Another process involves creating the ladder beforehand, then concealing it. Then people take turns choosing a path to start from at the top. If no part of the amidakuji is concealed, then it is possible to fix the system so that you are guaranteed to get a certain pairing, thus defeating the idea of random chance.
, amidakuji will always create a 1:1 correspondence, and can handle arbitrary numbers of pairings (although pairing sets with only two items each would be fairly boring). It is guaranteed that two items at the top will never have the same corresponding item at the bottom, nor will any item on the bottom ever lack a corresponding item at the top.
It also works regardless of how many horizontal lines are added. Each person could add one, two, three, or any number of lines, and the 1:1 correspondence would remain. The more lines that are added, the more unpredictable the final outcome is.
One way of realizing how this works is to consider the analogy of coins in cups. You have n coins in n cups, representing the items at the bottom of the amidakuji. Then, each leg that is added represents swapping the position of two adjacent cups. Thus, it is obvious that in the end there will still be n cups, and each cup will have one coin, regardless of how many swaps you perform.
i.e. Let M be a matrix representing a particular ghost leg, then Mn=I for some finite n.
there must exist a Ghost Leg M-1,
such that M M-1=I
There are an infinite number of Ghost Legs representing the same permutation.
contains the least number of legs, and hence is prime. This is equivalent to saying that bubble sort performs the minimum number of adjacent exchanges to sort a sequence.
In the same way, the maximum number of legs in a prime with n tracks =
When bubblization operates, the following two identities are repeatedly applied in order to move and eliminate "useless" legs.
When the two identities cannot be applied any more, the ghost leg is proved to be exactly the same as the Ghost Leg constructed by bubble sort
, thus bubblization can reduce Ghost Legs to primes.
If the legs are drawn randomly (for reasonable definitions of "drawn randomly"), the evenness of the distribution of permutations increases with the number of legs. If the number of legs is small relative to number of tracks, the probabilities of different attainable permutations may vary greatly; for large numbers of legs the probabilities of different attainable permutations approach equality.
game called Psycho Fox
uses the mechanics of an Amidakuji board as a means to bet a bag of coins on a chance at a prize at the top of the screen.
Konami
produced an arcade game named Amidar
which uses an Amidakuji board and rules as a setting for a Pac-Man
/Qix
like game.
New Super Mario Bros.
and Wario: Master of Disguise
feature an Amidakuji-style minigame in which the player uses the stylus
to trace lines that will lead the character down the right path.
In Mario Party
there is a mini game where one of the four players pours money into an Amidakuji made out of pipes. The goal is to try to choose the path that leading to the character controlled by the player.
The BoSpider in Mega Man X
and Maverick Hunter X descends onto the player via an Amidakuji path.
It consists of vertical lines with horizontal lines connecting two adjacent vertical lines scattered randomly along their length; the horizontal lines are called "legs". The number of vertical lines equals the number of people playing, and at the bottom of each line there is an item - a thing that will be paired with a player. The general rule for playing this game is: choose a line on the top, and follow this line downwards. When a horizontal line is encountered, follow it to get to another vertical line and continue downwards. Repeat this procedure until reaching the end of the vertical line. Then the player is given the thing written at the bottom of the line.
If the elements written above the Ghost Leg are treated as a sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
, and after the Ghost Leg is used, the same elements are written at the bottom, then the starting sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
has been transformed to another permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
. Hence, Ghost Leg can be treated as a kind of permuting operator.
Process
As an example, consider assigning roles in a play to actors.- To start with, the two sets are enumerated horizontally across a board. The actors' names would go on top, and the roles on the bottom. Then, vertical lines are drawn connecting each actor with the role directly below it.
- The names of the actors and/or roles are then concealed so that people do not know which actor is on which line, or which role is on which line.
- Next, each actor adds a leg to the board. Each leg must connect two adjacent vertical lines, and must not touch any other horizontal line.
- Once this is done, a path is traced from top of each vertical line to the bottom. As you follow the line down, if you come across a leg, you must follow it to the adjacent vertical line on the left or right, then resume tracing down. You continue until you reach the bottom of a vertical line, and the top item you started from is now paired with the bottom item you ended on.
Another process involves creating the ladder beforehand, then concealing it. Then people take turns choosing a path to start from at the top. If no part of the amidakuji is concealed, then it is possible to fix the system so that you are guaranteed to get a certain pairing, thus defeating the idea of random chance.
Mathematics
Part of the appeal for this game is that, unlike random chance games like rock, paper, scissorsRock, Paper, Scissors
Rock-paper-scissors is a hand game played by two people. The game is also known as roshambo, or another ordering of the three items ....
, amidakuji will always create a 1:1 correspondence, and can handle arbitrary numbers of pairings (although pairing sets with only two items each would be fairly boring). It is guaranteed that two items at the top will never have the same corresponding item at the bottom, nor will any item on the bottom ever lack a corresponding item at the top.
It also works regardless of how many horizontal lines are added. Each person could add one, two, three, or any number of lines, and the 1:1 correspondence would remain. The more lines that are added, the more unpredictable the final outcome is.
One way of realizing how this works is to consider the analogy of coins in cups. You have n coins in n cups, representing the items at the bottom of the amidakuji. Then, each leg that is added represents swapping the position of two adjacent cups. Thus, it is obvious that in the end there will still be n cups, and each cup will have one coin, regardless of how many swaps you perform.
Permutation
Ghost Leg can transform the sequence of the input elements into a different order at the output. Thus, it is a permutation operator.Periodicity
For any Ghost Leg, after applying it a finite number of times, the output sequence will become identical to the original input sequence.i.e. Let M be a matrix representing a particular ghost leg, then Mn=I for some finite n.
Reversibility
For any Ghost Leg M,there must exist a Ghost Leg M-1,
such that M M-1=I
Odd/Even property of permutation
As each leg represents one permutation, the number of legs indicates the odd/even permutation property of the Ghost Leg:- odd number of legs = odd permutation
even number of legs = even permutation
Infinite Ghost Legs with same permutation
Every permutation must be possible to be expressed as a Ghost Leg, but a particular permutation does not correspond to a unique Ghost Leg.There are an infinite number of Ghost Legs representing the same permutation.
Prime
As there are an infinite number of Ghost Legs representing a particular permutation, it is obvious those Ghost Legs have a kind of equivalence. Among those equivalent Ghost Legs, the one(ones) which have smallest number of legs are called Prime.Bubble sort and highest simplicity
A Ghost Leg can be constructed arbitrarily, but such a Ghost Leg is not necessarily prime. It can be proven that only those Ghost Legs constructed by bubble sortBubble sort
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
contains the least number of legs, and hence is prime. This is equivalent to saying that bubble sort performs the minimum number of adjacent exchanges to sort a sequence.
Maximum number of legs of prime
For a permutation with n elements, the maximum number of neighbor exchanging =In the same way, the maximum number of legs in a prime with n tracks =
Bubblization
For an arbitrary Ghost Leg, it is possible to transform it into prime by a procedure called bubblization.When bubblization operates, the following two identities are repeatedly applied in order to move and eliminate "useless" legs.
- ⇒
- ⇒
When the two identities cannot be applied any more, the ghost leg is proved to be exactly the same as the Ghost Leg constructed by bubble sort
Bubble sort
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
, thus bubblization can reduce Ghost Legs to primes.
Randomness
Since, as mentioned above, an odd number of legs produces an odd permutation and an even number of legs produces an even permutation, a given number of legs can produce a maximum of half the total possible permutations (less than half if the number of legs is small relative to the number of tracks, reaching half as the number of legs increases beyond a certain critical number).If the legs are drawn randomly (for reasonable definitions of "drawn randomly"), the evenness of the distribution of permutations increases with the number of legs. If the number of legs is small relative to number of tracks, the probabilities of different attainable permutations may vary greatly; for large numbers of legs the probabilities of different attainable permutations approach equality.
Games
An early Sega Master SystemSega Master System
The is a third-generation video game console that was manufactured and released by Sega in 1985 in Japan , 1986 in North America and 1987 in Europe....
game called Psycho Fox
Psycho Fox
Psycho Fox is a video game published by Sega for the Sega Master System in 1989.In Psycho Fox, an evil god named Madfox Daimyojin has corrupted the land. The people who want him gone send a hero, Psycho Fox, to get rid of the evil god.-Gameplay:...
uses the mechanics of an Amidakuji board as a means to bet a bag of coins on a chance at a prize at the top of the screen.
Konami
Konami
is a Japanese leading developer and publisher of numerous popular and strong-selling toys, trading cards, anime, tokusatsu, slot machines, arcade cabinets and video games...
produced an arcade game named Amidar
Amidar
Amidar is an arcade game programmed by Konami and published in 1981 by Stern. Its basic format is similar to that of Pac-Man: the player moves around a fixed rectilinear lattice, attempting to visit each location on the board while avoiding the enemies...
which uses an Amidakuji board and rules as a setting for a Pac-Man
Pac-Man
is an arcade game developed by Namco and licensed for distribution in the United States by Midway, first released in Japan on May 22, 1980. Immensely popular from its original release to the present day, Pac-Man is considered one of the classics of the medium, virtually synonymous with video games,...
/Qix
Qix
Qix is an arcade game, released by Taito America Corporation in 1981.-Gameplay:The objective of Qix is to fence off, or “claim”, a supermajority of the playfield...
like game.
New Super Mario Bros.
New Super Mario Bros.
is a side-scrolling platform video game published and developed by Nintendo for the Nintendo DS handheld game console. The game was released in North America and Japan in May 2006 and in Australia and Europe in June 2006...
and Wario: Master of Disguise
Wario: Master of Disguise
Wario: Master of Disguise, known in Japan as , is a platforming video game developed by Suzak, and published by Nintendo for the Nintendo DS handheld video game console. The game was released on January 18, 2007 in Japan, and was released on March 5 in North America. The game's Japanese title...
feature an Amidakuji-style minigame in which the player uses the stylus
Nintendo DS
The is a portable game console produced by Nintendo, first released on November 21, 2004. A distinctive feature of the system is the presence of two separate LCD screens, the lower of which is a touchscreen, encompassed within a clamshell design, similar to the Game Boy Advance SP...
to trace lines that will lead the character down the right path.
In Mario Party
Mario Party
is a party video game for the Nintendo 64 game console, developed by Hudson Soft and published by Nintendo. It was released in Japan on December 14, 1998, in North America on February 8, 1999, and in Europe on March 9, 1999...
there is a mini game where one of the four players pours money into an Amidakuji made out of pipes. The goal is to try to choose the path that leading to the character controlled by the player.
The BoSpider in Mega Man X
Mega Man X (video game)
Mega Man X, known in Japan as , is a video game developed by Capcom for the Super Nintendo Entertainment System . It is the first Mega Man game for the 16-bit console and the first game in the Mega Man X series, a spin-off of the original Mega Man series that began on the SNES's predecessor, the...
and Maverick Hunter X descends onto the player via an Amidakuji path.
External links
- http://www.webcitation.org/query?url=http://www.geocities.com/Athens/Acropolis/7247/amidakuji.html&date=2009-10-25+05:45:20
- Ladders: A Research Paper by David Senft (PDF)