Embedded Files
The Chess Engine "Innovation"
The Chess Engine "Innovation"
At Cornell I wrote a mainframe Lisp chess player for an AI class over one Christmas break. I didn't know anything about chess engines except for minimax search. I ended up re-inventing alpha-beta search, because it was an obvious thing to do once you look at the search logs. I called it Jargon. (Jeff's Sargon, which was the Apple II chess program.)
At Cornell I wrote a mainframe Lisp chess player for an AI class over one Christmas break. I didn't know anything about chess engines except for minimax search. I ended up re-inventing alpha-beta search, because it was an obvious thing to do once you look at the search logs. I called it Jargon. (Jeff's Sargon, which was the Apple II chess program.)
Later I rewrote the engine in C for Sun workstations and then ported it to Mac with a GUI. When Mac was to update to the PowerPC processor, I got a beta compiler for the chip, so I believe it was the first RISC chess engine.
Later I rewrote the engine in C for Sun workstations and then ported it to Mac with a GUI. When Mac was to update to the PowerPC processor, I got a beta compiler for the chip, so I believe it was the first RISC chess engine.
I called my engine Innovation, because again, I was following my own path. The main difference between it and traditional chess programs was that instead of following a line and calling a Static Board Evaluator (SBE) at a terminal node to score the position, Innovation would track the delta in scores between every move in the search. This made the code ten times more complex, for example, calculating how a move would locally change the pawn structure, but it avoided recalculating the same thing from scratch over and over. Ultimately this did not pan out as a superior solution for two reasons:
1) SBE's don't actually have to calculate everything from scratch. For example, you can look up a pawn structure evaluation that you previously scored in the search and saved in a hash table.
2) Computers got faster causing the search depth to increase. At a high depth, there is a lot of incremental evaluation needed to get to a terminal node.
I called my engine Innovation, because again, I was following my own path. The main difference between it and traditional chess programs was that instead of following a line and calling a Static Board Evaluator (SBE) at a terminal node to score the position, Innovation would track the delta in scores between every move in the search. This made the code ten times more complex, for example, calculating how a move would locally change the pawn structure, but it avoided recalculating the same thing from scratch over and over. Ultimately this did not pan out as a superior solution for two reasons:
1) SBE's don't actually have to calculate everything from scratch. For example, you can look up a pawn structure evaluation that you previously scored in the search and saved in a hash table.
2) Computers got faster causing the search depth to increase. At a high depth, there is a lot of incremental evaluation needed to get to a terminal node.
At Innovation's first computer-computer tournament in Vancouver it didn't have iterative deepening (because it's an idea I didn't think of) and so it had to try to guess in advance what depth to search! I learned about iterative deepening and other techniques from other operator comrades. In the end, I put in iterative deepening, alpha-beta search, search extensions (check, captures, etc.), search pruning, transposition tables with best responses, killer heuristic, and many other heuristics. I generated various elementary endgame databases -- KPK, KQK, KRK -- in a compact format with symmetries. Later, Ken Thompson (yes, the creator of Unix) sent me CDs of larger databases he had generated. For other endgames, I created heuristics, such as for KBBK, which is very tricky at some points.
At Innovation's first computer-computer tournament in Vancouver it didn't have iterative deepening (because it's an idea I didn't think of) and so it had to try to guess in advance what depth to search! I learned about iterative deepening and other techniques from other operator comrades. In the end, I put in iterative deepening, alpha-beta search, search extensions (check, captures, etc.), search pruning, transposition tables with best responses, killer heuristic, and many other heuristics. I generated various elementary endgame databases -- KPK, KQK, KRK -- in a compact format with symmetries. Later, Ken Thompson (yes, the creator of Unix) sent me CDs of larger databases he had generated. For other endgames, I created heuristics, such as for KBBK, which is very tricky at some points.
A couple nice features of the user interface:
* It was probably also the first chess program with figurine algebraic chess notation, as I'd been designing chess fonts since the 80's.
* I had a really nice teaching feature, where you could create tutorials in a custom scripting language.
The GUI eventually became the user interface to the commercial app "Internet Chess for Macintosh", except that in the chess program. The engine was eventually used in the commerical app "Maurice Ashley Teaches Chess".
Some of Innovation's Nicest Moves
Some of Innovation's Nicest Moves
White to Move
Innovation II-Evaluator 1-0
24th ACM Computer Chess Championship
Round 2, Move 32
Cape May, NJ 6/26/94
White to Move
Innovation II-Evaluator 1-0
24th ACM Computer Chess Championship
Round 2, Move 32
Cape May, NJ 6/26/94
Innovation played:
1. c5!! dc (1...bc? 2.c4 traps the knight)
2. d6! The point -- the b6 pawn's support is undermined
2...c4 (2...cd 3.Rxb6)
3.Bc2 b5
4. dc
This line was best for both sides according to Stockfish
White to Move
Innovation II-Evaluator 1-0
24th ACM Computer Chess Championship
Round 2, Move 4
Cape May, NJ 6/26/94 5
White to Move
Innovation II-Evaluator 1-0
24th ACM Computer Chess Championship
Round 2, Move 4
Cape May, NJ 6/26/94 5
Innovation played:
1. Nxf4!! +- ef
2. e5 a4?! (2...Ne8 3.Rxg6 Kh8 4.e6 +- with Bd4+ coming)
3. ef a3
4. Bb1 +- which stops the a-pawn since black's rook must stay on the 8th rank to guard c8, and White soon won.
Black to Move
Innovation-BP 1-0
23rd ACM Computer Chess Championship
Round 5, Move 12
Indianapolis, IN 2/16/93
Black to Move
Innovation-BP 1-0
23rd ACM Computer Chess Championship
Round 5, Move 12
Indianapolis, IN 2/16/93
Innovation just played Bh3 to stop White from castling, and now plays similarly with its other bishop:
1... Ba3! (1.Qh5 is also good) with the threat of Bxb2, Bxg2. At this point, IM Mike Valvo commented to the audience that Innovation was playing the game of its life. (Unfortunately, in this game it later ran into a time-control bug after obtaining a 3 pawn advantage.)
Black to Move
Spector-Innovation II 0-1
24th ACM Computer Chess Championship
Round 4, Move 36
Cape May, NJ 6/26/94
Black to Move
Spector-Innovation II 0-1
24th ACM Computer Chess Championship
Round 4, Move 36
Cape May, NJ 6/26/94
Innovation plays:
1... Qb4
2. Qc1 (only move) -/+
30 years later Stockfish assesses Innovation's play in this game as 91% accurate.
Black to Move
Human - Maurice Ashley Teaches Chess
0-1
Black to Move
Human - Maurice Ashley Teaches Chess
0-1
Pure tactics. Maurice Ashley Teaches Chess spots a forced mate with a sequence of queen checks:
1... Qc1+
2. Kg2 Qf1+
3. Kf3 Qh1+
4. Qg2 Qd1++
Maurice Ashley Teaches Chess
Maurice Ashley Teaches Chess
My chess engine was licensed for this commercial product. I also wrote all the chess-related code/libraries for it. Later it was bundled in Sierra's Complete Chess, Chess Advantage, and Family Fun Pack.
Review
My chess engine was licensed for this commercial product. I also wrote all the chess-related code/libraries for it. Later it was bundled in Sierra's Complete Chess, Chess Advantage, and Family Fun Pack.
Review
Maurice Ashley Teaches Chess
Simon & Schuster, Davidson
Sierra's Complete Chess
Sierra Attractions
Chess Advantage
Encore Software
Family Fun Pack
Encore Software
Dr. Schiller's Chess Game
Dr. Schiller's Chess Game
I did the programming on this, except that I integrated a friend's chess engine. The product was later bundled by Encore in Family Chess Pack along with Chessmaster 5000 and Lego Chess, and also in Chess Advantage II.
I did the programming on this, except that I integrated a friend's chess engine. The product was later bundled by Encore in Family Chess Pack along with Chessmaster 5000 and Lego Chess, and also in Chess Advantage II.
Dr. Schiller's Chess Game & How to Play Chess
Zane Publishing
Chess Advantage II
Encore Software
Family Chess Pack
Encore Software
Grandmaster Chess for Macintosh
Capstone
Grandmaster Chess for Macintosh
Capstone
A commercial app I ported from Windows to Mac by myself around 1995. It was successful, but I was a subcontractor and once the contractor received all the money, he decided he had better things to do with it than pay me. :-/
A commercial app I ported from Windows to Mac by myself around 1995. It was successful, but I was a subcontractor and once the contractor received all the money, he decided he had better things to do with it than pay me. :-/
Other Chess Software I've Worked On
Other Chess Software I've Worked On
Kasparov's Chess (Unreleased): Got an advance from Microsoft, but then they decided to kill all their new offline projects in favor of the Intenet Gaming Zone (which they acquired from my friends)
Internet Chess for Mac (Released): A commercial Mac interface for the Internet Chess Club.
Stealth Chess engine for Hoyle Majestic Chess II (Unreleased): You don't see the pieces! This was fun to play. The product was a follow-on to Hoyle Majestic Chess published by Sierra Entertainment/Vivendi, but unfortunately the product was killed.
Blitzen, Dasher, et. al. (Released): Chess clients and other frontend and backend software when I worked at the Internet Chess Club.
First Move (Released): A web-based chess variant for kids.
Chess variant program (Unreleased): This played Coin Chess and other variants, driven by a scripting language. This was the first general game playing program and an early pre-cursor to Zillions of Games
Zillions of Games (Released): Played chess and chess variants, among others.
Knightmare Chess (Unreleased): Demo for Steve Jackson Games.
Kasparov's Chess (Unreleased): Got an advance from Microsoft, but then they decided to kill all their new offline projects in favor of the Intenet Gaming Zone (which they acquired from my friends)
Internet Chess for Mac (Released): A commercial Mac interface for the Internet Chess Club.
Stealth Chess engine for Hoyle Majestic Chess II (Unreleased): You don't see the pieces! This was fun to play. The product was a follow-on to Hoyle Majestic Chess published by Sierra Entertainment/Vivendi, but unfortunately the product was killed.
Blitzen, Dasher, et. al. (Released): Chess clients and other frontend and backend software when I worked at the Internet Chess Club.
First Move (Released): A web-based chess variant for kids.
Chess variant program (Unreleased): This played Coin Chess and other variants, driven by a scripting language. This was the first general game playing program and an early pre-cursor to Zillions of Games
Zillions of Games (Released): Played chess and chess variants, among others.
Knightmare Chess (Unreleased): Demo for Steve Jackson Games.
[Event "24th ACM Computer Chess Championship"]
[Site "Cape May, NJ USA"]
[Date "1994.06.26"]
[Round "4"]
[White "Spector"]
[Black "Innovation II"]
[Result "0-1"]
1. e4 c6 2. d3 d5 3. Nd2 g6 4. Ngf3 Bg7 5. g3 e5 6. Bg2 Ne7 7. O-O O-O 8. b4 a5 9. bxa5 Qxa5 10. Nb3 Qc7 11. exd5 cxd5 12. Be3 Bg4 13. Qd2 Rc8 14. Bc5 Nf5 15. Ng5 h6 16. h3 Bh5 17. g4 Na6 18. Be3 d4 19. Ne4 dxe3 20. fxe3 Nb4 21. gxf5 Nxc2 22. Rac1 Rxa2 23. Nec5 Bf8 24. Rxc2 Rxc2 25. Qxc2 b6 26. fxg6 Bxg6 27. Rf6 bxc5 28. Rc6 Qd7 29. Rxc8 Qxc8 30. Qc3 Bf5 31. Kh2 Bd6 32. e4 Be6 33. Nd2 Qd7 34. Nc4 Bc7 35. Na3 Qd4 36. Qd2 Qb4 37. Qc1 Kg7 38. Bf3 f5 39. Nc2 Qc3 40. exf5 Bxf5 41. Be4 Bxe4 42. dxe4 c4 43. Qg1+ Kf7 44. Qf2+ Ke8 45. Qe2 Qd3 46. Qg2 c3 47. Qg8+ Kd7 48. Qg4+ Kd6 49. Qg6+ Kc5 50. Qg1+ Kb5 51. Qb1+ Ka5 52. Qa2+ Kb6 53. Qb3+ Ka7 54. Qa2+ Kb7 55. Qb3+ Bb6 56. Qd5+ Qxd5 57. exd5 Kc7 58. Kg3 Kd6 59. Kg4 Kxd5 60. Kf5 e4 61. Kf4 Bf2 62. Na1 Kd4 63. Nc2+ Kd3 64. Nb4+ Kc4 65. Na2 e3 0-1
[Event "24th ACM Computer Chess Championship"]
[Site "Cape May, NJ USA"]
[Date "1994.06.26"]
[Round "2"]
[White "Innovation II"]
[Black "Evaluator"]
[Result "1-0"]
1.d4 Nf6 2.c4 e6 3.Nc3 Bb4 4.e3 Bxc3+ 5.bxc3 Nc6 6.Bd3 d6 7.Ne2 0-0 8.0-0 e5 9.f3 Bd7 10.Rb1 Rb8 11.Kh1 a6 12.e4 h6 13.Kg1 Qe7 14.Be3 Na5 15.Kh1 Kh8 16.Rb2 Rg8 17.Qd2 Rge8 18.Rfb1 Ra8 19.Bf2 Kg8 20.Kg1 b6 21.Kh1 Nc6 22.d5 Na5 23.Kg1 Kh8 24.a3 Kg8 25.Kh1 Nh5 26.Be3 Rf8 27.Kg1 f5 28.Rb4 f4 29.Bf2 Kh7 30.Kh1 g6 31.R4b2 Qg5 32.c5 dxc5 33.d6 c4 34.Bc2 b5 35.dxc7 Bc6 36.Rb4 Qe7 37.Bb6 Nb7 38.a4 Nc5 39.Rd1 a5 40.Rxb5 Bxb5 41.axb5 Nf6 42.Qd6 Qxd6 43.Rxd6 Nb7 44.Re6 Rf7 45.Nxf4 exf4 46.e5 a4 47.exf6 a3 48.Bb1 Rd7 49.f7 Rd1+ 50.Bg1 1-0
[Event "WMCCC 1991"]
[Site "Vancouver, Canada"]
[Date "1991.01.01"]
[Round "3"]
[White "Innovation"]
[Black "Centaur"]
[Result "1-0"]
1.d4 d5 2.c4 e6 3.cxd5 exd5 4.Nc3 Nf6 5.Bg5 Bb4 6.a3 Bxc3+ 7.bxc3 h6 8.Bf4 Ne4 9.e3 c6 10.Ne2 g5 11.Bxb8 Rxb8 12.f3 Nd6 13.Qa4 a6 14.h4 gxh4 15.Qb3 Bd7 16.Nf4 b5 17.Bd3 Qe7 18.Kd2 h5 19.Rae1 Rg8 20.e4 Nc4+ 21.Kd1 Be6 22.exd5 cxd5 23.Nxd5 Qd8 24.Nf4 Qd6 25.Nxe6 fxe6 26.Bxc4 bxc4 27.Rxe6+ Kf7 28.Rxd6 cxb3 29.Rd7+ Kf8 30.Rd5 Rxg2 31.Rxh5 Rc8 32.Rh8+ Rg8 33.Rxg8+ Kxg8 34.Kd2 Rf8 35.Rxh4 Rxf3 36.Rh2 b2 37.Kc2 Rxc3+ 38.Kxb2 Rd3 39.Rg2+ Kf7 40.Rg4 Kf6 41.a4 a5 42.Rf4+ Ke6 43.Ka2 Re3 44.Rf8 Rc3 45.Ra8 Rc4 46.Rxa5 Kd6 47.Ka3 Rxd4 48.Rb5 Rc4 49.a5 Ke6 50.a6 Rc7 51.Rb7 Rc8 52.a7 Ra8 53.Kb4 Kd5 54.Ka5 Ke4 55.Kb6 Rf8 56.Re7+ Kf4 57.Kb7 Kg3 58.a8=Q Rxa8 59.Kxa8 Kf4 60.Kb7 Kg5 61.Rf7 Kh5 62.Rg7 Kh6 63.Rg8 Kh7 64.Rg1 1-0
[Event "24th ACM Computer Chess Championship"]
[Site "Cape May, NJ USA"]
[Date "1994.06.25"]
[Round "1"]
[White "WChess"]
[Black "Innovation II"]
[Result "1-0"]
24th ACM (1) Cape May, NJ, 1994
1.e4 c6 2.d4 d5 3.exd5 cxd5 4.c4 Nf6 5.Nc3 e6 6.Nf3 Be7 7.cxd5 Nxd5 8.Bd3 Nc6 9.0-0 0-0 10.Re1 Bf6 11.a3 Nxc3 12.bxc3 b6 13.Bf4 Bb7 14.Qc2 h6 15.Bh7+ Kh8 16.Be4 Rc8 17.Qd2 Kg8 18.Bxh6 Nxd4 19.cxd4 Bxe4 20.Rxe4 Qd5 21.Rf4 Be7 22.Rg4 Bc5 23.Rxg7+ Kh8 24.Rg4 f5 25.Qg5 Bxd4 26.Bg7+ Kg8 27.Bf6+ Kf7 28.Qg6# 1-0
[Event "24th ACM Computer Chess Championship"]
[Site "Cape May, NJ USA"]
[Date "1994.06.25"]
[Round "2"]
[White "Cray Blitz"]
[Black "Innovation II"]
[Result "1-0"]
1.e4 c6 2.d4 d5 3.exd5 cxd5 4.Bd3 Nc6 5.c3 Nf6 6.Bf4 Bg4 7.Qb3 Qc8 8.Ne2 e6 9.Nd2 Be7 10.f3 Bh5 11.0-0 0-0 12.Rfe1 a5 13.Bg5 a4 14.Qc2 Bg6 15.Bxg6 fxg6 16.Nf4 Ra6 17.Nxe6 Nb4 18.Qd1 Rxe6 19.cxb4 Rxe1+ 20.Qxe1 Bxb4 21.Rc1 Qd7 22.Qf1 Qd6 23.Qb5 a3 24.b3 Bxd2 25.Bxd2 Rb8 26.b4 Qe7 27.Qd3 Ra8 28.Rc3 b6 29.Rc6 Qa7 30.Qb5 Rb8 31.Bf4 Rb7 32.Be5 Rf7 33.Rc8+ Rf8 34.Rc7 Qb8 35.Rxg7+ Kxg7 36.Bxb8 Rxb8 37.Qc6 Re8 38.Qb7+ Kf8 39.Qxb6 Kf7 40.Qa7+ Re7 41.Qxa3 Rb7 42.Qa5 Ke7 43.b5 h6 44.a4 h5 1-0
[Event "24th ACM Computer Chess Championship"]
[Site "Cape May, NJ USA"]
[Date "1994.06.27"]
[Round "5"]
[White "Innovation II"]
[Black "Now"]
[Result "0-1"]
24th ACM (5) Cape May, NJ, 1994, Round 5
1.d4 Nf6 2.c4 e6 3.Nc3 Bb4 4.e3 0-0 5.Nge2 d5 6.a3 Be7 7.cxd5 exd5 8.b4 a5 9.b5 Bg4 10.f3 Be6 11.Nf4 c5 12.Be2 Nbd7 13.0-0 Bd6 14.e4 cxd4 15.Ncxd5 Bxd5 16.Nxd5 Nxd5 17.exd5 Bc5 18.Bd3 Bb6 19.Bf4 Nc5 20.Bc4 Qf6 21.Bg3 Rac8 22.Rc1 Rfe8 23.Kh1 Nd7 24.Re1 Re3 25.d6 Bc5 26.Rxe3 dxe3 27.Qd5 Rb8 28.Re1 b6 29.Bd3 Qc3 30.Bxh7+ Kxh7 31.Qf5+ Kg8 32.Qxd7 Qxa3 33.Qc7 Rf8 34.d7 Qd3 35.Bh4 f6 36.Bg3 a4 37.Qc8 Kf7 38.Qc7 Ke6 39.f4 a3 40.h3 a2 41.f5+ Kxf5 42.Qf4+ Ke6 43.Qa4 Qb1 44.Qd1 Qxd1 45.Rxd1 Ra8 0-1
Links
Links
Innovation
WMCCC 1991, Vancouver, Canada
- "Report on the 11th World Microcomputer Chess Championship" by Don Beal (PDF), ICCA Journal, Vol. 14, No. 2
ACM 1993 Indianapolis, Indiana
- The 23rd ACM International Computer Chess Championship (PDF) Rules. With games from 1992 tournament
ACM 1994 Cape May, New Jersey
- The 24th ACM International Computer Chess Championship (PDF) Rules. With games from 1993 tournament.
- ACM 1994 All Games Posted by Feng-Hsiung Hsu, programmer behind Deep Thought and Deep Blue
- ACM 1994 Games Corrected PGNs
ACM Computer Chess by Bill Wall
Chess Move Binary Encoding Standard
Chess Programming Wiki
Innovation
WMCCC 1991, Vancouver, Canada
- "Report on the 11th World Microcomputer Chess Championship" by Don Beal (PDF), ICCA Journal, Vol. 14, No. 2
ACM 1993 Indianapolis, Indiana
- The 23rd ACM International Computer Chess Championship (PDF) Rules. With games from 1992 tournament
ACM 1994 Cape May, New Jersey
- The 24th ACM International Computer Chess Championship (PDF) Rules. With games from 1993 tournament.
- ACM 1994 All Games Posted by Feng-Hsiung Hsu, programmer behind Deep Thought and Deep Blue
- ACM 1994 Games Corrected PGNs
ACM Computer Chess by Bill Wall
Chess Move Binary Encoding Standard
Chess Programming Wiki
Page updated
Google Sites
Report abuse