Jeff Rollason is the author of the Chess program Treebeard, as well as the earlier chess programs Merlin and Rasputin. He has also worked on many other game engines, but the largest influence in the design of Treebeard has come from work on his Shogi (Japanese Chess) program "Shotest". Treebeard and Shotest are AI Factory products. See also the new recent article Playing Badly Well - Modelling Errors in Chess.
Didzis Cirulis has a broad experience working with Chess programs, starting with a long-term testing of Christophe Theron's Chess Tiger 11.5. He also was involved with Ed Schroder's formidable program "Rebel" and contributed ideas to Richard Lang's "Chess Genius" (Richard Lang's Mephisto chess programs for many years dominated Computer Chess on microcomputers). In more recent times Didzis has also provided extensive testing of the Hiarcs program by Mark Uniacke for the Palm. Didzis is now involved with providing chess input and testing of AI Factory's Treebeard, where he has already made significant contributions. Didzis lives and works in Latvia, where he has an ELO chess ranking of 1950.
The Treebeard chess program was developed in 2004 and first appeared in the product Global Star Tournament Chess II, and since in Chess Championship Tournament and Chess II (Unbalance, Japan), Classic Compendium II (Gizmondo) and Treebeard Chess (Nokia 60). Unlike most chess programs, this product was designed from day one to provide a multi-platform commercial chess program. However it is not simply a plain vanilla alpha-beta program. Treebeard is the latest generation of a unique type of game analysis that is proprietary to AI Factory. Development started in the chess program Merlin, back in 1976, and most notably appeared in the Shogi program Shotest during 1997-2003. It has now been refined and returned to chess in Treebeard.
UPDATE! This original article was created in 2005, but now the vast majority of our chess users access Treebeard via our Android app Chess Free. This has over 80m downloads and has greatly refined the game engine. This app includes 2D/3D, a chess tutor, clocks, 12 play levels and various features such as game preview and analysis. It is by far the most reviewed/rated chess program on Android, with 1.5m reviews and ratings, over double any other chess app. Download it and take a look! (September 2019)
There are 2 main aspects of this proprietary game analysis.
(1) A static tactical evaluation
This first appeared in an engine for Merlin in 1976, allowing tactical features to be assessed statically. Of course simple swap-off algorithms are already widely used, but this algorithm takes things much further, allowing for pins and ties to defend against capture, forks and even mate threats. This is a whole board analysis that can predict sequences of moves across multiple squares, without tree search, and including defensive moves. A complex algorithm, it is described in depth in the paper http://www.aifactory.co.uk/downloads/SUPER-SOMA.doc and can also be found in Artificial Intelligence (see http://www2.teu.ac.jp/gamelab/SHOGI/articlesmain.html.)
(2) A highly directed probability-based tree search
This first appeared in the Shogi program Shotest. Depending on the intelligence of (1) above to reduce the search, the tree search is then more free to analyse just probable variations, rather than having to spend time proving that nonsense variations do not work. The fine detail of this is still rather under wraps. However it is not conventional forward pruning, which typically just restricts moves analysed at each ply, basically trying to do the job that alpha beta does to reduce search. In this system it is possible that the search might consider all moves at some great depth, if the probability was high enough. (The idea of using probability to guide search has also since been introduced by the Shogi program Gekisashi, a previous world champion, but this uses a different method).
The advantages
The freedom that reliable highly directed search gives is the ability to apply sophisticated analysis deep in the search. This is something that programs that think fast, but examine vast numbers of nodes, cannot do. There are many tricks than can be applied to allow big tree searches to do some seemingly clever things, but the validity of these analyses becomes suspect and inaccurate at depth. A good example is using tables to assess the value of a piece being on a particular square, which has its attractions, as the cost of doing it is very low. At the root ply the program analyses in detail on which squares a piece should be. A map is created, and as that piece reaches better positions, it gets a credit. Very easy. The search is let loose and spends its time trying vast numbers of combinations and credits those positions where pieces have reached these better squares.
This approach goes wrong when (for example) the pre-analysis sees a number of good attacking squares for pieces, near the opponent's king. In the search the king may run, but still the pieces get credit for gathering around the spot where the king used to be. This failing is true with many other features. The root analysis was valid, but by the time the search has been let loose, the position has changed too much. Also the analysis does not assess the combination of pieces moving together. Each piece is treated as a completely separate entity.
With a more sophisticated analysis, the program can get to some deep variation and detect a particular advantage or powerful move. Search can find these, but only by searching way beyond the position, recording the "good" move and trying it again elsewhere.
This lack of dependence on blanket search and simple evaluation works exceptionally well with Shogi in Shotest. There the ability of the program to assess almost any tactical situation, at any depth, allows it to tightly constrain the search and not get into difficulty assessing complex positions.
The problems
There are no free lunches, and to get an estimate of probability requires a good board analysis. However powerful your analysis is, it will still miss things, so you need some kind of supporting mechanism to help find moves that may have been overlooked. Your analysis could be good at picking moves that can be immediately understood, but sometimes moves that are interesting, but that cannot be immediately shown to be good, need to be considered. It is the job of plausibility analysis to find moves that are not obviously good, but have good features. An example is to move a piece to a square, where previously it was unsafe to do so. This can allow the program to solve problems that it did not see coming. The search can then try moves that have unforeseen benefits, which it can try to exploit. By such means the search can find a deep combination that required a number of problems to be solved first, before finally achieving the goal.
Treebeard
Treebeard is still a very young program, with little more than 2 man months spent on it. However this was clearly not from a zero starting point. This program has been tested, and will get much stronger, but it has shown that it can already play an interesting game.
Didzis Cirulis has been testing Treebeard, and the following games demonstrate some attributes of its play:
[Date "2005.08.02"]
[White "Treebeard A98"]
[Black "Chess Tiger 15.1"]
[Result "1-0"]
[ECO "D06"]
[Annotator ",Didzis"]
[PlyCount "139"]
[EventDate "2005.08.02"]
[SourceDate "2005.08.02"]
1. Nf3 Nf6 2. c4 d5 3. cxd5 Nxd5 4. e4 Nf6 5. Nc3 e6 6. d4 h6 7. Be2 Bb4 8. e5 Nd5 9. Bd2 a6 10. O-O Nc6 11. Qc2 Nde7 12. a3 Ba5 13. Be3 Bb6 14. Qe4 Nf5 15. Rad1 O-O 16. Bc4 Re8 17. b4 Qe7 18. Kh1 a5 19. b5 Nb8 20. Bc1 c6 21. Na4 Bd8 22. Bb2 g6 23. Rg1 Bd7 24. b6 Bc8 25. Bc1 Qf8 26. Qd3 Nd7 27. Qb3 Be7 28. g3 Nb8 29. Nc3 Rd8 30. Ne4 Nd7 31. Qb2 h5 32. Kg2 Re8 33. Nc3 Bd8 34. Na4 h4 35. g4 Ne7 36. Bg5 Nd5 37. Bxd8 Rxd8 38. Nxh4 Nf4+ 39. Kg3 Qh6 40. Nf3 Nh3
From this position Treebeard has pressure at several points, but Chess Tiger has planted its knight at h3 and simply threatens to take the rook it has just attacked. Many players would take the natural step of moving the rook away to a safe square, leaving the enemy knight planted in the position.
41. Qb1!
Treebeard has other ideas(!) and disregards the rook and instead moves the queen back one square to apply a little more pressure, sacrifing rook for knight.
Nxg1 42. Rxg1 Kg7 43. h4 Rh8 44. Rh1 Kg8 45. h5 Rb8 46. Bd3
Very quickly Treebeard has mobilised an attack, and what might have looked like a vulnerable king position for Treebeard has instead become the base for a steamroller attack on the opponent's king. The loss of rook for knight has left Treebeard with good activity. Treebeard now has the queen, bishop, rook and pawn attacking the king position, with a knight ready to support, whereas Chess Tiger has just Rook and Queen defending.
... Qf8 47. hxg6 Qg7 48. gxf7+ Kxf7 49. Rxh8 Qxh8 50. g5 Qh5
Now the material balance is restored and Chess Tiger is pinned down. The immediate attack on the king is suspended and Treebeard turns to exploit other weaknesses.
51. Qe1 Nf8 52. Qxa5 Nd7 53. g6+ Kg8
54. Qa7 Qh6 55. Nc5 Qf8 56. Nxe6 Qh6 57. Bf5 Qh8 58. g7 Qh1 59. Neg5
Treebeard gives up its passed pawn on the 7th rank to instead deliver the final blow.
... Kxg7 60. Bxd7 Bxd7 61. Qxb8 Qh8 62. Qxb7 Qc8 63. Qa7 Kf8 64. b7 Qd8
With substantial material advantage and passed pawns, the result is not in doubt!
65. b8=Q Qxb8 66. Qxb8+ Kg7 67. Qc7 Kf8 68. Qxd7 Kg8 69. Qf7+ Kh8 70. Qh7# 1-0
This game shows off a feature of Treebeard's analysis. When it sacrificed the rook, it did not calculate that material would eventually be restored, but was exchanging material value for positional gain. This is hard to do, and needs a complex evaluation.
The following game is annotated by Didzis, and show Treebeard's positional understanding. It is shown here in standard PGN format, so that it can be pasted to a PGN file and read directly by ChessBase,or any other PGN reader, with the comments embedded in the game.
[Event "A 97 test"]
[Site "?"]
[Date "2005.07.25"]
[Round "1"]
[White "A97"]
[Black "Chess Tiger 15.1"]
[Result "1-0"]
[ECO "A09"]
[Annotator "Didzis"]
[PlyCount "133"]
[EventDate "2005.07.25"]
[SourceDate "2005.07.25"]
{While testing the Treebeard chess engine, I decided to confront it with Chess Tiger 15.1, which was running on Palm Zire 71 and is about 2100 ELO strong. 15 minutes/game.} 1. Nf3 Nf6 2. c4 d5 3. cxd5 Qxd5 4. d4 Bf5 5. Nc3 Qd6 6. Bg5 Qb6 7. Bxf6 {As a chess player, I would not give a bishop up that early in the game. Na4 would be my preference.} exf6 8. Qd2 $14 Bb4 9. e3 O-O 10. a3 Qa5 11. Rc1 $16 Bxc3 12. Rxc3 Be4 13. Rc5 Qb6 14. Be2 Nd7 15. Rc1 Qd6 16. Qc3 c6 17. O-O Nb6 18. Nd2 Rfe8 {I would have played Bg6, but Tiger wants an active rook.} 19. Nxe4 $16 Rxe4 20. Qb3 Rh4 21. h3 Qd5 22. Qxd5 Nxd5 23. Bg4 {This looks like a nice move to me! It limits the Rook, which will have to wait several moves to return to the battlefield.} Kf8 24. g3 Rh6 25. e4 { Now, when opponent's rook is out of game, it is the right time for offensive.} Nb6 26. Rfe1 Rd8 $14 27. Red1 Rg6 $2 {This is a mistake. A better move would be f5 to free the Rook, even giving up a pawn.} 28. d5 $18 {Another good move by Treebeard! There is a weakness on c7 and Treebeard is going for it! Even a central pawn can be sacrificed for this purpose.} cxd5 29. Rc7 Ke8 30. Rxb7 { The "pig" in action! (Bruce Pandolfini used to call a rook sitting there a "pig", because it can eat up all of the enemy pawns on their own second rank)} dxe4 31. Rxd8+ Kxd8 32. Bf5 e3 33. Bd3 f5 34. Rxf7 Rd6 35. Be2 {Bf1 was a better move. Now Black has its own "pig" and gobbling contest can begin!} Rd2 $14 36. Kf1 Rxb2 37. Rxg7 a5 { A small favour from Tiger's side. Nd5 would provide better chances for Black.} 38. fxe3 Ra2 39. Rxh7 Rxa3 40. Rh6 $18 Kc7 41. Kf2 Nd5 42. Re6 a4 {The next stage of the game - "pawn races" - is about to begin! Treebeard now must decide what to do - accept the invitation with h4 or try to eliminate the obstacle on f5.} 43. Re5 Kd6 $16 44. Rxf5 Ra2 45. Kf3 Ra3 46. Kf2 { Another chance to start pushing the h-pawn. Missed.} Ra2 47. Kf3 Ra3 { After giving an opponent a false hope for a draw, Treebeard pushes the pawn.} 48. h4 Nxe3 {Another pawn is given to improve the chances of h-pawn} 49. Rf8 $16 Nf1+ $2 {This was a "Thank you very much" move for Treebeard. The King is under attack, but the Knight has chosen the wrong field. A jump to f5 would be better considering the passer on h-line.} 50. Kf2 Ne3 $4 {Tiger has to choose from bad and worse, but even Nxg3 would not have saved anything.} 51. h5 $18 { The pawn is running up the board and neither piece of Black can do anything about it.} Ke7 52. Rf4 { Rh8 and pushing the pawn would have been even better choice.} Nd5 53. Rd4 { Rh4 would be even better. It protects the h-pawn and keeps an eye on that black pawn on a4. If a black Rook leaves the a-line, that pawn falls.} Nc3 54. h6 Ra2 $4 {a blunder in a bad position} 55. h7 Rxe2+ 56. Kf3 Rh2 57. Rh4 { Game over!} Rd2 58. h8=Q Rd3+ 59. Kg4 Ke6 60. Rh5 Nd5 61. Rh6+ Kf7 62. Qh7+ Kf8 63. Qxd3 Ne7 64. Qd6 Ke8 65. Rh7 Nc8 66. Qe6+ Kd8 67. Rd7# 1-0
Jeff Rollason, Didzis Cirulis: 11th August 2005
