Friday, December 6, 2013

Estimating Number of Chess Positions

The exact number of unique chess positions is known for plies zero through ten from the start of the game, here.

Namely:


 0            1
 1           20
 2          400
 3         5362
 4        72078
 5       822518
 6      9417681
 7     96400068
 8    988187354
 9   9183421888
10  85375278064

And there is a serious upper bound calculated for the total possible number of unique chess positions, here.

Namely:

45193640626062205213735739171550309047984050718

Or approximately:
10^46.655

A plot of the log of the series:
 

This plot is curved downward, which makes sense, since the total number of unique positions is finite, meaning a plot of the number of positions must be asymptotic to approximately n=10^46.655, and the plot of the log10 of that number must be asymptotic to approximately 46.655.

I have hypothesized a simple asymptotic function and least-squares fitted it to the 11 data points using Excel.

I have used the parametrized function log10(n) = A(C-1/(p+B)^D), where p is the ply.  The asymptote is the limit as p-->infinity, =AC, which I have fixed at 46.655 (i.e. C=46.655/A).

Running the fit gives these approximate values (to 10 digits):
A=22215.23274
C=0.002100135549
B=53.67773548
D=1.547873206

Here is the plot with the fit overlayed:
   

And here is a table of original data against the log-fitted data, with a fourth column showing the deviation of the fit value (as a fraction of the original).


 0            1            0.939876583  -0.060123417
 1           20           19.40668546   -0.029665727
 2          400          349.1076095    -0.127230976
 3         5362         5518.540861      0.029194491
 4        72078        77265.05783       0.071964508
 5       822518       965178.7022        0.173443867
 6      9417681     10830020.03          0.149966752
 7     96400068    109839927.3           0.139417529
 8    988187354   1012777542             0.024884136
 9   9183421888   8535374347            -0.07056711
10  85375278064  66077223933            -0.226037965

But of course the interesting thing now is to extrapolate and predict the subsequent values, to compare against exact values, as they become available.

Here is an extrapolation through ply 26:

11  4.72081E+11
12  3.12601E+12
13  1.92630E+13
14  1.10879E+14
15  5.98252E+14
16  3.03569E+15
17  1.45312E+16
18  6.58063E+16
19  2.82698E+17
20  1.15496E+18
21  4.49817E+18
22  1.67377E+19
23  5.96297E+19
24  2.03796E+20
25  6.69427E+20
26  2.11715E+21


And here is the log plot with the extrapolated values included:
 

Of course there are possible problems with such a simple asymptotic model. Should the two initial points have been excluded, for instance, since in the first 2 plies the pieces have not started interacting? How about the model's prediction that the final ply-10 data point is a +23% outlier? It should be interesting to compare against the ply-11 actual data when available...

Friday, September 27, 2013

Did I Refute the Cochrane Gambit?

After five full-length rounds of the 2013 New York State Championship chess tournament (I played the four-day schedule for the first time), I finally felt I was getting some "chess legs" in the final round, six, when I successfully met the Cochrane Gambit and prevailed.  After the game, I turned over the score to genial chess journalist Bill Townsend, with the boast "a refutation of the Cochrane".  Forgive me, but I was feeling just a little cocky.

Later analysis shows that I did in fact find a best move over-the-board that was not in Fritz 10's book (but which was not a novelty either), and that I only made one serious error, which was not caught by my opponent.

For the viewers just tuning in, the Cochrane Gambit is a piece gambit by White in the Petroff Defense.  White gives up a knight for two pawns and an out-of-place black king.  Let's take a look.

Nigel Galia (1373) -- Jeff Young (1321)
New York State Championship, U1500, round 6, 9/2/2013

1.e4 e5 2.Nf3 Nf6

This is the Petroff Defense.

3.Nxe5 d6 4.Nxf7 Kxf7

And this is the Cochrane Gambit.

5.d4

The main theory move.  5.Nc3 is the alternative.  5.Bc4+ is not good, being well-answered by 5...d5 6.exd5 giving an additional pawn for an even better position after 6...Bd6 or 6...Qe8+.

5...Qe8

Not considered favorably in existing theory.  Fritz 10 book gives it a "?".  But I question that, because of the followup move below.  The queen, taking advantage of the square vacated by the king, gives an uncomfortable pin on e4, no longer protectable via d3.  (The immediate 5...Nxe4 loses the knight after 6.Qh5+, leaving Black down a pawn.)

6.Nc3 d5 7.e5

The theoretical responses, all moves trying to protect or attack the e4 pawn.  Of course that pawn remains pinned and thus vulnerable to the following indirect attack.

7...c5!

This is the followup I referred to above.  It destroys White's center.  I found this over-the-board, but in fairness it comes from the same idea in a similar line I studied years ago with help from former co-worker and local chess artist Michael Mockler:  6.Bc4+ Be6 7.Bd3 c5!

8.Bb5 Nc6

My opponent finds the right idea and I find the right response.  I was proud of my decision-making on this move also.  I felt the chess legs had really kicked in.

9.O-O cxd4

Here my opponent falters, and I keep pressing.  Ahead in material, I am more than happy to trade off knights or queens if he wants.  He needed to find 9.Ne2 both protecting d4 and breaking the pin on e5 (forcing Nd7 for black), but who wants to retreat, even if mutually, in a gambit?

10.Nxd5 Nxd5

In fairness, I did not even see the tactic, but it was obvious I had to retake, so I made this move quickly and thought on my opponent's time.  For some reason he took extra time here, perhaps trying to decide between the fork and Qh5+.  Basically I saw that Be6 would be solid for Black.

11.Qf3+ Kg8 12.Qxd5+ Be6 13.Qe4


The idea for White is obvious -- trade on c6 and then take on d4.  And here I engaged in some bad chess thinking.  I got locked in on the idea Bxc6 bxc6 without looking at the alternative recapture!  And I thought I had to protect both c6 and d4 with my queen for some reason.  The right idea for Black is to get rid of the c6 pin via a6, when after Bxc6 Qxc6 Qxd4 Qxc2 there is no imbalance of material loss either.  But the move I choose maintains Black's edge also, so I should be happy with it:

13...Qd7 14.f4 Qd5

More accurate is Bd5.

15.Qe2 Bc5

Developing with a cheapo threat, which my opponent is having nothing of:

16.Kh1 Rf8?

Here is the true blunder.  Although not horrible, it along with Black's previous inaccuracies does turn a practically winning black edge into a White edge, if White finds the way.
The idea is to control f5 to prevent the pawn advance.  What neither of us saw is that the bishop on e6 is not helping to control f5 due to the royal pin threat Bc4!  White can go ahead and play 17.f5! when Black would have to find the one response which eliminates White's control of c4, namely d3! (if Qxd3 then Nxe5; if Bxd3 then Nd4).  Instead:

17.c4 d3

Again Black is more than willing to trade down.

18.Qf2 Qxe5

Again my chess instincts come through.  I remember recognizing Qf2 as an error, and just needing to find the most accurate response, which I think I did.

19.fxe5 Rxf2

My opponent throws in the towel, trading down.  Bxf2 was more accurate for Black, because leaving the rooks on makes e5 completely vulnerable, but I was more than happy to force further trade-down in a won position.

20.Rxf2 Bxf2 21.Bxc6 bxc6

Even more towel throwing.

22.b3 Bd4

I saw the fork, a chance for even more material, a passed pawn, and took it.  Plus it centralizes the bishop.

23.Rb1 Bxe5 24.Ba3



A cheapo try for mate on f8 with the rook, but I just have too many ways out of it.

24...Bd4

The idea being 25.Rf1 c5.  I think I had by this time found a cheapo of my own as well, realizing that with the bishop on d4, the other bishop could defend any threat to d3 by safely planting on f5 with protection via g6 if necessary from any Rf1 attack, because any g4 attempt to attack the "pinned" bishop allows mate after Be4+.  To my opponent's credit, he did not fall for this.

25.Rd1 Bf5 26.Rf1 g6 27.Rd1 Kg7

And White resigns here.  The rook h8 will now finally emerge and combine with the d3 pawn to devastating effect.

So, is 7...c5! in this line a novelty?  No!  See note 52 here for references to games played from 2002 through 2005 with this line.  I suppose between the Petroff, let alone the Cochrane, being rarely-played high-level openings these days, and theoreticians focusing elsewhere, it takes a long time for results and analysis to filter up to established theory.  On the plus side, us patzers can enjoy being on the bleeding edge of theory in the meantime.  :-)

Sunday, September 1, 2013

French Advance, refuting IM John Watson

IM John Watson offers a series of videos on ICC giving a repertoire for Black, recommending the French against 1.e4.  Like most repertoire providers, he is just too glib in some lines about "his side's" advantages, usually couching it as better "practical chances".  In particular, he has left out White's best line in response to one of his recommendations in the French Advance, which I can't let stand, thus this post.

Here is the video:

free preview (first 5 minutes)

full video (requires ICC membership)

The line in question is the f6 response to White's a3:  1.e4 e6 2.d4 d5 3.e5 c5 4.c3 Nc6 5.Nf3 Qb6 6.a3 f6, where I am maintaining that the best response is 7.b4, which Watson begins analyzing in earnest at 7:48 in the video, and against which he recommends 7...fxe5 (at 8:49).  Here I am  maintaining that the best White response is 8.bxc5 which Watson covers starting at 13:43, recommending 8...Qa5 pinning the c3 pawn thus undermining d4.  Watson is correct that e5 now must be taken, but he only considers dxe5 and completely misses White's best response, 9.Nxe5!

The line then goes 9...Nxe5 10.dxe5 Bxc5 11.Qg4! (the point of getting the f3 knight off).  The most natural defense is now 11...g6, and the line goes 12.Bd3 Ne7 13.O-O O-O 14.Bg5 followed by Bf6 and Ra2, a very solid position for White.  If Black tries to defend g7 instead with 11...Qc7, she runs into 12.Bb5+!, another result of having the knights off.  Black, most unnaturally, can also let g7 go for counterplay against f2, where with perfect play by Black, White only gets a perpetual:  11...Ne7 12.Qxg7 Rf8 13.Ra2 Rf7 14.Qg4 Qb6 15.Rb2 Bxf2+ 16.Kd1 Qc7 17.Bb5+ Bd7 18.Qxe6 Bxb5 19.Rxb5 Qc4 20.Rb4 Qd3+ 21.Nd2 Rc8 22.Rxb7 Qxc3 23.Rxe7+ Rxe7 24.Qg8+ Kd7 25.Qxd5+ Ke8 26.Qg8+.

Finally, if Black declines the knight exchange after 9.Nxe5 trying for Watson's "big center", she can sac that pawn and get a restricting c6-d5-e4 chain (ironically somewhat the mirror of White's earlier advance chain) via 9...Nf6 10.Nxc6 bxc6 11.Bd3 e5 12.O-O e4 13.Be2.  But there is no further rolling and the position is very good for White.

So Mr. Watson, if you're reading have you addressed this line perhaps in another video?  (I haven't looked through all of them.)  If not, maybe you should at some point.  :-)

Sunday, May 26, 2013

ST:TNG 3-1 Evolution

As an Original Series fan, I still sometimes try to find something to like about Star Trek TNG (The Next Generation). Here are some comments/impressions/opinions I wrote after jumping into the beginning of season 3.


So many (stale?) flavors reused from TOS, starting with the obsessed scientist (Daystrom, The Ultimate Computer) with a touch of misguided rank-puller (Fox, A Taste of Armageddon; Ferris, The Galileo Seven).  The misbehaving computer (Tomorrow is Yesterday, Court Martial, The Menagerie).  The scientific probe launch (The Immunity Syndrome). The dilemma of whether to kill a sentient but dangerous lifeform (The Man Trap).  Alien life inhabiting and speaking through a crew member (The Lights of Zetar, Return to Tomorrow) (and a GREAT job as always from Spiner).  And the provision of a bare planet as a new home for the now-subdued enemy (Space Seed).

I also caught a flavor of http://en.wikipedia.org/wiki/Fantastic_Voyage in the miniaturization aspect, as well as The Andromeda Strain in the escaped-from-lab aspect.

Then there are all the "let the viewer identify" elements, most obvious in TOS as Earth-copied alien planets and problems and time travel back to Earth (City on the Edge of Forever, Tomorrow is Yesterday).  Here we have regular natural phenomenon ("just like geysers", gosh), everything Wesley (mother-son issues, teenage issues, school-project/all-nighter issues, admitting-mistakes issues), prodigy/fame issues, and of all things baseball obsession (what?).

As to "Evolution", obviously it is referring to the evolution of the Nanites into a collective sentience, but also of course to Stubbs's psychological evolution away from narrow obsession into compassionate humility, aided by Troi of course and also by the Nanites' near success in killing him and the doctor's success in saving him.  This at least is different from TOS, where the misguided always got poetic justice at the end.  Finally must be mentioned Wesley's supposed social evolution, but it's really just a tag line joke, blechh.

Best part of the episode: Wesley's 'fessing up to Mom followed by Mom doing the crew briefing.  Wheaton gets to show his chops, such as they are, and Mom steps up to run interference for her son.  Only problem is why didn't Wesley, as the expert, have more to say as to Nanite details at that point; I suppose we can chalk that up to them having evolved already beyond his expertise...

Sunday, March 10, 2013

Completely Annotated King's Knight's Gambit, Part 1

My idea for this post is a thorough annotation of each and every move of a King's Knight's Gambit main line (Fischer defense), with the ideas behind, the implications of, and the changes caused by that move. Mentioning but not exploring variations, in order to keep focus and avoid confusion.

1.e4
What is the idea of 1.e4? White has taken the pawn from the 4-time over-protected e2 square (from Qd1, Ke1, Bf1, and Ng1) to the completely unprotected e4 square. Viewed that way, it is a real "throw the hat over the fence" move. Compare against 1.d4, where a similarly 4-time over-protected pawn is similarly pushed 2 squares but remains protected by Qd1. So what are the corresponding benefits of 1.e4? I used to think the biggest benefit was the releasing of Bf1 (to 5 additional squares from 0) and Qd1 (to 4 additional squares from 0) (and Ng1 (to 1 additional square from 2) and Ke1 (to 1 additional square from 0)). But then why is 1.e3, which accomplishes the same thing, considered a bad opening move? And also note that 1.d4 is numerically equal in that regard except for Qd1 getting only 2 additional squares (d2,d3) instead of 4 (e2,f3,g4,h5). The answer as against 1.e3 is positional, offensive, and defensive I think. Positionally, the pawn on e3 is just a big block to the Bc1 later whereas e4 blocks nothing. Offensively, the pawn on e4 controls squares in the Black camp (d5,f5) which e3 of course does not, and also "threatens" to move into the Black camp itself (e5). Defensively, it is directly blocking Black from pushing a pawn to e4 herself. As against 1.d4, e4's advantage is a much greater latent potential against f7 should the opportunity arise (Bc4, Qf3, Qh5), as well as against Ke8 itself in some circumstances (Bb5,Qh5), none of which is facilitated by 1.d4.

As to the risk from e4 being unprotected, what can Black really do about it in the short term? One immediate attack on it which Black can launch is 1...Nf6 (Alekhine's Defense), when White's pawn simply turns the tables on the knight by enacting her "offensive" threat 2.e5, after which 2...Nd5 3.d4 seems to be the main line. The only other immediate attacks on e4 are with pawns themselves, 2...d5 (Scandinavian Defense) and 2...f5 (Fred Defense), both of which White simply answers by capturing the attacker. The only 2-move attacks by pieces available to Black (ignoring the suicidal 1...d6 2...Bf4) are 1...Na6 (Lemming Defense) intending 2...Nc5, which White preempts easily and obviously with 2.d4, and 1...b6 (Owen's Defense) preparing 2...Bb7, but White has time to defend comfortably: 1...b6 2.d4 Bb7 3.Bd3 (however note that 3...Nf6 can no longer be answered by 4.e5, because of 4...Bxg2).

1...e5
Black mirrors White's move, for all of the same reasons White chose it. The only difference being that Black is already blocked from pushing the pawn further, so in particular Black does not have the corresponding option of 2...e4 should White now play 2.Nf3 that White would have had (2.e5) should Black have played 1...Nf6. Such is the advantage of White having the first move. On the other hand, Black is now blocking White's push as well, which is one reason the Petroff Defense (2.Nf3 Nf6) is still viable for Black.

The other "good" Black response to 1.e4 is 1...c5, the Sicilian Defense, which sort of sidesteps all the issues raised by 1.e4. Except for leaving e5 as an option for White of course.

2.f4
The f pawns are important king protectors, especially at the beginning of the game. To move one is to open a dangerous line into the king, the e1-to-h4 diagonal in this case. The f4 move also takes the pawn from a protected square (by Ke1) to a square that is not only not protected but that is already controlled by Black! Welcome to the King's Gambit.

So what are the advantages? How can Black get away with this? What is the idea? First, although attacked itself, f4 also attacks Black's undefended e5, so forces Black to make a decision. Second, f4 is latently protected by Bc1; all White needs to do is move the d pawn. So Black's opportunity to grab the f4 pawn outright may be limited; and after grabbing the f4 pawn Black may quickly face the challenge of having to defend f4 herself or lose it to a good White development move (Bxf4). Third, if Black takes on f4, she gives up both the block of the e4 pawn and the control of the d4 square, giving White the moves d4 and e5 free and clear. This third purpose is called "distraction", in this case of the pawn on e5.

Is it worth it? I don't think so, which is why I don't play the King's Gambit as White and try to disprove its effectiveness as Black. Here's one demonstration that the threat against the undefended e5 is utterly nullified by the e1-to-h4 weakness: if Black declines the gambit and even leaves e5 undefended by playing 2...Bc5, White cannot even take e5 due to 3.fxe5 Qh4+; since 4.Ke2 Qxe4 is checkmate, the only choice is 4.g3 when 4...Qxe4+ 5.Qe2 Qxh1 leaves White down a whole rook for nothing.


2...exf4
I agree with Fischer, "The refutation of any gambit begins with accepting it." The disadvantages of this move have already been mentioned.What are the advantages besides the gain of material? The main one is the hit on g3 which adds significantly to White's e1-to-h4 weakness. Qh4+ has become an immediate threat because White no longer has g3 as a good counter to the move: 3...Qh4+ 4.g3? fxg3 5.hxg3? Qxh1. A secondary tactic that the move has made possible is the pin of e4 against Ke1 via Qe7.

There are three basic ways for White to meet the main threat, 1) take control of h4 thus directly preventing Qh4+, 2) make a safe(r) nest at f1 for the king to retreat into by moving the Bf1, or 3) shore up g3 with any piece other than the king, so that the g3 defense again works. 3.Nf3 seems the natural way to accomplish #1 and is the best move overall in my opinion, so it is addressed below as the main line. But it is worth considering the other ways to respond and how/why they are not as good.

There are actually four additional ways to accomplish #1: 1a) The immediate 3.g3 of course controls h4 before the queen can get there, but Black being already a pawn up is happy to force pawn trades while further breaking up White's king's defenses with 3...fxg3 4.hxg3 d5; 1b) 3.h4 occupies and controls h4 but is too easily doubled-up on via 3...Be7 4.Nf3 Nf6 leaving both g3 and g4 very vulnerable, to e.g. N-h5-g3 and/or a later Bg4, and leaves f4 untouched; 1c) 3.Qg4, the only move that both controls h4 and shores up g3, with a side benefit of attacking f4, but it fails to attacks upon it followed by Black's second tactic (pin and win of the e pawn) via 3...d5 4.Qxf4 Bd6 5.e5 Qe7 6.d4 f6; 1d) 3.Qh5 also controls h4 with a sneaky Qe5+ threat, but Black just prevents the check and then drives the queen away with 3...Nc6 4.Nf3 Nf6 and the e4 pawn also falls; if instead 4.Bc4 (mate threat), then 4...Qe7 (also pinning e4) with Nd4 and Nf6 to follow.

White has two reasonable ways to accomplish #2: 2a) 3.Bc4, the King's Bishop's Gambit, favored by some over 3.Nf3, but I think 3...Qh4+ 4.Kf1 Nf6 5.Nf3 Qh6 is a refutation (see my blog post); 2b) 3.Be2 is interesting, an only slightly more cramped version of the King's Bishop's Gambit: 3...d5 4.exd5 Qh4+ 5.Kf1 Bd6.

White has three ways to accomplish #3: 3a) 3.Qg4 already discussed as #1c above; 3b) 3.Qf3 which seems to be better than its reputation, both nullifying the immediate threat and attacking f4. One key is that Qf3 is unpinning h2 after g3 is played, because it then covers the Rh1. Black has to find (or know) that the best exploit has now changed to 3...Nc6, having some threats of hitting the queen via Nd4 or Ne5 but more importantly eyeing the fork on c2 (via Nd4 or Nb4) which the queen has abandoned. Book theory then seems to be 4.c3 Ne5 5.Qxf4 Bd6 6.Qe3 Ng4 7.Qh3, but a significant improvement for Black is 4.c3 Qh4+! 5.g3 fxg3 6.hxg3 Qe7, because White's Ng1 is now blocked from defending the pinned e4. So that theory seems to be incorrect and the main line is instead 3.Qf3 Nc6 4.Ne2!, which covers Nd4, attacks f4 a second time, shores up g3, and blocks the e-file pin all at once. (Black Nb4 is met by Na3.) 3c) The immediate 3.Ne2 is bad. Although it shores up g3, 3...Qh4+ 4.g3 fxg3 5.Nxg3 leaves White just a pawn down with a pinned knight on g3.

3.Nf3
The best move, directly preventing Qh4+ per above. Let's look at what else it does or doesn't do.  First, it doesn't do anything about stopping pins on the e file, Black's secondary strength (except for getting White closer to castling). The knight has moved from a square where it had only three moves to one where it now has five. Two of those potential moves are into Black territory (Ne5, Ng5), and they are important enough to have been given names (Kieseritzky Gambit, Allgaier Gambit) when used in the so-called Classical variation of the King's Gambit after 3...g5 4.h4 g4.

3...d6
The Fischer defense. Which he developed in 1960 or 1961 as an alternative to the Classical defense 3...g5. For more details see my blog post. Fischer called this "a high-class waiting move", but there is more to it than just that. The "waiting" part undoubtedly has to do with not rushing to defend f4 when it is not yet attacked. And as Fischer developed the defense in response to losing to a Kieseritzky Gambit (http://www.chessgames.com), it is safe to assume its main purpose is to preempt any Ne5 ideas by White. Other advantages to note: it also stops the pawn from advancing to e5 unhindered, and it releases the Bc8 (to 5 additional squares from 0) (and the Ke8 (to 1 additional square from 1) and the Qd8 (to 1 additional square from 4)). An additional subtle advantage is that it also permits Black the option of d5 (in addition to dxe5) if White plays e5, without the possibility of being captured en passant. Some disadvantages to note: it has blocked the Bf8 down to a single available move (a loss of 4 from the previous 5), and it has opened the a4-e8 diagonal into Black's king.  Another possible "disadvantage" could be that it doesn't attack anything the way d5 or f5 would (e4), thus giving White a choice of moves.

More to come in Part 2, including a possible "novelty" for Black on move 7.