Counting rules
Inspired by Tempo. This is a semi-formal treatment of counting, when to start a series of exchanges when a bunch of attackers and defenders are all pointed at a piece on a square. It assumes no in-between moves.If you don't like technical weird geeky computer stuff, stop reading now before you get annoyed. Chess programmers probably have this stuff down flat. I'm not sure it works perfectly, but I think it does. I'd be curious to see if anyone can find a counterexample.
In a follow-up post in the next few days I'll give more concrete examples.
Definitions
- A=attacker (to move). There are m attackers.
- D=defender. There are n defenders of the material D0.
- Ai is a number, the value of the piece (e.g., if the first attacker is a pawn, then A1=1).
- A and D are sorted in ascending order, except D0, which can be any value (e.g., it can be a queen). For example, if A has a rook, queen, and pawn, then A1=1, A2=5, A3=9.
- AxD(i) notation means attacker i takes defender i-1, and DxA(i) means defender Di takes attacker Ai. So, for instance, AxD(1) means A1 takes D0.
- E(i), the ith exchange value, is the difference between AxD(i) and DxA(i). For example, if AxD(1) is 9 (pawn takes queen) and DxA(1) is 1 (something takes pawn back), then E(1) is +8.
- Cum_Sum(k) is the cumulative sum of exchange values from E(1) to E(k). k must be less than or equal to m. Let’s define Cum_Sum(0) as zero, the pre-exchange state.
Example 1: A1 is 1, A2 is 9 (attacking with pawn and queen). D0 is 9, D1 is 1, D2 is 1 (queen is attacked, and defended with two pawns). AxD(1)=+9 and DxA(1)=-1, so exchange value E(1)= +8. Should white continue? In this instance AxD(2)= +1 and DxA(2)=-9, so E(2)=-8. So the cumulative sum after two sets of exchanges is E(1)+E(2)=0. In sum, Cum_Sum(1)=8 and Cum_Sum(2)=0, so stop after the first capture. We have one suggestion for a rule: stop exchanging when Cum_Sum decreases in value.
Example 2: Attacker values 1 and 5. D0 is 1 and the other defenders are 1 and 9. E(1)=0, E(2)=-4, and Cum_Sum(2)=-4. So don’t go through all the exchanges. You might do the first exchange if it helps you positionally, the deciding factor with even exchange sequences.
Example 3: Attackers have values 3, 3, and 3. Defender has values 1 for D0 with 1 and 9 for the others. E(1)=-2, E(2)=-2, and E(3)=9 (in this case there are more attackers than defenders, so DxA(3)=0). So Cum_Sum(1)=-2, Cum_Sum(2)=-4, and Cum_Sum(3)=+5. Should you do the original exchange? Of course not! D doesn’t have to recapture with his queen at the end. If you were to simply sum the values of all the attackers and defenders, or to count the number of attackers and defenders, you would think you should start the exchange. But defenders are not forced to recapture. This suggests that you should only continue to attack if Cum_Sum is nondecreasing. But this isn’t quite right, as the next example shows.
Example 4: Attackers have values 5 and 9. Attacked piece has value 1, and defender has value 5. E(1)=-4, so Cum_Sum(1)=-4, you have lost material. But in this case, there are no more defenders exist so E(2)=5. Cum_Sum(2)=1, you have won a pawn. This is the real value of having more attackers than defenders: it isn’t that the exchanges in such a case always yield material gain (see Example 3), but that you get to extend your capture sequence one more than your opponent, so can accept a temporary decrease in the Cum_Sum value when your final unanswerable capture will then bump your Cum_Sum back into the black.
So all these examples suggest the following rule for capture sequences.
Capture Rule: Make the move AxD(i) if it will increase Cum_Sum(i). If Cum_Sum(i) would stay the same, then make the exchange if it improves your position in other ways. If your opponent has fewer defenders than you have attackers, you can accept a temporary reduction in Cum_Sum on your second-to-last capture if on your final unanswerable recapture the Cum_Sum goes positive again.
In practice, it isn’t all that bad to start by counting the number of attackers, defenders, and summing all the relevant piece values. This is the standard solution, which is essentially Tempo’s solution. It will often work well when there are fewer defenders than attackers. But then you need to reconsider the sequence of captures to make sure it isn’t like Example 3, that the defender can’t simply stop the capture sequence ahead in material. When you realize this, something like Cum_Sum is required, and helpful as it is pretty simple. It is simple because it only involves addition and subtraction, and you don't have to go through the sequence of moves in your head, only the sequence of arithmetic problems.
It isn't necessary or desired to think in terms of all this notation: the notation is merely required to acheive an appropriate level of generality. In a real game you just have to think in terms of values of actual pieces in front of you, so it is a lot easier. Typically you can just see that he can't stop the exchanges, that you can keep going one more if he has fewer defenders than attackers. So lots of this we already do intuitively without thinking. But if our goal is to make a general mathematical strategy that always works, this or something equivalent is necessary.
I will toy with using it explicitly to see how much it screws up my games.
posted by Blue Devil Knight at 11/01/2007 06:40:00 PM
32 Comments:
This is the standard solution, which is essentially Tempo’s solution. It will often work well
If you look carefull at my description, you will find that all situations where this simple solution doesn't work are excluded. Implicit or explicit.
Tempo: I thought you said yours wouldn't work with pawns as defenders?
I wrote this because it wasn't clear how yours would handle certain situations, it didn't handle the pawn situations (the first thing I thought of in my reaction), and I couldn't divine what was implicit in your writing. So I made it all explicit.
For me it's just a mathematical puzzle. I can't resist little combinatorics puzzles like this. I wanted a more general formulation, not relying on intuition or people discerning my implicit intent.
There are a few places I didn't understand what you were saying. On the matter of stopping rules you said "If your attacker has less value than the victim you can stop retaking after the first capure. Or not." I don't understand that, don't see how it is implicit in the original formula, so I realized it would be easier for me to just make everything explicit.
This is in the spirit of coming up with the truth, laid bare in an explicit formulation, not of attacking your answer. Without yours I wouldn't have thought to formalize things explicitly like this.
Another place where yours doesn't work mine requires a tweaking too: queens in front of rooks or other pieces such that she has to capture before them. I also need to accommodate that by saying, instead of D being rank ordered from the smallest to largest period, it must be rank ordered from smallest to largest number in any actual recapture sequence.
I'm a little surprised you are fighting to hard to defend your original formulation rather than work with me to make things more clear and explicit. It isn't important after all. :P
Blue,
[repeated from my blog]
it's true, my method supposes the use of common sense, which is not necessary for your method.
Read for instance the following sentence with your common sense ON:
"If your attacker has less value than the victim you can stop retaking after the first capure. Or not."
That should read as follows: If you have just won his queen with your knight it problably doesn't matter how you continue since he will resign anyway:)
I'm a little surprised you are fighting to hard to defend your original formulation rather than work with me to make things more clear and explicit.
From the beginning I had the feeling we meant the same but said it differently. I thought you were thinking we weren't meaning the same. I feel not bound by any formulation as long as we both understand it. That was clearly not the case. Now it is.
Cum_Sum? Recommend changing the abbreviation. Or maybe I'm just immature.
I'm curious how much people Google will send to your Cum_Sum:)
Being a nitpicker in formulations is very important in a case like this where you try to create something out of nothing. It helps you to see similarities.
For instance Nimzowitsch talks alot about the similarity of blocking a passer and blocking a pawnchain. Of course you can ask "how important is that?" But it guided his thoughts. When he discovered something while thinking about pawnchains he could immediately apply it to passers too. That was helpful for him.
My attempt to broaden beancounting to more complex positions will show the same pecularities in formulation, you will see.
Your formulation from out a different mindset causes friction, which forces me to rethink things. That is very helpful.
LMAO. It's all for the traffic. Cum_Sum is bullshit! Buah ha ha!
I'm glad it didn't escalate more Tempo. I'm in the middle of a game and can only think of this. Now hopefully I'll get back in and not blunder! In academic matters like this I sometimes state things too strongly, overstate problems with other people's positions. I do it to be devil's advocate, get to the truth faster, but sometimes it is very annoying to people...I learned the hard way not to do it with religous matters.
As I suspected, this algorithm is useless in practice. Humans, at least this one, doesn't play like a computer.
Try mine. After reformulation in understandable english.
Chess programmers probably have this stuff down flat.
If you mean programmers who play chess do something like this in the game, ok, maybe (but this one does not).
If you mean to imply that chess programs are written in such a manner I would think not (someone, somewhere could have done something like this but it would not be the usual approach) as "brute force calculation" (with or without various refinements) is simple, quick, and handles the exceptions like in-between moves.
Glenn, I think that some of the quiescence search methods might resemble this algorithm.
At the end nodes of the brute force search the computer must make an evaluation. But it's pretty bad at evaluating positions with possible captures in them, so the computer has to extend the search to quiescence by evaluating if the captures (and possibly checks) are good. I wouldn't be surprised if some programs algorithms for this are similar to what BDK has written here.
Loomis: I was thinking of quiescience search. XY has implemented quiescience search so he could tell us.
I never thought of the idea to develop a formalism as to when to capture other than this: count in all relevant variations and when the result is positive for every new tree resulting from oppoent's alternatives than the move seems ok. If there is one variation which cannot be avoided and leaves you down material this is likely not a good idea. The only way to make this easier seems to be to cut down the variational tree, but i dont see any alternative to stupidly count for each branch (after this move he gains a bishop, so substract 3,25 (-3,25) now i take his rook, so add 5 (+1,75) now he can take my queen which means -9,75 (-8) so all in all this variation is horrible (-8), should this be best i'd better resign). With dascination I see what you are doing, which theories you (Temposchlucker and BDK) are applying to counting, but seriously I have difficulties in seeing how to use them. I think any general rule will have to make so many exceptions or become itself so complicated that I'll just continue counting for every variation, as this may well be the end-result of all those theories and exceptions... (which are fascinating and which I will try to understand better)
long live stupid counting!
kind regards,
svensp
By the way: I'm awfully sorry for mistreating the english language by my use of "than" when "then" should be applied ("than the move seems ok"). It pains me as much as you to read this (which wont stop me from doing it again, I guess).
kind regards,
svensp
I wouldn't be surprised if some programs algorithms for this are similar to what BDK has written here.
It is possible but I do not think it is the norm.
I think the following would be more typical:
Chess Programming Part V: Advanced Search
My own program uses a simple quiescence search which extends all lines of play (after a full-width search to depth X) by looking exclusively at captures.
or this:
A quiescence search is an additional search, starting at the leaf nodes of the main search, which tries to solve this problem. In chess, quiescence searches usually include all capture moves, so that tactical exchanges don't mess up the evaluation. In principle, quiescence searches should include any move which may destabilize the evaluation function--if there is such a move, the position is not quiescent.
quiesence search
or
n fact, Chess 4.0 set the paradigm that was and still is followed essentially by all modern Chess programs today. Chess 4.0 type programs won out for the simple reason that their programs simply played better chess. Such programs did not try to mimic human thought processes, but relied on full width alpha-beta and negascout searches. Most such programs (including all modern programs today) also included a fairly limited selective part of the search based around quiescence searches, and usually extensions and pruning (particularly null move pruning from the 1990s onwards) which were triggered based on certain conditions in an attempt to weed out or reduce obviously bad moves (history moves) or to investigate interesting nodes (e.g. check extensions, passed pawns on seventh rank, etc).
wikipedia: Computer Chess
and another nice source on the subject:
We should do static evaluations only in `quiet' positions; it's silly to report that you have a slight advantage because your opponent has some weak squares or a piece slightly out of play if next move he is going to take your queen for nothing. But how do you know he can take your queen? Only by looking at his available moves! But you can't do that at the bottom of the tree, which is when you want to use static evaluation, as it amounts to looking another move deeper. Most programs get around this by having two phases in their dynamic search: in phase one, all moves are searched; in phase two, only `interesting' moves are allowed. The degree of interest is a matter of judgement; if you allow too much to be of interest then the interesting moves never run out and the search goes on too long, if too little then you miss interesting consequences.
Just to let you all know, I am not giving you all the "silent treatment" as my last post indicates, I have to take some time off the intense bloggin regimine due to personal reshufflng of priorities.
I will still be lurking in thebackground, commenting on occasion... but won't be able to devote much depth for a while.
Later, BP
Sven: I think that in some circumstances there should be an easier way. But always careful for exceptions. You are right that they are many once you add in-between moves and such.
Glenn: cool! Thanks for all the references. It will take me some time to sift through this and compare them to what I've said.
As for this cum_sum thingy, I am finding some simplifications that can be made and will post about it when I get a chance. Right now I'm on the beach in San Diego, listening to the waves hit the sand, soon to go out to my old haunts....I love San Diego!
BDK: i always suspected,
when you told me that you were just a simple unsophisticed guy or that some of what i wrote 'was beyond' you,
that you were pulling my leg. you are the reincarnaation of Laplace or Kurt Godel, or something like that?
its like me telling you that im a relaxed guy. come on BDK! you must be to academia to what i am to OCD's. nice going.
i wont say bravo, so lets try some other words:
palms turned up, sanctity, reverence, i gaze at him, remembering the force of all the layers of men come and gone, upon the earth, some proto-cretian ruin resurrected, like a bouquet of flowers, on sunday, surrounded by well dressed, bright skinned cleanly appointed children come to sing Handel's massiah in choir with a Bose sound system run on a Atlanta Ghetto gangstar rappers chrome wheeled boat like conveyance marshalled by a black boot, silver sunglassed state motorcade.
DK: LMAO!!! Thanks. It was fun, and I think I may be able to formulate it in a useful way eventually. Things start out complex but hopefully will simplify.
DK,
When Blue said that what you said was "beyond him", I hadn't the impression that he was referring to his qualities as analyst:)
There is a good saying in the south, in the United States, where accents are exadurated but quiet lovely to hear:
[said in THAT accent:}
"Hee is ah highh brainn dude"
BDK,
The prior links describe what happens. Here I will attempt to summarize and explain why. This is obviously a general and simplified description.
Chess engines have a move generation function that applies to a specific board Position (where the pieces are, side to move, is castling k-side allowed? etc). Given a Position and a list of generated Moves the engine can generate all of the possible next Positions. This can be applied recursively to consider all possible Positions N ply into the future.
Because of constraints of Time (need to move sometime in the next 5 seconds, or today, or this year) and Space (computer memory to hold all of these generated positions) and the geometric progression of this exercise a chess engine can not see all possibilities forever into the future. There is some limit to the depth that the chess engine can consider.
Numerous techniques are used to improve on the "brute force" search described above. At some point though, this exercise is done and we need to evaluate the endpoint Positions. If captures are pending then those need to be considered to get a meaningful evaluation.
The normal method of considering those is to continue the search, as above, but limited to captures (and possibly other strong moves like checks) until none are left or some absolute limits are reached.
The beauty and simplicity of this is that it uses the same technique that got us there except it continues on only for captures and other strong moves.
The impracticality of what you are describing in a chess engine is that the engine would be required to recognize many things that it does not currently recognize. It would have to be smart in ways that it is not. This gets to the classic split in chess program design of which would be the better way to go: "brute force" or "smart"? Brute force has clearly won out although many have tried to make "smart" chess engines.
Anyway, I hope this early morning ramble helps or intrigues or at least does not bore. :)
TM
DK: I should say that this algorithm is objectively not that impressive, not hard to come by. If you think about it, it just involves arithmetic that we do all the time when evaluating trades. A bunch of addition, subtraction, and comparisons of the results.
Glenn: I find discussions of details of computer engines very interesting. I have yet to be bored by such discussions!
I think it would be pretty easy to have a program implement the pseudo-code in this post (e.g., it just has to sort values of pieces, calculate cum_sum, calculate number of attackers and defenders, etc etc).
However, it seems like it would simply be a lot less efficient (both computationally and in terms of programmers' time) than the method you nicely describe here, which is a relatively simple restriction of brute force search, something the computer is very good at!
Indeed, I am sort of happy I didn't just rediscover what the programmers are doing. I had assumed this stuff would be old hat. But the difference is, I formalized it in a way that tries to capture how I actually think about this stuff. That gives me some hope that it will simplify to a more practical form, or at least a practical set of rules (e.g., something like 'Assume Ai=Di for all i, and that m=n: this implies that you should not attack'.). Such simplifications in my mind, already out there in the literature, could be very helpful when I'm in a time crunch in a real game.
Or not. :) It is very hard to predict how useful an algorithm will be in practice.
BDK,
You can look at a position and deduce that it is 1) a "counting position" and 2) what the focal point is. The chess engine has a difficult time classifying positions in such a way. Perhaps they could retroactively after the brute force analysis and use that information to help teach humans how to better play chess!
Of course, there is much that can be done in the future with chess engines and much that has been done that I am not familiar with so I would not totally discount the use of such techniques at some point.
The attempts to add "knowledge" to chess engines may never stop.
TM
GW: I think this should be the easy part. Any square with a piece on it that could in principle be captured, triggers this algorithm. (Again, I'm not saying this is how it should be done, but it likely could). For instance, one attacker zero defenders implies take.
The real hard part is the need to consider in-between moves. Though for a computer that may not be hard. For humans they are easy to overlook.
BDK,
When one considers the in betweeners, the fact that some pieces may be pinned in a subsequent position but not the original and vice versa, some pieces may be involved in more than one focal point, etc., I believe that the computer is back to just calculating the moves and positions. Which, by the way, is not a burden to the computer. That is what it is good at...
If the position is not quiet, I believe (but can not prove), that in the general case generating moves and considering the subsequent positions is the only way to get an accurate evaluation of the position. For humans or computers.
Which means (and I was not intending to go there but at least I am consistent) chess is pretty much nothing but tactics.
Cheers,
TM
much of that has been writen is either sincerely beyond me, or have not have parsed myself, nor need we any comments from me thereof,
except to note this very fine link on computor chess calculating and Rybkya.
i dont so much read all this stuff with full comprehension as enjoy the general style, flow, and drift of it all... like eating intelectual chocolate for me. much richness is presented or writen and linked there beyond immediate page, above.
By the way, Vaclav Rajlich says somewhere that he feels that Jerz is correct in some ways here, and wrong in others. Let the kind reader browse here, where much being discussed above, I am confident, is touched upon.
------------------
giant cliffs, towering north coast
sea walls churning ancient mariners
blue light from the stars bellowing
we stand in silence, all of them
relentless progression of evolution
Bravo! Or not.
And I thought Tempo's math problem is complicated. Despite your warnings I did continue to read this post to the end. Damn, where's my Advil! (TM) {I had to stick that one in after reading your old post on types of bloggers. Great one! ROFLMAO!)
It's funny because no sooner then this topic comes up, I have a few games these last few nights that have had multiple attackers and defenders on a piece. I found myself thinking about all these discussions.
I'm not sure whether trying to think in this formulated fashion contributed to my time pressure woes or not.
Polly: lol. It definitely hurt me the other night. I'm not sure if it's because it is new or because it is useless in practice. Maybe both! :)
A challenge for you at my blog.
"If you don't like technical weird geeky computer stuff, stop reading now before you get annoyed."
Whew, that was a close one. Thanks for the warning. LOL!
Just kidding of course. I think trying to break things down into what you can understand and what works for you is one of the major keys to improvement.
I am currently in a "go with the flow" mode for improvement, satisfying only my desire for the combination, attack, thrill of time pressure. Thinking has been put on hold ;)
Post a Comment
<< Home