Tuesday, December 11, 2007

Error propagation in combinatorial thinking

A while ago, after doing a statistical postmortem with around 60 of my games, I wrote:
Most realistic combinations are two or three moves long, typically one move. This is an extremely useful fact, and should be impressed into the minds of all beginners. When I first started playing chess, I looked at the board as a structure with infinite tactical possibilities that were well out of my reach, I would sit and search for complicated N-move combinations, wrongly believing that they must be there, but that I was just too stupid to see them. My post-mortem showed me how naive my thinking was, and this is liberating.

The law of short combinations also makes sense from an analytical point of view (and could probably be proven mathematically): the longer the imagined combination, the more likely it is that the opponent will have defensive resources, will have in-between moves that are hard to see, the more likely it is that you are simply missing an obvious weakness in your attack or somehow miscalculating the combination.
The truth of the "law of short combinations" has been impressing itself on my mind more and more, its relevance to practical play showing itself in spades. Still most of my games are lost because I become derailed thinking through lengthy and speculative sequences of moves rather than looking thoroughly for simple tactics (taking a piece, forks, etc). That is, I make the mistake of thinking deeply but not broadly in the middlegame (exceptions to the law of short combinations where it really pays to think deeply are for sequences of forcing moves and in the endgame (though in the endgame I am learning much of the thinking should involve coming up with a good general plan, and then thinking of move sequences)).

I mentioned the possibility of a mathematical proof of this law. I think that was a bit over the top, but making some simple assumptions it gives a good picture of what I was thinking. Let's define P(e1) as the probability that you made an error in the first move, and P(c1) is the probability of being correct (that, say, his piece is truly safe for free capturing, or you do actually have a mate in one). For me P(c1) is probably around 0.95 (and hence P(e1) is 0.05). So, one out of 20 times I'll make a mistake with something this simple.

Plugging it in my formulas (see below) you can construct a list of probabilities of making mistakes on N move combinations. I calculated it out up to four-move combinations, where the P(c) sequence from P(c1) to P(c4) is (.95, .76, .51, .245). The probability you are making an error increases by about 0.25 with each move in the combination.

So, for longer combinations, think very carefully, especially if it is crucial that it actually work. For instance, the other night I tried a rook sacrifice hoping for a mate (it would have been a three-move combination) that had an obvious refutation whose consequences were deadly. For nonsacrificial combinations it doesn't necessarily matter if it doesn't work if setting it up actually helps your position.

Some of the details
You can construct a chain where the first node is the first move in the combination (a kind of Markov chain). The second node is the second move, and the probabilities there depend on the pattern at the first node. E.g., P(c2)=P(c2|e1)P(e1)+P(c2|c1)P(c1) (this follows from probability theory: you are basically calculating the marginal distribution).

P(c2|e1) is zero (errors propagate). P(c2|c1), for me, is around 0.8. THat is, about 2 out of 10 times I make some mistake thinking about the second move of a two move combination, e.g., there are defensive resources I didn't consider). So plug in the numbers: P(c2)=0+0.8*0.95=0.76. So about 75% of the time I will be OK with a two-move tactic, and 25% of the time I overlook something.

You can iterate this algorithm for an arbitrary number of moves, substituting your own conditional probabilities. Just multiply each successive probability (it will ground it out at P(c1)). So, for an N-move sequence, P(CN)=P(c1)*P(c2|c1)*P(c3|c2) ... * P(CN|PCN-1).

17 Comments:

Blogger Loomis said...

But doesn't there also have to be a law that says the better the opponent, the longer the combination you'll have to find to win? Once you are able to find all 2 move combinations, I'll have to be able to find a 3 mover to beat you, and if you can spot all 3 movers, I'll have to be able to spot a 4 move combo to win, etc.

Of course, that ignores the question of consistency since the proof relies on the fact you see all 2, 3, etc. move tactics.

12/12/2007 12:01:00 AM  
Blogger Blue Devil Knight said...

Well, it really is conditional, if I think I see an N-move combination, and N is larger than 3 or so, chances are I am wrong so I need to really be careful and visualize all in between moves etc..

Also, for stronger players, the probabilities will be different. I used the arbitrary sequence of .95, .8, .65, etc (subtract .15 for each).

Better players it will be more like .99, .95, etc..

Note my original point was that (in my games) there literally weren't that many tactics involving more than 1-3 moves. And tons of missed tactics 1-3 moves long. At a higher level, these opportunities won't come up as much, as you have to make a low-level mistake to allow such tactics. At my level, they come up almost every game.

It would be cool to look objectively at the frequency of 1 to N move combinations as a function of rating. Obviously the frequency of low N combinations will drop off with rating. My hunch is that the frequency of possible higher N move combination possibilities is similar across skill levels, and these are fairly rare even in principle. This would be easy to do with a large database and Fritz. It would be very cool.

In practice, it really helps my game to remember to not spend too much time on complicated tactical speculation until I've looked broadly for the simple stuff first. In yesterday's game I left his rook hanging as I was way ahead and got lazy, and was thinking about relatively complicated endgame plans!

12/12/2007 12:49:00 AM  
Blogger Blue Devil Knight said...

Just to be clear, the formula I used for this post was a kind of 'personal' formula of probability that a tactic you think is there is actually there. A more interesting study would be an objective calculation of the proportion of N move tactics that are objectively (i.e., computer checked) there. That in some ways would be even more useful to know. I wonder if Soltis has done that. I know he calculated the proportion of situations in his database in which there was a clear 'best' move was about 0.33. A subset of these were likely tactical situations (though OTOH there are tactical situations where there are multiple good tactical shots that all reach the same goal).

My guess is that the number is around 20 percent at beginner level, and going down to around 5-10 percent for the GMs, all the while the average length of the combinations increasing.

12/12/2007 12:52:00 AM  
Blogger Glenn Wilson said...

I agree with your basic points: short combinations occur frequently and are frequently missed or messed up by "most players."

A tweak to your formula is to consider the probability that your opponent will make a mistake. If the opponent's probability of error is the same as yours and if errors occur randomly then this would likely have a small impact on the calculation (with a small error rate).

If the errors are not random, but depend on the nature of the position and the calculation, two players may err in the same way in the same combination. I once played a queen sac to get a smothered mate. It was mate in one. My opponent resigned. An observer later pointed out that the smothered mate that we both saw coming was an illusion.

OTOH, after your move your opponent has one less ply to look ahead which can help. And, in a three move combination if the refutation is three moves deep the opponent does not have to see it until it is on the board. Both of these effects help the defender find the right moves even if they would not have at the beginning of the calculation.

Also, of course, the width of the search is a factor. If it is three moves deep but all moves are forced and there is only one line that is far easier to see right than one where there are multiple reasonable choices at each move.

Trying to factor human error (and other error) into general decision making frameworks sounds like an interesting challenge. Hmmm...

12/12/2007 05:33:00 AM  
Blogger Temposchlucker said...

This is a very broad area. Just some random thoughts.

If I play a combination which involves a piece sac, it is usually sound. Otherwise I don't play it. So do opponents of equal level. This is afterwards confirmed by the computer. The keyword here is usually which means not always. Your story raises the question, how correct is that feeling? By playing with the criteria it is easy to delude yourself.

Most of the time the computer reveals a combination that I could have played, but didn't see. A sort of passive blunder.

I checked about 100 complex tactical positions of Polgar's middlegame brick with Rybka. In 25% of the cases there was a variation that was flawed. This means that if a GM throws a complex combination to you, in 25% of the cases this is not deadly. If you can think like Rybka.

Somebody who is rated 250 points below me, usually sees about the same combinations as I do. It only takes him more time to see it. If I want to outsmart him tactically, this means that I must go really deep. Only from time to time the position is suitable for that. The same is true for me in comparison to someone who is rated 250 points above me.

This is only a story about tactics. But now I get some positional knowledge, it is often a simple task to outplay somebody who is lower rated positionally. For the sole reason that they have no idea what you are after and why. If they would have known, they probably would have found a refutation, but since they don't, they help you to achieve your goal. Given the fact that I have to go deep to outplay somebody lower rated tactically, this is a simpler alternative.

So a little knowledge that you have but your opponent hasn't, nullifies possible refutations. Presumably GM's have about the same knowledge. Hence their attempt to get an edge in the opening where specific knowledge still can play a crucial role. But with the internet every novelty can be used only a few times before it becomes public domain.

12/12/2007 07:22:00 AM  
Blogger Blue Devil Knight said...

Glenn: good points. Often I'll make an error but the opponent "goes along" with it, not finding the proper refutation. There are other times when making an error, while not having a good outcome, doesn't have a bad outcome. The refutation of my tactic might just be "Oh, he can move his knight to c6, so now his Knight isn't attacked and he is out of check. Oops. Well, at least his Knight isn't on d4 anymore."

But you are right that for it to really work it would need something like P(e and o) (o=opponent sees error). In practice, my numbers reflect this implicitly, as they are sort of based on frequencies with which my opponents call me out on my mistakes.

This also touches on Tempo's point: if you can think like Rybka you will find the refutation, but in practice the opponent will often have trouble finding it. There are certain patterns of refutation/defense people are used to. Sometimes the right defense is outside the scope of their patterns so it will be hard to find. I still have the pattern of not first checking to see if I can simply capture a piece that is attacking my material. I reflexively look to see how I can move it. This leads to many a gross blunder.

Even during a game I often get a sense for how my opponent plays chess, and can come up with ideas for attacking that I think he is unlikely to see (for instance, he is playing fast, mindlessly recapturing, I am behind, so I can make some captures that are actually not good for him). I know this is bad form: you are supposed to play the board, not the person. But when I am behind I typically have to start getting tricksy.

Glenn also has the excellent point that the opponent has a one-ply advantage in visualizing what to do. You are visualizing the future. He is responding to the board. A good proportion of my error rate is due to simple poor visualization of the future.

So one obvious question is, how do I get these probabilities up? They aren't fixed. For a GM, P(c1) is probably around .999. It is crucial, when we initiate tactics that fail, to examine why.

However, initiating incorrect tactics is less common than not even seeing tactics that are available. That's a whole new probability: the probability that, if there is a tactic there, you will see it. My responses above to loomis discuss the question of the probability that a tactic is there, as a function of player strength. It is this probability I would really like to increase (and have some with Circles type training).

12/12/2007 12:12:00 PM  
Anonymous reassembler.com said...

BDK et al - quite fascinating.

Drives home for me (again) that my "style" (i.e. bad habits) are highly impractical. I still calculate long strings, or try to. Of course I also have a pretty high risk tolerance and happily make speculative sacrifices. There is a little practical upside there, the much-discussed and debated concept of putting constant pressure on your opponent. But yes, sometimes a piece sacrificed is a piece lost :) Also this all raises the question of whether you want to play to maximize your results, or play to maximize your growth. Discarding long variations automatically saves time on the clock and avoids some errors, but it also teaches you to discard long variations automatically :)

12/12/2007 03:21:00 PM  
Blogger drunknknite said...

Interesting topic.

I would say that the length of the combination is a very minor factor in determining whether or not to pursue a combination. Much more important is the correctness of the positional and tactical THEMES that are being exploited.

First of all like you said, forcing sequences can be calculated for many more moves than non-forcing sequences without increasing the probability for error. What is happening to you is that you are making an incorrect valuation of the position that is a result of a forcing sequence. If you look at long-term sacrifices (which sometimes come as a result of a small introductory combination) the compensation is not always clear for many moves, sometimes Fritz doesn't even agree with sacrifices by strong grandmasters for 10 or more moves, in spite of not being able to find a winning continuation for the other side. Now these grandmasters are not calculating 10+ moves (Fritz can't even do it), they feel the positional themes and they are making them work for their side.

This is what is important, that the combination be consistent with the position.

A combination is nothing more than a forced transformation of the position. It usually involves a significant change in the strategic themes. If you are aware with how you are changing the position, you will be able to find the right plans for both sides and form a correct evaluation.

The initial goal should not be a sequence of moves, but a favorable change in the position (you mentioned that you recognize this in endgames). If your strategic goals are sound, then you will be able to find the right combination, no matter how long it is.

12/12/2007 03:48:00 PM  
Blogger Blue Devil Knight said...

Reassembler: A good point. Often I will make a sac if it is unclear that it is sound, just so I can better learn from the game. Sometimes it is sound but I didn't follow up correctly. Often it just isn't sound. But it also makes the games more fun, pumps a bit of adrenaline into the match.

Drunknknite: Your post shows your relatively advanced chess compared to mine. I am just at the level where I can understand what you are saying, but am not very good about pushing combinations so that I end up with a setup that has positional plusses. I am starting to see this in the endgame a little bit (I'll post a surprising success I had with this the other day). I am still at the level where the key is to avoid giving away, and overlooking opportunities to steal, material.

However, now that I've got some rudimentary tactical competence, I have started to make moves just to weaken the opponent's position (e.g., threaten mate just so he will weaken his pawn structure, especially if he weakens a color for which he doesn't have a bishop, and I do). For me, this stuff is still pretty advanced feeling, and frankly if I worry too much about it in subtle ways in my games I end up missing a basic tactic and losing. Probably a year or two more and I'll be ready to really sink into positional chess thinking. Right now I keep that fairly superficial on purpose so I don't miss basic tactics.

On the other hand, the endgame is a great place to practice planning, thinking not in terms of moves but positions in which I'd like to push the gameflow. Perhaps, since I plan on reading through Silman's endgame book soon, this will give me a better sense for this style of thinking which will spill over a bit into the middle game.

Very useful and smart comments here! I was expecting 'Stop thinking and play chess' crap. What a relief.

12/12/2007 04:01:00 PM  
Blogger Polly said...

OMG! There you go with those formulas again! :-Þ I think you make an excellent point that the combinations and tactics that typically arise in our games are much shorter then we think. Though there is the danger that if we are only looking 2-3 moves deep that something may come up that's 5 moves deep, and we can't avoid it once we played the first move. The stronger players can find those deeper combinations.

12/12/2007 05:18:00 PM  
Blogger Blue Devil Knight said...

Polly: very true. But the consequences of missing a 1-3 move tactic/combination are typically much worse than missing a longer combination (since the opponent is also less likely to find it). Not least of which because they occur so much more frequently (at my level). As I said, there are clearly exceptions with cool and forcing long sequences. I am not saying to give up on deep thinks, but to do the shallow but broad tactical inspection first.

Sometimes I go through a kind of heirarchy during games. OK, assume this guy is a beginner. Did he leave you any pieces to take? No. OK, now assume he is a novice who misses the simplest of tactics. See if you can find them. OK, none there. OK, now it's time to think.

As I mentioned recently, my opponent (rated around 1260 or something) recently checked with his queen. I tacitly assume my opponents don't make stupid moves, started looking at K moves, interpositions. Then, before I moved, I realized I could simply capture his queen with my Knight! Everybody makes stupid moves. Even GMs on rare occasions (think, Kramnik blunder). It's important to look for them :)

12/12/2007 05:26:00 PM  
Blogger Temposchlucker said...

I don't know which grandmaster said that tactics should flow easily from a good position. This seems to indicate that there is no need to find that 11-mover right now. By simply continuing to improve your position the fruit will drop off by a more simple combination later on.

12/13/2007 10:21:00 AM  
Blogger Liquid Egg Product said...

See, this is exactly why I keep a pocket Fritz under the table during tournaments.

12/13/2007 11:25:00 AM  
Blogger wormwood said...

the depth of vision/calculation between players of different strengths, is a topic that comes up pretty regularly on RHP. last time this week.

the thing that has become apparent (to me), is that the weaker players tend to say they look very deep (5-8 moves or even deeper), while the stronger ones look only a couple of moves deep (2-4). obviously there are exceptions in both groups, but the tendency is quite clear. clear enough to make me a bit suspicious when a strong player claims to look 5-7 moves deep on average.

it could be because weaker players only think they see that deep, when they actually crack 1-2 moves deep, and it's probably partly true. but the real reason, in my opinion, is that weaker players have the misconception that you need to calculate deep to be strong, which simply isn't true (excluding exceptions like forced variations & endgames). the better I've become, the less deeply I calculate (on average). nowadays I almost never calculate deeper than 2 moves in CC, and I can remember only 1 single time when looking 5 moves deep (against a 2300) would've made a slight difference (he managed to equalize my slight advantage in the endgame).

the errors happen 1-2 move deep, and the overwhelmingly most common one is underestimating a move that you did look into. and by underestimating I mean direct consequences that are blindingly obvious once you see that move made, not consequences that lie deeper. "oh hell, that pawn move blows my center to pieces" is what happens. -you correctly assessed that you won't lose material, fall into a tactic or a mate, but you missed the amount of trouble (that may or may not be survivable) the move causes.

another thing which I think strengthens the misconception, is that weaker players absolutely uncritically love what engines say. they see engine evaluation as 'objective truth', which it's not. it's a subjective numeric approximation, which has only one strength: it's not susceptible to tactical errors. an engine can't tell shit about a position without calculating, at best things like "a doubled pawn is -0.2" which may not be relevant at all. a strong human can tell enough to beat weak engines.

and because weaker players know this specific kind of 'objective truth' is reached by extremely deep calculation, they think aping that will magically give them greater understanding of the position, which it generally won't.

12/13/2007 12:11:00 PM  
Blogger Blue Devil Knight said...

Wormwood: a simply kick ass comment. This is great stuff. You put it better than I could, what I was trying to say. I remember talking to my father-in-law about chess and he said "When I was a kid I could look seven moves ahead." And I was like, hmmm, I usually don't look that many ahead. It's weird how outside of chess the big measure of how good you are includes how many moves you can look ahead, when in fact taking a lot of time to look far ahead is usually a time management blunder not to mention counterproductive as play for the reasons we've been discussing.

Just an excellent point about Fritz worship. I am certainly guilty of that. You should make that comment into a full post. It could be a book.

I think partly beginners do have to calculate more as they have zero intuition, zero patterns stored. They have absolutely no idea what to expect (as I mentioned in my post, I would just think wow my opponent must see all these complicated combinations I have to think about this deeply to make sure he doesn't trap me--typically that ain't the case--typically there are one to two move tactics that I miss and which lose the game (last night I let my Queen get pinned to my King!!!)).

If I ever teach chess, I will stress these points early and often. Why aren't they stressed more by Heisman, I wonder? I

Tempo: good point, though one has to be careful of taking it too literally. Don't you know it was J'adoube who discovered that. :) Seriously, I've seen it in Heisman, who probably cites the source.

LEP: LMAO!

12/13/2007 01:23:00 PM  
Anonymous Anonymous said...

Yup, wormwood definitely nailed it.

How do GM's move so fast during simultaneous exchibitions? They aren't really doing a long series of one deep calculations, one after another, even though that is the stereotype of the general public.

12/13/2007 01:45:00 PM  
Blogger wormwood said...

well okay. I just saved it into my diary of a blog as a new post. no new material though, at least for now. it's about what I have to say about the topic without getting long-winded.

12/13/2007 02:50:00 PM  

Post a Comment

<< Home