Category Archives: Computer Chess

Are improvements in computer chess due mostly to hardware or software?

file000183685005My recent revival in interest in computer chess/checkers/gameplaying was in part spawned by the impression (not particularly support by evidence at the time) that the dramatic increase in computer chess strength must have come from more than just basic hardware improvements. It seemed obvious to me that some fraction of the increase in the play was due to new cleverness and discoveries by chess programmers. But I had no real datapoints to figure out what that split might have been.

Until I found this 2010 post by Bob Hyatt. Bob has been an expert programmer in computer chess for decades, first for Cray Blitz and later for Crafty, an awesome open source Chess program. It’s source code is amazingly interesting, and has tons of features which are pretty cool.

In the forum post, Bob compared Crafty 23.4 (which was at the time the highest ranked version he had produced) with Crafty 10.18, the version which was available 15 years earlier from 1995. Running on the same hardware, you find that Crafty 23.4 was 360 ELO points higher than older version.

But how much would we expect to gain from the factor of 1000x increase in speed between 1995 and 2006? I remember reading that each doubling of CPU speed would be worth about 100 ELO points. Bob did some experiments that suggests for Crafty, that result might be something more like 80 ELO points. That means that from hardware improvements alone, you might expect to see an increase of 800 ELO points.

This would seem to imply that only 1/3 of the improvement of Crafty was due to software, with the remaining 2/3 of the improvement due to increases in hardware speed. Bob doesn’t believe the 360/800 numbers are accurate (they are likely too broad, 1995 Crafty was probably not 1100 points weaker than 2010 Crafty) but that the ratio of the two is likely to stand up.

Bob did this post to respond to this rather long thread which I find much harder to draw any real conclusions from. But it’s still good reading.

But it would seem that my intuition is likely wrong: that at least for Crafty, about 2/3 of its gains are likely to increases in hardware speed, with only 1/3 coming from software improvements. Interesting.

Pondering computer chess…

At the risk of name dropping, on my flight out to Vancouver for SIGGRAPH last week, I had the exceedingly high luck of scoring a seat next to Pat Hanrahan. 25 years ago, I was working at Princeton in the Applied Math department, and the single smartest thing I did was make Pat’s acquaintance. Besides providing countless insights into computer graphics over lunch and chats, he helped me score my current job, where I’ve been gainfully employed for the last 23 years. He claims that he occasionally even reads my blog, so if you are reading this Pat, thanks a million!

During the two hour flight, our chat ranged over a wide variety of topics. One topic that is completely unrelated to my work is my interest in computer chess and checkers, mainly as applications of game tree search. Even as an undergraduate, I was fascinated by this topic, but when Deep Blue beat Kasparov 2-1 in a six game series in 1997, I kind of pushed this to the back of my mind. I mean, I thought it was over.

I’ve made this mistake before.

What’s amazing is that computer chess programs have gotten better recently. And not just a little better, a lot better. One particularly interesting chess program is Stockfish. Firstly, it is an open source project, which means that its innards are available for your inspection. Secondly, it is available on a wide variety of platforms, including as a free application on the iPhone. I interrupt this diatribe to show the game I played against Stockfish on my return flight. I don’t play very often, but managed to eke out a shaky draw against Stockfish with it taking 10 seconds per move. I only lost concentration once and stumbled into an obvious blunder (which I shamelessly took back and went at for another try). Here’s the game, using a spiffy WordPress plugin.

[pgn width=”512″]
[Event “Airplane Chess Game”]
[Site “WestJet 1776”]
[Date “Aug 14, 2014”]
[Round “?”]
[White “Mark”]
[Black “Stockfish”]
[Result “1/2-1/2”]

1. e4 e5 2. Nf3 Nc6 3. c3 d5 4. Qa4 Bd7 5. exd5 Nd4 6. Qd1 Nxf3+ 7. Qxf3 Nf6 8.
Bc4 e4 9. Qe2 Bd6 10. O-O O-O 11. d3 exd3 12. Bxd3 Re8 13. Qc2 Nxd5 14. Bxh7+
Kh8 15. Bf5 Bb5 16. c4 Qh4 17. g3 Qxc4 18. Qxc4 Bxc4 19. Rd1 Be2 20. Rd4 Bf3
21. Rh4+ Kg8 22. Bd2 Be7 23. Ra4 Bf6 24. Nc3 Rad8 25. Rb1 Ne7 26. Be4 b5 27.
Rb4 c5 28. Rxb5 Bxc3 29. Bxf3 Bxd2 30. Rxc5 Ng6 31. Kf1 Ne5 32. Be2 Bb4 33. Rb5
Rd2 34. Rxb4 Rxe2 35. Kxe2 Nc6+ 36. Kd2 Nxb4 37. a3 Rd8+ 38. Ke2 Nc2 39. Rc1
Nd4+ 40. Ke3 g6 41. Rc5 Nf5+ 42. Ke2 Kg7 43. b4 Rd6 44. g4 Re6+ 45. Kd3 Nh4 46.
a4 Nf3 47. h3 Ng1 48. h4 Nh3 49. f3 Nf4+ 50. Kc4 Re1 51. Rc6 Ng2 52. h5 Nf4 53.
hxg6 Nxg6 54. Ra6 Rc1+ 55. Kb5 Rc7 56. Rc6 Rd7 57. Ka6 Ne5 58. Rc5 Kf6 59. Rb5
Nc6 60. Rb7 Rd4 61. Kb5 Nxb4 62. Kc5 Nc2 63. Rxa7 Rf4 64. a5 Rxf3 65. a6 Rc3+
66. Kb5 Nd4+ 67. Kb4 Rc1 68. Rb7 Nc6+ 69. Kb5 Ne7 70. a7 Rb1+ 71. Kc5 Ra1 72.
g5+ Ke6 73. Rb6+ Ke5 74. Rb7 Nc8 75. Rxf7 Nxa7 76. Kc4 Nc8 77. Kd3 Rg1 78. Rg7
Rg3+ 79. Ke2 Nd6 80. Rg8 Kf5 81. Rf8+ Ke6 82. Rg8 Ne4 83. Re8+ Kd5 84. Rd8+ Kc6
85. g6 Rxg6 86. Kd3 Nd6 87. Ra8 Rg5 88. Kd4 Rd5+ 89. Ke3 Kd7 90. Ra7+ Ke6 91.
Kf4 Rf5+ 92. Ke3 Rb5 93. Rh7 Re5+ 94. Kf3 Kd5 95. Rd7 Rh5 96. Kg4 Rh8 97. Kf4
Re8 98. Kf3 Ke5 99. Ra7 Nc4 100. Rf7 Rd8

[/pgn]

Anyway, the third thing that I thought was cool about Stockfish was that stockfish is really good. It’s clear that it would crush all human players in a match: it’s ranked about 400 points higher than Magnus Carlsen, which means that Stockfish 5 would be expected to score about 90% against Carlsen. I didn’t think that this increase in the state of the art could have been done purely as the result of CPU speed improvements, so I wanted to look into it a bit and see what might have helped Stockfish get so good.

Interestingly, I think one of the greatest causes is from exhaustive testing. The Stockfish project has implemented a distributed testing facility called Fishhtest. The idea is pretty simple: volunteers contribute cpu time to exhaustive test commits to the source tree to see the effect on gameplay You can read more about it here.. According to the Wikipedia article on Stockfish, this allowed Stockfish to gain 120 ELO points in just 12 months.

Anyway, my chats with Pat and pondering some of the ideas from Stockfish make me want to dust off my Milhouse checkers program, and see if I can’t borrow some ideas from Stockfish as well as other ideas from Pat (implementing checkers on an FPGA?). We’ll see what happens.

On Computer Chess, including Stockfish and SmallFish

Off and on I’ve been pondering some changes to my computer checkers program called Milhouse. Most of these changes have relatively little to do with checkers per se, but are just changes to the algorithms that are common to nearly all game-tree search programs. Since computer chess has always been more popular than computer checkers, that means I’m reviewing a lot of chess programs and papers on chess.

Years ago when I started milhouse, the open source chess programs that I knew about were basically gnuchess (which has gone through a bunch of different versions, including some complete changes of the underlying chess engine) and Bob Hyatt’s Crafty. Bob is a veteran of computer chess, having written the famous program Cray Blitz which one several ACM chess events, and two World Computer Chess Championships. Crafty is very cool, and can obviously play chess at a much higher level than I ever aspire to.

But it turns out that in the last few years, chess engines continue to get better. Like a lot better. The top ranked computer programs now have ELO rankings of around 3200. By way of perspective, Gary Kasparov was the first human to break the 2800 barrier in 1989. A 400 point difference between (say) Houdini and Gary Kasparov means that we’d expect Houdini to win 92% of all games between the two. (You can find some some ratings for current chess engines here)
Poor old Crafty, ranked 600 points below at around 2621 (with 2 cpus) would probably struggle to win one game out of 100.

I find this fascinating: it’s clear that modern chess engines are plumbing depths of chess knowledge which have been beyond human understanding, and that the difference between the best human play and what is achievable by “God’s algorithm” is still pretty broad.

Anyway…

During this, I found out a few things.

First, the latest version of GNUchess is based upon the Fruit engine, and that it is probably at least in the same league as Crafty, which it wasn’t before. So, if you were dissatisfied with the old versions of GNUchess, revisiting it might be a good thing to do.

Second, a very competitive engine called Stockfish was available. The multi-cpu versions of Stockfish are very near the top performers on every ranking list I could fine, and probably represent more chess knowledge than you could ever home to find.

Third, and perhaps what is cooler, is that you can get nice IOS versions of chess programs that use Stockfish, with cool interfaces! Download versions for IOS, Android, or get the source code!, and it’s free on the iPad/iPhone. Very, very nice. I particularly like that the app includes the ability to mail the log of completed games, so you can use other programs to analyze your play.

But perhaps you are thinking: “I don’t need the best chess engine in the world, I’m just an average player, and being crushed repeatedly doesn’t help me enjoy the game.” Well, then you can definitely try out SmallFish. SmallFish uses the same powerful insides as Stockfish, but it’s wrapped in a friendly wrapper that allows you to tone it down. In fact, I found it’s default “average” difficulty level to be a bit too easy for me to beat. Here’s the log from a game I played over lunch, where I easily crushed it. I let Crafty provide an annotation to the game, so I could find out how many blunders it made. The answer appears to be about 4x as many as I made, and often quite serious ones. I’ll have to tune it up (probably to ELO 1600 or so) to keep me on my toes.

[Event "?"]
[Site "Pixar Atrium"]
[Date "Jan 13, 2014"]
[Round "1"]
[White "Mark"]
[WhiteElo ""]
[Black "Average"]
[BlackElo "1200"]
[Result "1-0"]
[Annotator "Crafty v23.4"]
{annotating both black and white moves.}
{using a scoring margin of +1.00 pawns.}
{search time limit is 10.00}

  1.      d4     Nf6
  2.     Nf3      d5
  3.      e3     Bf5
  4.     Bd3    Bxd3
  5.    Qxd3     Nc6
  6.     O-O      a6
  7.     Bd2      e6
  8.      c4     Be7
  9.     Nc3     Nb4
 10.     Qe2    dxc4
 11.    Qxc4     Nc6
 12.      a3     O-O
 13.      e4     Qd7
 14.    Rad1    Rfe8
 15.     Bf4     Bf8
 16.     Ne5     Na5
 17.    Nxd7    Nxc4
 18.    Nxf8     Nh5
                ({18:+1.99}  18. ... Nh5 19. Nxe6 fxe6 20. Bc1 Nf6 21. e5 Nd5 22. Nxd5 exd5 23. Rfe1 Re6 24. b3 Na5 25. Rd3 Rf8 26. Bg5 Nc6 27. Rc3 $18)
                ({18:+0.35}  18. ... Kxf8 19. a4 Nh5 20. Bc1 Rad8 21. e5 c5 22. dxc5 Nxe5 23. Ne4 Nd3 24. Nd6 Nxc1 25. Rxc1 Re7 26. Rfd1 Nf4 27. Rd2 $14)
 19.    Nxe6      c5
                ({18:+4.47}  19. ... c5 20. Nc7 Nxf4 21. Nxa8 Rxa8 22. dxc5 Nxb2 23. Rd7 Nc4 24. Rxb7 Nxa3 25. c6 Nc4 26. c7 Rc8 27. Rd1 Ne6 28. Rb8 $18)
                ({18:+2.02}  19. ... fxe6 20. Bc1 Rf8 21. f4 Rad8 22. e5 g6 23. d5 exd5 24. Nxd5 c6 25. Ne3 Rxd1 26. Nxd1 Rd8 27. Ne3 Nd2 28. Rd1 $18)
 20.     Nc7    Nxf4
 21.    Nxa8    Rxa8
 22.    dxc5      h6
 23.     Rd7     Rb8
 24.    Rfd1     Ne5
                ({21:+7.13}  24. ... Ne5 25. Rd8+ Rxd8 26. Rxd8+ Kh7 27. b4 Ne6 28. Rb8 a5 29. Rxb7 h5 30. f3 Nd8 31. Rb5 Nc4 32. c6 Nxc6 33. Rxh5+ Kg6 34. Rc5 N6e5 35. bxa5 f5 36. Nd5 fxe4 37. fxe4 Nxa3 $18)
                ({21:+4.95}  24. ... Ne6 25. Na4 g5 26. R7d5 Kh7 27. g3 g4 28. Rc1 Na5 29. Nb6 Nb3 30. Rc4 Re8 31. Nd7 Kg7 32. Kg2 Rc8 33. Ne5 Na5 34. Rb4 h5 $18)
 25.    Rd8+    Rxd8
 26.   Rxd8+     Kh7
 27.      b4      h5
 28.     Rb8      h4
 29.    Rxb7     Nc6
 30.    Rxf7     Nh5
                ({22:+12.07}  30. ... Nh5 31. Rc7 Nd4 32. c6 Ne6 33. Rf7 h3 34. gxh3 Kh8 35. c7 Nxc7 36. Rxc7 Nf4 37. Rc6 g5 38. Rxa6 Nxh3+ 39. Kg2 Nf4+ 40. Kf3 Nd3 41. Re6 Ne1+ 42. Ke2 Nc2 $18)
                ({22:+9.96}  30. ... Ng6 31. Rc7 Nd4 32. Ra7 Nf4 33. Rxa6 h3 34. gxh3 Nde6 35. Rd6 Nxh3+ 36. Kg2 Nhg5 37. Rb6 Nf4+ 38. Kg3 Nge6 39. Ra6 Kg8 40. Nd5 g5 41. Nxf4 gxf4+ 42. Kf3 Kf7 $18)
 31.      e5
                ({23:+10.21}  31. e5 Kh6 32. Rd7 Kg5 33. Rd6 Ne7 34. c6 Nf4 35. c7 Kf5 36. Rxa6 Ne6 37. Nd5 Nc8 38. Ne3+ Kxe5 39. Ra8 Nd6 40. Re8 g5 41. Ng4+ Kf5 42. c8=Q Nxc8 43. Ne3+ Ke5 44. Rxc8 $18)
                ({24:+12.17}  31. Rc7 Nd4 32. c6 Ne6 33. Rf7 Kg8 34. c7 Nxc7 35. Rxc7 Nf4 36. Rc6 h3 37. gxh3 Kf7 38. Rxa6 g5 39. a4 Nxh3+ 40. Kf1 Nf4 41. b5 Ke7 42. Rc6 Kd7 43. Nd5 Nxd5 44. exd5 $18)

 31.     ...     Kh6
 32.      e6     Nf6
 33.      e7     Kh7
 34.    Rxf6    gxf6
                ({17:Mat09}  34. ... gxf6 35. e8=Q Ne5 36. c6 Nc4 37. Qf7+ Kh6 38. Qxf6+ Kh7 39. c7 Nb6 40. Qxb6 Kg7 41. c8=Q Kf7 42. Qd7+ Kf8 43. Qbd8# $18)
                ({21:+20.29}  34. ... Nxe7 35. Re6 Nf5 36. Ne4 Kg8 37. c6 Kf7 38. Ng5+ Kf8 39. c7 Ne7 40. Nh7+ Kf7 41. Rxe7+ Kxe7 42. c8=Q h3 43. Qf8+ Kd7 44. Qxg7+ Kd6 45. Qh6+ Ke7 46. Qxh3 Kf7 47. Qd7+ Kg6 48. Qd3+ Kg7 $18)
 35.    e8=Q     Ne5
 36.      c6      a5
 37.    bxa5
                ({11:+30.34}  37. bxa5 Nxc6 38. Qxc6 Kg6 39. a6 h3 40. a7 hxg2 41. a8=Q Kf7 42. Qae8+ Kg7 $18)
                ({11:Mat06}  37. c7 Kh6 38. c8=Q Kg5 39. Qg8+ Kh6 40. Qf5 Nf3+ 41. gxf3 axb4 42. Qh8# $18)

 37.     ...    Nxc6
 38.    Qxc6     Kh6
 39.   Qxf6+     Kh7
 40.     Ne4      h3
 41.    gxh3
                ({5:+23.89}  41. gxh3 Kg8 42. Qd8+ Kh7 43. Nf6+ Kg6 44. Ng8 $18)
                ({5:Mat03}  41. Ng5+ Kg8 42. Qf7+ Kh8 43. Qf8# $18)

 41.     ...     Kg8
 42.     Nd6     Kh7
 43.     Nf5     Kg8
 44.    Qg7#
       1-0

Both programs are free and highly recommended.