brainwagon

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.