Archive for the ‘games’ Category



Surreal numbers & chess

Tuesday, April 8th, 2008

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

exotic chess positions (2)

Wednesday, March 5th, 2008

Juan de Mairena linked in the comments to last post to a truly great retro-chess problem ! In the position below white is to play and mate in three!

At first this seems wrong as there is an obvious mate in two : 1. Qe2-f1, Kh1xh2 2. Rg3-h3 The ingenious point being that black claims a draw after 1. Qe2-f1 invoking the 50 moves rule which states

The game is drawn, upon a correct claim by the player having the move, if
(a) he writes on his scoresheet, and declares to the arbiter his intention to make a move which shall result in the last 50 moves having been made by each player without the movement of any pawn and without the capture of any piece, or
(b) the last 50 consecutive moves have been made by each player without the movement of any pawn and without the capture of any piece.

I’d love to have the ‘official’ solution to this problem. Here’s what I’ve come up with, spending the better part of the afternoon… It will not be optimal but hopefully isn’t too far off. The crucial part is a maneuver unlocking the lower left-hand cluster of pieces (in particular the ordering of white and black rook). All captures were done with pawns and the final pawn move was b2-b3. Immediately before it the situation might look something like the situation on the left (essential is that the white king should not be too far from its home-square as he will be needed later to block the white rook)

after b2-b3 the bisshop on c1 travels to f4 and the black rook squeezes in to block the white rook so that also the black king can come in and position himself at e2. Then the two rooks evacuate the first row, allowing the black king to go to h1 and then the white king comes in to block the white rook from checking the black king (situation on the left below).

Finally, the white rook comes in and positions itself at e2, afterwards the white king evacuates the first row via b2 and travels to the right-hand upper corner entering via g7. Meanwhile, the black rook comes to g1, the white rook then travels to a3 and the black rook to a2. Then, the white king goes to b7 allowing the bishop to unlock the rook on a8 going to g7, allowing finally the king to go to d8…

Perhaps there is a much simpler and more elegant solution, so if you know, please comment. Oh, btw. how is the original problem solved. Well white first cancels the 50-move rule by 1. Kd8xd7 to continue for example with 2. Rg3-g4, 3. Qe1

exotic chess positions (1)

Tuesday, March 4th, 2008

Ever tried a chess problem like : White to move, mate in two! Of course you have, and these are pretty easy to solve : you only have to work through the finite list of white first moves and decide whether or not black has a move left preventing mate on the next white move. This is even a (non-optimal) fool-proof algorithm to find the solution to this kind of chess problems. Right?

Wrong! There exist concrete positions, provable mate in two in which it is NOT possible to determine the winning first move for white! So, what’s wrong with the argument above? We did assume that, given the position, it is possible to determine all legal moves for the two players. So?

Well, some moves are legal only depending on the history of the game. For example, you are only allowed to do a castling if your king nor your rook made a prior move. Further, you can only make an en-passant-capture on the next move.

But surely all this is just theoretical? No-one ever constructed a provable 2-mate with impossible winning move. Wrong again. The logician Raymond Smullyan did precisely that in his retro-chess puzzle book Chess mysteries of Sherlock Holmes. Here’s the position :

Presumably every chess player goes for the mate : 1. Kf5-e6 2. g7-g8D But what if black counters your first move with a castling 1. … 0-0-0 ? Surely he isnt allowed to do this. Why not, is there any clue in the position to prove that either the king or the rook must have moved before?

Well, what was black previous move then? It cannot be the pawn move e6-e5 as before that move the white King would be in check, so what was it? Just one possibility left : it must have been e7-e5.

This offers then another winning strategy for white, as white can capture en-passant. 1. d5xe6 e.p. and then if black castles 1. … 0.0.0, 2. b6-b7 or is black does any other move : 2. g7-g8.

Hence, whatever the games’ history, white has a mate in two! However, looking ONLY at the given position, it is impossible for him to judge whether Kf5-e6 will do the trick!

Anyone seen similar constructions?

UPDATE

According to the wikipedia page on Retrograde chess analysis, the Smullyan-idea is an adaptation of a much older problem due to W. Langstaff in the Chess Amateur of 1922. Here’s the situation (the solution is the same as above)

Decryptable, only on fridays

Friday, February 29th, 2008

The mini-post Bill Gates’ favourite prime number, encrypted below, can only be read on a friday. Here’s why.

[BEGIN URLCRYPT decode at lce.xamai.ca/urlcrypt.php]

cScSYXdhkQUWRwVOMHzMMFdHwVdCU3VU5LcSNgXc 1VB2plVn7jPqxmJD51UWFETGVWUTR2XNNmH89EBH M3EYxUAKcxOPoEVwcjJgUCGX4Bdd0xTkAFW2YVGi YoEqs1FulUWaZRQCalJRd0Ix0iNq4BnAdERckxfE VEMYpRGwM1MUIlJSN0Sd2VVXETUdFTZwUDq6IEVe Z1EZFDFVlUIDx0Y+ZRYXQyWCREGWs0RIVzPItGGh MDLSZFEXZFWqAWXFpSVUN2VjU1R4FGVCdlFdlVLM VUl8czJlZCWDBRXc9jFhoFRrYVGmAFZhplViMRXd x0SOFTGVoVM10zNgAhUYl1RTglKUIEKZh1N8dFIU sVLGZnM1ITz6UnXBcXc1FncGwQBJYgACQ3BJUHC1 tweDMnBAcnBEsQ3KkwBk0VUmcSJ8N9eQoAEDlzOP ljQF3CELZCUpEUWhZlKdFlSIdRZLBVMkA4Al9CXe J3EW5VMvRRHoEFVqEVIQZ115YFWYYVc98kM4c9Zr 12drRURBB0EJL1KVFBaZl0YeECjUQUNdFFTLZFWh gNGZRSMqAiLRNlXrZUVWMyWRcDRQRC5bBCFSlyRQ sUWYM/Wu0lQlZTJl9GXQbVXaB1UhUVShglWZYiWw QRWoMxVWBZUMl1NXZVZ2ESIpbDXU5lWTIELUsgyo EFVqEVIQZVOWJIWYYVUXATXXhCMgoSZwk1XE5FQe 9iF6lmYukXYklmcmxHdpNXauc3d39yLmrDc0RHaA 5FQTYV5TZDFEtSSZ0yVss0QXkCVZBFGL5lYMtEQp ADIq4CESh1BHNBUqQxEoEFXzAvQlQxUzYlXagRX5 8lFa8DSPlEIuk1rFB0EUUEIAB1AQIbT20lJVdBOS NEGTdFTXETUdFTZ3QSVrABWYR0EfgCQZNladt0Jf cTWYYSQo+lFdVFW2gET3YiprpWeANERbtxaitkRU lSUcFTUXQhU+3iUVpnGjdxOaVRXhAyLmICWXMkUE dqFoEVR3kkSjdFLkD0FtJAAIoAGR1ymYkVKkISZm g1QQkYXaZxKRlFMQ0kNjBnT50DTCUQAA4w5CoXAB IXd2NneDAJAJsQBCEXDJMHBOAQdEM3BFM3CIoQyM EAAxpQB0Znc8NrdIAAET4gF14DPF4UPRdzWzQha5 YlOEdxYIh2P+50JnEDLxISXr12SWJkHwQxQhYkVj ZVIa5VmnYFVY0lTFdzWV0NJlNyKqMkQQw1RbZEPG JFZV9UMHdyEUQFKHBUUURlUidlVaVWIhYjISdxQ+ IFRWASWUxyUqNW5GpSUaRCVRZVW1p1FxwUXiwiFl 9SUfNUWUplcldkFwYlqWBTX2clXMkTPy8aNFowfF gAe4lHeH4XDK0gDOsAeJwQq51AB+9QeJoAfOkUDF UQBKgUNHByJjmCMtAhUdpVQGVmGRVULCxELEViUX EsZAVFTZ93FuQFXdcgC

[END URLCRYPT]

the King’s problem on MUBs

Thursday, February 28th, 2008

MUBs (for Mutually Unbiased Bases) are quite popular at the moment. Kea is running a mini-series Mutual Unbias as is Carl Brannen. Further, the Perimeter Institute has a good website for its seminars where they offer streaming video (I like their MacromediaFlash format giving video and slides/blackboard shots simultaneously, in distinct windows) including a talk on MUBs (as well as an old talk by Wootters).

So what are MUBs to mathematicians? Recall that a d-state quantum system is just the vectorspace \mathbb{C}^d equipped with the usual Hermitian inproduct \vec{v}.\vec{w} = \sum \overline{v_i} w_i. An observable E is a choice of orthonormal basis \{ \vec{e_i} \} consisting of eigenvectors of the self-adjoint matrix E. E together with another observable F (with orthonormal basis \{ \vec{f_j} \}) are said to be mutally unbiased if the norms of all inproducts \vec{f_j}.\vec{e_i} are equal to 1/\sqrt{d}. This definition extends to a collection of pairwise mutually unbiased observables. In a d-state quantum system there can be at most d+1 mutually unbiased bases and such a collection of observables is then called a MUB of the system. Using properties of finite fields one has shown that MUBs exists whenever d is a prime-power. On the other hand, existence of a MUB for d=6 still seems to be open…

The King’s Problem1 is the following : A physicist is trapped on an island ruled by a mean king who promises to set her free if she can give him the answer to the following puzzle. The physicist is asked to prepare a d−state quantum system in any state of her choosing and give it to the king, who measures one of several mutually unbiased observables on it. Following this, the physicist is allowed to make a control measurement on the system, as well as any other systems it may have been coupled to in the preparation phase. The king then reveals which observable he measured and the physicist is required to predict correctly all the eigenvalues he found.

The Solution to the King’s problem in prime power dimension by P. K. Aravind, say for d=p^k, consists in taking a system of k object qupits (when p=2l+1 one qupit is a spin l particle) which she will give to the King together with k ancilla qupits that she retains in her possession. These 2k qupits are diligently entangled and prepared is a well chosen state. The final step in finding a suitable state is the solution to a pure combinatorial problem :

She must use the numbers 1 to d to form d^2 ordered sets of d+1 numbers each, with repetitions of numbers within a set allowed, such that any two sets have exactly one identical number in the same place in both. Here’s an example of 16 such strings for d=4 :

11432, 12341, 13214, 14123, 21324, 22413, 23142, 24231, 31243, 32134, 33421, 34312, 41111, 42222, 43333, 44444

Here again, finite fields are used in the solution. When d=p^k, identify the elements of \mathbb{F}_{p^k} with the numbers from 1 to d in some fixed way. Then, the d^2 of number-strings are found as follows : let k_0,k_1 \in \mathbb{F}_{p^k} and take as the first 2 numbers the ones corresponding to these field-elements. The remaning d-2 numbers in the string are those corresponding to the field element k_m (with 2 \leq m \leq d) determined from k_0,k_1 by the equation

k_m = l_{m} * k_0+k_1

where l_i is the field-element corresponding to the integer i (l_1 corresponds to the zero element). It is easy to see that these d^2 strings satisfy the conditions of the combinatorial problem. Indeed, any two of its digits determine k_0,k_1 (and hence the whole string) as it follows from k_m = l_m k_0 + k_1 and k_r = l_r k_0 + k_1 that k_0 = \frac{k_m-k_r}{l_m-l_r}.

In the special case when d=3 (that is, one spin 1 particle is given to the King), we recover the tetracode : the nine codewords

0000, 0+++, 0—, +0+-, ++-0, +-0+, -0-+, -+0-, –+0

encode the strings (with +=1,-=2,0=3)

3333, 3111, 3222, 1312, 1123, 1231, 2321, 2132, 2213

  1. actually a misnomer, it’s more the poor physicists’ problem… []
AWSOM Powered