games – Page 6 – neverendingbooks

5 years blogging

Published December 31, 2008 by lieven

Here’s a 5 move game from $\mathbb{C} $, the complex numbers game, annotated by Hendrik Lenstra in Nim multiplication.

$\begin{matrix} & \text{White} & \text{Black} \\ 1. & 3-2i & { 3_{\mathbb{R}} } \\ 2. & 3_{\mathbb{R}} & (22/7)_{\mathbb{Q}} \\ 3. & (-44_{\mathbb{Z}},-14_{\mathbb{Z}})? & { -44_{\mathbb{Z}} } \\ 4. & -44_{\mathbb{Z}} & ( 0_{\mathbb{N}},44_{\mathbb{N}} )! \\ 5. & \text{Resigns} & \\ \end{matrix} $

He writes : “The following 5 comments will make the rules clear.

1 : White selected a complex numbers. Black knows that $\mathbb{C} = \mathbb{R} \times \mathbb{R} $ by $a+bi = (a,b) $, and remembers Kuratowski’s definition of an ordered pair: $~(x,y) = { { x }, { x,y } } $. Thus black must choose an element of ${ { 3_{\mathbb{R}} }, { 3_{\mathbb{R}},-2_{\mathbb{R}} } } $. The index $\mathbb{R} $ here, and later $\mathbb{Q},\mathbb{Z} $ and $\mathbb{N} $, serve to distinguish between real numbers, rational numbers, integers and natural numbers usually denoted by the same symbol. Black’s move leaves White a minimum of choice, but it is not the best one.

2 : White has no choice. The Dedekind definition of $\mathbb{R} $ which the players agreed upon identifies a real number with the set of all strictly larger rational numbers; so Black’s move is legal.

3 : A rational number is an equivalence class of pairs of integers $~(a,b) $ with $b \not= 0 $; here $~(a,b) $ represents the rational number $a/b $. The question mark denotes that White’s move is a bad one.

4 : The pair $~(a,b) $ of natural numbers represents the integer $a-b $. Black’s move is the only winning one.

5 : White resigns, since he can choose between ${ 0_{\mathbb{N}} } $ and ${ 0_{\mathbb{N}},44_{\mathbb{N}} } $. In both cases Black will reply by $0_{\mathbb{N}} $, which is the empty set” (and so wins because White has no move left).

These rules make it clear what we mean by the natural numbers $\mathbb{N} $ game, the $\mathbb{Z} $-game and the $\mathbb{Q} $ and $\mathbb{R} $ games. A sum of games is defined as usual (players are allowed to move in exactly one of the component games).

Here’s a 5 term exercise from Lenstra’s paper : Determine the unique winning move in the game $\mathbb{N} + \mathbb{Z} + \mathbb{Q} + \mathbb{R} + \mathbb{C} $

It will take you less than 5 minutes to solve this riddle. Some of the other ‘exercises’ in Lenstra’s paper may take you a lot longer, if not forever…

Exactly 5 years ago I wrote : “As it is probably better to run years behind than to stand eternally still, I’ll try out how much of a blogger I am in 2004.”

5 months ago this became : “from january 1st 2009, I’ll be moving out of here. I will leave the neverendingbooks-site intact for some time to come, so there is no need for you to start archiving it en masse, yet.”

5 minutes before the deadline, this will be my last post….

of 2008

less entropy in 2009!

Comments closed

sporadic simple games

Published July 13, 2008 by lieven

About a year ago I did a series of posts on games associated to the Mathieu sporadic group $M_{12} $, starting with a post on Conway’s puzzle M(13), and, continuing with a discussion of mathematical blackjack. The idea at the time was to write a book for a general audience, as discussed at the start of the M(13)-post, ending with a series of new challenging mathematical games. I asked : “What kind of puzzles should we promote for mathematical thinking to have a fighting chance to survive in the near future?”

Now, Scientific American has (no doubt independently) taken up this lead. Their July 2008 issue features the article Rubik’s Cube Inspired Puzzles Demonstrate Math’s “Simple Groups” written by Igor Kriz and Paul Siegel.

By far the nicest thing about this article is that it comes with three online games based on the sporadic simple groups, the Mathieu groups $M_{12} $, $M_{24} $ and the Conway group $.0 $.

the M(12) game

Scrambles to an arbitrary permutation in $M_{12} $ and need to use the two generators $INVERT=(1,12)(2,11)(3,10)(4,9)(5,8)(6,7) $ and $MERGE=(2,12,7,4,11,6,10,8,9,5,3) $ to return to starting position.

Here is the help-screen :

They promise the solution by july 27th, but a few-line GAP-program cracks the puzzle instantly.

the M(24) game

Similar in nature, again using two generators of $M_{24} $. GAP-solution as before.

This time, they offer this help-screen :

the .0 game

Their most original game is based on Conway’s $.0 $ (dotto) group. Unfortunately, they offer only a Windows-executable version, so I had to install Bootcamp and struggle a bit with taking screenshots on a MacBook to show you the game’s starting position :

Dotto:

Dotto, our final puzzle, represents the Conway group Co0, published in 1968 by mathematician John H. Conway of Princeton University. Co0 contains the sporadic simple group Co1 and has exactly twice as many members as Co1. Conway is too modest to name Co0 after himself, so he denotes the group “.0” (hence the pronunciation “dotto”).

In Dotto, there are four moves. This puzzle includes the M24 puzzle. Look at the yellow/blue row in the bottom. This is, in fact, M24, but the numbers are arranged in a row instead of a circle. The R move is the “circle rotation to the right”: the column above the number 0 stays put, but the column above the number 1 moves to the column over the number 2 etc. up to the column over the number 23, which moves to the column over the number 1. You may also click on a column number and then on another column number in the bottom row, and the “circle rotation” moving the first column to the second occurs. The M move is the switch, in each group of 4 columns separated by vertical lines (called tetrads) the “yellow” columns switch and the “blue” columns switch. The sign change move (S) changes signs of the first 8 columns (first two tetrads). The tetrad move (T) is the most complicated: Subtract in each row from each tetrad 1/2 times the sum of the numbers in that tetrad. Then in addition to that, reverse the signs of the columns in the first tetrad.

Strategy hints: Notice that the sum of squares of the numbers in each row doesn’t change. (This sum of squares is 64 in the first row, 32 in every other row.) If you manage to get an “8”in the first row, you have almost reduced the game to M24 except those signs. To have the original position, signs of all numbers on the diagonal must be +. Hint on signs: if the only thing wrong are signs on the diagonal, and only 8 signs are wrong, those 8 columns can be moved to the first 8 columns by using only the M24 moves (M,R).

Surreal numbers & chess

Published April 8, 2008 by lieven

Most chess programs are able to give a numerical evaluation of a position. For example, the position below is considered to be worth +8.7 with white to move, and, -0.7 with black to move (by a certain program). But, if one applies combinatorial game theory as in John Conway’s ONAG and the Berlekamp-Conway-Guy masterpiece Winning Ways for your Mathematical Plays it will turn out that the position can be proved to have an infinitesimal advantage for white…

So, what do we mean by this? First some basic rules of combinatorial game theory. To start, we evaluate a position without knowing which player has the move. A zero-game is by definition a position in which neither player has a good move, that is, any move by either player quickly leads to losing the game. Hence, a zero-game is a position in which the second player to move wins.

What is the chess-equivalent of a zero-position game? A position in which neither player has a good move is called a Mutual Zugzwang in chess literature. An example is given by the above position, if we restrict attention only to the 4 pieces in the upper right-hand corner and forget the rest. We don’t know who has the move, but, White cannot move at all and Black cannot move the King or Bishop without losing the Bishop and allowing White to promote the pawn and win quickly. In CGT-parlance, the upper-right position has value $\{ \emptyset | \emptyset \} = 0 $ where the left options denote the White moves and the right options the Black moves.

All other values are determined by recursion. For example, consider a position in which White has just one move left before the sitution is again a Mutual Zugzwang, and, Black has no good move whatsoever. After white’s move, the position will again be a zero-position and Black has no options, so the value of this position would be denoted by $\{ 0 | \emptyset \} $ and we call the value of this position to be $+1 $. Similarly, if white has no options and black has one final move to make, the position would be considered to have value $\{ \emptyset | 0 \}= -1 $.

Clearly, these are just the three easiest game-values to have and the real kick comes further down the road when one can prove by recursion that some games have non-integer values (such as $\{ 0 | 1 \} = \frac{1}{2} $ for a position in which white has one move to get to a mutual zugzwang and black has a move leading to a position of value $+1 $ (defined as before)), or non-number values such as $\ast = \{ 0 | 0 \} $ where both white and black’s best move is to get to a mutal zugzwang. Game-values such as $\ast $ are called fuzzy (or confused with zero) and are defined by the property that the first player to move wins.

Similarly, positive game-values are those positions where White wins, independent of who has the move and negatives are those that Black wins. There is a whole menagery of game-values and the WinningWays-booklets give an example based introduction to this fascinating theory.

Brief as this introduction was, it will allow us to determine the exact value of the position in the above diagram. We know already that we can forget about the right-hand upper corner (as this is a zero-position) and concentrate attention to the left-hand side of the board.

It is easy to see that neither Knight can move without loosing quickly, nor can the pawns on a5 and b7. That is, white has just 2 options : either c3-c4 (quickly loosing after d5xc4 2. d3xc4,d4-d3 3. Nc1xd3,Na1-b3) or, and this is the only valid option c3xd4 leading to the position on the left below. Black has only one valid move : d4xc3 leading to the position on the right below.

Clearly, the left-diagram has value 0 as it is a mutual Zugzwang. The position on the right takes a moment’s thought : White has one move left d3-d4 leading to a 0-position, whereas black has one move d5-d4 leading to a position of value -1 (as black still has one move left d6-d5, whereas white has none). That is, the CGT-value of the right-hand position is $\{ 0 | -1 \} $ and therefore, the value of the starting position is precisely equal to

\[ \{ 0 | \{ 0 | -1 \} \} = +_{1} \]

(called tiny-one among ONAGers)

It can be shown that $+_1 $ has a positive value (that is, White wins independently of who has the first move) but smaller than any positive number-valued games!

Noam Elkies has written a beautiful paper On numbers and endgames: Combinatorial game theory in chess endgames containing many interesting examples (the example above is an adaptation of his diagram9).

Tag: games

5 years blogging

sporadic simple games

Surreal numbers & chess