Identifying combinations in a game

[rjgibert]

How would one go about identifying all the combinations contained in game in an automated way?

Defining what is and isn't a combination is a bit slippery and what you wind up with may not be so practical to efficiently use in an algorithm.

What I would like to see is for an engine to provide you with all the combinations played and/or missed in a given game and present them to you as White (or Black) to move and win (or draw).

This would be useful to players for pedagogical reasons. Are there programs already out there that do this? If so, how good are they at doing this? It doesn't need to be perfect at it. It just needs to be good enough to be significantly useful.

BTW, a perhaps useful byproduct of this is that moves that drop in score without hanging material or succumbing to a combo could be identified as a positional error. This is a little half-baked, but perhaps not so unreasonable.

[bob]

How would one go about identifying all the combinations contained in game in an automated way?

Defining what is and isn't a combination is a bit slippery and what you wind up with may not be so practical to efficiently use in an algorithm.

What I would like to see is for an engine to provide you with all the combinations played and/or missed in a given game and present them to you as White (or Black) to move and win (or draw).

This would be useful to players for pedagogical reasons. Are there programs already out there that do this? If so, how good are they at doing this? It doesn't need to be perfect at it. It just needs to be good enough to be significantly useful.

BTW, a perhaps useful byproduct of this is that moves that drop in score without hanging material or succumbing to a combo could be identified as a positional error. This is a little half-baked, but perhaps not so unreasonable.

I don't think it would be that hard if you can define combination.

My first cut:

1. Initial move is a capture.
2. Final result is a gain of material (one might want to extend this to a gain of some significant positional edge, and so long as the "edge" can be quantified, I thnk it would be as easy as a material gain).

The usual annotate option in many programs (like Crafty) could be modified to only display the captures that appear to win material (and here I am not talking about a re-capture just recovering material of course).

[rjgibert]

Your definition would identify from 1 d4 d5 2 c4 dxc4 3 Nf3 2..dxc4 as a combination? My thinking had been along somewhat similar lines as yours, but I always came up with too many combos that were not really combos. Also, with your definition, it would tend to mis-identify the beginning of a combo. Too many combos actually begin with a non-capture e.g. a double attack. That's too big a category to miss.

I've also dismissed a series of captures occurring on just one square as being a combo. To me this is just a generalized variant of capturing a hanging piece. A little better for example is to require that there be capturing occurring on more than one square, but this too is incomplete. It also suffers from the fact that a secondary capture square is hidden in a side variation. This is hard to fix efficiently.

It's like I said, creating a decent definition is a bit slippery. But I would certainly be interested in hearing more of your ideas after you have given it more thought.

[bob]

Your definition would identify from 1 d4 d5 2 c4 dxc4 3 Nf3 2..dxc4 as a combination? My thinking had been along somewhat similar lines as yours, but I always came up with too many combos that were not really combos. Also, with your definition, it would tend to mis-identify the beginning of a combo. Too many combos actually begin with a non-capture e.g. a double attack. That's too big a category to miss.

I've also dismissed a series of captures occurring on just one square as being a combo. To me this is just a generalized variant of capturing a hanging piece. A little better for example is to require that there be capturing occurring on more than one square, but this too is incomplete. It also suffers from the fact that a secondary capture square is hidden in a side variation. This is hard to fix efficiently.

It's like I said, creating a decent definition is a bit slippery. But I would certainly be interested in hearing more of your ideas after you have given it more thought.

I don't disagree, but a combination to me has always started with a capture. Checks or other threatening moves are different. A sacrifice might be a combination that loses material, if the first move is a capture, or it might just be a sacrifice.

Whether that definition of "combination" is good or not is certainly debatable, but once a good definition is developed, this ought to be possible...

[Gerd Isenberg]

How would one go about identifying all the combinations contained in game in an automated way?

Defining what is and isn't a combination is a bit slippery and what you wind up with may not be so practical to efficiently use in an algorithm.

What I would like to see is for an engine to provide you with all the combinations played and/or missed in a given game and present them to you as White (or Black) to move and win (or draw).

This would be useful to players for pedagogical reasons. Are there programs already out there that do this? If so, how good are they at doing this? It doesn't need to be perfect at it. It just needs to be good enough to be significantly useful.

BTW, a perhaps useful byproduct of this is that moves that drop in score without hanging material or succumbing to a combo could be identified as a positional error. This is a little half-baked, but perhaps not so unreasonable.

I don't know whether this was tried in chess programs. I guess yes, for instance if it is about to decide to take one further iteration.

Each time a new pv is determined at the root (or PV-nodes) one may replay the pv to look for a characteristic curve of typical combinations - eval scores taken from even plies (0,2,4,..) along the pv. If the curve fits (one or more score drops, but a final or late rise to make the pv > alpha), one may look for tactical motives involved along the pv, such as forks, pins, skewers, undermining, discovered attacks, passers, mate threats, etc., which may appear as single feature or in combination. The more features involved, the higher the amplitude, and the longer the duration of the curve, the more impressive the combination. Based on the score one may distinguish petit from mating combinations. Looks like an application to teach a neural network what kind of combinations exists, feeding in some feature-sets and curve characteristics, like amplitude and duration, e.g. {init, min, max score} and their even ply indices.

[michiguel]

Your definition would identify from 1 d4 d5 2 c4 dxc4 3 Nf3 2..dxc4 as a combination? My thinking had been along somewhat similar lines as yours, but I always came up with too many combos that were not really combos. Also, with your definition, it would tend to mis-identify the beginning of a combo. Too many combos actually begin with a non-capture e.g. a double attack. That's too big a category to miss.

I've also dismissed a series of captures occurring on just one square as being a combo. To me this is just a generalized variant of capturing a hanging piece. A little better for example is to require that there be capturing occurring on more than one square, but this too is incomplete. It also suffers from the fact that a secondary capture square is hidden in a side variation. This is hard to fix efficiently.

It's like I said, creating a decent definition is a bit slippery. But I would certainly be interested in hearing more of your ideas after you have given it more thought.

I don't disagree, but a combination to me has always started with a capture. Checks or other threatening moves are different. A sacrifice might be a combination that loses material, if the first move is a capture, or it might just be a sacrifice.

Whether that definition of "combination" is good or not is certainly debatable, but once a good definition is developed, this ought to be possible...

In many combinations, the first move is not a capture. It may look like it loses material, but it could be an apparent quiet move.

It think that many would involved a negative SEE score on the "to" square after the fist move is played, but that is not necessarily a capture. Interceptions are a typical example.

Miguel

[bob]

Your definition would identify from 1 d4 d5 2 c4 dxc4 3 Nf3 2..dxc4 as a combination? My thinking had been along somewhat similar lines as yours, but I always came up with too many combos that were not really combos. Also, with your definition, it would tend to mis-identify the beginning of a combo. Too many combos actually begin with a non-capture e.g. a double attack. That's too big a category to miss.

I've also dismissed a series of captures occurring on just one square as being a combo. To me this is just a generalized variant of capturing a hanging piece. A little better for example is to require that there be capturing occurring on more than one square, but this too is incomplete. It also suffers from the fact that a secondary capture square is hidden in a side variation. This is hard to fix efficiently.

It's like I said, creating a decent definition is a bit slippery. But I would certainly be interested in hearing more of your ideas after you have given it more thought.

I don't disagree, but a combination to me has always started with a capture. Checks or other threatening moves are different. A sacrifice might be a combination that loses material, if the first move is a capture, or it might just be a sacrifice.

Whether that definition of "combination" is good or not is certainly debatable, but once a good definition is developed, this ought to be possible...

In many combinations, the first move is not a capture. It may look like it loses material, but it could be an apparent quiet move.

It think that many would involved a negative SEE score on the "to" square after the fist move is played, but that is not necessarily a capture. Interceptions are a typical example.

Miguel

Then, for a starting point, a move that looks bad (negative eval) for a very shallow search but which later proves to win material, not lose it, we call a "winning combination.

We probably want to also have "a move that looks bad but later proves to lead to some sort of drawing swindle" as well.

The only issue is "what is a shallow search". Sometimes you offer your opponent a chance to play something that looks bad for you for quite a deep search, hoping he overlooks the stinger that is hidden way down.

Maybe then a move that looks bad for a period of time, but which then looks good after a deep search. And the "quality" of a combination is based on how deep you have to search before it "turns around" into a winner???

[mcostalba]

Then, for a starting point, a move that looks bad (negative eval) for a very shallow search but which later proves to win material, not lose it, we call a "winning combination.

IMHO you can lift the negative eval at start (has no sense) and keep the big jump in eval (no need to win material, also this constrain has no sense, could also mate as example).

The only metrics should be the evaluation value.

Another thing that is missed is the comparison with siblings moves otherwise in a winning position every move is a winning combination.

This is my definition of a winning combination

1) A move that does not increase the eval more then LOWER_THRESHOLD for the following DEPTH_LIMIT_1 plies

2) A move that after DEPTH_LIMIT_2 plies makes the eval jump high

3) A move that keep a very high eval for as long as the analisys goes deep.


In a line conditions are:

Eval(ply) - Eval(0) < LOWER_THRESHOLD for ply < DEPTH_LIMIT_1
Eval(ply) - Eval(0) > HIGHER_THRESHOLD for ply > DEPTH_LIMIT_2

Where DEPTH_LIMIT_1 < DEPTH_LIMIT_2


And now the new trick:

4) Called eval_second_best the evaluation of the second best move after deep analysis then must be:

Eval(ply) - eval_second_best > SECOND_BEST_THRESOLD for ply == MAX_DEPTH.

So parameters are:

DEPTH_LIMIT_1
DEPTH_LIMIT_2
LOWER_THRESHOLD
HIGHER_THRESHOLD
SECOND_BEST_THRESOLD
MAX_DEPTH

[bob]

Then, for a starting point, a move that looks bad (negative eval) for a very shallow search but which later proves to win material, not lose it, we call a "winning combination.

IMHO you can lift the negative eval at start (has no sense) and keep the big jump in eval (no need to win material, also this constrain has no sense, could also mate as example).

The only metrics should be the evaluation value.

Another thing that is missed is the comparison with siblings moves otherwise in a winning position every move is a winning combination.

This is my definition of a winning combination

1) A move that does not increase the eval more then LOWER_THRESHOLD for the following DEPTH_LIMIT_1 plies

2) A move that after DEPTH_LIMIT_2 plies makes the eval jump high

3) A move that keep a very high eval for as long as the analisys goes deep.


In a line conditions are:

Eval(ply) - Eval(0) < LOWER_THRESHOLD for ply < DEPTH_LIMIT_1
Eval(ply) - Eval(0) > HIGHER_THRESHOLD for ply > DEPTH_LIMIT_2

Where DEPTH_LIMIT_1 < DEPTH_LIMIT_2


And now the new trick:

4) Called eval_second_best the evaluation of the second best move after deep analysis then must be:

Eval(ply) - eval_second_best > SECOND_BEST_THRESOLD for ply == MAX_DEPTH.

So parameters are:

DEPTH_LIMIT_1
DEPTH_LIMIT_2
LOWER_THRESHOLD
HIGHER_THRESHOLD
SECOND_BEST_THRESOLD
MAX_DEPTH

I had suggested the negative eval so that the move would look bad at first glance. Otherwise if it is just a "normal-looking move" that springs a deeper trap, one could luck into it just because it looks normal to start with, where to play a move that looks bad up front means you either made a mistake that lucked out, or you saw deeply enough to discover that it was a good move after all. I also treat captures differently since an equal exchange can expose an overloaded piece, so I would not use the "negative eval" trigger for captures, just non-captures.

[mcostalba]

Then, for a starting point, a move that looks bad (negative eval) for a very shallow search but which later proves to win material, not lose it, we call a "winning combination.

IMHO you can lift the negative eval at start (has no sense) and keep the big jump in eval (no need to win material, also this constrain has no sense, could also mate as example).

The only metrics should be the evaluation value.

Another thing that is missed is the comparison with siblings moves otherwise in a winning position every move is a winning combination.

This is my definition of a winning combination

1) A move that does not increase the eval more then LOWER_THRESHOLD for the following DEPTH_LIMIT_1 plies

2) A move that after DEPTH_LIMIT_2 plies makes the eval jump high

3) A move that keep a very high eval for as long as the analisys goes deep.


In a line conditions are:

Eval(ply) - Eval(0) < LOWER_THRESHOLD for ply < DEPTH_LIMIT_1
Eval(ply) - Eval(0) > HIGHER_THRESHOLD for ply > DEPTH_LIMIT_2

Where DEPTH_LIMIT_1 < DEPTH_LIMIT_2


And now the new trick:

4) Called eval_second_best the evaluation of the second best move after deep analysis then must be:

Eval(ply) - eval_second_best > SECOND_BEST_THRESOLD for ply == MAX_DEPTH.

So parameters are:

DEPTH_LIMIT_1
DEPTH_LIMIT_2
LOWER_THRESHOLD
HIGHER_THRESHOLD
SECOND_BEST_THRESOLD
MAX_DEPTH

I had suggested the negative eval so that the move would look bad at first glance. Otherwise if it is just a "normal-looking move" that springs a deeper trap, one could luck into it just because it looks normal to start with,

Please take a good look at condition 4, after that I think it should be clear why your above exposed case is already taken care of.