1.
Chess
–
Chess is a two-player strategy board game played on a chessboard, a checkered gameboard with 64 squares arranged in an eight-by-eight grid. Chess is played by millions of people worldwide, both amateurs and professionals, each player begins the game with 16 pieces, one king, one queen, two rooks, two knights, two bishops, and eight pawns. Each of the six piece types moves differently, with the most powerful being the queen, the objective is to checkmate the opponents king by placing it under an inescapable threat of capture. To this end, a players pieces are used to attack and capture the opponents pieces, in addition to checkmate, the game can be won by voluntary resignation by the opponent, which typically occurs when too much material is lost, or if checkmate appears unavoidable. A game may result in a draw in several ways. Chess is believed to have originated in India, some time before the 7th century, chaturanga is also the likely ancestor of the Eastern strategy games xiangqi, janggi and shogi. The pieces took on their current powers in Spain in the late 15th century, the first generally recognized World Chess Champion, Wilhelm Steinitz, claimed his title in 1886. Since 1948, the World Championship has been controlled by FIDE, the international governing body. There is also a Correspondence Chess World Championship and a World Computer Chess Championship, online chess has opened amateur and professional competition to a wide and varied group of players. There are also many variants, with different rules, different pieces. FIDE awards titles to skilled players, the highest of which is grandmaster, many national chess organizations also have a title system. However, these are not recognised by FIDE, the term master may refer to a formal title or may be used more loosely for any skilled player. Until recently, chess was a sport of the International Olympic Committee. Chess was included in the 2006 and 2010 Asian Games, since the 1990s, computer analysis has contributed significantly to chess theory, particularly in the endgame. The computer IBM Deep Blue was the first machine to overcome a reigning World Chess Champion in a match when it defeated Garry Kasparov in 1997, the rise of strong computer programs that can be run on hand-held devices has led to increasing concerns about cheating during tournaments. The official rules of chess are maintained by FIDE, chesss international governing body, along with information on official chess tournaments, the rules are described in the FIDE Handbook, Laws of Chess section. Chess is played on a board of eight rows and eight columns. The colors of the 64 squares alternate and are referred to as light, the chessboard is placed with a light square at the right-hand end of the rank nearest to each player

2.
Game theory
–
Game theory is the study of mathematical models of conflict and cooperation between intelligent rational decision-makers. Game theory is used in economics, political science, and psychology, as well as logic, computer science. Originally, it addressed zero-sum games, in one persons gains result in losses for the other participants. Today, game theory applies to a range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals. Modern game theory began with the idea regarding the existence of equilibria in two-person zero-sum games. Von Neumanns original proof used Brouwer fixed-point theorem on continuous mappings into compact convex sets and his paper was followed by the 1944 book Theory of Games and Economic Behavior, co-written with Oskar Morgenstern, which considered cooperative games of several players. The second edition of this provided an axiomatic theory of expected utility. This theory was developed extensively in the 1950s by many scholars, Game theory was later explicitly applied to biology in the 1970s, although similar developments go back at least as far as the 1930s. Game theory has been recognized as an important tool in many fields. With the Nobel Memorial Prize in Economic Sciences going to game theorist Jean Tirole in 2014, John Maynard Smith was awarded the Crafoord Prize for his application of game theory to biology. Early discussions of examples of two-person games occurred long before the rise of modern, the first known discussion of game theory occurred in a letter written by Charles Waldegrave, an active Jacobite, and uncle to James Waldegrave, a British diplomat, in 1713. In this letter, Waldegrave provides a mixed strategy solution to a two-person version of the card game le Her. James Madison made what we now recognize as an analysis of the ways states can be expected to behave under different systems of taxation. In 1913 Ernst Zermelo published Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels and it proved that the optimal chess strategy is strictly determined. This paved the way for more general theorems, the Danish mathematician Zeuthen proved that the mathematical model had a winning strategy by using Brouwers fixed point theorem. In his 1938 book Applications aux Jeux de Hasard and earlier notes, Borel conjectured that non-existence of mixed-strategy equilibria in two-person zero-sum games would occur, a conjecture that was proved false. Game theory did not really exist as a field until John von Neumann published a paper in 1928. Von Neumanns original proof used Brouwers fixed-point theorem on continuous mappings into compact convex sets and his paper was followed by his 1944 book Theory of Games and Economic Behavior co-authored with Oskar Morgenstern

3.
Simultaneous game
–
In game theory, a simultaneous game is a game where each player chooses his action without knowledge of the actions chosen by other players. Normal form representations are used for simultaneous games. Rock-Paper-Scissors, a widely played game, is a real life example of a simultaneous game. Both make a decision at the time, randomly, without prior knowledge of the opponents decision. There are two players in game and each of them has 3 different strategies to make decision. We will display Player 1’s strategies as rows and Player 2’s strategies as columns, in the table, the numbers in red represent the payoff to Player 1, the numbers in blue represent the payoff to Player 2. Hence, the pay off for a 2 player game in Rock-Paper-Scissors will look like this, In game theory terms, Prisoner dilemma is an example of simultaneous game

4.
Extensive-form game
–
Extensive-form games also allow representation of incomplete information in the form of chance events encoded as moves by nature. Whereas the rest of this article follows this approach with motivating examples. This general definition was introduced by Harold W. Kuhn in 1953, each players subset of nodes is referred to as the nodes of the player. Each node of the Chance player has a probability distribution over its outgoing edges, at any given non-terminal node belonging to Chance, an outgoing branch is chosen according to the probability distribution. A pure strategy for a player thus consists of a selection—choosing precisely one class of outgoing edges for every information set, in a game of perfect information, the information sets are singletons. Its less evident how payoffs should be interpreted in games with Chance nodes and these can be made precise using epistemic modal logic, see Shoham & Leyton-Brown for details. A perfect information two-player game over a tree can be represented as an extensive form game with outcomes. Examples of such games include tic-tac-toe, chess, and infinite chess, a game over an expectminimax tree, like that of backgammon, has no imperfect information but has moves of chance. For example, poker has both moves of chance, and imperfect information, the numbers by every non-terminal node indicate to which player that decision node belongs. The numbers by every terminal node represent the payoffs to the players, the labels by every edge of the graph are the name of the action that edge represents. The initial node belongs to player 1, indicating that player 1 moves first, play according to the tree is as follows, player 1 chooses between U and D, player 2 observes player 1s choice and then chooses between U and D. The payoffs are as specified in the tree, there are four outcomes represented by the four terminal nodes of the tree, and. The payoffs associated with each outcome respectively are as follows, if player 1 plays D, player 2 will play U to maximise his payoff and so player 1 will only receive 1. However, if player 1 plays U, player 2 maximises his payoff by playing D, player 1 prefers 2 to 1 and so will play U and player 2 will play D. This is the perfect equilibrium. An advantage of representing the game in this way is that it is clear what the order of play is, the tree shows clearly that player 1 moves first and player 2 observes this move. However, in some games play does not occur like this, one player does not always observe the choice of another. An information set is a set of decision nodes such that, in extensive form, an information set is indicated by a dotted line connecting all nodes in that set or sometimes by a loop drawn around all the nodes in that set

5.
Combinatorial game
–
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been confined to two-player games that have a position in which the players take turns changing in defined ways or moves to achieve a defined winning condition. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, in CGT, the moves in these and other games are represented as a game tree. CGT has a different emphasis than traditional or economic theory, which was initially developed to study games with simple combinatorial structure. Essentially, CGT has contributed new methods for analyzing game trees, for using surreal numbers. The type of games studied by CGT is also of interest in artificial intelligence, in CGT there has been less emphasis on refining practical search algorithms, but more emphasis on descriptive theoretical results. An important notion in CGT is that of the solved game, for example, tic-tac-toe is considered a solved game, as it can be proven that any game will result in a draw if both players play optimally. Deriving similar results for games with rich combinatorial structures is difficult, for instance, in 2007 it was announced that checkers has been weakly solved—optimal play by both sides also leads to a draw—but this result was a computer-assisted proof. Other real world games are too complicated to allow complete analysis today. Applying CGT to a position attempts to determine the sequence of moves for both players until the game ends, and by doing so discover the optimum move in any position. In practice, this process is difficult unless the game is very simple. However, a number of fall into both categories. Nim, for instance, is an instrumental in the foundation of CGT. Tic-tac-toe is still used to basic principles of game AI design to computer science students. CGT arose in relation to the theory of games, in which any play available to one player must be available to the other as well. One very important such game is nim, which can be solved completely, Nim is an impartial game for two players, and subject to the normal play condition, which means that a player who cannot move loses. Their results were published in their book Winning Ways for your Mathematical Plays in 1982, however, the first work published on the subject was Conways 1976 book On Numbers and Games, also known as ONAG, which introduced the concept of surreal numbers and the generalization to games. On Numbers and Games was also a fruit of the collaboration between Berlekamp, Conway, and Guy, Combinatorial games are generally, by convention, put into a form where one player wins when the other has no moves remaining

6.
Backgammon
–
Backgammon is one of the oldest board games known. It is a two player game where playing pieces are moved according to the roll of dice, and a player wins by removing all of their pieces from the board before their opponent. Backgammon is a member of the family, one of the oldest classes of board games in the world. Backgammon involves a combination of strategy and luck, while the dice may determine the outcome of a single game, the better player will accumulate the better record over series of many games, somewhat like poker. With each roll of the dice, players must choose from options for moving their checkers. The optional use of a doubling cube allows players to raise the stakes during the game, like chess, backgammon has been studied with great interest by computer scientists. Owing to this research, backgammon software has been developed that is capable of beating world-class human players, Backgammon playing pieces are known variously as checkers, draughts, stones, men, counters, pawns, discs, pips, chips, or nips. The objective is to all of ones own checkers from the board before ones opponent can do the same. In the most often-played variants the checkers are scattered at first, as the playing time for each individual game is short, it is often played in matches where victory is awarded to the first player to reach a certain number of points. Each side of the board has a track of 12 long triangles, the points form a continuous track in the shape of a horseshoe, and are numbered from 1 to 24. In the most commonly used setup, each begins with fifteen checkers. The two players move their checkers in opposing directions, from the 24-point towards the 1-point, points 1 through 6 are called the home board or inner board, and points 7 through 12 are called the outer board. The 7-point is referred to as the bar point, and the 13-point as the midpoint, to start the game, each player rolls one die, and the player with the higher number moves first using the numbers shown on both dice. If the players roll the number, they must roll again. Both dice must land completely flat on the side of the gameboard. The players then alternate turns, rolling two dice at the beginning of each turn, after rolling the dice, players must, if possible, move their checkers according to the number shown on each die. For example, if the player rolls a 6 and a 3, the player must move one checker six points forward, and another or the same checker three points forward. The same checker may be moved twice, as long as the two moves can be separately and legally, six and then three, or three and then six

7.
Tic-tac-toe
–
Tic-tac-toe is a paper-and-pencil game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game, the following example game is won by the first player, X, Players soon discover that best play from both parties leads to a draw. Hence, tic-tac-toe is most often played by young children. The game can be generalized to an m, n, k-game in which two players alternate placing stones of their own color on an m×n board, with the goal of getting k of their own color in a row. Hararys generalized tic-tac-toe is an even broader generalization of tic tac toe and it can also be generalized as a nd game. Tic-tac-toe is the game where n equals 3 and d equals 2, according to Claudia Zaslavskys book Tic Tac Toe, And Other Three-In-A Row Games from Ancient Egypt to the Modern Computer, tic-tac-toe could be traced back to ancient Egypt. Another closely related ancient game is Three Mens Morris which is played on a simple grid. An early variation of tic-tac-toe was played in the Roman Empire and it was called Terni Lapilli and instead of having any number of pieces, each player only had three, thus they had to move them around to empty spaces to keep playing. The games grid markings have been found chalked all over Rome, the different names of the game are more recent. The first print reference to noughts and crosses, the British name, in his novel Can You Forgive Her,1864, Anthony Trollope refers to a clerk playing tit-tat-toe. Tic-tac-toe may also derive from tick-tack, the name of an old version of backgammon first described in 1558, the U. S. renaming of Noughts and crosses as tic-tac-toe occurred in the 20th century. In 1952, OXO, developed by British computer scientist Alexander S. Douglas for the EDSAC computer at the University of Cambridge, the computer player could play perfect games of tic-tac-toe against a human opponent. In 1975, tic-tac-toe was also used by MIT students to demonstrate the power of Tinkertoy elements. The Tinkertoy computer, made out of only Tinkertoys, is able to play tic-tac-toe perfectly and it is currently on display at the Museum of Science, Boston. A position is merely a state of the board, while a game usually refers to the way a position is obtained. Naive counting leads to 19,683 possible board layouts, and 362,880 possible games, however, two matters much reduce these numbers, The game ends when three-in-a-row is obtained. If X starts, the number of Xs is always equal to or exactly 1 more than the number of Os. The complete analysis is complicated by the definitions used when setting the conditions

8.
Go (board game)
–
Go is an abstract strategy board game for two players, in which the aim is to surround more territory than the opponent. The game was invented in ancient China more than 2,500 years ago and it was considered one of the four essential arts of the cultured aristocratic Chinese scholar caste in antiquity. The earliest written reference to the game is recognized as the historical annal Zuo Zhuan. The modern game of Go as we know it was formalized in Japan in the 15th century CE, despite its relatively simple rules, Go is very complex, even more so than chess, and possesses more possibilities than the total number of atoms in the visible universe. Compared to chess, Go has both a board with more scope for play and longer games, and, on average. The playing pieces are called stones, one player uses the white stones and the other, black. The players take turns placing the stones on the vacant intersections of a board with a 19×19 grid of lines, beginners often play on smaller 9×9 and 13×13 boards, and archaeological evidence shows that the game was played in earlier centuries on a board with a 17×17 grid. However, boards with a 19×19 grid had become standard by the time the game had reached Korea in the 5th century CE, the objective of Go—as the translation of its name implies—is to fully surround a larger total area of the board than the opponent. Once placed on the board, stones may not be moved, capture happens when a stone or group of stones is surrounded by opposing stones on all orthogonally-adjacent points. The game proceeds until neither player wishes to make another move, when a game concludes, the territory is counted along with captured stones and komi to determine the winner. Games may also be terminated by resignation, as of mid-2008, there were well over 40 million Go players worldwide, the overwhelming majority of them living in East Asia. As of December 2015, the International Go Federation has a total of 75 member countries, Go is an adversarial game with the objective of surrounding a larger total area of the board with ones stones than the opponent. As the game progresses, the players position stones on the board to map out formations, contests between opposing formations are often extremely complex and may result in the expansion, reduction, or wholesale capture and loss of formation stones. A basic principle of Go is that a group of stones must have at least one liberty to remain on the board, a liberty is an open point bordering the group. An enclosed liberty is called an eye, and a group of stones with two or more eyes is said to be unconditionally alive, such groups cannot be captured, even if surrounded. A group with one eye or no eyes is dead and cannot resist eventual capture, the general strategy is to expand ones territory, attack the opponents weak groups, and always stay mindful of the life status of ones own groups. The liberties of groups are countable, situations where mutually opposing groups must capture each other or die are called capturing races, or semeai. In a capturing race, the group with more liberties will ultimately be able to capture the opponents stones, capturing races and the elements of life or death are the primary challenges of Go