1.
Combinatorial game theory
–
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

2.
Abstract strategy game
–
An abstract strategy game is a strategy game that does not rely on a theme. Many of the classic board games, including chess, Nine Mens Morris, checkers and draughts, Go, xiangqi, shogi, Reversi. Play is sometimes said to resemble a series of puzzles the players pose to each other, as J. which in theory could be solved by logic alone. A good abstract game can therefore be thought of as a family of potentially interesting logic puzzles, good players are the ones who find the most difficult puzzles to present to their opponents. The strictest definition of a strategy game requires that it cannot have random elements or hidden information. In practice, however, many games that do not strictly meet these criteria are classified as abstract strategy games. A smaller category of abstract strategy games manages to incorporate hidden information without using any random elements, two examples are the IAGO World Tour and the Abstract Games World Championship held annually since 2008 as part of the Mind Sports Olympiad. Some abstract strategy games have multiple starting positions of which it is required that one be randomly determined, at the very least, in all conventional abstract strategy games, a starting position needs to be chosen by some means extrinsic to the game. Some games, such as Arimaa and DVONN, have the build the starting position in a separate initial phase which itself conforms strictly to abstract strategy game principles. Most players, however, would consider that one is then starting each game from a different position. Indeed, Bobby Fischer promoted randomization of the position in chess in order to increase player dependence on thinking at the board. Analysis of pure abstract strategy games is the subject of game theory. As for the aspects, ranking abstract strategy games according to their interest, complexity, or strategy levels is a daunting task. This suggests that computer programs, through brute force calculation alone, as for Go, the possible legal game positions range in the magnitude of 10170. The Mind Sports Olympiad first held the Abstract Games World Championship in 2008 to try to find the best abstract strategy games all-rounder. The MSO event saw a change in format in 2011 restricting the competition to players five best events and it was again won by David Pearce. 2008, David M. Pearce 2009, David M. Pearce 2010, David M. Pearce 2011, David M

3.
Y (game)
–
Y is an abstract strategy board game, first described by John Milnor in the early 1950s. The game was invented in 1953 by Craige Schensted and Charles Titus. Schensted and Titus book Mudcrack Y & Poly-Y has a number of boards for play of Y, all hand-drawn, most of them seem irregular. The pie rule can be used to mitigate any first-move advantage, the rules are as follows, Players take turns placing one stone of their color on the board. Once a player connects all three sides of the board, the ends and that player wins. The corners count as belonging to both sides of the board to which they are adjacent. As in most connection games, the size of the changes the nature of the game, small boards tend towards pure tactical play. Schensted and Titus argue that Y is a game to Hex because Hex can be seen as a subset of Y. Consider a board subdivided by a line of white and black pieces into three sections, the portion of the board at the bottom-right can then be considered a 5×5 Hex board, and played identically. However, this sort of construction on a Y board is extremely uncommon. Mudcrack Y & Poly-Y also describes Poly-Y, the game in the series of Y-related games. Y, like Hex, yields a strong first-player advantage, the standard approach to solving this difficulty is the pie rule, one player chooses where the first move will go and the other player then chooses who will be the first player. Ys chief criticism is that on the standard hexagonal board a player controlling center can reach any edge no matter what the other player does. This is because the distance from the center to an edge is only approximately 1/3 the distance along the edge from corner to corner, as a result, defending an edge against a center attack is very difficult. Schensted and Titus attacked this problem with successive versions of the game board and this made defending a side from a center attack much more plausible. Thus the present official board is essentially a geodesic dome hemisphere squashed flat into a triangle to provide this effect and it has been formally shown that Y cannot end in a draw. That is, once the board is complete there must be one, in Y the strategy-stealing argument can be applied. It proves that the player has no winning strategy

4.
Star (board game)
–
Star is a two-player abstract strategy board game developed by Craige Schensted. It was first published in 1983 in Games magazine and it is connection game, related to games such as Hex, Y, Havannah, and TwixT. Unlike these games, however, the result is based on a player having a final score rather than achieving a specific goal. He has since developed a more complicated version called *Star with better balance between edge and center moves, writing *Star is what those other games wanted to be. Star is played on a board of hexagonal spaces, although the board can have any size and shape, a board with unequal edges is generally used to avoid ties. Players may not place stones on the partial hexagons off the edge of the board, one player places black stones on the board, the other player places white stones. The game begins with one player placing a stone on the board, to avoid giving an advantage to the first player, a pie rule is used, allowing the second player to switch sides at that point. Players then alternate turns, placing a stone on an empty hexagon on the board, players may pass, the game is over when both players pass. At the end of the game the players count their scores, a star is a group of connected stones belonging to one player that touches at least three partial edge hexagons. The score of a star is the number of edge hexagons it touches minus two, a players score is the total of all the stars of that players color. The player with the higher score wins, for any given board, the total final score of the two players is constant

5.
Hex (board game)
–
Hex is a strategy board game for two players played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11×11 rhombus. Players alternate placing markers or stones on unoccupied spaces in an attempt to link their opposite sides of the board in an unbroken chain, one player must win, there are no draws. The game has deep strategy, sharp tactics and a profound mathematical underpinning related to the Brouwer fixed point theorem and it was invented in the 1940s independently by two mathematicians. The game was first marketed as a game in Denmark under the name Con-tac-tix. Hex can also be played with paper and pencil on hexagonally ruled graph paper, hex-related research is current in the areas of topology, graph and matroid theory, combinatorics, game theory and computer heuristics. Hex is a game, and can be classified as a Maker-Breaker game. The game can never end in a draw, in other words, Hex is a finite, perfect information game, and an abstract strategy game that belongs to the general category of connection games. When played on a graph, it is equivalent to the Shannon switching game. As a product, Hex is a game, it may also be played with paper. The game was invented by the Danish mathematician Piet Hein, who introduced it in 1942 at the Niels Bohr Institute, the game was independently re-invented in 1948 by the mathematician John Nash at Princeton University, Nashs fellow players at first called the game Nash. According to Martin Gardner, who featured Hex in his July 1957 Mathematical Games column, in 1952, Parker Brothers marketed a version. They called their version Hex and the name stuck, Hex was also issued as one of the games in the 1974 3M Paper Games Series, the game contained a 5½ × 8½ inch 50-sheet pad of ruled hex grids. The move to be made corresponded to a certain specified saddle point in the network, the machine played a reasonably good game of Hex. Later, researchers attempting to solve the game and develop hex-playing computer algorithms, in 1952 John Nash expounded an existence proof that on symmetrical boards, the first player has a winning strategy. The game was shown to be PSPACE-complete. In 2002, the first explicit winning strategy on a 7×7 board was described, in the 2000s, by using brute force search computer algorithms, Hex boards up to size 9×9 have been completely solved. Various paradigms resulting from research into the game have used to create digital computer Hex playing automatons starting about 2000. The first implementations used evaluation functions that emulated Shannon and Moores electrical circuit model embedded in an alpha-beta search framework with hand-crafted knowledge-based patterns, starting about 2006, Monte Carlo tree search methods borrowed from successful computer implementations of Go were introduced and soon dominated the field

6.
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