brainwagon

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.