Includes chess math

Math and chess and beauty

Transcript

1 Mathematics and Chess and Beauty Christian Hesse The Ministry of Education and Research has been organizing the Science Years since 2000. After 2007, the year of the humanities, 2008 was declared the year of mathematics. In addition, both a World Chess Championship (for the first time in 74 years) and a Chess Olympiad (for the first time in 48 years) took place in Germany in 2008. Looking back, 2008 can also be seen as the year of chess in Germany. Reason enough for us to look at some problems in the intersection of these two intelligent activities. Specifically, we are concerned with solving chess problems with mathematical tools on the one hand and solving non-chess (!) Mathematical problems with chess accessories, namely with chessboard and pieces, on the other hand, both against the background of intelligent beauty. Many mathematicians have been inspired by the game of chess to answer interesting questions, and quite a few chess players, conversely, are also enthusiastic about mathematical puzzles and problems. In the language of mathematical game theory, chess is a two-person, non-random, zero-sum game with complete information. The term zero-sum game in the context of two people generally describes competitive situations in which one is always the other's disadvantage. There are no so-called win-win situations from which both parties benefit. The addition with complete information means that both players are in principle always fully informed of all possible consequences of all possible courses of action. As early as 1912, the mathematician Ernst Zermelo proved that such games (such as, besides chess, mill, checkers, tic-tac-toe) are determined. This means that one of the following three statements is true: A: White has a strategy that guarantees victory. B: White has a strategy that guarantees at least a draw, but a strategy like in A. C: Black has a strategy that guarantees victory. Because of the astronomical number of possible move orders, it is open whether statement A or B or C applies to chess. G. H. Hardy has estimated that there are different game courses (i.e. 10 to the power of 10 to the power of 50). An incredible number, even in comparison with the estimated only for the number of particles in the universe. Zermelos result is a pure result of existence. It proves the existence of a strategy that makes either A or B or C a true statement, but does not state what that strategy looks like and which of the three statements is correct. In principle one can construct this strategy for a perfect game in chess through the mathematical method of the backward indution. The starting point is a database with all positions in which black is matt. From this a partial database is generated with all positions in which White can checkmate only once, then a partial database with positions in which Black cannot prevent White's mating in the next move, then a partial database with positions from which White always has one Can reach a position in which Black on the move cannot prevent White from being mated on the next move. This process is continued in stages: In each step you move a half-move further away from mate to positions with all 32 pieces and White to move. Then the set W of all these 32-Steiner is connected by the shortest path in the constructed sequence of sub-databases with a mated position. Starting from one of these 32-stoneers, the associated path shows the moves for a perfect game on both sides: When it is White's turn, there is an alternative that leads to mate faster. When it is Black's turn, there is another defense that delays mate longer. The set W includes all positions with 32 pieces, in which White can win with a move. Now you can do the same thing from the point of view of black, starting with the database of all possible positions in which white is matt. Ultimately, you get the set S of all 32-Steiners in which, with White on move, Black can necessarily win. All other 32-stoners, i.e. all except enes in the sets W and S, lead to a draw with the best game on both sides. This set of draw positions is denoted by R. Then it depends on which of these three sets the starting position in chess is in, in W or R or S. It depends on whether the statement A or B or C applies to the game of chess. But the game tree in chess is so big that even the most powerful computers cannot cope with it. It is different with mill, lady and tic-tac-toe; these games have now been analyzed. All three lead to a draw with the best game on both sides. Chess and math have a number of structural and other similarities. Chess is as abstruse as math. For simplified illustration only, 156 FOKUS MDMV 17 /

You play it with pieces on a board. But in the end one only has to imagine 64 related spatial points and the effects of force fields on these spatial points, because the figures are only embodiments of forces, and these require a physically extended field of view. Chess is subject to rules. These are arbitrary and man-made, just like the axioms in mathematics. You determine what it means to play chess or do math. In chess, piece patterns are their identification, analysis and evaluation - of crucial importance. Mathematics, on the other hand, is, according to one possible definition, the science of patterns. One of the oldest sub-areas, geometry, studies patterns of point sets in plane and space. The undemanding intelligent province of number theory onglates with patterns in whole numbers. The modern domain of stochasti examines patterns in random processes. And last but not least, and above all: Mathematics and chess are both sources of perceived beauty. The feeling of something beautiful is fundamentally linked to the feeling of pleasure. As a basic requirement for an aesthetic experience, one needs something that touches the senses, the heart or the mind in a positive way: a perfectly shaped building, a beguiling symphony, a colorful sunset, a sympathetic face, a sophisticated demonstration of thought. It is comparatively easy to experience beauty through the senses. In order to feel intelligent beauty, on the other hand, the basic requirement is a training of the mind. This applies to chess and math in equal measure. But the intelligently perceived beauty is no less intense than the sensual one. And to follow up on this last statement immediately: An important reason to deal with math and chess is the beauty that can be experienced. As far as the aesthetics of mathematics are concerned: the seamless fit with which an ensemble of individual considerations and small fragments of thought form a stringent line of argument, as they interlock like the cogs on a clock and provide the larger whole of a successful mathematical proof, has something extremely elegant , Harmonious and simply beautiful. The most successful manifestations of this genre sometimes trigger real firewalls on the cerebral cortex. The aesthetics of mathematics lie in the radiation of ingeniously connected ideas. Mathemati is ideology, the study of ideas. The bestselling author Simon Singh calls it the sexiest discipline on the planet. And mathematicians are engineers in this wonderful world of ideas. Korolov, who will checkmate in one move? Mathematical tools for chess problems Mathematical methods can be used extensively, also in chess. Let us consider the above example, which demonstrates in an impressive way the effectiveness and beauty of even simple mathematical ideas in solving chess problems. The problem is clear, but an answer seems impossible. If it were White's turn, he could mate with 1.Nxc7. With Black to move, 1 ... Nxc2 would be mate. The question therefore boils down to determining who is to move in the above position. But how should this be decided on the basis of the diagram position alone? After all, the knights, rooks and kings of both sides can have made any number of moves and therefore it seems that it is now both white and black's turn. However, this is not the case with a more detailed analysis with a higher fine adjustment. The answer is based on the simple concept of parity. The term parity is used in mathematics to distinguish between even and odd numbers. If two integers are both even or both odd, they have the same parity. If one is even and the other is odd, they have different parities. There are many ingenious considerations based on simple parity considerations. The solution to the above chess problem is actually quite simple and at the same time extremely elegant when using the parity principle as a tool: a knight changes the color of his standing square with every move. At the beginning the two jumpers of a team stand on fields of different colors. In the diagram above, however, the two white knights are on squares of the same color and have therefore made an odd number of moves overall. How many moves that are is unannounced, but it is an odd number. The two white rooks and the white king together have made an even number of moves, and a white pawn move has also taken place. All other white pieces have not moved. So MDMV 17 / FOKUS is an even number 157

3 white moves happen. With a similar argument one shows that the number of black moves is odd. We don't need any more information. Since White has started, it is Black's turn and can mate with 1 ... Nxc2. The most famous mathematician among chess players (and vice versa) was probably the Dutchman Max Euwe (), world chess champion from and from 1954 professor of mathematics. In Euwe's time, the World Chess Federation was discussing several rules that were supposed to force the end of any game of chess in a finite number of moves. One of these rules was as follows: A game of chess ends in a draw when the same sequence of moves, with all pieces on exactly the same squares, occurs three times in a row. It doesn't matter how many moves this sequence consists of. Concretely, towards the end of the 1920s, Euwe asked himself whether this rule turns chess into a game that is necessarily over after a finite number of moves. Conversely: Are there infinite, senseless games to which it cannot be used? Is it possible that a game of chess can go on forever without any arbitrarily long sequence of moves occurring three times in a row? In his treatise Set Theoretical Considerations on the Game of Chess, Koninlie Aademie van Wetenschappen, 32, (1929), Euwe answered this question with yes. For this purpose, Euwe has constructed a game that is based on a sequence of numbers, the Thue-Morse sequence. It consists only of zeros and ones. It can be easily constructed with the following recipe: Start with a 0. Then always append the complementary sequence to the existing part of the sequence. This is the sequence where 0 and 1 are swapped. The beginning of the sequence is therefore formally, one can write the Thue-Morse sequence (an) as a 0 = 0 and for all natural numbers then a 2 = a and a 2 + 1 = a, where x is the term for a sequence term x = 1 x denotes the binary complement of x. If the first 2 terms of the sequence have been formed, this reursion formula gives the next 2, i.e. a total of 2 +1 terms. Two statements are obvious: Fact 1: The sequence consists only of blocks of four, either of the form 0110 or 1001. Fact 2: The sequence does not change because a 2 = a if you delete every sequence term with an odd index: 01/10/10/01/10/01/01/10/10/01/01/10/01/10 / 10/01 / Euwe could now prove that the Thue-Morse sequence is triple-free. What this means is that there is a section in the sequence that occurs three times in a row. It works like this: We assume that the episode is not triple-free. So there is a sequence section of m sequence members (an m section) that occurs three times in a row. We show that this can be a natural m. For m = 1 this would require 3 sections of the form 000 or 111, which contradicts fact 1. From this one immediately deduces the impossibility for m = 2, because because of fact 2, the occurrence of three identical 2-sections directly one after the other would also result in the same for three identical 1-sections. For m = 3, let xyz be a 3-section. According to the current state of our discussion, there are six possibilities for the appearance of three consecutive of these 3 sections: or or or or or All these segments are, however, impossible due to fact 1. The case m = 4 is also impossible because of fact 2, because the occurrence of three 4-sections in a row would result in the occurrence of three 2-sections, which we have already ruled out. The cases m> 4 still remain. The odd m can be excluded from this as follows: Due to fact 1, the m-section must contain a pair 11 or a pair 00 and the first member of any pair must always have an odd index. But if m were odd, the first repetition of the m-segment would have the first member of the pair with an even index. The same argumentation as for m = 2 and m = 4 can be applied to all even numbers, until this reduction leads to an odd m or an m <5. QED. What does the Thue-Morse series have to do with chess and the possibility of infinite games? Euwe constructed a game of chess from this sequence using the simple rule: Replace ede 0 with the move sequence Nb1 c3 Nb8 c6 Sc3 b1 Sc6 b8. Replace ede 1 with the move order Ng1 f3 Ng8 f6 Nf3 g1 Nf6 g8. Then the Thue-Morse sequence corresponds to the infinite, low-content partie1.sc3sc62.sb1sb83.sf3sf64.sg1 Sg85.Sf3Sf66.Sg1Sg FOKUS MDMV 17 /

4 Because the sequence of numbers is not triplicate, there is a sequence of moves, no matter how short or long, that is repeated three times immediately. The proposed rule allows a draw relation in this game. Euwe's analysis prompted the World Chess Federation not to introduce this rule. Mathemati with chessboard and pieces Every possible assignment of the lecturer to lectures means the selection of exactly one symbol + from each row and each column. This can be translated into a language of chess. A rook in chess allegedly attacks a piece that is in the same row or column as the rook. The assignment of lecturers to lectures is therefore synonymous with the placement of four non-attacking towers on the not crossed out squares of the following 4 4 chess board: Are you running out of money in the bar? ... Let your friend pay! writes Greg Gutfeld in Men s Health magazine: Let him shuffle two decks of cards and place them next to each other. Explain that you will always take one card from each stack at the same time. And bet that at some point a pair of identical cards will appear. Intuitively, it seems quite unlikely that identical cards will appear in identical positions in two shuffled decks of cards. But intuition can be fooled. Is it really unlikely? To make the work easier, we will switch to a different but equivalent type of representation. To do this, we write the numbers 1, 2, ..., 52 next to each other in this order. Then we note a purely random scrambling, i.e. permutation, of the numbers 1 to 52 in the row directly below, generated, for example, by repeatedly pulling from an urn without putting it back. How likely is it to find two identical numbers in the same position in the two rows? This is the question of the probability of a fixed point in the case of a random permutation. Put another way, the task falls into the context of problems that ask about the number of permutations with forbidden positions. Another example of this type of problem is as follows: In an institute there are four lecturers and four lectures to be given. The lecturers have specializations and preferences and can therefore give (+) or not give () certain lectures. Lecture Lecturer Algebra Geometry Stochasti Topology Adler + + Bauer + + Conrad Dorfmann Each lecturer must offer exactly one lecture, and each lecture must be offered exactly once. In how many different ways can the lecturers be assigned to the lectures? Illustration of a chessboard with a forbidden area The crossed-out squares together are labeled V and form the forbidden area. It is a subset of fields of the nxn chessboard S. Every permutation f of n numbers can also be represented on an nxn chessboard: The columns denote i = 1, 2, ..., n and the rows denote the f (i ), i = 1, 2, ..., n. Each permutation then corresponds to a partial coloring of the chessboard, in which exactly one field (i, f (i)) is colored in every row and column. We call the set of colored fields the pattern of the permutation f. Analogously, one can say: Each permutation corresponds to the placement of n non-attacking rooks on an nxn chessboard. Now let N be the number of permutations in which exat the entries (i, f (i)), i = 1, 2, ..., n, fall into the forbidden area V.This is equal to the number of possibilities to place n non-attacking rooks on the chessboard S with forbidden area V in such a way that the squares contained in V are exactly. Furthermore, let t (S) or shortly t be the number of possibilities to place non-attacking rooks on the chessboard S so that all are in the forbidden area V. After these determinations we now define the polynomial N n (x) = N 0 + N 1 x 1 + N 2 x 2 + + N nxn We are looking for the value of the coefficient N 0, the number of different permutations without forbidden positions . This is the value of the polynomial N n (x) evaluated at position 0. This polynomial obeys the following relationship: N n (x) = t (n)! (X 1) = 0 This consideration may serve as a reason: Let m the number of pairs (f, B), where f is a permutation and B is a subset of the pattern MDMV 17 / FOKUS 159 consisting of fields

5 denoted by the forbidden area V cut from f. The numbers m can be determined in two different ways: 1. For each one can choose the permutation f in N ways so that entries fall into the set V, and then there are possibilities to define the subset B. Hence m = = N 2. There are t possibilities to choose the subset B and then to choose (n)! Possibilities to extend every B to a permutation f. Hence m = t (n)! Taken together both results in = N = t (n)! and with summation over we get to = 0 = N y = t (n)! y = 0 The line side of this relationship can easily be processed further to = 0 = 0 N y = = N = 0 = 0 y N (y + 1) = 0 = N n (y + 1) If one sets y = x 1 in this, then one obtains the desired N n (x) = t (n)! (X 1) = 0 This equation fulfills an oversoll. All we need is: N 0 = N n (0) = t (n)! (1) = 0 and this is the number of permutations we are looking for with no forbidden entries. The advantage of this approach is that the numbers N including N 0 are usually extremely difficult to access, whereas the numbers t can easily be determined using their polynomial: For a given chessboard S with a forbidden area, we define with the numbers t = t (S) (the different possibilities of placing non-attacking towers on the fields of S so that all are in the forbidden area) the so-called tower polynomial of S: t (s, x) = 1 + t 1 x 1 + t 2 x 2 + + tnxn Even for complicated chessboards S and forbidden areas, rook polynomials can be calculated with relatively little effort, since there are certain simplifying operations that can be applied to the board. First of all, the rows as well as the columns of the chessboard can be interchanged at will without the rook polynomial changing for the newly created board. Furthermore, if the chessboard S including the forbidden area can be broken down in the form S 1 L 1 L 2 S 2 where L 1, L 2 are suitably dimensioned rights of non-forbidden fields, then the pleasantly simple product formula for rook polynomials t (s, x) = t (s 1, x). t (s 2, x). The reason for this is the following: Place Mananni towers on S 1 and i towers on S 2. For this there is t i (S 1). t i (S 2) possibilities .. Then all cases have to be added, that is to say sum over all i. This gives t (S) = ti (S 1) ti (S 2) i = 0 with t 0 (S i) = 1. This results in the product formula by multiplying by x, summing over = 0 to = n and sorting the summand. Finally, a development sentence should be noted here. For every given field P from the forbidden area of ​​a chessboard S, the t (S) possible arrangements of rooks can be divided into two classes. Those with a tower on P and ene without a tower on P. If a tower is on P, there may be another tower in the row or column of P. This partial board, reduced by the row and column of P, is denoted by S r, and there are t 1 (S r) tower arrangements on it. In the second case, only the P field needs to be removed. This sub-board, reduced by the field P, is called S e.also t (S) = t 1 (S r) + t (S e) and, analogously to the product formula, the development theorem t (s, x) = xt (sr, x) + t (se, x) Applying these easy-to-use rules to the lecturer example, we first get that the rook polynomial from the chessboard in Figure 1 with the prohibited area there is the same as the rook polynomial of the following Boards: 160 FOKUS MDMV 17 /

6 of the permutations without forbidden entries and the total number of all possible permutations: Figure chessboard with equivalent forbidden area The transition is explained by swapping the 2nd and 4th row of the original board. The tower polynomial of this new board can be calculated from the tower polynomials of the two simple 2 2-part boards S 1 and S 2 with forbidden areas as marked: p 52! E 1 52! = e 1 = 0.3679 And the probability of at least one fixed point is 1 p 0.6321 That is a rather high probability of almost 2/3 for this event that was initially not considered to be very likely. It is therefore beneficial to bet on the event of identical cards in the same position. This type of problem is just one of many beautiful uses of tower polynomials in mathematics. They prove to be extremely useful tools not only in combinatorial problems, but also in group theory and in many areas of number theory. Figure 3. Deomposition of the board from Figure 2 into 2x2 part boards S 1 and S 2 It is quite obvious t (s 1, x) = t (s 2, x) = 1 + 3x + x 2 excerpts from the opening lecture at the Chess Olympiad Dresden 2008 and a lecture at the University of Stuttgart Prof. Dr. Christian Hesse, University of Stuttgart, Institute for Stochasti and Applications, Pfaffenwaldring 57, Stuttgart. and thus t (s, x) = t (s 1, x). t (s 2, x) = (1 + 3x + x 2) 2 = 1 + 6x + 11x 2 + 6x 3 + x 4 By reading off the coefficients you get the numbers t 1 (S) = 6, t for this board 2 (S) = 11, t 3 (S) = 6, t 4 (S) = 1 together with t 0 (S) = 1. In summary, the desired solution N 0 = 4 results! 6. 3! ! 6. 1! ! = 5 Applying these considerations to the card placement problem, n = 52. And the forbidden positions on the associated chessboard are all squares along the diagonal from top left to bottom right. How many possibilities are there t of placing non-attacking towers on this diagonal? Obviously, t is equal to the number of possibilities to select the 52 diagonal fields, so quite simply 52 t = Harvard graduate Christian Hesse is professor of mathematics at the University of Stuttgart. The research focus of the professor in the Federal Republic of Germany, who was the longest after his appointment in 1991, is in the field of stochasti. In addition to numerous scientific works and some textbooks, he published the chess book Expeditions in die Schachwelt in 2006, which was praised by the Vienna Standard as one of the most ingenious and readable books that was written about the game of chess. Together with the Klitscho brothers, soccer coach Felix Magath, film producer Artur Brauner, actress and singer Vaile and ex-world champion Anatoli Karpov, he was appointed international ambassador for the 2008 Dresden Chess Olympiad. In May 2009 his latest book was published: The leash table of laren denens 22 tools for a better life. This leads us immediately to N 0 = (52)! (1) = 0 = 52! (1 1 1! + 1 2! 1 3!!) 52! E 1 Thus the probability p is that the card decoding takes place without a fixed point , the quotient of the number MDMV 17 / FOKUS 161