Wednesday, July 22, 2009

Two – no, three – Utterly Ridiculous Games

Well, I was so bored the other day that I succumbed to the madness of reading Geurt Gijssen’s arbiter column on ChessCafe, and – as unfortunately so often happens with bad behavior – I was richly rewarded with the most ridiculous game I’ve ever seen, which someone had submitted for an official opinion.

I won’t have time to make anything like a real chess post for a week at least, so I thought I’d throw this out there – especially for any of you whose brain may have been fried by the 8 x 8 queens post.

The question was whether, in a game where White starts with his king and queen in each other’s positions, is the checkmate after
1.e4 e5
2.Bc4 d6
3.Kh5 g6#

legal? Or – more to the point – does the result stand in a tournament game?

The questioner quoted a whole bunch of rules relating to making an illegal move, which I didn’t read because I don’t really give a damn. Gijssen said that the more relevant rules were those governing pieces being set up wrong in the starting position – if it’s discovered during the game, the game must be restarted from the beginning (with, one hopes, the pieces set up correctly).

However, he added, since giving checkmate and pressing one’s clock ends the game, then the result of the game must stand, even though it would really pain him to allow it. He proposed several technical rule changes to allow such a game to be disqualified, which (of course) I didn’t read either, since if I’d been that bored I would have been banging my forehead against the computer, not reading stuff on it.

My main point in sharing is that this is just a hilariously ridiculous game, and it’s even more hilariously ridiculous to see an international arbiter approaching it seriously. I mean, this is a game where White (a) attempts the Scholar’s Mate while (b) not noticing that he’s moving his king to h5. What are the chances that this is going to occur in an event governed by the laws of FIDE?

Furthermore, I think that Gijssen is just dead wrong for two reasons:
First of all, what the hell are the standards for “discovering” that the pieces were set up wrong – or that an illegal move was made earlier in the game? It’s hard to imagine that Black delivered checkmate without “discovering” that it was his opponent’s king he was checkmating. I mean, unless he played 4...g6 and then went “Wait a minute! That’s your king!”

For Gijssen’s logic to be correct, both players have to have realized that the piece on h5 was a king immediately after (and only after) Black played 4...g6. After all, if White still thought it was a queen, he would have just retreated it to f3 and the game would have continued. To constitute “discovering” that the pieces were set up wrong, is Black somehow required to blurt out “Oh my God! That’s your king on h5! It must have come from d1, where it was set up incorrectly in the initial position and it was an illegal move to bring it out to h5!”? Give me a break. If Black delivered checkmate intentionally, it’s hard to imagine that he didn’t also realize that the king’s appearance on h5 was not quite kosher.

An alternative, of course, is that perhaps the helpful arbiter who submitted the question pointed out that a checkmate had occurred, when neither player had noticed it. (In this case, the arbiter should simply be shot, because he should have let the kids play) I have no idea what the rules are on continuing the game after checkmate, because (like I said) I’m not that bored. I’m just a bit intrigued by the ridiculousness of it all.

Okay: the second reason that Gijssen is dead wrong is that White should be forfeited on principle for attempting to mate on f7. Quite honestly, this should overrule all other considerations. Especially with children. Granted, perhaps this is a Nakamura game (blitz playoff?) where he decided to revert to his Qh5 repertoire, but in that case he should lose even more so, because it might influence young people.

I once had an eight year old student who would not accept that this strategy could possibly be bad. I lectured him sternly about the need to get all your pieces out, but he would not listen. “Okay,” I said, “we’re going to play a practice game.” This went:
Howard – Leon
CalArts, ~1990
1.e4 e6
2.Bc4 Nc6
You see, I have prepared for my opponent’s repertoire.
3.Qf3 Nd4
and here he joyfully picked up his queen to deliver checkmate at f7, only to discover that his bishop was blocked. And that he had a problem on c2. Consternation ensued.

(Here, actually, you see why this mindless checkmate goal is such a destructive meme: here’s a kid who – when he looks freshly at a position – can notice that not only his queen is attacked but there’s also a costly fork on c2. And yet, when planning his mate, he was so deeply on automatic that he didn’t notice that my e6 pawn blocks his bishop from f7)

The game continued:
4.Qc3 Bc5 I considered 4...c5, but thought it wouldn’t teach him as much about the importance of development if I won while behind in development. Luckily, the game finished very “instructively”:
5.d3?? Bb4
6.Qxb4 Nxc2+
because of 7...Nxb4 coming

A much nicer game, which actually accomplished its instructional purpose and got me the best parental response that I’ve ever had or heard of. Howard was a bit sulky after the game, so I thought it best to give his mom a little heads-up on what had happened.
So I drew her aside when she came to pick him up and said (quietly, out of the side of my mouth, like a secret agent) “We played a training game today, and I, uh, sort of kicked his ass.”
Mom: Well, I should hope so! We are paying you after all!

She also reported the following week that in his games with his father, Howard had taken to admonishing him over and over to get all his pieces out. It is good to have one’s instructions taken to heart.

If my math is right, Howard is almost 30 years old now. I wonder if he still plays chess.

The Third Ridiculous Game
When I started this post, I called the first game the most ridiculous one I’ve ever seen, but then I realized that wasn’t true. The most ridiculous chess game I know of goes
1.e4 e5
2.Qh5 Ke7

But that’s just so offensively ridiculous that I won’t even give it a diagram. It does seem to show, though, that there’s a theme of an early Qh5 being associated with ridiculousness. Elizabeth Viccary just made a post where she mentions an argument among some players about what move is most often a good one (or bad one) – wherever it occurs in whatever game. I’d make a case for Qh5 to most often turn out to be a silly move.

Sunday, July 5, 2009

8 x 8 Queens

The famous Eight Queens problem has always fascinated me, perhaps because I’m so bad at it. The problem is to place eight queens on the chessboard in such a way that none of them attack one another (diagram shamelessly copied from Wikipedia).

I actually think that the reason it’s so fascinating to me is because I can’t see any pattern for the placement of the queens. I mean, a lot of the queens are a knight’s move apart, which only makes sense, since it’s the closest way to pack them without them attacking one another. But obviously this also gets broken quite a bit, and there turns out to be no simple heuristic as to where to start over once you’ve run your string of knight-related queens to the edge of the board (as happens on the left-hand side of the diagram).

This would also be why I’m so bad at it – because I can’t see any overall pattern. So ideally, to “subdue” this problem, I’d want to find a way to see patterns in it – by which I mean human-recognizable ones, not paper algorithms that can generate a solution but can’t be perceived over the board.

Another thing I’ve wondered about off and on is how many eight-queen solutions can be placed on a single board, where one is not allowed to put more than one queen on a square. In other words, can I put one set of eight yellow queens on the board such that none of them attack one another, then put a set of blue queens on vacant squares such that none of them attack one another, and so on for eight sets of eight queens?

Packing: the Rotational Approach
Now, these patterns are much too random-looking for me to just try mixing and matching them. One needs a heuristic. The first one involved packing a whole 8-queen pattern into one quarter of the board via rotation.

For instance, if I give the board three quarter-turns, and on each turn I “trap” whatever queen is in the lower-right, then I’ve packed all eight queens into one quarter of the board. If I can do this without any of them landing on top of one another, I’ll have proved that the initial position can be rotated four times to give us four solutions that fit on the same board. The diagram below shows how our initial position fails this test:

Here I’ve colored the home square of each queen, and colored the square that it packs to (in the lower right) the same color. Six of the queens rotate without interference, but the two on the magenta squares map onto one another, ruining the situation.

Well, let’s not try to break down an existing pattern – let’s try to generate one of our own. And let’s not bother with the four rotations, let’s immediately test for eight.

Generating our own solutions
This quarter of the board can be split in half down the long diagonal. If I can take each eighth of the board and spin it out into a valid eight-queens pattern, then the way I’ve generated it will prove that (a) it can be spun three times to give us four non-interfering eight-queens patterns, and (b) it can then be flipped across the long diagonal to give us four more – our ideal solution of eight non-interfering patterns.

It’s not quite as simple as that, because the long diagonal squares can’t each be divided in half. But one can split them two and two: for instance in the diagram above, one can take the set of the six yellow squares plus the two deep blue ones on the long diagonal, and then take the set of the six light blue squares plus the two black ones on the long diagonal. If both sets can be spun out into a valid eight-queens pattern, it will show that it is possible to fit eight sets of eight queens on a chess board.

It is fairly easy to show that this is impossible. Let’s start with the central dark blue square and work our way down the column of yellow squares beneath it:

Already, ominously, there is only one rotational slot possible for the second square (possible rotations shown in green). And there is only one for the third square (shown in magenta). By the time we get to the fourth square, there is no space available for it that doesn’t attack an already placed queen.

The reason for this is easy to see: we’re starting out with four squares on the same column, and there are only four rotations available. Therefore, we have to distribute our rotations with optimum efficiency, one queen each on the two central columns and two each on the two central rows. But queen number one is already on both a central column and a central row, taking up two slots. Thus, we can only add two more queens before running out of slots. The exact same problem applies with the corner square.

I believe that there are similar issues with light-blue-centered eighth of the board, but those would be more complicated to demonstrate. In the meantime, it’s clear – there can be no fully 8x8 queen solution generated in this way.

Is this a packing problem or a tiling problem?
Well, this got me thinking about approaching the problem in a related way: these rotational rings of queens don’t attack one another; so if I can find a pair of rings that cover the whole board without attacking one another (a) it’ll be pretty cool and (b) it might open the way to seeing other patterns.

Well, that doesn’t work. In fact, if we make a ring of queens that are on rotations of the square e3:

We find that just two more queens (in the lower left and right corners) completely cover the board. Now we’re starting to get more human-grokkable patterns, but we’re also straying a bit from the task. So I started to wonder: is this a packing problem or a tiling problem?

It’s sort of a mixture of each: if it’s a packing problem, then it’s to find the most efficient packing given a constraint (queens can’t attack each other) that makes the packing very inefficient; or, if it’s a tiling problem then it’s to find the least efficient tiling given a constraint that tends to make the tilings maximally efficient. This is an issue especially with our 8 x 8 queens task, since it's actually a packing of a packing (or a packing of a tiling?).

Okay, so let’s take a look at whether this ring of queens idea can give us patterns that need less than six queens to control (or occupy) the whole board. One does not have far to look for a generalized solution!

For each non-mutually-attacking rotational ring of queens outside the central sixteen squares, the four queens in the ring leave exactly four squares uncovered. These squares are symmetrically distributed on the long diagonals, so that one more queen on any of these four squares covers them all and completely controls the board.

In other words, now that we’ve shown that e3 needs six queens to cover the whole board, the five remaining yellow squares from our original eighth-board formation all have five-queen solutions to the problem of covering the whole board. Here are those formations:

e2 (I’ve just colored the appropriate squares rather than drawing actual queens)





A few points here:

1) I think this exhausts the solutions possible with five queens. I don’t have a proof, but these five patterns strongly exploit both the rotational symmetry of the board and that of the queen herself. As soon as I mess up the symmetry, the solutions start requiring more queens.

2) I will hold out the possibility that there may be a solution with four queens, randomly and brilliantly placed (sort of like the famous problem of how to connect nine dots with only four straight lines). But I think the probability of this is low.

3) Among these five solutions, each uses a different long diagonal square except that two use the corner. However, you can see that I have cunningly notated one corner in the lower left and one in the upper left (all other long diagonal squares are in their lower left rotation). This means that (a) we can place each of these five solutions on the chessboard at the same time without any queens landing on top of one another, and (b) we can then flip this composite solution horizontally to give us a total of ten solutions packed onto the same chessboard.

I like this.

Update: after writing all this, I did some online research and found out that there already exists a proof that five queens is the minimum number to completely cover an 8x8 chessboard, and that moreover there are 638 “basic” solutions that can be rotated and reflected to produce a total of 4860 distinct positions satisfying the condition. But intriguingly, the position given as an example follows the same form as my five solutions: a ring of four queens plus one “cleaning up” on the long diagonal. I wonder how many of the solutions follow this form.

Back to the original problem
Can this shed any light on our original problem of the eight queens, and how many of them can be packed onto a chessboard? It does. Let’s take a look at Wikipedia’s solution #1 again:

Although the presence of queens at d8 and h5 mean that this solution can’t be rotated a quarter-turn in either direction, it can be rotated 180 degrees. That gives us the following pair of solutions, notated here with red squares for the original queens, and blue squares for the rotation:

Now I call that an amazingly regular pattern – one that is very human-understandable! First of all, this is a pair of solutions packed onto the same board. But one can also easily see by looking at the pattern that it can be flipped either horizontally or vertically without any of the queens landing on top of one another. But then it can’t be flipped again, because either of these flips gives us the same composite pattern of four solutions packed onto the same board. (This is actually a result of the operations we’ve done, since flipping horizontally followed by flipping vertically is the same as rotating 180 degrees)

Looking at the existing “basic” eight queens solutions (there are only twelve), there aren’t any whose composite patterns of four magically compliment one another, giving us the ideal eight solutions. However, there is at least one pair of eight-queen patterns where the solution and one reflection can fit into the space left by the full composite of another.

Each of the twelve basic solutions must also be a distinct eight-queen pattern in either of its reflections, since for a reflection to have a queen land on top of another means that those queens must have started out on the same row or column – an impossibility giving the starting restrictions. Each of the twelve basic solutions also possesses exactly one non-interfering rotational version. All twelve patterns contain at least one pair of queens that interfere with one another rotationally, but those that contain two pairs interfere with each other at the same number of rotations.

So each basic eight-queen pattern can be packed onto the board with exactly three other versions of itself. And once this is accomplished, there is at least one pair of basic patterns where two permutations of the second pattern can be packed onto the board with the full four permutations of the first.

Let’s take a look. Here is Wikipedia’s pattern #2:

In passing: I like the way this pattern contains two permutations of my e3 tiling covering the chessboard with six queens:

Okay, here is Wikipedia’s #2 pattern rotated 180 degrees and then flipped horizontally (or vertically):

So far, so good.
All right, here is Wikipedia’s pattern #12:

You can see that it fits in the blank spaces left in the diagram just above it. Let’s flip this one horizontally:

This one fits, too, so let’s put them all together:

This gives us six eight-queen patterns packed onto a single chessboard.

Okay, summing up:

1) I think that this is a maximum packing for eight queens. Just looking at the twelve basic solutions, they all interfere with themselves or one another if you try to do more than six on a board. This is still a very concrete result, though, achieved by spot-checking the twelve basic solutions for rotational interference. I have no idea how to give the result (generalized or specific) in theoretical terms – for starters because I have no idea if there exists any way to represent the basic solutions themselves in theoretical terms.

2) I find it interesting that the five-queen solution can be packed onto a chessboard ten times, and the eight-queen solution six times – as close to being inverses of one another as the number of queens being used allows. One occupies 50 total squares on the chessboard and the other 48. I wonder how this number will behave for other numbers of queens on other sizes of chessboard. I imagine that as the board gets larger, it will become possible to fill a larger and larger proportion of the available squares with queens – by an analogy with knot theory, where as you increase the number of dimensions, it becomes easier and easier to slip out of a knot, and also because as the board increases in size the queen becomes proportionally less powerful.