Tower of Hanoi
The Tower of Hanoi is a mathematical game or puzzle. It consists of a number of disks of different sizes, which can slide onto any rod; the puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: Only one disk can be moved at a time; each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod. No larger disk may be placed on top of a smaller disk. With 3 disks, the puzzle can be solved in 7 moves; the minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks. The puzzle was invented by the French mathematician Édouard Lucas in 1883. There is a story about an Indian temple in Kashi Vishwanath which contains a large room with three time-worn posts in it, surrounded by 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks in accordance with the immutable rules of Brahma since that time.
The puzzle is therefore known as the Tower of Brahma puzzle. According to the legend, when the last move of the puzzle is completed, the world will end. If the legend were true, if the priests were able to move disks at a rate of one per second, using the smallest number of moves it would take them 264 − 1 seconds or 585 billion years to finish, about 42 times the current age of the Universe. There are many variations on this legend. For instance, in some tellings the temple is a monastery, the priests are monks; the temple or monastery may be said to be in different parts of the world—including Hanoi, Vietnam—and may be associated with any religion. In some versions other elements are introduced, such as the fact that the tower was created at the beginning of the world, or that the priests or monks may make only one move per day; the puzzle can be played with any number of disks, although many toy versions have around 7 to 9 of them. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.
A simple solution for the toy puzzle is to alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it to the next position in the same direction. If there is no tower position in the chosen direction, move the piece to the opposite end, but continue to move in the correct direction. For example, if you started with three pieces, you would move the smallest piece to the opposite end continue in the left direction after that; when the turn is to move the non-smallest piece, there is only one legal move. Doing this will complete the puzzle in the fewest moves. For an number of disks: make the legal move between pegs A and B, make the legal move between pegs A and C, make the legal move between pegs B and C, repeat until complete. For an odd number of disks: make the legal move between pegs A and C, make the legal move between pegs A and B, make the legal move between pegs B and C, repeat until complete. In each case, a total of 2n − 1 moves are made.
Another way to generate the unique optimal iterative solution: Number the disks 1 through n. If n is odd, the first move is from peg A to peg C. If n is the first move is from peg A to peg B. Now, add these constraints: No odd disk may be placed directly on an odd disk. No disk may be placed directly on an disk. There will sometimes be two possible pegs: one will have disks, the other will be empty. Place the disk on the non-empty peg. Never move a disk twice in succession. Considering those constraints after the first move, there is only one legal move at every subsequent turn; the sequence of these unique moves is an optimal solution to the problem equivalent to the iterative solution described above. The key to solving a problem recursively is to recognize that it can be broken down into a collection of smaller sub-problems, to each of which that same general solving procedure that we are seeking applies, the total solution is found in some simple way from those sub-problems' solutions; each of thus created sub-problems being "smaller" guarantees that the base case will be reached.
Thence, for the Towers of Hanoi: label the pegs A, B, C, let n be the total number of disks, number the disks from 1 to n. Assuming all n disks are distributed in valid arrangements among the pegs. Rules are not violated, by assumption; this leaves the disk m. Move the disk m from the source to the target peg, guaranteed to be a valid move, by the assumptions — a simple step. Move the m − 1 disks that we have just placed on the spare, from the spare to the target peg by the same general solving procedure, so they are placed on top of the disk m without violating the rules; the base case being to move 0 disks, that is, do nothing – which doesn't violate the rules. The full Tower of Hanoi solution consists of moving n disks from the source peg A to the target peg C, using B as the sp
Gomoku called Five in a Row, is an abstract strategy board game. It is traditionally played with Go pieces on a Go board, using 15×15 of the 19×19 grid intersections; because pieces are not moved or removed from the board, Gomoku may be played as a paper-and-pencil game. The game is known in several countries under different names. Players alternate turns placing a stone of their color on an empty intersection; the winner is the first player to form an unbroken chain of five stones horizontally, vertically, or diagonally. Gomoku has existed in Japan since the Meiji Restoration; the name "Gomoku" is from the Japanese language. Go means five, moku is a counter word for pieces and narabe means line-up; the game is popular in Korea, where it is called omok which has the same structure and origin as the Japanese name. The Japanese call this game Go-moku. In the nineteenth century, the game was introduced to Britain where it was known as Go Bang, said to be a corruption of the Japanese word goban, said to be adopted from Chinese k'i pan "go-board."
Besides many variations around the world, the Swap2 rule is adapted in tournaments among professional players, including Gomoku World Championships. In Swap2 rule, the first player starts by placing three stones on the board; the second player next can select one of these three options: choose to play black, or to play white and place one more stone, or to place two more stones to change the shape and let the first player choose the color. This is a more elaborate pie rule. Swap2 makes the game fairer. Like other rules and variations, 100% fairness can be reached by playing two alternating games for each point. Most variations are based on Standard gomoku. Free-style gomoku requires a row of five or more stones for a win. Standard gomoku requires a row of five stones for a win: rows of six or more, called overlines, do not count. Black was long known to have a big advantage before L. Victor Allis proved that black could force a win. So a number of variations are played with extra rules; the rule of three and three bans a move that forms two open rows of three stones.
The rule of four and four bans a move that forms two rows of four stones. Alternatively, a handicap may be given such that after the first "three and three" play has been made, the opposing player may place two stones as their next turn; these stones must block an opponent's row of three. Efforts to improve fairness by reducing first-move advantage include the rule of swap, generalizable as "swap-" and characterizable as a compounded and iterated version of the pie rule: One player places on the board x stones of the first-moving color and a lesser number y stones of the second-moving color. Renju is played on a 15×15 board, with the rules of three and three and four, overlines applied to Black only and with opening rules, some of which are following the swap pattern. In Caro, the winner must have an unbroken row of five stones and this row must not be blocked at either end; this rule provides more power for White to defend. Omok is played the same as Standard Gomoku; the overlines rules, do not count.
Ninuki-renju or Wu is a variant. M,n,k-games are a generalization of gomoku to a board with m×n intersections, k in a row needed to win. Connect games are another generalization of gomoku to a board with m×n intersections, k in a row needed to win, p stones for each player to place, q stones for the first player to place for the first move only; each player may play only at the lowest unoccupied place in a column. In particular, Connect is called Connect6; this game on the 15×15 board is adapted from the paper "Go-Moku and Threat-Space Search". The opening moves show black's advantage. An open row of three has to be blocked or countered with a threat elsewhere on the board. If not blocked or countered, the open row of three will be extended to an open row of four, which threatens to win in two ways. White has to block open rows of three at moves 10, 14, 16 and 20, but black only has to do so at move 9. Move 20 is a blunder for white. Black can now force a win against any defence by white, starting with move 21.
There are two forcing sequences for black, depending on whether white 22 is played next to black 15 or black 21. The diagram on the right shows the first sequence. All the moves for white are forced; such long forcing sequences are typical in gomoku, expert player
Draughts or checkers is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. Draughts developed from alquerque; the name derives from the verb to move. The most popular forms are English draughts called American checkers, played on an 8×8 checkerboard. There are many other variants played on 8×8 boards. Canadian checkers and Singaporean/Malaysian checkers are played on a 12×12 board; the 8×8 variant of draughts was weakly solved in 2007 by the team of Canadian computer scientist Jonathan Schaeffer. From the standard starting position, both players can guarantee a draw with perfect play. Draughts is played on opposite sides of the gameboard. One player has the dark pieces. Players alternate turns. A player may not move an opponent's piece. A move consists of moving a piece diagonally to an adjacent unoccupied square. If the adjacent square contains an opponent's piece, the square beyond it is vacant, the piece may be captured by jumping over it.
Only the dark squares of the checkered board are used. A piece may move only diagonally into an unoccupied square; when presented, capturing is mandatory in most official rules, although some rule variations make capturing optional. In all variants, the player without pieces remaining, or who cannot move due to being blocked, loses the game. Uncrowned pieces move one step diagonally forwards, capture an opponent's piece by moving two consecutive steps in the same line, jumping over the piece on the first step. Multiple enemy pieces can be captured in a single turn provided this is done by successive jumps made by a single piece. In English draughts men can jump only forwards; when a man reaches the kings row, it becomes a king, is marked by placing an additional piece on top of the first man, acquires additional powers including the ability to move backwards and capture backwards. Like men, a king can make successive jumps in a single turn provided that each jump captures an enemy man or king.
In international draughts, kings move any distance along unblocked diagonals, may capture an opposing man any distance away by jumping to any of the unoccupied squares beyond it. Because jumped pieces remain on the board until the turn is complete, it is possible to reach a position in a multi-jump move where the flying king is blocked from capturing further by a piece jumped. Flying kings are not used in English draughts. In most non-English languages, draughts is called dame, damas, or a similar term that refers to ladies; the pieces are called men, stones, "peón" or a similar term. In these languages, the queen in chess or in card games is called by the same term as the kings in draughts. A case in point includes the Greek terminology, in which draughts is called "ντάμα", one term for the queen in chess; the World Championship in English draughts began in 1840. The winners in men's have been from the United Kingdom, United States and most Italy; the women's championship in English draughts started in 1993.
The women's winners have been from Ireland and Ukraine. The World Championship in international draughts began in 1885 in France, since 1948 has been organized by the World Draughts Federation, it occurs every two years. In years following the tournament, the World Title match takes place; the men's championship has had winners from the Netherlands, the Soviet Union, Senegal and Russia. The first Women's World Championship was held in 1973; the World Junior Championship has been played since 1971. European Championships have been held since 1965 and 2000. Other official World Championships began as follows: Brazilian draughts, in 1985. Blue and Gray: On a 9×9 board, each side has 17 guard pieces that move and jump in any direction, to escort a captain piece which races to the center of the board to win. Cheskers: A variant invented by Solomon Golomb; each player begins with a bishop and a camel, men reaching the back rank promote to a bishop, camel, or king. Damath: A variant utilizing math principles and numbered chips popular in the Philippines.
Dameo: A variant played on an 8×8 board and capture rules are similar to those of Armenian draughts. A special "sliding" move is used for moving a line of checkers similar to the movement rule in Epaminondas. By Christian Freeling. Hexdame: A literal adaptation of international draughts to a hexagonal gameboard. By Christian Freeling. Lasca: A checkers variant on a 7×7 board, with 25 fields used. Jumped pieces are placed under the jumper. Only the top piece of a jumped; this variant was invented by World Chess Champion Emanuel Lasker. Philosophy shogi checkers: A variant on a 9×9 board, game endi
Nine men's morris
Nine men's morris is a strategy board game for two players dating at least to the Roman Empire. The game is known as nine-man morris, mills, the mill game, merrills, marelles and ninepenny marl in English; the game has been called cowboy checkers and is sometimes printed on the back of checkerboards. Nine men's morris is a solved game -- one, its name derives from the Latin word merellus,'gamepiece'. Three main alternative variations of the game are three and twelve men's morris; the board consists of a grid with twenty-four points. Each player has nine pieces, or "men" coloured black and white. Players try to form'mills'—three of their own men lined horizontally or vertically—allowing a player to remove an opponent's man from the game. A player wins by leaving them without a legal move; the game proceeds in three phases: Placing men on vacant points Moving men to adjacent points Moving men to any vacant point when the player has been reduced to three men The game begins with an empty board. The players determine who plays first take turns placing their men one per play on empty points.
If a player is able to place three of their pieces on contiguous points in a straight line, vertically or horizontally, they have formed a mill and may remove one of their opponent's pieces from the board and the game, with the caveat that a piece in an opponent's mill can only be removed if no other pieces are available. After all men have been placed, phase two begins. Players continue to this time moving a man to an adjacent point. A piece may not "jump" another piece. Players continue to try to remove their opponent's pieces as in phase one. A player can "break" a mill by moving one of his pieces out of an existing mill moving it back to form the same mill a second time, each time removing one of his opponent's men; the act of removing an opponent's man is sometimes called "pounding" the opponent. When one player has been reduced to three men, phase three begins; when a player is reduced to three pieces, there is no longer a limitation on that player of moving to only adjacent points: The player's men may "fly" from any point to any vacant point.
Some rules sources say this is the way the game is played, some treat it as a variation, some do not mention it at all. A 19th-century games manual calls this the "truly rustic mode of playing the game". Flying was introduced to compensate. At the beginning of the game, it is more important to place pieces in versatile locations rather than to try to form mills and make the mistake of concentrating one's pieces in one area of the board. An ideal position, which results in a win, allows a player to shuttle one piece back and forth between two mills, removing a piece every turn. Three men's morris called nine-holes, is played on the points of a grid of 2×2 squares, or in the squares of a grid of 3×3 squares, as in tic-tac-toe; the game is for two players. The players put one man on the board in each of their first three plays, winning if a mill is formed. After that, each player moves one of his men, according to one of the following rules versions: A player wins by forming a mill. H. J. R. Murray calls version No. 1 "nine holes", version No. 2 "three men's morris" or "the smaller merels".
Six men's morris gives each player six pieces and is played without the outer square of the board for nine men's morris. Flying is not permitted; the game was popular in Italy and England during the Middle Ages but was obsolete by 1600. This board is used for five men's morris. Seven men's morris uses this board with a cross in the center. Twelve men's morris gives each player twelve pieces; this means. This variation on the game is popular amongst rural youth in South Africa where it is known as morabaraba and is now recognized as a sport in that country. H. J. R. Murray calls the game "the larger merels"; this board is used for eleven men's morris. This variant was invented by Emanuel Lasker, chess world champion from 1894 to 1921, it is based on the rules of nine men’s morris, but there are two differences: each player gets ten pieces. This means each player can choose to either place a new piece or to move one of his pieces on the board; this variant is more complex than nine men's morris, draws are less likely.
According to R. C. Bell, the earliest known board for the game includes diagonal lines and was "cut into the roofing slabs of the temple at Kurna in Egypt". However, Friedrich Berger wrote that some of the diagrams at Kurna include Coptic crosses, making it "doubtful" that the diagrams date to 1400 BCE. Berger concluded, "certainly they cannot be dated."One of the earliest mentions of the game may be in Ovid's Ars Amatoria. In book III, after discussing latrones, a popular board game, Ovid wrote: There is another game divided into as many parts as there are months in the year. A table has three pieces on either side, it is a bad thing for a woman not to know how to play, for love comes into being during play. Berger believes the game was "probably well known by the Romans", as there are many boards on Roma
A chess variant is a game "related to, derived from, or inspired by chess". Such variants can differ from chess in many different ways, ranging from minor modifications to the rules, to games which have only a slight resemblance. "International" or "Western" chess itself is one of a family of games which have related origins and could be considered variants of each other. Chess is theorised to have been developed from chaturanga, from which other members of this family, such as shatranj and xiangqi evolved. Many chess variants are designed to be played with the equipment of regular chess. Although most variants have a similar public-domain status as their parent game, some have been made into commercial, proprietary games. Just as in traditional chess, chess variants can be played over-the-board, by correspondence, or by computer; some internet chess servers facilitate the play of some variants in addition to orthodox chess. In the context of chess problems, chess variants are called fairy chess.
Fairy chess variants tend to be created for problem composition rather than actual play. There are thousands of known chess variants; the Classified Encyclopedia of Chess Variants catalogues around two thousand, with the preface noting that — with creating a chess variant being trivial — many were considered insufficiently notable for inclusion. The origins of the chess family of games can be traced to the game of chaturanga during the time of the Gupta Empire in India. Over time, as the game spread geographically, modified versions of the rules became popular in different regions. In Sassanid Persia, a modified form became known as shatranj. Modifications made to this game in Europe resulted in the modern game. Courier chess was a popular variant in medieval Europe, which had a significant impact on the "main" variant's development. Other games in the chess family, such as shogi, xiangqi, are developments from chaturanga made in other regions; these related games are considered chess variants, though the majority of variants are, modifications of chess.
The basic rules of chess were not standardised until the 19th century, the history of chess prior to this involves many variants, with the most popular modifications spreading and forming the modern game. While some regional variants have historical origins comparable to or older than chess, the majority of variants are express attempts by individuals or small groups to create new games with chess as a starting point. In most cases the creators are attempting to create new games of interest to chess enthusiasts or a wider audience. Variants have the same public domain status as chess, though a few are proprietary, the materials for play are released as commercial products; the variations from chess may be done to address a perceived issue with the standard game. For example, Chess960, which randomises the starting positions, was invented by Bobby Fischer to combat what he perceived to be the detrimental dominance of opening preparation in chess. Several variants introduce complications to the standard game, providing an additional challenge for experienced players, for example in Kriegspiel, where players cannot see the pieces of their opponent.
A handful, such as No Stress Chess, attempt to simplify the game, so as to be attractive to chess beginners. The table below details some, but not all, of the ways in which variants can differ from the orthodox game: Variants can themselves be developed into further sub-variants, for example Horde chess is a variation upon Dunsany's Chess; some variations are created for the purpose of composing interesting puzzles, rather than being intended for full games. This field of composition is known as fairy chess. Fairy chess gave rise to the term "fairy chess piece", used more broadly across writings about chess variants to describe chess pieces with movement rules other than those of the standard chess pieces. Forms of standardised notation have been devised to systematically describe the movement of these. A distinguishing feature of several chess variants is the presence of one or more fairy pieces. Physical models of common fairy pieces are sold by major chess set suppliers. Individuals notable for creating multiple chess variants include V. R. Parton, Ralph Betza, Philip M. Cohen and George R. Dekle Sr.
Some board game designers, notable for works across a wider range of board games, have attempted to create chess variants. These include Andy Looney. Several chess masters have developed variants, such as Chess960 by Bobby Fischer, Capablanca Chess by José Raúl Capablanca, Seirawan chess by Yasser Seirawan. While chess and xiangqi have professional circuits as well as many organised tournaments for amateurs, play of the majority of chess variants is predominately on a casual basis; some variants have had significant tournaments. Several Gliński's hexagonal chess tournaments were played at the height of the variant's popularity in the 1970s and 1980s. Chess960 has been the subject of tournaments, including in 2018 an "unofficial world championship" between reigning World Chess Champion Magnus Carlsen and fellow high-ranking Grandmaster Hikaru Nakamura. Several internet chess servers facilitate live play of popular variants, including Chess.com and the Free Internet Chess Server. The software packages Zillions of Games and Fairy-Max have been programmed to support many chess variants.
Play in most chess variants is sufficiently similar to chess that games can be recorded with algebraic notation, although additions to this are required. For example, the third dimension in Millennium 3D Chess means that move notatio
Janggi, sometimes called Korean chess, is a strategy board game popular in Korea. The game derived from xiangqi and is similar to it, including the starting position of the pieces, the 9×10 gameboard, but without the xiangqi "river" dividing the board horizontally in the middle. Janggi is played on a board nine lines wide by ten lines long; the game is sometimes fast paced due to the jumping cannons and the long-range elephants, but professional games most last over 150 moves and so are slower than those of Western chess. In 2009, the first world janggi tournament was held in People's Republic of China; the board is composed of 90 intersections of 10 horizontal rows. The board has nearly the same layout as that used in xiangqi, except the janggi board has no "river" in the central row; the pieces consist of disks marked with identifying characters and are placed on the line intersections. Janggi pieces are traditionally octagonal in shape, differ in size according to their rank; the sides are Blue, versus Red.
Each side has a palace, 3 lines by 3 lines in the centre of their side of the board against the back edge. The palace contains four diagonal lines extending outwards from the centre; the pieces are labeled with hanja. The labels on the blue pieces are all written in the semi-cursive script. For instance, the blue chariot or cha has a cursive version of 車, which looks something like 车; the pieces that are equivalent to the kings in Western chess are referred to as military generals in Korean. They are labelled with the Chinese character Han on the red side, Cho on the blue side, they represent the rival states of Han and Chu that fought for power in the post-Qin Dynasty interregnum period in China. In North Korea, the Chu–Han setup is not used. Both kings can be referred to as. Janggi differs from its Chinese counterpart in that the janggi general starts the game from the central intersection of the palace, rather than from the centre intersection of the back edge; the general may move one step per turn along marked board lines to any of the nine points within the palace.
There are four diagonal lines in the palace connecting the centre position to the corners. When the general is checkmated the game is lost; the general cannot leave the palace under any circumstances. If the generals come to face each other across the board, the player to move does not move away, this is bikjang—a draw; this rule is different from that of xiangqi. If there is no move for the general to make without getting into check or checkmate, but it is safe for it to stand still, the person may pass their turn; the pieces are civilian government officials. They are called guards, since they stay close to the general. Other names are mandarins; the guards start to the right of the general on the first rank. They move the same as one step per turn along marked lines in the palace; the guards are one of the weakest pieces. They are valuable for protecting the general. Called the horse or ma, this piece moves and captures like the horse in xiangqi. A horse can be transposed with an adjacent elephant in the initial setup.
The elephants begin the game to the right of the guards. They move one point orthogonally followed by two points diagonally away from their starting point, ending on the opposite corner of a 2×3 rectangle. Like the horse, the elephant is blocked from moving by any intervening pieces. Unlike xiangqi, which confines elephants to one side of the board behind a "river", in janggi there is no river and elephants are not limited to one side of the board; the janggi elephant can therefore be used more offensively than the xiangqi elephant. An elephant can be transposed with an adjacent horse in the initial setup; these are labelled cha. Like the rook in Western chess, the chariot moves and captures in a straight line either horizontally or vertically. Additionally, the chariot may move along the diagonal lines inside either palace, but only in a straight line; the two chariots begin the game in the corners. The chariot is the most powerful piece in the game; these are labelled po. Each player has two cannons.
The cannons are placed on the row behind the soldiers, directly in front of the horses. The cannon moves by jumping another piece vertically; the jump can be performed over any distance provided that there is one piece anywhere between the original position and the target. In order to capture a piece, there must be one piece between the cannon and the piece to be captured; the cannon moves to that point and captures the piece. They may move or capture diagonally along the diagonal lines in either palace, provided there is an intervening piece in the centre They are powerful at the beginning of the game when "hurdles" are plentiful, but lose value with attrition; the other piece over whic
A cellular automaton is a discrete model studied in computer science, physics, complexity science, theoretical biology and microstructure modeling. Cellular automata are called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, iterative arrays. A cellular automaton consists of a regular grid of cells, each in one of a finite number of states, such as on and off; the grid can be in any finite number of dimensions. For each cell, a set of cells called. An initial state is selected by assigning a state for each cell. A new generation is created, according to some fixed rule that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood; the rule for updating the state of cells is the same for each cell and does not change over time, is applied to the whole grid though exceptions are known, such as the stochastic cellular automaton and asynchronous cellular automaton. The concept was discovered in the 1940s by Stanislaw Ulam and John von Neumann while they were contemporaries at Los Alamos National Laboratory.
While studied by some throughout the 1950s and 1960s, it was not until the 1970s and Conway's Game of Life, a two-dimensional cellular automaton, that interest in the subject expanded beyond academia. In the 1980s, Stephen Wolfram engaged in a systematic study of one-dimensional cellular automata, or what he calls elementary cellular automata. Wolfram published A New Kind of Science in 2002, claiming that cellular automata have applications in many fields of science; these include cryptography. The primary classifications of cellular automata, as outlined by Wolfram, are numbered one to four, they are, in order, automata in which patterns stabilize into homogeneity, automata in which patterns evolve into stable or oscillating structures, automata in which patterns evolve in a chaotic fashion, automata in which patterns become complex and may last for a long time, with stable local structures. This last class are thought to be computationally universal, or capable of simulating a Turing machine.
Special types of cellular automata are reversible, where only a single configuration leads directly to a subsequent one, totalistic, in which the future value of individual cells only depends on the total value of a group of neighboring cells. Cellular automata can simulate a variety of real-world systems, including biological and chemical ones. One way to simulate a two-dimensional cellular automaton is with an infinite sheet of graph paper along with a set of rules for the cells to follow; each square is called a "cell" and each cell has two possible states and white. The neighborhood of a cell is the nearby adjacent, cells; the two most common types of neighborhoods are the von Neumann neighborhood and the Moore neighborhood. The former, named after the founding cellular automaton theorist, consists of the four orthogonally adjacent cells; the latter includes the von Neumann neighborhood as well as the four diagonally adjacent cells. For such a cell and its Moore neighborhood, there are 512 possible patterns.
For each of the 512 possible patterns, the rule table would state whether the center cell will be black or white on the next time interval. Conway's Game of Life is a popular version of this model. Another common neighborhood type is the extended von Neumann neighborhood, which includes the two closest cells in each orthogonal direction, for a total of eight; the general equation for such a system of rules is kks, where k is the number of possible states for a cell, s is the number of neighboring cells used to determine the cell's next state. Thus, in the two dimensional system with a Moore neighborhood, the total number of automata possible would be 229, or 1.34×10154. It is assumed that every cell in the universe starts in the same state, except for a finite number of cells in other states. More it is sometimes assumed that the universe starts out covered with a periodic pattern, only a finite number of cells violate that pattern; the latter assumption is common in one-dimensional cellular automata.
Cellular automata are simulated on a finite grid rather than an infinite one. In two dimensions, the universe would be a rectangle instead of an infinite plane; the obvious problem with finite grids is. How they are handled will affect the values of all the cells in the grid. One possible method is to allow the values in those cells to remain constant. Another method is to define neighborhoods differently for these cells. One could say that they have fewer neighbors, but one would have to define new rules for the cells located on the edges; these cells are handled with a toroidal arrangement: when one goes off the top, one comes in at the corresponding position on the bottom, when one goes off the left, one comes in on the right. This can be visualized as taping the left and right edges of the rectangle to form a tube taping the top and bottom edges of the tube to form a torus. Universes of other dimensions are handled similarly; this solves bounda