Hot game

Last updated

In combinatorial game theory, a branch of mathematics, a hot game is one in which each player can improve their position by making the next move.

Contents

By contrast, a cold game is one where each player can only worsen their position by making the next move. Cold games have values in the surreal numbers and so can be ordered by value, while hot games can have other values. [1]

Example

For example, consider a game in which players alternately remove tokens of their own color from a table, the Blue player removing only blue tokens and the Red player removing only red tokens, with the winner being the last player to remove a token. Obviously, victory will go to the player who starts off with more tokens, or to the second player if the number of red and blue tokens are equal. Removing a token of one's own color leaves the position slightly worse for the player who made the move, since that player now has fewer tokens on the table. Thus each token represents a "cold" component of the game.

Now consider a special purple token bearing the number "100", which may be removed by either player, who then replaces the purple token with 100 tokens of their own color. (In the notation of Conway, the purple token is the game {100|−100}.) The purple token is a "hot" component, because it is highly advantageous to be the player who removes the purple token. Indeed, if there are any purple tokens on the table, players will prefer to remove them first, leaving the red or blue tokens for last. In general, a player will always prefer to move in a hot game rather than a cold game, because moving in a hot game improves their position, while moving in a cold game injures their position.

Temperature

The temperature of a game is a measure of its value to the two players. A purple "100" token has a temperature of 100 because its value to each player is 100 moves. In general, players will prefer to move in the hottest component available. For example, suppose there is a purple "100" token and also a purple "1,000" token which allows the player who takes it to dump 1,000 tokens of their own color on the table. Each player will prefer to remove the "1,000" token, with temperature 1,000 before the "100" token, with temperature 100.

To take a slightly more complicated example, consider the game {10|2} + {5|−5}. {5|−5} is a token which either player may replace with 5 tokens of their own color, and {10|2} is a token which the Blue player may replace with 10 blue tokens or the Red player may replace with 2 blue tokens.

The temperature of the {10|2} component is ½(10 − 2) = 4, while the temperature of the {5|−5} component is 5. This suggests that each player should prefer to play in the {5|−5} component. Indeed, the best first move for the Red player is to replace {5|−5} with −5, whereupon the Blue player replaces {10|2} with 10, leaving a total of 5; had the Red player moved in the cooler {10|2} component instead, the final position would have been 2 + 5 = 7, which is worse for Red. Similarly, the best first move for the Blue player is also in the hotter component, from {5|-5} to 5, even though moving in the {10|2} component produces more blue tokens in the short term.

Snort

In the game of Snort, Red and Blue players take turns coloring the vertices of a graph, with the constraint that two vertices that are connected by an edge may not be colored differently. As usual, the last player to make a legal move is the winner. Since a player's moves improve their position by effectively reserving the adjacent vertices for them alone, positions in Snort are typically hot. In contrast, in the closely related game Col, where adjacent vertices may not have the same color, positions are usually cold.

Applications

The theory of hot games has found some application in the analysis of endgame strategy in Go. [2] [3]

See also

Related Research Articles

Dots and Boxes

Dots and Boxes is a pencil-and-paper game for two players. It was first published in the 19th century by French mathematician Édouard Lucas, who called it la pipopipette. It has gone by many other names, including the game of dots, dot to dot grid, boxes, and pigs in a pen.

Nim

Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps or piles. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap or pile. Depending on the version being played, the goal of the game is either to avoid taking the last object or to take the last object.

In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as a natural number, the size of the heap in its equivalent game of nim, as an ordinal number in the infinite generalization, or alternatively as a nimber, the value of that one-heap game in an algebraic system whose addition operation combines multiple heaps to form a single equivalent heap in nim.

In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first. The game is played until a terminal position is reached. A terminal position is one from which no moves are possible. Then one of the players is declared the winner and the other the loser. Furthermore, impartial games are played with perfect information and no chance moves, meaning all information about the game and operations for both players are visible to both players.

In mathematics, the nimbers, also called Grundy numbers, are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim. The nimbers are the ordinal numbers endowed with nimber addition and nimber multiplication, which are distinct from ordinal addition and ordinal multiplication.

Winning Ways for Your Mathematical Plays by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy is a compendium of information on mathematical games. It was first published in 1982 in two volumes.

Combinatorial game theory

Combinatorial game theory (CGT) is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely 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. CGT has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.

In combinatorial game theory, a game is partisan if it is not impartial. That is, some moves are available to one player and not to the other.

Casino token

Casino tokens are small discs used in lieu of currency in casinos. Colored metal, injection-molded plastic or compression molded clay tokens of various denominations are used primarily in table games, as opposed to metal token coins, used primarily in slot machines. Casino tokens are also widely used as play money in casual or tournament games.

Col is a pencil and paper game, specifically a map-coloring game, involving the shading of areas in a line drawing according to the rules of Graph coloring. With each move, the graph must remain proper, and a player who cannot make a legal move loses. The game was described and analysed by John Conway, who attributed it to Colin Vout, in On Numbers and Games.

Domineering

Domineering is a mathematical game that can be played on any collection of squares on a sheet of graph paper. For example, it can be played on a 6×6 square, a rectangle, an entirely irregular polyomino, or a combination of any number of such components. Two players have a collection of dominoes which they place on the grid in turn, covering up squares. One player places tiles vertically, while the other places them horizontally. As in most games in combinatorial game theory, the first player who cannot move loses.

Hackenbush

Hackenbush is a two-player game invented by mathematician John Horton Conway. It may be played on any configuration of colored line segments connected to one another by their endpoints and to a "ground" line.

In mathematics, the mex of a subset of a well-ordered set is the smallest value from the whole set that does not belong to the subset. That is, it is the minimum value of the complement set. The name "mex" is shorthand for "minimum excluded" value.

Map-coloring games

Several map-coloring games are studied in combinatorial game theory. The general idea is that we are given a map with regions drawn in but with not all the regions colored. Two players, Left and Right, take turns coloring in one uncolored region per turn, subject to various constraints. The move constraints and the winning condition are features of the particular game.

Dodgem

Dodgem is a simple abstract strategy game invented by Colin Vout in 1972 while he was a mathematics student at the University of Cambridge as described in the book Winning Ways. It is played on an n×n board with n-1 cars for each player—two cars each on a 3×3 board is enough for an interesting game, but larger sizes are also possible.

Grundys game

Grundy's game is a two-player mathematical game of strategy. The starting configuration is a single heap of objects, and the two players take turn splitting a single heap into two heaps of different sizes. The game ends when only heaps of size two and smaller remain, none of which can be split unequally. The game is usually played as a normal play game, which means that the last person who can make an allowed move wins.

Kayles

Kayles is a simple impartial game in combinatorial game theory, invented by Henry Dudeney in 1908. Given a row of imagined bowling pins, players take turns to knock out either one pin, or two adjacent pins, until all the pins are gone. Using the notation of octal games, Kayles is denoted 0.77.

The octal games are a class of two-player games that involve removing tokens from heaps of tokens. They have been studied in combinatorial game theory as a generalization of Nim, Kayles, and similar games.

In combinatorial game theory, cooling, heating, and overheating are operations on hot games to make them more amenable to the traditional methods of the theory, which was originally devised for cold games in which the winner is the last player to have a legal move. Overheating was generalised by Elwyn Berlekamp for the analysis of Blockbusting. Chilling and warming are variants used in the analysis of the endgame of Go.

In combinatorial game theory, a subtraction game is an abstract strategy game whose state can be represented by a natural number or vector of numbers and in which the allowed moves reduce these numbers. Often, the moves of the game allow any number to be reduced by subtracting a value from a specified subtraction set, and different subtraction games vary in their subtraction sets. These games also vary in whether the last player to move wins or loses (misère). Another winning convention that has also been used is that a player who moves to a position with all numbers zero wins, but that any other position with no moves possible is a draw.

References

  1. ↑ "The Life of Games |". Mathenchant.wordpress.com. 2015-08-12. Retrieved 2019-01-09.
  2. ↑ Berlekamp, Elwyn; Wolfe, David (1997). Mathematical Go: Chilling Gets the Last Point . A K Peters Ltd. ISBN   1-56881-032-6.
  3. ↑ A bibliography is given in Conway 2001 , p. 108
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.