Decision Trees In Chess

Part Of: [Chess] sequence
Followup To: [An Introduction To Chess]

Table Of Contents

  • Setting The Stage
  • Constructing Options
  • Analyzing “Quiet” Moves
  • Analyzing “Sharp” Moves
  • Chess Decisions Are Graph Computations
  • Takeaways
  • Appendix

Setting The Stage

Let’s pick up where we left off. I had just played:

  1. e5 dxe5
  2. f5

A decision which as White’s most promising option, yielding a small (~0.2 pawn) increase in our advantage.

Starting Score End Score Difference
Estimated Total +0.4 +0.6 +0.2

Black responds by attacking White’s bishop, forcing another important decision.

  1. … f6

first_chess_position

In this post, I will be discussing several chess positions in depth. Unless you are a trained professional able to simulate move sequences in your head, it would be much better if you followed along on a board. I cannot underscore this point enough. You should be able to do this digitally, by re-enacting moves via this link: http://bit.ly/1GyEcQ5

Constructing Options

Back to the position at hand. Black is threatening my Bishop: other things being equal, I should remove it from danger.  Where to?  Bh4 feels wrong: the Bishop is misplaced.  Be3 is a natural retreat.  Bh6, offering a trade of Bishops (Bxh6 Qxh6), is also possible.

Our spidey-sense should be tingling here. Can we transcend a retreat, and pursue a more aggressive course of action? Can we create threats of our own, scary enough to dissuade Black from capturing our Bishop? If we captured his pawn (fxg6) could Black afford to capture our bishop? Similarly, what if we simply moved our Knight towards his vulnerable King?  (Ne4 fxg5 Nxg5) while losing two points, should be examined because our Knight is about to land in the powerful e6 square, and make Black’s life rather bleak.

Please note, explicitly, the kind of tradeoff we are here considering: position vs material (quality vs quantity).  Surrendering the latter for the former brings with it a large amount of risk – material factors “persist forever”, whereas positional advantages tend to be fleeting.  Further, note that as the pawns are move aside and our pieces make inroads into each others armies, our game will become highly volatile, with the entire game often hinging on one individual moment.  When the pace of the game accelerates in this way, it is said to produce sharp positions.

To restate our four options:

  • 22. Be3
  • 22. Bh6
  • 22. fxg6
  • 22. Ne4

I shall now survey my analysis of these options. I spent four hours combing over the implications of these options. I want you to pay attention to the language I use, and the inter-analysis differences you can spot.  I will be drawing from such observations in my next post.

Analyzing “Quiet” Moves

For our first positional option, if I play the quiet 22. Be3, Black will most likely resolve the f5-g6 pawn tension:

Suppose Black plays 22 … gxf5.  

Here, White cannot play the aggressive 23. Bc2 f4 24. Qd3 because Black’s King escapes after 24 …fxe3 25. Qxh7+ Kf8 (-3.0, [pos 1a]).  

Perhaps White does best with the quiet 23. Rxf5 e6 24. dxe6 Rxe6 25. Rh5 with control of the light squares (+0.2, [pos 1b]).

If he instead locks down the Kingside with 22 … g5, I will perhaps want to open it up with 22. h4.  Play may proceed 22 …h6 23. Kf2 Nf8 24. Rh1, with play on the Kingside (+0.5, [pos 1c]).

For our second positional option, 22. Bh6 is very similar to Be3, but forces the trade of the dark Bishops.

After 22 …g5 23. Bxg7 Kxg7 Black has more room to breathe than the former line, and can swing his Rooks over to the King’s defense (-0.2, [pos 2a]).

Here are the final positions & scores of the four lines we considered here:

Chess Decision Tree- Quiet Position Comparison

We can represent these analyses graphically, as follows:

Chess Decision Trees- Positional DTree after f5 f6

We are now done with half of our analysis. Take a deep breath, get a glass of water. We’re almost there! 😛

Analyzing “Sharp” Moves

Consider our first tactical option, 22. fxg6. Black may “play my game” and accept the pawn trade, or “call my bluff” and annihilate my bishop.

On 22 … hxg6 White’s threat is dissolved and he must bring his bishop to safety. After 23. Bh6, Black may try to protect his king by gaining space, or by holing up:

On 23 … f5 White must hammer on Black’s new center before it becomes too strong. 24. g4 can only be met with 24 … f4, after which 25. Bxg7 Kxg7 Ne4 and White’s attack is dead, and is left down a pawn (-0.8, [pos 3a])

Black may instead try the defensive 23 … Bxh6 24. Qxh6 Nf8, but White has a fighting chance after 25. Bg4 Rcd8 where his bishop has a promising view of the light squares (+0.0, [pos 3b])

On 22 … fxg5, Black dares White to prove his attack is worth more than the sacrificed Bishop. White is obliged to blow away Black’s safety net with 23. gxh7, after which Black has two options:

If Black recaptures 23 … Kxh7, after 24. Qxg5 White has a strong attack, potentially leveraging his Re4 to Rh4 (+1.4, [pos 3c])

Black can “hide behind” White’s pawn with 23 … Kh8. A plausible line here may be 24. Ne4 Bh6 25. Ng5 Bxg5 Qxg5, where again White dreams of bringing other pieces to bear in the attack (+0.8, [pos 3d])

Chess Decision Tree- Sharp Position Comparison Part One
Consider instead the second tactical option 22. Ne4. Here, Black may play defensively, capture my bishop, or capture my pawn:

On 22 … Nf8 a plausible line may proceed: 23. Bh6 Rb8 24. Bc2 Bc8 25. Ng3 with strong positional pressure (+0.5, [pos 4a])

On 22 … fxg5 23. Nxg5 Black is faced with several defensive options, of which three stand out:

On 23 … Nf8 24. fxg6 Nxg6 25. Rf7 Black can avoid the Ne6 fork with 25 … Qd6, with a very sharp, unclear game ahead (+0.0, [pos 4b])

On 23 … Qd6 24. fxg6 hxg6 25. Ne6 White’s control of the light squares is very powerful. Play might continue 25 … Nf8 26. Bg4 (+1.0, [pos 4c])

On 23 … Nf6 24. Ne6 Qd6 25. fxg6 hxg6 26. Qg5 White’s Queen bears down on the weak g-file (+0.8, [pos 4d])

Chess Decision Tree- Sharp Position Comparison Part Two

On 22 … gxf5 23. Rxf5 Black can challenge the Rook with 23 … e6 after which 24. dxe6 Rxe625. Bh6 and White is comfortable (+1.0, [pos 4e])

But Black can simply capture the bishop on instead. After 23 … fxg5 24. Nxg5, Black is again faced with many defensive options.

On 24 … Rf8 Qd3 White threatens to move the rook and checkmate via Qh7. (+0.9, [pos 4f])

On 24 … Nf8 Bg4 White is poised to threaten the Rc8, and counter Black moving his e-pawn (+0.7, [pos 4g])

On 24 … e6 Nxe6 25. Qd6 Qg5 White threatens Qg7 checkmate, but this threat can be blocked (+0.5, [pos 4h])

Chess Decision Tree- Sharp Position Comparison Part Three

We can again represent the above analyses graphically, as follows:

Chess Decision Trees- Sharp DTree after f5 f6

Chess Decisions Are Graph Computations

Congratulations on surviving the past two sections! We’re almost done. Take a deep breath.

The last question on our plate today is:

How should we take the above analyses and produce a move?

This seems difficult to answer. But consider the following simpler question

What is the score of our original four choices?

If we knew the score attached to our four possible moves, we would have an answer: make the move with the best possible score! 🙂

How to solve this simplified question? If we need scores in the head of the tree, graphically our task becomes propagating the already-known leaf scores back up the tree. Let’s see this in action.

Chess Decision Trees- Positional Minimax after f5 f6

We have a clear understanding of the score for the position after 22. Bh6: it is -0.2.

But what is the score after 22. Be3?

To answer this, we must first evaluate the score after 22 … gxf5. It is White’s turn, should he choose 23. Bc2 or 23. Rxf5? He should choose Rxf5, because it has a higher score! In mathematical terms, we simply take the maximum of all white moves: max(0.2, -3.0) = 0.2!

Now that we know that the state after gxf5 is +0.2, what is the score made by Be3? It is Black’s turn, should he choose gxf5 or g5? He should choose gxf5, becuase it has a lower score! In mathematical terms, we simply take the minimum of all of black’s option scores: min(0.2, 0.5) = 0.2

The above two paragraphs express the basics of the minimax algorithm. The name comes from the application of max() for White and min() for Black. Its procedure is how computers, and as I will argue brains, do chess.

Can you apply the same logic to fxg6 and Ne4?  Take a moment to valuate their scores, and then come back to check your work!

  • Be3: 0.2
  • Bh6: -0.2
  • fxg6: 0.0
  • Ne4: 0.0

Now, given these scores for White’s candidate moves, which should White pick? The maximum, or 22. Be3. And that is precisely the move I chose. 🙂

Here’s a graphical representation of the above results:

Chess Decision Trees- Complete Minimax after f5 f6

It is my hope that chess decisions now remind you of lightning physics:

Takeaways

  • When considering possible moves, it is helpful to graph moves as nodes in a decision tree.
  • Analyzing chess is hard work!
  • When you are done constructing the decision tree, the minimax algorithm translates its data into a decision.

Appendix

If anybody is interested in how the game concluded, let me attach a link to it here for completeness. While I did win, I feel like the win was not particularly instructive. This particular moment analyzed above, however, contained a nice mix of different strategies and thereby was pedagogically useful.

1. d4 Nf6 2. c4 g6 3. Nc3 Bg7 4. e4 d6 5. Nf3 O-O 6. Be2 c5 7. d5 a6 8. a4 Nbd7 9. O-O b6 10. h3 Bb7 11. Bf4 Re8 12. Qd2 Qc7 13. Rae1 Rad8 14. Bd3 Nh5 15. Bg5 Ne5 16. Be2 Nxf3+ 17. Bxf3 Nf6 18. Bd1 Rc8 19. f4 Nd7 20. e5 dxe5 21. f5 f6 22. Be3 g5 23. b3 Rb8 24. h4 gxh4 25. Qf2 h3 26. Qg3 Kh8 27. Bh5 hxg2 28. Kxg2 Rg8 29. Bg6 Bh6 30. Rh1 Nf8 31. Rxh6 e6 32. Qh4 exf5 33. Qxf6+ Rg7 34. Kf2 Nxg6 35. Rxg6 hxg6 36. Bh6 Kg8 37. Bxg7 Qxg7 38. Qe6+ Qf7 39. Qxe5 Rf8 40. Qe6 Qxe6 41. Rxe6 Kg7 42. Rxb6 Rf7 43. b4 cxb4 44. Rxb4 Kf6 45. Rb6+ Kg5 46. c5 f4 47. Ne4+ Kh4 48. Nd6 Bxd5 49. Nxf7 Bxf7 50. c6 Be6 51. c7 Bf5 52. Rxg6 Kh5 53. Rg8 1-0

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s