One Interesting Thing: The preponderance of 2-groups among finite groups

This is a preliminary discussion of my knowledge about 2-groups. There are still many questions I have, and I would appreciate any insights.

When we first learn about group theory, we learn some theorems about how to decompose finite groups, most notably the Sylow theorems, which tell us (roughly) how to decompose groups based on their maximal $p$-power subgroups. So, we might expect that for random finite groups, we can obtain a lot of information about them by analyzing what happens at each prime factor of the order.

And indeed, groups that appear “in nature” tend to have several prime factors, and their Sylow subgroups are typically interesting objects in their own right.  However, if we count groups not by their occurrences in nature but simply by their orders, then we see something very different: most finite groups are 2-groups: their order is a power of 2, so there is no information to be obtained by looking at other primes.

I was surprised at first to learn that the vast majority of groups are 2-groups: for example, there are 49,910,529,484 group of order up to 2000, and of those, 49,487,365,422, or more than 99%, have order $1024=2^{10}$. And the proportion of groups with 2-power order will only increase to 1 as we go further.

I don’t really understand why this is true (I have only barely skimmed the relevant papers, such as Eick and O’Brien’s “Enumerating $p$-groups” and Besche, Eick, and O’Brien’s “The groups of order at most 2000”), but here is my vague intuition. The Jordan-Hölder theorem tells us that we can assemble groups out of simple groups. Now, it is likely possible to glue two large simple groups together in quite a few ways, whereas there are fewer ways of assembling two small simple groups together. However, more relevant than the size of the pieces is the number of pieces: a Jordan-Hölder series for a group of order 1024 will contain ten factors, each isomorphic to $\mathbb{Z}/2\mathbb{Z}$. As we all learned when we were very young and trying to assemble jigsaw puzzles, there are lots of ways of putting together many small pieces, but there are not so many ways of putting together a few large pieces. And this is just as true of groups as it is of jigsaw puzzles.

But there’s a problem with this analysis: there are way more groups with order 1024 than there are with $1536 = 2^9\times 3$, even though they contain the same number of factors in their composition series. In fact, there are 408,641,062 of order 1536, which is only roughly 40 times as many as there are groups of order $512=2^9$ (as opposed to nearly 5000 times for 1024). I would like to understand this discrepancy, but I’m not there yet.

One obstacle to understanding this point for me is that there isn’t such a discrepancy for groups of order $p^nq$ versus $p^{n+1}$ when $n$ is small: for example, when $p=2$ and $n=3$, there are 14 groups of order 16, 15 of order 24, 14 of order 40, 13 of order 56, and so forth. Similarly, when $n=4$, there are 51 groups of order 32, 52 of order 48, 52 of order 80, and 43 of order 112. Since I don’t know any exciting examples of groups of order $2^n$ for $n$ large, it’s hard for me to gain intuition about what’s going on here.

There are lots of things to look into in the future, such as reading the papers by Besche and Eick. Perhaps I’ll report on them in the future.

One Interesting Thing: Homomorphic Encryption

I plan to start writing about one interesting thing I learn each week. This will serve two purposes: forcing me to think about interesting things, and also forcing me to write. Here is the first installment in the series.

Suppose I have a lot of computation I need to do, based on some initial data. (I sometimes find myself in this situation, having to calculate tables of number fields or something else of this flavor.) I could buy a supercomputer to do it for me, but then maybe I don’t need to these big computations very frequently, so it would be an expensive investment to buy a supercomputer for only occasional use. So instead, I decide to rent computing power from someone else’s supercomputer, so that I can upload my program and data to that other supercomputer.

Oh, but there’s a problem: my data are rather sensitive (so I’m probably not just computing tables of number fields), and I don’t know if the owner of the supercomputer is trustworthy or not. So I have to encrypt my data.

But now I have another problem: I have to do computations with my data, but they are encrypted. So, how do I do computations on encrypted data?

Let’s illustrate the problem with a simple example. Suppose my data consist of a string of letters. I encrypt them with a substitution cipher, replacing each letter with some other letter. So maybe I replace all instance of the letter “A” with “Q,” all instances of “B” with “D,” and so forth, making sure not to have any duplicates. Suppose I wish to increment the third letter of my string by 2, so if it was originally an “A,” then it should become a “C,” and if it was originally an “H,” then it should become a “J,” and so forth. How do I do it?

Well, if I have access to the original string, then it’s easy: just change that character. But what if I only have the encrypted version? I look at the string, and I see that the third letter is a “U.” But it wasn’t originally a “U”; that’s just the encrypted version of some letter. So, I don’t know how to increment it.

So, in order to do this increment procedure, I first have to decrypt the message. If I want this to be done on the supercomputer, then I need to provide it with the substitution key. But if I’m going to do that, then why did I bother encrypting it in the first place? My data is no longer securely encrypted. Alternatively, I could send the string back to my own computer, where I could do the process safely, and then encrypt it again and send it back to the supercomputer. But then what is the point of renting supercomputer time if I’m going to have to send the data back to my own computer whenever I want to do a computation?

In order to solve these problems, I need to encrypt my data in such a way that it is still possible to perform computations on it even when it is encrypted. To see how I might do this, let us return to the letter substitution example. If instead of having some weird rule about how to substitute letters I use a Caesar cipher, where my encryption is simply to push every letter forward by five positions (so that “A” becomes “F,” “B” becomes “G,” and so forth), then I can ask the supercomputer to increment the third letter by two positions even in its encrypted form, since incrementing the encrypted version by two also increments the unencrypted version by two.

This is a simple example of homomorphic encryption. Of course, the Caesar cipher is a terrible way of encrypting data, as it is trivial to decrypt. But some trickier encryption schemes like the Vigenère cipher also have the same property. They still aren’t secure, but we’re making small amounts of progress.

Unfortunately, my scope is still very limited here: I can increment some characters by fixed amounts, but I can’t perform other string operations. For example, I can’t replace the third character with a “T.” And if I’m using a Vigenère cipher, then I can’t reverse the string either. I want to be able to do more interesting operations with the ciphertext. Can I find an encryption method that will let me do everything I want just by acting on the ciphertext?

This is the question that homomorphic encryption answers. I won’t explain how to do the full version of it, but here’s a limited version, that can only deal with plaintext strings that are either 0 or 1 (so, two possible choices). Clearly, that isn’t sufficient for all our cryptographic needs, but it will serve to illustrate how some of this stuff works anyway.

Let $m$ be a binary digit, so either 0 or 1. To encrypt it, we choose integers $N,P,Q$. I’ll explain how they are to be related (i.e. how big they are) later. To encrypt $m$, I first pick a key $p$, which will be an odd, $P$-digit binary number (so the last digit is a 1). Now, let $m'$ be a random $N$-digit number whose last digit is $m$ (i.e. $m\equiv m'\pmod{2}$). Also, pick a random $Q$-digit binary number $q$. Encrypt $m$ as $c=m'+pq$.

Decrypting $c$ is easy if we know $p$: $m=(c\pmod{p})\pmod{2}$, where $c\pmod{p}$ means the unique integer from 0 to $p-1$ congruent to $c$ modulo $p$.

Craig Gentry, in his paper “Computing Arbitrary Functions of Encrypted Data” from which I learned most of this material, suggests choosing a parameter $\lambda$ and then setting $N=\lambda$, $P=\lambda^2$, and $Q=\lambda^5$. These choices don’t matter too much, and indeed I might suggest making $P$ a little larger relative to $N$, but they are suggestive of how large they need to be relative to each other.

Now, why is this encryption scheme homomorphic? If I have two plaintext messages $m_1$ and $m_2$, with ciphertexts $c_1$ and $c_2$, respectively, then $c_1+c_2$ and $c_1c_2$ are encrypted versions of $m_1+m_2$ and $m_1m_2$, respectively. (Note that I say “encrypted versions” rather than “the encrypted versions,” because there are many ways to encrypt the same message due to the random choices of $m'$ and $q$.)

However, we have to be a bit careful here, because the underlying point in this encryption scheme is that $c$ is close to being a multiple of $p$ and the relevant part of it (namely $m'$) is small relative to $p$. But if we do lots of operations, then the $m'$ bit can get ever larger, so that it is no longer small relative to $p$.

The conclusion is that this setup allows us to perform operations on a ciphertext a few times, but after that, we cannot reliably decrypt it into what we were supposed to get.

The Gentry paper explains how we can fix this problem into a fully homomorphic encyrption scheme, so that we can perform as many operations as we want. His paper is refreshingly readable, and he prefaces each of his technical remarks by an allegory of a jewelry store in which the owner (named Alice, appropriately enough for a paper on cryptography) does not trust her workers not to steal expensive jewels if they can get their hands on them.

Also helpful is this blog post by Craig Stuntz, called “What is Homomorphic Encryption, and Why Should I Care?” I recommend reading that before the Gentry paper for an explanation of the background of homomorphic encryption.

An experiment in imbalances

Ordinarily, when I play chess, I favor relatively balanced positions, in which the result of the game is more likely to hinge on positional ideas, rather than tactics. Hence, I do not sacrifice material often, unless I have calculated that doing so is guaranteed to work. However, this past weekend, I played a game in which I was inspired to play more freely, sacrificing material for evident compensation, but no clear win.

Simone Liao (2202) vs. Simon Rubinstein-Salzedo (2026)

My opponent is yet another of the endless string of very strong kids to play chess in the Bay Area. It’s actually a rather unusual occurrence to play against someone who has graduated from high school around here, even in the master section of a tournament. This particular kid has the distinction of being the top woman under age 21 in the country, despite being only 14!

1. e4 e6 2. d4 d5 3. Nc3 Bb4 4. e5 c5 5. a3 Bxc3+ 6. bxc3 Ne7 7. Qg4 Qc7 8. Qxg7 Rg8 9. Qxh7 cxd4 10. Ne2 Nbc6 11. f4 dxc3 12. Qd3

Up to here, everything is completely standard, except that perhaps 11…Bd7 is slightly more common than 11…dxc3. With 12…Bd7, we would transpose back into the most common line, but I wanted to play something different.

12…d4

I was still well within my book knowledge at this point, but my opponent started to think for the first time after this move. Before this, we had each only taken a few seconds to play all of our moves. The most testing line is 13. Nxd4, but she opted for what I consider to be a less dangerous variation.

13. Ng3

This is still a known move, but I forgot what the textbook response is. Fortunately, it isn’t very hard to find: white wants to put her knight on either d6 or f6 after Ne4 (or Nh5), so I have to make sure that that isn’t particularly dangerous.

13…Bd7 14. Ne4 O-O-O

White can win a pawn with 15. Nd6+ Kb8 16. Rb1 b6 17. Nxf7, but after 17…Rdf8 18. Nd6 Nf5, it may well be black who benefits more from the loss of the pawn, due to the files available for the rooks. Thus, it makes sense to play something else. In my understanding of this opening, white suffers a bit by having an exposed king and somewhat awkward piece play, but the compensation is a passed h-pawn that can become dangerous quickly if black is slow to react. Therefore, my opponent’s next move seems very reasonable.

15. h4

Okay, so white’s plan is clear. As for black’s plan, well, nothing makes a French player happier than acquiring mobility for the central pawns. One way of obtaining that is by playing f6 and trying to trade them off. However, I favored a more dramatic way of accomplishing this task: blowing the center open with a piece sacrifice. I didn’t want to play 15…Nxe5 immediately though, because I was concerned about 16. Qxd4. It turns out that black is doing fine, but I preferred to defend the d4-pawn first and then see what would happen.

15…Nf5 16. Rh3

16…Nxe5!?

Definitely not the way I usually play chess, but it felt like such a logical thing to do. Her king is stuck in the center, so I have an attack that isn’t going away any time soon, and there isn’t any clear way for white to clarify the position. I believe that I get full compensation for the knight, but no more. (I’m certainly not winning, which is reasonable, because white hasn’t done anything wrong.)

The main line I calculated before playing 16…Nxe5 was 17. fxe5 Qxe5 18. Qe2 Bc6 19. Nf2, after which I get my material back. But of course 19. Nf2 isn’t the strongest line.

17. fxe5 Qxe5 18. Qe2 Bc6 19. Ng5!

Definitely the right move. Before I played 18…Bc6, I realized that there were plenty of reasonable options other than Nf2, and I had to work out that in particular 19. Nxc3? loses (to 19…Qa5!). I also had to work out what happened after Ng5, calculating the line played through move 23.

19…Qxe2+ 20. Bxe2

20. Kxe2 f6 and now 21. Nxe6? is impossible due to 21…Rde8, winning the knight, with a big edge for black.

20…f6 21. Nxe6 Rde8 22. Nf4

And now I have two ways of recovering some material: 22…Bxg2 and 22…Ng3. I chose wrong, unfortunately.

22…Ng3 23. Rxg3

Forced. Black threatens 23…Nxe2 24. Nxe2 Rxg2. And after 23. Rh2, 23…Bb5 wins (although not my planned 23…Rxe2+? 24. Nxe2 Re8 25. Kf2 Nxe2 26. h5, and white is better).

23…Rxg3 24. Kf2 Reg8 25. Bf1

Now is a good time to take stock of the position. I felt that I was the one playing for a win here, although it’s not necessarily clear what to do. My logic, though, is that white’s pieces are rather awkwardly placed. She has to keep a bunch of pieces defending g2, and in the meantime it’s not so easy to get the queenside pieces into the game. However, it’s not so easy for me to improve my position and increase pressure. So, I decided to eliminate Ne6 possibilities.

25…Kd7? 26. h5 Be4 27. Ra2?

This seems logical enough, and it’s what I expected, but actually 27. Rb1! is much stronger, and white is doing very well. Because of this possibility, it was better to switch my 25th and 26th moves, as 25…Be4 more or less forces 26. Ra2. (The computer initially considers 26. h5 a viable option for tactical reasons, but at deeper levels of analysis, it turns out not to work very well.)

27…R3g4 28. Bd3 f5

28…Bxd3 is actually better, since white quickly gets in zugzwang: 29. cxd3 Rh4 30. Rc2 Re8, and there is no way to save the h5-pawn. However, white can still draw with 31. Ne2 Rxh5 32. Nxd4 Rd5 33. Be3 Rde5 34. Bc1 Rd5, repeating moves. During the game, though, I thought I would do well to encourage a bishop trade if doing so would allow me to strengthen my central pawn mass. After 29. Bxe4 fxe4, the central pawns are rather dangerous.

29. Bf1 Kd6 30. Ng6

30…R8xg6!?

I felt that playing this move was the height of frivolity, as there is really no need to sacrifice the exchange here. However, I couldn’t imagine that I might be worse after doing so, and the sacrifice eliminates one of white’s main sources of play. (Note how most of the white pieces are rather tied down.)

31. hxg6 Rxg6 32. Bf4+ Kc5 33. a4

This was a move I was hoping to be able to prevent, but then there it was. I was about to play 33…a5, but then I noticed something interesting.

33…Rb6!

With the threat of 34…Rb2. There is only one way to defend.

34. Bc1 Rb1 35. Ba3+ Kb6

And now I threaten 36…Bd5. Again there is only one defense (although she can throw in 36. a5+ first).

36. Bc4 Rd1

And now white loses at least a pawn.

37. a5+ Kc6

Not 37…Kxa5?? 38. Bc5#, but typically players at this level don’t do things quite that stupid.

38. Bb3 f4

The g-pawn will still be available later, so I wanted to prevent her from getting her king activated.

39. Be7 Rd2+ 40. Kf1?

So far, she has defended fairly well, and after 40. Ke1 Rxg2 41. Bf6, the game is close to equal. One possible line is 41…Bd5 42. Ra4 Bxb3 43. cxb3 c2 44. Rc4+ Kd5 45. Bxd4 c1Q+ 46. Rxc1 Kxd4, which white can hold easily. But after 40. Kf1, black is winning.

40…Bxg2+ 41. Kg1 Bd5 42. Ba4+ Kc7 43. Ra1 Rg2+ 44. Kf1 f3

Threatening 45…Bc4+, so white has to abandon defense of the c-pawn.

45. Bb5 Rxc2 46. Bf6 Rd2?!

The zwischenzug 46…a6! wins immediately: 47. Be5+ Kd8! (not Kc8, after which white gets an extra check on a light square and can therefore put up stiffer resistance) 48. Bd3 Rd2 49. Bf6+ Kc7, and the light squared bishop cannot move off the diagonal and must therefore be sacrificed.

After 46…Rd2, black is still winning, but I started losing the thread, as the bishops became increasingly active.

47. Bg5 Rb2 48. Bd3 Kc6 49. Bc1 Rh2 50. Kg1 Rg2+ 51. Kf1 Kc7?

I wanted to bring my bishop around to h3 without having something nasty happen on e4, but this is the wrong way to play. Instead, 51…f2! with the idea of running white out of moves wins comfortably. For example, 52. Rb1 c2 53. Ra1 (53. Rb2 Rg1+ 54. Kxf2 Rxc1 55. Bxc2 Ra1, and winning with three extra pawns is trivial) Rh2 54. Be2 Be6 55. Bf3+ Kc5 56. Bg2 Bd5 57. Ba3+ Kc4 58. Bxd5+ Kxd5, and the pawns win.

After this, there are still some chances for black, but we were reaching the time trouble stage after nearly five hours of play, and so there wasn’t sufficient time to make sure that our moves made much sense.

52. Rb1 a6 53. Bf4+ Kd7 54. Rb6 Bc6 55. Rb4 Ra2 56. Rxd4+ Ke7 57. Bd6+ Kf6 58. Rf4+ Kg5 59. Rf5+ Kg4 60. Rf4+ Kg5 61. Rf5+ Kg4 1/2-1/2

Neither one of us knew during the game whether this position was equal, or if not, who was better, but with 2 minutes each, we were both happy not to do anything really stupid and split the point.

I found it quite freeing to sacrifice material in this game. It has been several years at least since I last sacrificed material for any reason other than a forcing line or out of desperation in a bad position, but it might be worth trying it out again in the future.

I’d say that the opening line I played in this game was a great success, because my opponent (with the white pieces) did nothing wrong in the opening, but I was still able to sacrifice a piece and get full compensation for it. From a philosophical point of view, it’s hard for me to understand how that is possible, but perhaps the philosophy is irrelevant, and I simply ought to enjoy the games I can get out of it.

On (Not) Learning Things

I have to learn new things constantly in order to keep myself entertained. I’m rarely interested in doing things that don’t allow me to learn, and when I look back at things I have done that don’t teach me anything, I tend to feel that I have missed a good opportunity to do something sensible with my time. But it is easy for me to get confused and think that I am learning something when I am actually not.

Last weekend, I went to New York for the purpose of teaching a class on wishful thinking in mathematics, but it ended up being canceled due to too much snow. So I went to the Morgan Library for the hope of getting a good educational experience. Going to an art museum seems like a good thing to do in order to try to learn something; after all, that’s one of the things that society tells us that cultured people are “supposed” to do, and shouldn’t being “cultured” be correlated with learning things? So I thought, and so I have repeatedly thought, but now I’m reconsidering (and looking for other opinions as well).

I don’t really know what the goal of learning things ought to be, but I do have a way of determining whether I have done so: is it possible for me to write something nontrivial based on my new information that I could not have written before? If I spend two hours walking around a museum looking at paintings, then I ought to be able to say something new about art and, perhaps, write a page of two that I couldn’t have written before. But I usually can’t, and when I can, it’s generally because I’ve looked really closely at a few types of paintings and determined which sorts of brush strokes tend to result in more or less realistic-looking paintings. And I doubt that’s what I’m supposed to get out of going to an art museum. (Or is it? What am I supposed to learn from going to art museums?) I also doubt that what I’m supposed to learn from art museums is that looking at paintings teaches me nothing about art but something about how I ought to spend my time and organize my life, but that’s what happens to me some of the time.

It would probably be worthwhile to go through all the activities that I do in which I expect myself to learn something and verify that I am learning. I could try to do that by writing about everything that I do, but I would expect that to be a huge time and energy sink that would take away from other activities. I probably ought to do that more than I do (I stopped writing here for a while in my last year of graduate school, since I was already spending a lot of my time writing my thesis and didn’t want to write recreationally as well), and I will try to make it a habit to do so. However, it would also be good to have some heuristics to suggest that I am learning, even when I don’t go through with the exercise of verifying it. I could, perhaps, simply have a conversation with someone else about my experiences. That wouldn’t force me to organize my thoughts in the same way as or as carefully as writing would, but it might take less energy, and it would also have the benefit of giving me immediate feedback: if I believe I have learned something but I am wrong, I have a good chance of figuring that out as fast as possible. (And that’s something I always want: I hate being wrong, and in fact I hate being wrong so much that if I ever am, I want to know as soon as possible so that I can change and stop being wrong. I might be temporarily offended, but that’s a small price to pay for getting better at being right.)

However, asking other people to review everything I do is a lot to ask of others, even if I spread it out over quite a lot of people, and I don’t like being a burden to others any more than is necessary.

Also, much of the time, it appears to be the case that there is something interesting for me to learn, but I simply lack the creativity to work out what it is. How do I fix this?

I invite suggestions; please tell me how I can learn more and spend less time only pretending that I am learning.

Posted in education, truth | 4 Comments

My most stressful game

This past weekend, I went to Burlington to play in the Vermont Open. I had a fairly good result, scoring 2 wins, 2 draws, and 1 loss. My most interesting, and also my most stressful, game was the one from round 4, against Vermont’s top player, David Carter.

Simon Rubinstein-Salzedo (2013) vs. David Carter (2195), Vermont Open, Round 4.

1.e4 e6 2.d4 d5 3.Nc3 Bb4

The Winawer is one of the sharpest opening variations in all of chess. It can be a lot of fun to play, and I enjoy it from both sides.

4.e5 c5 5.a3 Bxc3+ 6.bxc3 Qc7

This move is annoying. The main move is 6…Ne7, when the sharpest and most common line continues with 7. Qg4 Qc7. Black sacrifices some pawns on the queenside for good piece play and (perhaps) an attack.

Black’s move could be an attempt to transpose into this line after 7. Qg4 Ne7, but there are other possibilities as well. In particular, after 7. Qg4, black could play 7…f5 or 7…f6. Both of those are quite common variations, but I didn’t know the theory for them. Thus, I thought it would be wise to stay away from them against a (presumably) well-prepared opponent. So, I just continued to develop normally.

7.Nf3 b6

This is quite a common idea in many lines of the French. Black’s biggest problem in the French is eir light-squared bishop. Thus, black does well to trade it off quickly. Of course, white should try to avoid this possibility, and I did the only really sensible maneuver that does avoid it.

8.Bb5+ Bd7 9.Bd3 Ne7 10.0-0 c4 11.Be2 Nbc6 12.a4

This move looked good at the time, and in fact it probably actually is good. The d6 square looked like such a great square to plant my bishop after I get in Ba3 and Bd6. The problem is that black gets to make moves too.

12…f6

And now I started panicking. I really have to take on f6, but then the g-file gets opened, and my king might be strongly attacked. I thought at this stage that I was probably completely lost, having fallen into some well-known (to my opponent) opening trap and would have to struggle to survive to move 30. Fortunately, this was a needlessly pessimistic view, and white is just fine.

13.exf6 gxf6 14.g3

Apparently this isn’t the sort of move that people usually make, for here my opponent started thinking for the first time. I wanted to play Bf4 next and try to control one useful diagonal, although clearly black will not let me. However, white has possibilities other than Bf4 in this position, and even ones which are consistent with 14. g3.

14…Ng6 15.Re1 0-0-0 16.Bf1

My idea was to follow up with Bh3, hitting the e-pawn, but later I opted for a different setup instead.

16…h5 17.h4 Rdg8

And here they come. I expected that black would just start piling his pieces up around my king, and that seemed very scary. Maybe I should be okay, as my king has many defenders in the area, but one is generally worried when there are so many angry pieces hovering around.

18.Kh1 Rf8

This move is completely incomprehensible to me. In fact, I guessed very few of my opponent’s moves in the next stage of the game. Generally, I get most of them right.

19.Bg2

My idea had been to play 19. Bh3, but after 19…e5, black probably benefits from having the position opened up more. As a French player myself, I know that nothing makes a French player happier than seeing the central pawns move down the board. So, I wanted to discourage that.

19…Kb7 20.Ba3

I didn’t really know what to do here. It’s not easy to find an ideal setup for my pieces, and attacking the black king also doesn’t look easy. I figured I’d at least try to rearrange my pieces a bit somehow.

The difficulty in positions like this one is that white’s strengths are not immediately relevant: I have the two bishops, perhaps good scope for my pieces once a few of them get traded, and perhaps more space. On the other hand, black is very active and has what seems to be an obvious plan: pile up on the g-file and attack my king.

20…Re8 21.Qd2

One idea I was considering was to play for something like Bb4 and a5, breaking open the queenside. But if I move my bishop to b4, black will just play a5, shutting down my play on that side of the board for a while. And then it will take me a while to get my bishop back to a sensible location of the board.

21…Nge7 22.Reb1 Ka8 23.Bc1 Nf5

Now, the move I wanted to play was 24. Bf4, and I tried a while to make 24. Bf4 e5 25. dxe5 fxe5 26. Nxe5 Rxe5 27. Bxd5 work. Unfortunately, it doesn’t work at all, so I gave up and looked for something else. The next move I might want to play is 24. Qe2, but that loses to 24…Qxg3!!, so I had to avoid that as well.

24.Qd1 Rhg8 25.Bf4 Nd6

That was a big surprise. I thought he would play Qd8 and transfer the queen to the kingside. My first thought was to try to exploit the pin on the knight with Qc1-a3, and I thought for a while that this was an unstoppable winning idea. Fortunately I then woke up out of fantasyland and realized that black would just play e5 after my queen got to a3, and then my queen would look really stupid on a3.

26.Qe2 Rg4

Okay, so black wants to sacrifice the exchange on f4. I didn’t know which one of us would benefit from that sacrifice, but I thought that at least I could encourage it under slightly better circumstances for me. Also worth noting was that the time control at move 40 was looking perilously far away, even though I still had half an hour or so remaining at this point.

27.Nh2 Rxf4 28.gxf4 Nf5 29.Qxh5 Qxf4 30.Bh3

Black was threatening 30…Qxf2 followed by 31…Ng3#. So, my first inclination was to defend with 30. Rf1. But then I thought I could just trade off the knight, and then black would have fewer attackers in the vicinity.

The computer, however, does not like my move and instead recommends 30.  Qh7 Qxf2 31. Ng4 Ng3+ 32. Kh2 Qf4 33. Qxd7 Ne2+ with a draw. But black could also try 30…Rd8, and maybe black is a little bit better.

30…Qxh4

This move was quite shocking for me. I thought black would play 30…Nxh4 or 30…Qxf2, since it doesn’t make so much sense to trade queens while attacking. The best line seems to be 30…Qxf2 31. Bxf5 exf5 32. Rg1 Re2 33. Nf3 Rxc2, with a small edge for black.

30…Nxh4 turns out to be less successful, as 31. Rg1 Qxf2 32. Raf1 Qxc2 33. Qxh4 Qxc3 34. Rg7 looks good for white: black’s pawns aren’t sufficiently far advanced as to be dangerous, while white’s pieces are actively placed.

My opponent, however, saw the logjam of pieces on the h-file and thought that it would cause me tactical problems once the queens were traded. I had thought about this as well and was worried about it, but I didn’t see anything concrete, so I suspected that I wasn’t in any danger.

31.Qxh4 Nxh4 32.Rg1 Rh8 33.Rg7 Bc8 34.Rag1 Nf3 35.Nxf3 Rxh3+ 36.Kg2 Rh8

Now white is winning. The question is how to convert this position most effectively. I had two ideas, based on two different principles. My first idea was to double my rooks on the 7th rank, since they can be quite dangerous there, and I might be able to arrange to tie up black’s pieces enough that I can get my knight in and win a few pawns.

My other idea was to trade a set of rooks off. The principle behind this idea is that it is beneficial to get rid of redundant pieces when there is a material imbalance. The point is that my two rooks serve the same purpose as each other, so the second rook might be slightly less valuable to me than to my opponent.

With these two principles at odds, I had to choose which one to follow. I decided to follow the first one for now and try to double on the 7th, but I was prepared to change that at a moment’s notice.

37.Kf1 e5

And I meant a moment’s notice. With this change in the pawn structure, black can no longer defend the f6 pawn. So, it’s time to trade rooks and attack some pawns.

38.Rg8 Rxg8 39.Rxg8 Kb8 40.Rf8 e4

And we made time control, although it wasn’t a serious issue in the end; the last several moves were fairly quick.

I looked at 41. Rxf6 exf3 42. Rxc6 Bd7 43. Rf6 Bxa4 44. Rxf3 for a while. I think it should be a fairly straightforward win, as I can get my king over to the queenside in time to stop the a-pawn from causing trouble, while I have my own passed f-pawn. But why bother getting fancy and risking it?

41.Nh4 f5 42.Nxf5 Kc7 43.Rf7+ Bd7 44.Ne3 Kd6

And now I had a long think, trying to work out whether the knight and pawn endgame was winning. If it is, that’s definitely the way to play. But if not, it would be very sad to sacrifice the exchange back and only get a draw. I concluded that it was indeed winning, although I missed some ideas.

In fact, I now think that black can draw the knight endgame. But we’ll get to that shortly.

45.Rxd7+? Kxd7 46.Nxd5 Ke6

Forced, or else 47. Nf6 picks up the e-pawn.

47.Ne3 Na5?

I thought this move was required in order to hold onto the c-pawn, but 47…Ne7! is much better. I guess we both missed this possibility. In fact, I cannot see how to win after 47…Ne7. One possible line is 48. Ke1 Nd5 49. Kd2 Nxe3! 50. Kxd3 Kd5 51. Ke2 a5!!. This last move prevents the black king from getting through on the queenside, and the kingside is too far away: if the white king tries to get through on the kingside, black will play b5! and promote the a-pawn and win.

So, instead white might try to play 51. a5, with the idea of breaking up black’s queenside pawns and then collecting them with the king. The problem is that the black king can chase the white f-pawn and promote the e-pawn. For example, play might continue 51…bxa5 52. Kd2 Ke6 53. Kc1 Kf5 54. Kb2 Kf4 55. Ka3 Kf3 56. d5 Kxf2 57. d6 e3 58. d7 e2 59. d8Q e1Q, and the queen endgame is surely drawn.

Alternatively, I can take the c-pawn immediately with 48. Nxc4, but black just plays 48…Nd5 and 49…Nxc3, and it’s hard to see why white should expect to win that.

48.Kg2 Kf6 49.Kg3

Gaining a tempo.

49…Kg5 50.f3 exf3 51.Kxf3 Kf6 52.Ke4 Ke6 53.d5+ Kd6 54.Kd4 a6 55.Nxc4+?!

This move wins, but 55. Nf5+! wins much more easily. Play can continue 55…Kd7 56. Ng3 Kd6 57. Ne4+ Ke7 58. Ke5 Nb7 59. d6+ Kd7 60. Kd5 a5 61. 62. Nf6+ Kd8 62. Kc6 Nc5 63. Kb5 Nb7 64. Ne4, eventually winning all the pawns.

55…Nxc4 56.Kxc4 b5+?

The most testing line, by far, is 56…Ke5!. Then I have to find 57. d6! Kxd6 58. Kd4 Kc6 59. c4 Kd6 60. c5! bxc5 61. Ke4! Kc6 62. c4! Kd6 63. Kf5 Kc6 64. a5 Kd6 65. Kf6, and I’ll eventually win both of the black pawns. But after 56…b5+, it’s trivial.

57.axb5 axb5+ 58.Kxb5 Kxd5 59.c4+ Kd6 60.Kb6 1-0

It wasn’t a perfect game, and trading down from a winning late middlegame/early endgame to what now appears to be a completely drawn knight and pawn endgame was inexcusable, especially after spending 15 on that move. But I’m mostly pleased with my play. However, I’m probably going to dump the 7. Nf3 line against 6…Qc7, because it just seems too easy to find ideas for black and too hard to find them for white. Also, I’ll probably get a heartattack if I keep trying to play games like this. (Well, either that or I’ll get used to them and they’ll stop causing me such anxiety.) I was a wreck until at least half an hour after the game had finished. That couldn’t have helped me much in the next round, where I lost against a master without much of a fight.

Posted in chess tournament | 1 Comment

I shall have to be contented with a tulip or lily

I came to the Labor Day tournament this year full of high expectation. I’d just done a large overhaul of my openings and was feeling quite well-prepared.

In my first game, I faced Philipp Perepelitsky, whom I had known since high school. (Philipp beat me once in a high-school league game back in 2002. Back then, Philipp was rated around 1800, and I around 1400.) I played his (very) identical twin brother Edward in February, and we got a draw in a poorly-played game.

Simon Rubinstein-Salzedo (2047) vs. Philipp Perepelitsky (2151), Round 1

1. e4 d6 2. d4 Nf6 3. Nc3 g6 4. Be2

Well, I didn’t prepare for the Pirc, so already I was making it up. I wanted to play 4. Be3 but then thought that 4…Ng4 might be a bit annoying, so I might as well put a stop to that move first.

4…Bg7 5. Be3 Nc6

I was surprised to see this move; the knight gets kicked around while white gains space. It’s probably okay, but I was under the impression that black intends to play …c6 instead of …Nc6 in the Pirc.

6. d5 Ne5

I’d love to play 7. Nf3 here, but after Neg4, I thought black would be quite happy. In retrospect, this seems like a stupid thing to have been concerned about: 8. Bd4 c5 9. dxc6 bxc6 10. h3 Nh6 looks excellent for white.

7. h3 c6 8. dxc6 bxc6 9. Nf3 Qa5 10. Bd2 Qc7?

After 10…Nxf3+, black has equalized. Now, white is close to winning.

11. Nxe5 dxe5 12. 0-0 0-0

White has a position with no weaknesses, and all the white pieces have at least decent scope. On the other hand, black has weak pawns on a7 and especially c6, and the bishop on g7 has nowhere to go. My plan is to get my pieces to good squares on the queenside, and especially to put either a knight or bishop on c5, and start pressuring the c6 pawn.

At this point during the game, I thought it might make more sense to neutralize some of black’s pieces on the kingside, so I played

13. Bg5.

This move is okay; my idea was to prevent the knight from moving to a better square. (Black would probably like to play something like Nd7-b6.) But the knight isn’t the most dangerous black piece at the moment, so I should discourage play with a black rook on the d-file instead. 14. Be3 with the idea of Bc5 is better.

13…Be6 14. Qc1 Rfd8

Black wants to place the rook on d4 to gain counterplay against the e-pawn. I can stop this by playing f3 at some point, but then black can play Nh5-f4, so I’d prefer not to have to do that.

15. Be3

At this point, I was expecting my opponent to play 15…Rd4 anyway; if 16. Bxd4 exd4 17. Na4 Nxe4, I think black has fantastic compensation for the exchange: he has managed to get his bishop on g7 active, and it’s now a strong piece. Furthermore, black’s center pawns are now strong; it’s hard to stop ideas of c5-c4. So, on 15…Rd4, I was planning to play 16. Bd3 (now threatening to take on d4). After 16…Rd6 17. Na4 Rad8 18. Nc5, white is doing well.

15…Rab8 16. Bc5 Ne8

Black’s plan is to play Nd6, followed by either Nc4 or Bc4, getting a bit of activity. I thought about playing 17. b3 in order to control the c4-square, but in the end I decided on

17. b4,

which I think is a stronger move. My idea was to fix the pawn on c6 as much as possible so that I can attack it and win it when the time is right. This move also has the advantage of making the rook on b8 less powerful.

17…Nd6 18. Qe3 f5 19. f3 f4 20. Qf2 a5 21. a3 Bf6 22. Rfd1 Kh8 23. Na4 Nc8 24. Bd3 g5 25. Qe2 Nd6 26. Qf2 Nc8

I didn’t know how to make progress here if my opponent “passed” for the rest of the game (perhaps, playing Kg8-h8 endlessly). But the computer suggests that I play for bxa5; for instance, I can play 27. Ba6 h5 28. Bxc8 Qxc8 29. Ba7 Rxd1+ 30. Rxd1 Rb7 31. bxa5 Rd7 32. Rb1, and white has a delightful position. It’s not completely straightforward to win, since black is going to open up the kingside and develop threats, but with careful play, white should be winning.

27. Be2 Rxd1+ 28. Rxd1 axb4 29. Bxb4 Nd6 30. Nc5 Bc8

At this point, I felt much more comfortable about my position than I had at move 26. I have a passed pawn, a weakness on c6 to pressure, and black’s dark-squared bishop is still dismally placed.

31. Na6

My opponent looked a bit surprised when I played this move. I guess that’s understandable: the knight had a great square on c5, and the bishop was serving a purely defensive role on c8. But getting the two bishops was appealing to me, and I also reasoned that the queen would be as well-placed on c5 as the knight had been before.

31…Bxa6 32. Bxa6 Rd8 33. Qc5 Nf7 34. Rxd8+ Qxd8 35. Qxc6

And the rest should be easy, with two passed pawns on the queenside. Right? (Apparently not.)

35…Qd1+ 36. Bf1?!

I saw that after 36. Kh2 g4? I had 37. Qc8+ and 38. Qxg4(+), but I rejected it for some reason I now cannot understand. I think that’s the most sensible way to play though: I should then continue with Bd3!, cutting the queen off, and then try to get in Qg1 with a queen trade if possible. Black will make it difficult to do these things, but they might be possible.

36…Kg7 37. Qc3 h5 38. Qd2 Qa1 39. c4 e6 40. c5 Bd8

This can’t be bad either. The problem is that black’s king is frustratingly safe. Another problem is that 41. c6?? loses to 41…Bb6+, so that makes it more difficult to advance the c-pawn.

41. Kf2 g4 42. hxg4 hxg4 43. fxg4

At this point, I didn’t believe that black had any counterplay to speak of. And, in fact, that’s correct, assuming that I avoid being a complete idiot. (Sadly, I proceeded to fail spectacularly at that task from this point on.)

43…Qb1 44. Qd3 Qc1 45. Kg1 Qb2 46. Qc3 Qb1 47. c6 Bc7 48. Ba5 Bb8

So far, I’ve still been doing everything right, but now black threatens 49…Ba7+. The best move, which I strongly considered, is 49. Qc5. I was scared, however, of putting my queen and king on the same diagonal, where the queen might get pinned by the bishop. But there’s no way for black to do that. I was starting to get low on time here, though, so it’s somewhat understandable that I didn’t want to enter into something where I thought I might fall for a cheap tactic.

One possible continuation is 49. Qc5 Bd6 50. Qc4 Bxa3 51. c7 Nd6 52. Qxe6 Bc5+ 53. Kh2 Qxf1 43. Qxe5+ Kg6 55. Qh5+ Kf6 56. Qxc5 Qd3 57. e5+ Ke6 58. Qxd6+ where black’s only move is to resign.

But instead, I played the hideous blunder

49. Qc4??,

and after

49…Ba7+

I can get a draw with 50. Kh2. But, not sensing any danger, I played

50. Kh1??,

completely missing black’s next move.

50…Qb8!

with the threat of Qh8#!

51. Qd3 Be3 52. g3

I can prolong things with 52. Bd8, but that loses as well.

Qh8+ 53. Kg2 Ng5 54. Qd7+ Kg6 55. Qxe6+ Nxe6 56. gxf4 Nxf4+ White resigns

A horrific end to what seemed certain to be a well-played win for me against a rather strong player. On the plus side, though, I get to use a G&S quote for a post title.

I was devastated by this loss and proceeded to play uncharacteristically bad chess the rest of the tournament, losing 25 ratings points in the process. But that happens sometimes. I’ll try to recover my form in the next one!

Book review: Good and real

We don’t have to look very hard to find aspects of the real world that appear at first glance not to make sense or that are perplexing. With careful analysis, however, we can frequently make sense of weird scenarios.

Gary Drescher’s book Good and real is devoted to demystifying some of these paradoxes in as clean a manner as possible. The book is divided between two classes of paradoxes: those arising from physics, and those arising from ethics. According to Drescher, though, these two classes actually have a sizable overlap.

Early in the book, Drescher discusses a paradox arising from looking at mirrors: it appears that mirrors do not switch up and down, but they do switch right and left. That is, if I were to look at myself in the mirror while wearing a watch on my left hand, I would find that reflected-Simon is wearing a watch on his right hand. However, he would not be standing on his head. However, this seems unlikely to be the end of the story: how can the mirror favor one axis parallel to its surface over another?

Also, we can see by experiment that this can’t possibly be right: if I lie down facing the mirror so that my left hand is on the floor, then reflected-Simon’s right hand is on the floor; however, his head is on the same side as my actual head. In short, something different is going on. Actually, the mirror doesn’t flip the left/right axis or the up/down axis; it flips the axis perpendicular to its surface (the front/back axis). However, our method of interpreting what’s going on suggests that it flips the left/right axis when we look at our own reflections because that’s the only axis of near-symmetry that we have. Drescher’s explanation for what’s going on isn’t revolutionary, but I found it well thought-out.

Less familiar to me was his discussion about the asymmetry of time: why does moving forward in time (which is easy to do) feel so different from moving backward in time (which we can only do in some suitable metaphorical sense)? The laws of physics don’t distinguish one direction of movement in time, so why shouldn’t we be able to use similar mechanisms to move forward or backward in time, as we do to move right or left?

Drescher demonstrates, using a toy model, that time-symmetric models can easily yield time-asymmetric effects. Imagine a small universe consisting of a bunch of balls. Most of the balls are very small and move slowly; a few of the balls are very large and move quickly. Furthermore, assume that there are a lot of these balls, so that they fill up a substantial portion of the universe.

As they move around, these balls routinely collide. Eventually, the large balls slow down, and the small balls might speed up, but let’s say we don’t get to watch for long enough to get much of a sense of that. Let’s also say we’re taking a video of these balls moving around, and we’re allowed to play this video forward or backward. Are there features of this movie that will allow us to distinguish between the forward and backward versions?

Yes, there are. In particular, if we look at the forward version and we look just behind one of the large balls, we’ll see empty space, because the small balls can’t move quickly enough to fill in the space. As we look at the backward version, the empty space is in front of the balls, which is inconsistent with the way of the physics of this system works.

What’s going on here is that we’ve started with a configuration that cannot have had much of a past in this universe: we start with a configuration with low entropy, but entropy always increases. Drescher explains that the feeling we have of moving forward in time comes from an innate understanding of the increase in entropy of the forward-direction of motion in time. This section was my favorite part of the book.

Drescher then moves on to a discussion of quantum mechanics, which I found less satisfactory. His gripe with the standard (Copenhagen) interpretation of quantum mechanics is that we need a collapse of superposition when we observe a particle, but this collapse doesn’t seem to show up in the equations. So, he advocates for Everett’s “many-worlds” model, where we’re really living in a much larger configuration space and where observers are superpositions of observers. This rids quantum mechanics of its nondeterminism.

As far as I can tell, this does nothing to clear up any paradoxes we might have had: any nondeterministic system can be converted into a deterministic system if we’re willing to pass to a much larger state space, as I learned when I studied finite automata. Such a conversion is purely formal, so I fail to see how it can help to explain any paradoxes that we can’t explain at least as easily without leaving a nondeterministic world.

Then Drescher moves on to ethical paradoxes; here I start to disagree with his views sharply. The central problems he tackles are Newcomb’s problem and the (non-iterated) prisoner’s dilemma.

Here’s the setup for Newcomb’s problem. A benefactor with great predictive powers presents me with two boxes. One is a transparent box containing $1000; the other is an opaque box which is either empty or else contains$1000000. I am allowed to choose between taking both boxes and taking just the opaque box. If the benefactor has predicted that I’ll take just the opaque box, then ey has placed \$1000000 in it; if ey has predicted that I’ll take both, then ey has left it empty. What should I do? (Assume I’m just trying to maximize our payoff; the benefactor has no preference about which option I choose.)

To me, the answer is clear: regardless of what the opaque box contains, I do better to take both boxes than to take just the opaque one. The content of the box doesn’t change once I decide what to do or while I’m deciding.

Strangely, Drescher disagrees with my analysis. His line of reasoning, roughly, is that I should be the type of person who takes only the opaque box, so that the benefactor will predict this. My counter, then, is that I should be the type of person who takes only the opaque box, but then I should still take both boxes. Drescher would probably say that that’s contradictory.

Drescher provides a reasonably careful analysis, but I think his error is that he subtly assumes that this is a repeated game. If we’re going to be presented with this scenario many times (and we anticipate that), then it makes sense to take only the opaque box, because that will influence the benefactor’s predictions in the future. But that doesn’t hold if we’re only playing once.

Here’s the setup for the prisoner’s dilemma: Two criminals are caught for committing a crime and are held separately. The police ask each prisoner separately to report the other. If they both stay silent, they each get 5 years in prison; if both talk, they each get 10 years in prison. If one talks and the other doesn’t, then the one who talks goes free, and the other one gets 20 years in prison. What should they do?

For each prisoner, the better option is to talk, but it both stay silent, that’s better for both of them than if both talk. Drescher claims that they should stay silent, again roughly because he subtly interprets this as a repeated game, where this is (to a first approximation) the correct strategy.

But here, there’s an interesting point that deserves consideration. Hofstadter proposes an approach to rational decision making known as superrationality. Since the prisoner’s dilemma is a symmetric game, both prisoners should realize that only symmetric plays really make sense; therefore, they shouldn’t even consider asymmetric options in their analysis of the game and should thus stay silent.

How can we justify this way of looking at the problem? Well, suppose that both prisoners are extremely confident in the rationality of the other. If I’m one of the prisoners, I should realize that, since I’m extremely confident about both my rationality and the rationality of the other prisoner, then whatever conclusion I come to will also be the conclusion that the other prisoner comes to. So, we can’t possibly end up with differing conclusions. And it’s obvious that I prefer to stay silent, so the other prisoner much prefer that as well.

Is it convincing? Not exactly, but it’s a start. It would certainly be interesting if people could regularly come to such conclusions (the ramifications of which would be fantastic), but I don’t believe that it works as well as Drescher believes it does.

All in all, this is an interesting book, with a lot of provocative ideas. (There are lots more that I didn’t talk about here.) Some of them I think don’t make complete sense, but I’m generally more interested in people throwing out ideas than in making sure that they’re all perfectly worked out.

Posted in bias, book reviews | 5 Comments