Author: Robert Hyatt
Date: 11:34:16 11/12/98
Go up one level in this thread
On November 12, 1998 at 12:13:26, Larry Coon wrote: >(Long question follows -- sorry.) > >I know I saw SEE talked about recently, but I couldn't >locate the discussion here, on rgcc or anybody's web >page (I don't remember where I saw it). Can somebody >tell me if I'm thinking about this the right way? your approach is a complicated way of thinking about it, but it ought to work. An easier way is to simply play out the captures and save the material score after each one, just as you suggested, until one side can't make a capture. Then you simply back up thru this list to see what the material score before the capture and after the capture is... but the score after the capture is the score that happens at the end of the sequence, or somewhere along the way... here is a simple bit of code: next_capture--; if(next_capture&1) sign=-1; else sign=1; while (next_capture) { if (sign < 0) { if(swap_list[next_capture] <= swap_list[next_capture-1]) swap_list[next_capture-1]=swap_list[next_capture]; } else { if(swap_list[next_capture] >= swap_list[next_capture-1]) swap_list[next_capture-1]=swap_list[next_capture]; } next_capture--; sign=-sign; } next_capture tells me how many entries are in swap_list... notice that at each step along the way, I compare the current to the next entry and if the next is "better" from my point of view, I back this up to the previous entry.. then the side on there can choose to accept my value, or the value he would have if he chooses to not make a capture at all and stand pat... Pretty simple idea, pretty difficult to explain it. The above can be written a bit shorter because the two comparisons can be done like we do with negamax... but this one is probably easier to understand... Bob > >I'll start with a contrived position: >1kq5/3n2p1/5p2/8/6N1/5R2/5RK1 w > >Would a SEE do the following? > 1. Find all attackers on the square in question (f5). > 2. For each side, order the attackers in value, lowest > to highest. Include the piece that is initially > captured to start off the exchange. Put them into > two....whatever, I'll say stacks just to make it > easy to talk about. The lowest valued pieces will > be at the top of the stack. Only the values of the > pieces need to be pushed onto the stack. > 3. Start with a "trade balance" of zero. > 4. Pop the next value for the side NOT to move (black's > stack if it's white's move) and SUBTRACT it from > the trade balance, then do the same for the other > stack. (This works because at least in my program > opposing pieces have opposite signs). > 5. When all values have been popped off either one of > the stacks, then the exchange is over and the trade > balance lets you know where you stand. > 6. However, neither side has to follow the exchange > through to its completion. So if either of the > following happen: > a. You pop the next value of "your" stack and > subtract it from the trade balance and it ends > up negative (for white, positive for black) > b. You do the same for the opponent's stack and > the result is positive (if black is the > opponent, otherwise negative) > Then you can assume that the side to move will not > continue the exchange, exit the loop now, and the > current trade balance will be the final balance. > >So in my example position, the stacks would look like >(top of stack to the left): > white: 3, 5, 5 > black: -1, -1, -3, -9 > >And the process would be as follows: > Step stack value balance > ---- ----- ----- ------- > 0 0 > 1 b -1 1 > 2 w 3 -2 > 3 b -1 -1 * > 4 w 5 -6 ** > 5 b -3 -3 > 6 w 5 -8 > 7 b -9 1 > >So at the point I marked *, the value is negative >with black to move and the loop can actually stop >here. Black doesn't have to play NxR, and he's >won the exchange. Therefore, the initial capture >is bad for white. > >However, if black DOES play NxR the following move >takes him to an even better position (**). Maybe >I keep track of "most positive after an odd-numbered >step" and "most negative after an even numbered >step"? Then the "most negative" would be the >assumed jumping-out point for black, and the "most >positive" would be the jumping-out point for white. > >Or is it like beta-cutoff in alpha-beta where you >don't care how big the cutoff is, as long as you >find -a- cutoff? So in this case, it doesn't >matter if the next exchange takes black from -1 to >-6, because the -1 by itself means the initial >capture is bad for white. > >I think I'm missing something obvious here about >the essence of this problem. Can anybody help? > >Thanks, > >Larry Coon
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.