see

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Sven
Posts: 3572
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: see

Post by Sven » Wed Nov 29, 2017 8:49 pm

flok wrote:

Code: Select all

// xy are of the victim
int Scene::getSEE(const int x, const int y, const ChessPiece *const attacker) const
{
	const ChessPiece *const victim = b.getAt(x, y);

	const PlayerColor c = attacker -> getColor();

	// bit 0...15: if set, then a white piece can walk over and/or attack this field, 16...31 black
	const uint32_t bits = ss.back().tcs.cells[y][x];

	int see_val = victim -> getEvalVal();
	int trophy_val = attacker -> getEvalVal();

	PlayerColor sc = opponentColor(c);
	int so[] = { 0, 16 }; // where to start to search in the bit pattern. so[0] is for white
	constexpr int soe[] = { 16, 32 }; // where to stop searching. soe[0] is for white

	for&#40;; so&#91;sc&#93; < soe&#91;sc&#93;;) &#123;
		// find a 1 bit
		while&#40;&#40;bits & &#40;1 << so&#91;sc&#93;)) == 0&#41; &#123;
			// if end of pattern, stop searching
			if (++so&#91;sc&#93; == soe&#91;sc&#93;)
				break;
		&#125;

		if &#40;so&#91;sc&#93; >= soe&#91;sc&#93;)
			break;

		if &#40;sc == c&#41;
			see_val += trophy_val;
		else
			see_val -= trophy_val;

		// get eval val. bit number is an index in pieces&#91;color&#93;&#91;index&#93; pointing to the
		// piece.
		trophy_val = sc == WHITE ? pieces&#91;sc&#93;&#91;so&#91;sc&#93;&#93; -> getEvalVal&#40;) &#58; pieces&#91;sc&#93;&#91;so&#91;sc&#93; - 16&#93; -> getEvalVal&#40;);

		// on to the next bit!
		so&#91;sc&#93;++;

		sc = opponentColor&#40;sc&#41;;
	&#125;

	return see_val;
&#125;
I think this is not a correct SEE implementation. Whenever you find a new attacker for the target square you always have the choice between "making the capture" and "standing pat" (i.e., doing nothing). So at any point in your loop over pieces attacking the target square (not just in the root!) you would have to calculate the outcome of the capture but then ignore it if it loses material (so in fact you would also need to modify your algorithm). Just like in QS. What you seem to do in the code shown above is to always make the capture with the lowest remaining attacker, until no more attackers are left. But that is incorrect because it does not consider standing pat. For instance if the last enemy piece that did a capture was a knight and your next attacker is a queen but the enemy has another knight as attacker (defender) then you must detect that QxN NxQ is worse than not capturing.

It is slightly harder to do that correctly with an iterative algorithm compared to the very simple recursive one, but of course it is possible (by definition).

AlvaroBegue
Posts: 880
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York

Re: see

Post by AlvaroBegue » Wed Nov 29, 2017 9:00 pm

Sven wrote:It is slightly harder to do that correctly with an iterative algorithm compared to the very simple recursive one, but of course it is possible (by definition).
I actually showed how to do it in a previous post in this thread.

lauriet
Posts: 161
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: see

Post by lauriet » Thu Nov 30, 2017 2:01 am

Hi all.
With all this talk about SEE........
I dont have it in my program, so can someone explain what to do with it once you have calculated it ?
How would it improve my program, what are the gains.


Laurie (LTchess)

AlvaroBegue
Posts: 880
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York

Re: see

Post by AlvaroBegue » Thu Nov 30, 2017 5:07 am

lauriet wrote:Hi all.
With all this talk about SEE........
I dont have it in my program, so can someone explain what to do with it once you have calculated it ?
How would it improve my program, what are the gains.


Laurie (LTchess)
I only use it in two places:
(1) In quiescence search I skip captures with SEE < 0
(2) In the regular alpha-beta search, I use it for move ordering, which goes like this:
* Hash move
* Captures with SEE > 0, ordered by MVV/LVA
* Captures with SEE == 0, ordered by MVV/LVA
* Killers
* Non-captures, ordered by history heuristic
* Captures with SEE < 0, ordered by MVV/LVA

The way I implement (2) is to generate all captures, sort them by MVV/LVA and when you are about to explore a capture, compute its SEE, then move it to a different list for later processing if SEE <= 0.

lauriet
Posts: 161
Joined: Sun Nov 03, 2013 8:32 am
Contact:

Re: see

Post by lauriet » Thu Nov 30, 2017 5:43 am

Sounds like a lot of processing for a little gain ???
Has anybody got data on if it effective in increasing ELO ?

AlvaroBegue
Posts: 880
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York

Re: see

Post by AlvaroBegue » Thu Nov 30, 2017 11:47 am

lauriet wrote:Sounds like a lot of processing for a little gain ???
Has anybody got data on if it effective in increasing ELO ?
In my notes I have the results of trying to remove the pruning of SEE<0 moves from quiescence search: -40 Elo (391-597-818)

abulmo2
Posts: 131
Joined: Fri Dec 16, 2016 10:04 am
Contact:

Re: see

Post by abulmo2 » Thu Nov 30, 2017 12:44 pm

AlvaroBegue wrote:
lauriet wrote:Sounds like a lot of processing for a little gain ???
Has anybody got data on if it effective in increasing ELO ?
In my notes I have the results of trying to remove the pruning of SEE<0 moves from quiescence search: -40 Elo (391-597-818)
In Amoeba, I use see to prune moves in quiescence search, to sort them and even to prune some bad moves during search. Removing all of them costs Amoeba 70 +/- 10 Elo.
Richard Delorme

tttony
Posts: 254
Joined: Sat Apr 23, 2011 10:33 pm
Contact:

Re: see

Post by tttony » Fri Dec 01, 2017 10:51 am


Post Reply