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

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

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

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