Chess programming:
http://www.frayn.net/beowulf/index....
http://u.cs.biu.ac.il/~davoudo/tuto...
http://en.wikipedia.org/wiki/Nolot
http://chessprogramming.wikispaces....
http://members.home.nl/matador/ches...
http://www.pdf-search-engine.com/ch... http://www.gamedev.net/reference/pr... http://www.maths.nott.ac.uk/persona...

Alpha-beta pruning
http://www.cs.ucla.edu/~rosen/161/n... http://www.ocf.berkeley.edu/~yosenl...

Human GMs analyze schematically by formulating plans or objectives, then calculating the means to achieve them. Engines analyze as many positions as possible and play the move or line that returned the best numerical evaluation. In the position below from Short vs Timman, 1991

click for larger view

Engines cannot see the strategy of mating with the King (starting with <31.Kh2>) until deep into the line or unless sliding back from the won position (Rybka 3 [+3.43] d=23 31.Ne1)(Modern Chess Analysis by Robin Smith 2004; Gambit Publications, London).

From <How to Use Computers to Improve your Chess by Christian Kongsted http://www.gambitbooks.com/books/co...) >

The horizon effect prevents engines from realizing that the Black Bishop will be pinned permanently after <32...Rxa2?>, thus salvaging a draw for Anand after <33.Rdd2> (From Anand - Fritz 6, 1999 zanshin chessforum (kibitz #2610)).

click for larger view

Rybka 3: [-1.35] d=26 32...Rxa2 (1:07.46) 543881kN

<Types of positions misevaluated by engines, excerpts from Modern Chess Analysis by Robin Smith>

<1. exchange sacrifices> - Engines have difficulties evaluating material loss for positional considerations. In Kasparov vs Shirov, 1994

click for larger view

Kasparov played <17.Rxb7!> dominating the light squares, especially d5. (See John Nunn's comments quoted on the gamepage)

<2. box canyons> - ie forced lines. The term is taken from canyons in the American southwest where floods have carved out a single path forward. Engine evals may be quite different at the entrance and exit of a box canyon. In Nunn vs Van der Wiel, 1982, Nunn played <29.e5?!> entering a box canyon until move 40 that he felt was won (and too many plies away for engines to analyze). Engines prefer <29.Rc1> or <29.Rxg8>.

<3. Prisons> - trap a piece, requiring a sacrifice to escape. From Timman vs P Nikolic, 1987, engines will want to play <24.Be2?> likely leading to a draw (Rybka 3 [+0.68] d=23 24.Be2).

click for larger view

Timman played <24. Ra6! Nxa6 25. bxa6 Rd7 26. Kf1 Ra7 27.Bb7>

click for larger view

imprisoning the Rook and winning the game.

<4. King drift> refers to gradual movement of pawns and pieces towards the King. Engines often do not sense the danger before it is too late. In Smirin vs Shredder, 2002, Shredder allows King drift by weak moves in the opening.

<5. material imbalances> Positions with significant material imbalances are difficult for engines to evaluate (eg where one side has sacrificed material for a positional bind). In the position below from Junior 8 - Hiarcs 8 2003, different engines evaluated the position as +2.5 to slight advantage to Black.

click for larger view

White probably has the advantage and eventually won. Positions like this are good candidates for engine matches.

<6. quiet positions> When short term tactical gain is clear, engines are very purposeful. However, they can struggle in positions where there are no clear short term objectives. In R Knaak vs Geller, 1982, White needs to re-position his Bishop to b3, Rook b1 to d1, Knight to f4 all with pressure on d5. All engines tested preferred <22.h6?> (Rybka 3 [+0.69] d=19 22.h6)

click for larger view

<7. fortresses> - are formations that prevent forces from breaking in. This technique is usually found in the endgame to hold a draw under material disadvantage. Black has played <45...Qb6?!> in A Petrosian vs L Hazai, 1970

click for larger view

Engines cannot resist taking the Queen with high material gain. (Rybka 3 [+6.76] d=22 46.Nxb6 (0:08.56) 41463kN) However, the resulting fortress is a draw. This game was featured as a GOTD (April 19, 2009). A possible win for White is given in the CG game page. See also: zanshin chessforum (kibitz #2976)

<8. passed pawns> - Engines love passed pawns, especially advanced ones. In Abreu - Perez (1999), the following position is evaluated at between +2 to +2.5 by several engines (Rybka 3 [+1.41] d=17 1.Re1). However, the position is drawn because the pawns cannot Queen.

click for larger view

<9. perpetual check> Whereas draws by repetition can be detected easily, perpetual checks are difficult for engines because one side can salvage a draw despite severe material disadvantage. At move 55 in Korchnoi vs G Rechlis, 1988, the game was drawn in the position below:

click for larger view

Despite the large advantage given to White by engines (Rybka 3 [+7.25] d=19 55...Kh2), the game is a draw by perpetual check.

Another example based on J. H. Donner (2006) "The King" (white to move):

click for larger view

Rybka finds the right move (5.Nh6!), but the evaluation is incorrect (-4.35 d=22 5.Nh6). The game is a draw by perpetual check along the g-file. (http://www.chessbase.com/newsdetail...)

<10. quirks in engine design> Based on a puzzle from http://susanpolgar.blogspot.com/ (8 July 2009). In the position below, White wins by under-promoting the pawn to Bishop. Fritz and Fruit (but not Crafty) both find the solution. Rybka 3 does not because under-promotion to Bishop is not included in Rybka analysis (http://rybkaforum.net/cgi-bin/rybka...)

click for larger view

Fritz 10: 2.h8B +- (5.55) Depth: 23/41 00:04:44 709mN, tb=336

Fruit: [+5.04] d=27 1.h8B Qb8 2.Be5 Qc7 3.Nd6 Kg5 4.Ne4 Kh4 5.Bg3 Qxg3 6.Nxg3 Kg5 7.Nf1 Kf4 8.Kg2 h4 9.Nh2 Ke4 10.Nf3 Kf5 11.Nxh4 Kf4 12.Nf3 Ke4 13.h4 Kf5 14.Kg3 Kf6 15.Kf4 Kg7 16.Kxe3 Kg6 17.Ke4 Kh5 (0:00.31) 56559kN

Crafty: [+7.58] d=21 1.h8Q Qxh8 2.Nxh8 Kg5 3.Nf7 Kf6 4.Nd6 Ke5 5.Nc8 Kd5 6.Ne7 Kc4 7.Nf5 Kxb5 (0:00.49) 132436kN

Rybka 3: [+0.00] d=27 1.h8Q Qb8 2.Qe5 Qd6 3.Nxd6 (0:02.13) 27379kN

(see also: zanshin chessforum (kibitz #2672))

Another well documented bug in Rybka 3 is the absence of 'wrong-colored bishop' knowledge that was removed from Rybka 2 (but is supposed to be returned in Rybka 4; see http://rybkaforum.net/cgi-bin/rybka...

In the position below, Rybka 3 cannot find the tablebase draw 1... Bh3! 2.gxh3 Kh6 3.h4 Kg7, whereas Fruit finds it immediately.

click for larger view

(Rybka 3: [+5.12] d=27 3...Kh4 4.Ke2 (0:04.06) 69612kN); Fruit 2.3 [+0.00] d=12 3...Bh3 4.Kf2 Bxg2 5.Bxg2 Kg6 6.Ke3 Kg7 (0:00.00) 175kN)

Update: Rybka 4 finds it immediately: [+0.00] d=12 1...Bh3 2.Kf2 Bxg2 3.h4 Kf6 4.Bxg2 Kg7 5.Ke3 Kg6 6.Kf3 Kg7 7.Kg3 Kh8 (0:00:01) 36kN

Rybka 3 also suffers from the "Blind Bishop" bug, ie a pawn is about to Queen, but the opposing King can cover the Queening square and the Bishop cannot. The position below is drawn (either side to move), but Rybka 3 gives a high numerical evaluation:

click for larger view

Tablebase draw; Firebird 1.2 ([+0.05] d=34 1.Bf8 Kb8 2.Bg7 Ka8 3.Kc7 Ka7 4.Bh8 Kxa6 5.Kc6 ...); Rybka 3 ( [+6.08] d=19 1.Ka5 (0:13.57) 355388kN)

Update: Rybka 4 evaluates correctly even at low ply: [+0.00] d=30 34.Bc5 Kb8 (0:00:00) 1kN

<11. zugzwang positions> Engines are poor at handling positions where an advantage is conveyed by <not> moving (because of "null move heuristic"). In the position below, engines cannot find the winning line (<1.Qc8!> Kg8 2.Bc7 Qxc8 3.gxf7+ Kh8 4.Be5 Qc5 5.Bb2 Nc7 6.Ba1 a4 7.Bb2 a3 8.Ba1 a2 9.Bb2 a1Q 10.Bxa1 Qe5+ 11.Bxe5 Nd5+ 12.Kg5+ Nf6 13.Bxf6#):

click for larger view

[+0.17] d=23 1.Qc5 Kg8 2.gxh7 Kh8 3.Be7 Qb8 4.Qg5 Qb2 5.Kxf7 Qb3 6.Kf8 Qb8 7.Bd8 Qb4 8.Kf7 Qb7 9.Kf6 Qc6 10.Ke7 Qb7 11.Kd6 Qb4 12.Ke5 (0:12.03) 132204kN (Rybka 3)