Play with perfect information

Game with perfect information , sometimes also called game with perfect information , is a term in mathematical game theory . Accordingly, a game has perfect information if, at the time of a decision, each player is always aware of the previous game events, ie the decisions made by his teammates beforehand and the random decisions made beforehand.

Among the board games the most classic own board games perfect information. Examples are Go , Chess , Checkers , Mill , Halma , Nim and Mancala as two-person games or also Solitaire and SameGame as a solitaire game. Even games with a random influence such as backgammon and Mensch är är dich nicht , the latter regardless of the number of players, have perfect information.

A game without perfect information is also called a game with imperfect information . Examples are card games such as skat and poker , because there each player only knows his own cards. Even a game with simultaneous moves such as scissors, stone, paper is not a game with perfect information, since the deciding player is not aware of the opponent's simultaneous decision. In this respect, information stands that are asymmetrical in relation to the players are characteristic of games with imperfect information.

properties

In 1912 Ernst Zermelo proved that a finite two-person zero-sum game with perfect information and without the influence of chance has a clearly defined game result, in the sense that one player can force at least this result regardless of how the opponent plays, while it is Opponents are able to prevent an even higher result. For the chess game considered by Zermelo as an example, this specifically means that chess either

• as with a problem white allows a winning strategy , or else
• Black has such a winning strategy, or else
• both players can force at least one draw for themselves .

Such games are also called determined .

Applied to a back and forth game with reversed colors, Zermelo's sentence has the consequence that a player with an error-free game can force at least an even overall result - but not even if the opponent also plays without errors.

The game result resulting from a game that is faultless on both sides is referred to as the value of the game . Its practical determination can be very difficult for a given game, even if theoretically there is always a possibility of calculation with the Minimax algorithm . Numerous games, including checkers , mill and four in a row , are now completely dissolved and the corresponding strategies are known. For some games, such as Hex , only the values ​​of the starting position can be determined based on symmetry considerations, without knowing the associated strategies.

Games of a special subclass are examined within the so-called combinatorial game theory .

For a finite two-person zero-sum game with perfect information and chance influence, Zermelo's theorem applies analogously with regard to the expected value of the profit. That is, a player has a strategy so that the expected value of his winnings reaches at least this value, while a strategy exists for his opponent that limits the profit expectation of the first player to a maximum of this value. Consequently, for example, every position in backgammon , which strictly speaking must be limited to a finite length, has a clearly defined value.

Zermelo's theorem does not apply to finite games with perfect information, which are played with more than two people or which do not have a zero-sum character. This means that, in general, objectively best strategies cannot be found for such games. However, according to a statement by Harold Kuhn from 1950, equilibria exist in pure strategies .

The property of perfect information cannot generally be seen from the normal form of a game. Within the extensive form , which represents a game based on a directed graph , the perfect information is characterized by single-element sets of information.

Random free finite games with 2 players with no ties

Zermelo's sentence applies all the more to those among the games mentioned, in which a draw cannot occur. In these finite two-person zero-sum games with perfect information without the influence of chance or a tie , his sentence implies the following statement:

A playing position belongs to one of exactly two categories:

1. Z-position (from "compulsion"): A Z-position must always be made into a C-position.
2. C-position (from "chance"): A C-position can always be made into a Z-position.

Zermelo's argument, however, is a set-theoretic existential argument and does not contain an algorithm for categorizing the positions of a particular game.

As mentioned above, the Minimax algorithm, which is part of the graph-theoretical procedures, delivers a categorizing value for each position. However, less complex algorithms and criteria are presented below.

The categorization of the positions can be worked out in small tableaus with pencil and paper, which corresponds to the graph-theoretical categorization . Once you have got a first impression, you can develop a numerical categorization from this.

The Nim game ( see below ) was examined in detail by Roland Sprague in 1935 and independently of it by Patrick Michael Grundy in 1939 and made a prime example of this type of game (see also Sprague-Grundy's sentence ). In this respect, it marks a starting point for mathematical game theory .

In the above-mentioned Grundy paper, the Z position is called “W” (for winning ) and the C position is called “L” (for losing ); at Berlekamp “ position” ${\displaystyle {\mathcal {N}}}$ (for negative ) or “ position” ${\displaystyle {\mathcal {P}}}$ (for positive ); at Wythoff «cold» or «hot». It's about the identification of a position and not a move, which the Z- and C-speaking styles best express.

Examples

One or two

This matchstick game is one of the simplest:

There is a pile of matches between two players. Both players take turns taking a stick or two. Whoever takes the last stick wins (see one or two and Bachet's game ).

You can also change the rule by losing whoever has to take the last stick.

Wythoff's game

In the " game of Wythoff " (also: "Wythoffs Nim"), 2 players take turns from 2 stacks of objects, from one of the two stacks or from both, but then an equal number of items from each stack. The game ends when a player removes the last item - with which he wins the game.

The game was mathematically analyzed by this Dutch mathematician in 1907, but according to Martin Gardner it is said to have been played in China under the name 捡 石子jiǎn shízǐ (“taking stones”).

In the game by Rufus Isaacs (quoted from Berge), the players alternately mark a node in the first quadrant of the level with an integer grid ( in formulas ${\displaystyle \mathbb {N} _{0}\times \mathbb {N} _{0}}$ ), the successor node being on the same coordinate (horizontal or vertical) or the bisector as seen from the previous node must be in the direction of the origin. The player who reaches the origin first wins. The starting position is drawn.

The two rules of the game are equivalent. However, the graphical view is particularly well suited for the representation of the graph-theoretic algorithm.

Nim

In the Nim game, there are several rows of matches. Two players take turns taking matches from one of the rows. How many you take doesn't matter; there must be at least one match and only matches from a single row may be taken during a move. The player who makes the last move - that is, removes the last matches - wins.

→ Main article : Nim game

Misère-Nim

The player who makes the last move (takes the last match) has not won, but has lost. This rule is called the misère rule.

The Nim game Marienbad , made famous by Alain Resnais' film Last year in Marienbad , is a misère variant.

Hex

The strategic board game Hex is not a "neutral" ( impartial ) game, as the 2 players, called "red" and "blue", can only make moves with stones of their color. As a game of this type, it cannot be analyzed using Sprague-Grundy's theorem .

For rules of the game etc. refer to the

→ Main article : Hex (game)

referenced. In this article it should only be shown that the positions can be categorized graphically in the same way as in the other determined games.

Graph theoretical categorization

The positions can be represented for each (finite) tableau in a directed graph with nodes for the positions and arcs (directed edges ) for the possible moves. I.e. a single possible move is represented by an arc that leads from a direct predecessor position to a direct successor position , in symbols This graph reflects the rules of the game, limited to the tableau. ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u\to v.}$

The requirement for finiteness made at the beginning can only be met by the freedom from cycles of the graph, which is therefore a directed acyclic graph ( DAG for directed acyclic graph ). In the form defined in this way, it is called the positional DAG. From the finiteness of the graph itself it follows that there must be end nodes, i.e. nodes for which there are no successor nodes.

We also assume:

The game should end when a player can no longer move. This should then also be the loser.

If there is an end node with a Misère win rule, we add a bow to an additional node, after which last move the next player can no longer move and is therefore the correct loser.

The presentation of the following algorithm is simplified by a strict total order of the positions, which is compatible with the sequence of moves. It can be constructed as follows, for example: ${\displaystyle \succ }$

In the games mentioned, the number of items in the tableau either increases or decreases with each turn. So one takes this number as the highest-ranking criterion in a lexicographical order . Subordinate criteria must ensure that different positions are considered greater or come out smaller, whatever is possible. Such a total order ensures that it always follows. ${\displaystyle \succ }$ ${\displaystyle u\to v}$ ${\displaystyle u\succ v}$

Algorithm:

We start with the minimum of the chosen total order - it has to be a depression and an end position. We work through the positional space of total order in ascending order (against the direction of the arrow, quasi “causally backwards”) and step by step in the direction of its maximum.

If we come to an unmarked node , then we mark it as a Z-node (=:   Z-Action ( )). Then we mark all its direct predecessors (i.e. the ones ) as C-Nodes (=:   C-Action ). ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle u\to v}$ ${\displaystyle (v,u)}$

The step-by-step procedure of the total order "upwards" ensures that we search the entire position area. Already marked nodes remain unchanged; no other action is required for them either.

Proof of the algorithm and thus renewed proof of the statement:

If the node is a Z-node, then all of its direct successors (i.e. those with ) are C-nodes. If a Z-node were there, the direct predecessor of from would have to be marked as a C-node in a C-Action ( ). And a successor cannot be unmarked either, because then a Z-Action ( ) should actually have come before the Z-Action ( ) because of the "time reversal" . ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle v\to w}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle w,v}$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle v}$

Its direct predecessors (i.e. those ) can only have been unmarked or have been C-nodes before the C-Action ( ). Because it cannot be a Z-node, because the Z-Action ( ) would always happen before a Z-Action ( ). ${\displaystyle u}$ ${\displaystyle u\to v}$ ${\displaystyle v,u}$ ${\displaystyle u}$ ${\displaystyle u\succ v}$ ${\displaystyle v}$ ${\displaystyle u}$

In the graph-theoretic way of speaking we have constructed a kernel (English kernel , French noyau ) for a directed acyclic graph , i.e. i. a stable subset of nodes that is also dominant . The core is the set of Z-nodes. It always exists and is unique. The stability is the compulsion to go from a Z-node to a C-node must , and go-node Z's dominance for the chance of a C-node to a can .

The cited algorithm can - at least theoretically - clarify for each position whether it is a profit or a loss position. However, the size of the positional DAG, which is even larger than the positional space, can make "practical" implementation impossible.

The graphics below show the results that can be obtained with the algorithm described. The C -Actions emanating from the (green) Z-nodes are represented by red "rays", which turn the nodes they hit into (red) C-nodes.

"Core" of the game by Wythoff

One or two

Even the trivial game one or two , whose optimal strategy can be understood immediately without a lot of math, can be treated with the above algorithm: The positional space is an interval of non-negative integers that represent the current number of matches. ${\displaystyle \left[0,n\right]}$

Wythoff's game

In Wythoff's game, the properties of the core come out nicely . The black sketch of the rules of the game in the lower right corner symbolizes a kind of “future light cone” , to which the “past light cones” correspond, which emanate from the Z-nodes (green). If a C-node (red) is drawn as the starting position, the attractive player can force victory. With a Z-knot (green) as the starting position, the attracting person can only reach a C-knot, after which his opponent can force victory.

2 colored standing rooms of the Nim game with 3 rows

Nim

Nim embeds the positional DAG in an obvious way in the -dimensional interval of the positions, where the number of rows is and the number of matches in the -th row. A game position then corresponds to a node with the current number of matches as its coordinates. The possible moves (arcs) are parallel to exactly 1 coordinate with the direction towards the origin . ${\displaystyle n}$ ${\displaystyle \left[0,r_{1}\right]\times \left[0,r_{2}\right]\times \ldots \times \left[0,r_{n}\right]}$ ${\displaystyle n}$ ${\displaystyle r_{i}}$ ${\displaystyle i}$

Each of the lexicographical orders is a total order compatible with the sequence of moves. There is only one end position that coincides with the origin.

The graphic on the right shows the Z-positions (green nodes) and the C-positions (red nodes) for the standard (above) and the misère rule (below) of the Nim game in two diagrams - each in one for the sake of simplicity Tableau of 3 rows (axes) of 5, 4 and 1 sticks. In both diagrams, the row with 1 matchstick is represented by 2 superimposed levels, the 0 and 1 level, so that the 0 level effectively corresponds to the absence of the third row and the 1 level to the presence of 1 stick in this row.

The origin is always in the lower left front. ${\displaystyle (0,0,0)}$

Valid moves in the graph are movements on exactly one of the coordinate axes, i.e. H. either horizontally or vertically or also in the third direction from the 1-level to the 0-level, closer to the origin.

The algorithm starts at the origin, which is colored green for the standard rule and red for the misère rule.

It is noticeable that between the 2 Nim variants the colors only differ in the nodes very close to the origin.

The winning strategy with 2 rows for the standard rule is: If you can, draw level with your opponent.

With 3 and more rows it gets more complicated, as the 1-levels in the diagram already indicate. The more general cases, especially those with more than 3 rows, are even more difficult to depict.

Hex board with 11 by 11 fields

Hex

If the diamond-shaped plank of times hexagonal fields, then there are extreme positions and against total positions. The algorithm described is therefore only practicable for very small ones. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\binom {n^{2}}{{\big \lfloor }{\tfrac {n^{2}}{2}}{\big \rfloor }}}}$ ${\displaystyle 3^{n^{2}}}$ ${\displaystyle n}$

The lexicographical order of can serve as a total order compatible with the move order with as number of free fields in the highest lexicographical priority, as index of a field and ${\displaystyle (f,a_{1},\ldots ,a_{n^{2}})}$ ${\displaystyle f\in \left[0,n^{2}\right]}$ ${\displaystyle i\in \left[1,n^{2}\right]}$ ${\displaystyle F_{i}}$

${\displaystyle a_{i}:={\begin{cases}\\\\\\\end{cases}}}$	${\displaystyle 0}$if free , ${\displaystyle F_{i}}$
	${\displaystyle 1}$if red , ${\displaystyle F_{i}}$
	${\displaystyle 2}$if blue , ${\displaystyle F_{i}}$

For example, the position (11² = 121, free , free , free , ...) the position (120, red , free , free , free , ...) and this the position (119, red , free , blue , free , free , free , ...) can follow.

In the position DAG, the moves on the red stones alternate with those on the blue ones. The core of the position DAG contains positions with both red and blue to move. The first move in the middle is always good for Red - but it's not the only good one. The first move in a sharp corner is bad, then blue can create a Z-position with his first move in the middle.

Minimax algorithm

Minimax at game one or two
(The thicker edges are the strategic ones.)

In contrast to the positional DAG of the above algorithm , the Minimax algorithm requires a game tree, i. H. a root tree expanded version of the positional DAG.

One or two

The minimax algorithm is explained using the very simple game one or two .

In the nebensbleau of the game with 6 matches expanded. For reasons listed below, the two players are called “maximizers” and “minimizers”. The figure above is the game tree for a Tanoten (positions) and edges (moves) are green for the maximizer and red for the minimizer. The nodes contain a number and a sign: the number is the number of matches and the sign is the value of the position with the meaning:

+	the maximizer can force victory
−	the minimizer can force victory

The algorithm starts with the leaves of the tree , which all represent an end position of 0 matches. Since the player whose turn it was has lost, one hand with a maximizer to move receives the marker grün 0−and another rot 0+. A green node receives the maximum of the game values ​​of the successor nodes or a red node their minimum as the game value; hence the name Minimax and also the names of the players. If the values ​​of the successor nodes are different, the strategically optimal move is shown more strongly. In the positions with grün −and rot +, it is the player who surrenders the move who has achieved or can force the victory. (These are Z-positions . Since the Minimax algorithm always comes to a result, the existence and uniqueness of a core of the position-DAG is proven by its applicability.)

Compared to the algorithm above , the Minimax algorithm is a little more complex:

• It allows any real game values, even if only the 2 values  (: = +1) and  (: = −1) are used in the random-free finite games with 2 players without a tie .+−
• In the example, the game tree contains repetitions, e.g. B. 8 times the position with 1, 5 times the position with 2, 3 times the position with 3 and 2 times the position with 4 matches.
• The positional DAG nodes are the nodes in the leftmost column. Its core is formed by the knots with grün −and rot +.

Both algorithms start with the leaves and work their way up to the roots, i.e. against the direction of the game.

The other games

With the other games described in this article, savings from tree to position DAG result from the fact that there are any number of moves that lead to the same position. This has to be repeated in the tree, whereas it only occurs once in the DAG.
In addition, in the games Nim and Wythoff's game, the positional DAG is simplified by the fact that the moves with a common goal are in a simple linear order.

Numerical categorization

Numerical categorization should be understood to mean that there is a formula that clarifies for each position based on its numbered parameters whether it is a profit or a loss position. If the formula exists, then in the language of the article Solved games the game can be described as "strongly solved".

One or two

The Z-nodes in game one or two are exactly the positions in which the number of matches is divisible by 3; with the associated misère rule ≡ 1 mod 3.

Wythoff's game

In Wythoff's game, the Z-nodes are on the coordinates with and  (number of the golden section ) and the same is mirrored again at the bisector. ${\displaystyle {\big (}\lfloor n\Phi ^{2}\rfloor ,\lfloor n\Phi \rfloor {\big )}}$ ${\displaystyle n\geq 0}$ ${\displaystyle \Phi :=(1+{\sqrt {5}})/2}$

The irrationality of results in an aperiodic, irregular distribution. ${\displaystyle \Phi \,}$

Nim

Regarding the formulas for the Nim sums of the Nim game and the proof of their optimality is referred to the main article Nim game . The Z-nodes of the graph correspond to positions with even Nim sums. The latter only come with a number ≥ 3 of rows, i.e. H. the composition of several "games", right to wear. However, this is difficult to make clear in a 2-dimensional graphic.

Hex

A strategy for hex with arbitrarily large n × n tableau is not known. However, there are studies up to n ≤10 on certain opening moves. With m × n tableaus with m < n there is a winning strategy for the player who has the shorter path (see Hex ).

Conclusion

The graph theoretical algorithm determines the "play value" of a position. In the sense of the Solved Games article , it represents a “weak solution” to a game. The graphs are naturally always finite and are therefore sufficient for the player's “personal needs”. The expansion of the positional graph is often of exponential complexity. They also provide clues for the numerical formulas, but they can be very different. From the mathematical point of view, the formulas are to be placed on higher ranks and also require proof specially tailored to them. If the evaluation options are suitable, they are to be regarded as “strong solutions”.

Obviously, it is not interesting to play one of these games when both players know the optimal strategy, because then winners and losers will be determined in advance. In the hex game, however, this is only effectively known for small n . In fact, the winner is certain from the start when one of the two players plays the optimal strategy and gets to a C-position.

Since the Z-positions represent a vanishing minority among the successor positions in a present C-position, a perfect player who has to start with a Z-position - i.e. leave a C-position to his opponent - the greater the chances of winning the larger the starting board and the more possibilities of error there are for the opponent. And after the first mistake on their part, he can no longer be dissuaded from the road to victory.

literature

• Claude Berge : Graphs et hypergraphes . Dunod, Paris 1970, Chapitre 14 Noyaux et fonctions de Grundy, p. 291-313 (French).
• Jörg Bewersdorff : Luck, Logic and Bluff: Mathematics in Play - Methods, Results and Limits. Springer Spectrum, 6th edition, Wiesbaden 2012, ISBN 978-3-8348-1923-9 , doi: 10.1007 / 978-3-8348-2319-9_2 , pp. 95–245.
• Elwyn Berlekamp , John Horton Conway , Richard K. Guy : Gewinnen , Braunschweig, 1985/86, 4 volumes, ISBN 3528085312 , ISBN 3528085320 , ISBN 3528085339 , ISBN 3528085347 (original: Winning Ways for your Mathematical Plays. , 2 volumes, ISBN 0120911019 , ISBN 0120911027 , updated new editions 2001 to 2004).
• GH Hardy , EM Wright: An introduction to the theory of numbers. Fifth edition. The Clarendon Press, Oxford University Press, New York, 1979, pp. 117-120.

Individual evidence

1. ^ Christian Rieck : Game Theory , Gabler, Wiesbaden 1993, ISBN 3-409-16801-X , p. 95.
2. ^ Walter Schlee, Introduction to Game Theory: with examples and exercises , ISBN 3-528-03214-6 , p. 95
3. ↑ E. Zermelo: On an application of set theory to the theory of the chess game , Proceedings of the Fifth Congress of Mathematics, Vol. II, Cambridge 1913, pp. 501–504 ( Memento from March 24, 2016 in the Internet Archive )
4. ^ HW Kuhn : Extensive games , Proceedings of the National Academy of Sciences of the USA, Volume 36, 1950, pp. 570-576 ( online ; PDF; 713 kB).
5. ^ Roland P. Sprague: About mathematical fighting games , Tôhoku Mathematical Journal, 41 (1935), pp. 438-444 ( online ).
6. ^ Patrick M. Grundy: Mathematics and games , Eureka. 27 (1940), pp. 9–11 ( online ( memento of the original dated September 27, 2007 in the Internet Archive ) Info: The archive link has been inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice . ). 
7. ^ WA Wythoff : A modification of the game of Nim , Nieuw Archief voor Wiskunde. Tweede reeks 7, 1907, pp. 199-202
8. ↑ Wythoff's game on Cut-the-knot (citing Martin Gardner's book Penrose Tiles to Trapdoor Ciphers )
9. ↑ Claude Berge, op. a. Cit., P. 308.
10. ↑ Claude Berge, op. a. Cit., P. 296.
11. ↑ Richardson (1953), p. Claude Berge, a. a. Cit., P. 299.
12. ↑ Claude Berge, op. a. Cit., P. 298.

See also

• Take-a-square game