Implementing SEE

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Implementing SEE

Post by cms271828 » Fri Aug 12, 2011 10:20 pm

Hi

I've been away from chess programming for a while, but I'm still stuck on SEE.
Every time I try to resolve something I seem to open a new can of worms.

I planned on using an iterative static exchange evaluation following the psuedo code:

Code: Select all

int staticexchangeevaluationw ( const int from , const int to ) 
{
    int iteration ;
    int valuelist[ 3 2 ] ;
    int next ;
    int valueattacker ;

    // iteration for White
    iteration=0;
    valuelist[iteration] = boardvalue ( to ) ;
    next = from ;
    generateattackers ( next , to ) ;
    if ( blackattackers( ) == 0 ) return boardvalue ( t o ) ;

    valueattacker = boardvalue ( from ) ;

    // forward−iterationloop : ( 1 ) fill the valuelist
    while ( true ) 
    {
        // iteration for Black
        iteration ++;
        valuelist[ iteration ]= valueattacker −valuelist [iteration− 1 ] ;
        next = nextblackattacker ( ) ;
        updatexrayattackers ( next , t o ) ;

        if ( whiteattackers( ) == 0 ) break ;

        valueattacker = board value ( next ) ;

        //iteration for White
       iteration ++;
       valuelist [iteration ]= valueattacker −valuelist [iteration − 1 ] ;
       next = nextwhiteattacker ( ) ;
       updatexrayattackers( next , t o ) ;

       if ( blackattackers( ) == 0 ) break ;

       valueattacker = board value ( next ) ;
    }

    // reverse −iteration loop : ( 2 ) evaluate the valuelist
    while ( true ) 
    {
        if( iteration == 0 ) return valuelistt [ 0 ] ;

        if ( valuelist [iteration ] > − valuelist [ iiteration −1])
        {
            valuelist [iteration −1] = −valuelist [iteration ] ;
        }

        iteration −−;
    }
}
I'm not sure about generating attackers, the problem is more trickier than it seems.
I have had a few ideas but they all seem problematic.

Any advice would be grateful, thanks.
Last edited by cms271828 on Fri Aug 12, 2011 10:30 pm, edited 2 times in total.
Colin

Daniel Shawul
Posts: 3757
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Implementing SEE

Post by Daniel Shawul » Fri Aug 12, 2011 10:24 pm

i c a n ' t r e a d y o u r c o d e : (

User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Re: Implementing SEE

Post by cms271828 » Fri Aug 12, 2011 10:31 pm

I know, I copied from pdf file, I've fixed it now..
Colin

tpetzke
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

Re: Implementing SEE

Post by tpetzke » Fri Aug 12, 2011 10:52 pm

Hi,

you need a swap list of pieces with alternating sides and increasing values.

I use 2 variables that are initialized to pawns

Code: Select all

EPiece lowestAttackerW = W_PAWN;  // init the lowest attacker to pawns	
EPiece lowestAttackerB = B_PAWN;  
then with alternating sides I scan whether a piece of that type attacks the square for the see.

If I find one, I store it in the list and process a piece of the opponent side.
If I find none I increase lowestAttacker to the next valuable piece type and look for that and so on until I pass the king as piece to look for for one side. Then I'm done

To find stacked attackers you must reset the lowestAttacker to Bishop whenever you store a queen in your list

Code: Select all

// if the attacker was a rook or a queen, we reset the lowest attacker to bishop, so we find hidden attackers as well
if (lowestAttackerW == W_QUEEN) lowestAttackerW = W_BISHOP;

This gets you started. It's not perfect yet as for instance a black bishop hidden behind a white bishop might get overlooked but with 2 statements you capture those cases as well.

When you have your swap list the hardest part is done. How you come to the final SEE value with it is explained nicely in the wiki.

http://chessprogramming.wikispaces.com/ ... +Algorithm

Thomas...

Daniel Shawul
Posts: 3757
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Implementing SEE

Post by Daniel Shawul » Fri Aug 12, 2011 10:57 pm

Well you have to generate all hidden slider attacks when you move a piece. If you consider only the original state of the board, it will not perform good. With piece lists I just check the squares behind a slider to see if there are other slider pieces of our own i.e inside the while loop. May be you can achieve the same thing outside the loop if you use bitboards but I don't remember. Your SEE should detect at least pins to improve upon LVA/MVV. Other than that it looks good for SEE from white's perspective.

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Implementing SEE

Post by hgm » Sat Aug 13, 2011 8:14 am

I Joker I use an iterative implementation of alpha-beta for SEE, where the captures are generated from the piece list (traversed in LVA order). But I keep track of the point where I was in the piece list, so that it does not needlessly performs attack tests on pieces that have already failed them, or were used in an earlier ply.

I keep a scratch board of markers, where I mark all pieces that has already been used in earlier plies, and where I mark every blocker encountered in an attack test together with the number (piece-list index) of the piece it blocked. When a blocker is used because it had a capture itself, this enables me then to 'rewind' to the now unblocked piece, (if needed), so it will be tried again, thus implementing X-rays. The capture tests are conducted such that blockers that are marked as already used will be ignored.

The basic idea is to save time on compiling a list of attackers by deferring the actual capture test to the point you are sure you want to use that piece, and not waste time on searching attackers / defenders if at an early ply the next capture in line is futility pruned. E.g. consider a Pawn defende by two Pawns and an X-ray Bishop, and attacked by Knight, Rook +X-Rook and Queen. After NxP, PxP the next capture would be futile, so you never need to throw capture tests on your Rooks and Queen (and Bishops).

In my newer engines I no longer use SEE, but switched to the simpler, less reliable, but cheaper BLIND.

User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Re: Implementing SEE

Post by cms271828 » Sat Aug 13, 2011 11:40 am

Thanks for messages..

I use bitboards, kind of unsure if I should use them, or just loop over squares.

Assuming the capture is W x B (ignore en passant scenarios for now)..
The first piece in the capture sequence is obviously the white piece thats moving.

Now for black, we can easily test for pawn attacks, just 2 squares...
If no pawn attack, the knight is more or less next valuable.
In theory could be 8 knights that could defend, I can easily store these in a bitboard, to loop through.

If no knight attacks, can look at sliding pieces.
This is where it gets awkward...
Like in the move generator:
x = bitboard of diagonal squares, found magically
+ = bitboard of horiz/vert squares, found magically

I can do x & WB, x & WQ, x & BB, x & BQ, + & WR, + & WQ, + & BR, + & BQ
And then store these pieces somewhere.
Supposing there is a black bishop(with white bishop behind), and say a white queen on a different ray.
If the black bishop is played, it would be wrong to use the white queen next.
So the problem is updating x, I have 3 ideas:

1. all_pieces ^ black_bishop, then regenerate x (magically) as before.
2. Manually scan outwards by testing each square beyond where the black bishop was, each time doing x ^ (1L << square), stopping when a piece is found, or at edge of board.
3. Use magics just on that ray to get a new ray of squares, then x |= ray

I'm thinking 2, but of course still a lot of work to get a working system.
Colin

User avatar
Desperado
Posts: 638
Joined: Mon Dec 15, 2008 10:45 am

Re: Implementing SEE

Post by Desperado » Sat Aug 13, 2011 3:34 pm

Code: Select all


//******************************************************************************
//* AUTHOR&#58; Michael Hoffmann
//* FILE  &#58; attack.cpp
//******************************************************************************

#include "nemo.h"


//******************************************************************************
//* SEE
//******************************************************************************

//* special moves
//* oo,ooo    &#58; return 0
//* doublePush&#58; HACK&#58; ep-move is ignored
//* enPassent &#58; HACK&#58; always winning score 100
//* promotions&#58; like other moves

int seeMove&#40;pos_t *pos,mv_t mve&#41;
&#123;
 int gain&#91;32&#93;, d ,aPiece,sidePick,dst = unpackDst&#40;mve&#41;;
 ui64_t mayXray,fromSet,occ,attadef;

 if&#40;moveIsOO&#40;mve&#41;) return&#40;0&#41;;
 if&#40;moveIsEP&#40;mve&#41;) return&#40;100&#41;;

 sidePick  = pos->ctm ^ side;
 aPiece    = pos->sq&#91;unpackSrc&#40;mve&#41;&#93;;
 fromSet   = onebit&#40;unpackSrc&#40;mve&#41;);
 occ       = OCCUPIED;
 attadef   = attackers&#40;pos,dst,white&#41; | attackers&#40;pos,dst,black&#41; | fromSet/*pawnPush*/;
 gain&#91;d=0&#93; = vSee&#91;pos->sq&#91;dst&#93;&#93;;

 mayXray   =   occ
	         ^ &#40;pos->bb&#91;wnEnum&#93; | pos->bb&#91;bnEnum&#93;
            |  pos->bb&#91;wkEnum&#93; | pos->bb&#91;bkEnum&#93;);

 do
 &#123;
  d++; gain&#91;d&#93; = vSee&#91;aPiece&#93; - gain&#91;d-1&#93;;

  attadef^= fromSet;
  occ    ^= fromSet;

  if&#40;fromSet & mayXray&#41;
  &#123;
   attadef |= attackSlider&#40;pos,occ,dst,white&#41;;
   attadef |= attackSlider&#40;pos,occ,dst,black&#41;;
  &#125;

  for&#40;aPiece=wpEnum+&#40;sidePick&#41;;aPiece<=wkEnum+&#40;sidePick&#41;;aPiece+=2&#41;
	 if&#40;fromSet = pos->bb&#91;aPiece&#93; & attadef&#41;
		&#123;fromSet &=- fromSet;sidePick^=side;break;&#125;

 &#125;while&#40;fromSet&#41;;

 while&#40;--d&#41; gain&#91;d-1&#93; = -maxN&#40;-gain&#91;d-1&#93;,gain&#91;d&#93;);return&#40;gain&#91;0&#93;);
&#125;

Code: Select all

//******************************************************************************
//* attackersToSquare
//******************************************************************************

extern __inline bb_t attackers&#40;pos_t *pos,sq_t sq,isBool bySide&#41;
&#123;
 return&#40;   attack&#91;wpEnum+bySide^side&#93;&#40;sq,0&#41; & pceP&#40;bySide&#41;
         | attackN&#40;sq&#41; & pceN&#40;bySide&#41;
         | attackK&#40;sq&#41; & pceK&#40;bySide&#41;
         | attackB&#40;sq,OCCUPIED&#41; & &#40;pceB&#40;bySide&#41;|pceQ&#40;bySide&#41;)
         | attackR&#40;sq,OCCUPIED&#41; & &#40;pceR&#40;bySide&#41;|pceQ&#40;bySide&#41;));
&#125;

static __inline bb_t attackSlider&#40;pos_t *pos,bb_t occ,sq_t sq,isBool bySide&#41;
&#123;
 return ((  attackB&#40;sq,occ&#41; & &#40;pceB&#40;bySide&#41;|pceQ&#40;bySide&#41;)
          | attackR&#40;sq,occ&#41; & &#40;pceR&#40;bySide&#41;|pceQ&#40;bySide&#41;))
          &  occ&#41;;
&#125;

Code: Select all

// piece macros used for better readability
#define pceP&#40;SIDE&#41;  pos->bb&#91;wpEnum + &#40;SIDE&#41;&#93;
#define pceN&#40;SIDE&#41;  pos->bb&#91;wnEnum + &#40;SIDE&#41;&#93;
#define pceB&#40;SIDE&#41; &#40;pos->bb&#91;wlEnum + &#40;SIDE&#41;&#93;|pos->bb&#91;wdEnum + &#40;SIDE&#41;&#93;)
#define pceR&#40;SIDE&#41;  pos->bb&#91;wrEnum + &#40;SIDE&#41;&#93;
#define pceQ&#40;SIDE&#41;  pos->bb&#91;wqEnum + &#40;SIDE&#41;&#93;
#define pceK&#40;SIDE&#41;  pos->bb&#91;wkEnum + &#40;SIDE&#41;&#93;
just want to share my code i use in Nemo. Everyone is free to use this
code. It is far away from perfect, but i think a reasonable implementation.
The code is based on the pseudocode given from chessprogramming wiki.

if there is need for clarification,explanation, just ask.
i am aware of some optimizations which can be done,but anyway
every constructive criticism is welcome.

Michael

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Implementing SEE

Post by mcostalba » Sat Aug 13, 2011 5:02 pm

Desperado wrote: if there is need for clarification,explanation, just ask.
i am aware of some optimizations which can be done,but anyway
every constructive criticism is welcome.
I like your implementation, is simple and should be also quite fast. One hint could be to calculate the startup attacks only for the side to move and if opponent has no defendants (common case) return immediately without calculating our attackers.

User avatar
Desperado
Posts: 638
Joined: Mon Dec 15, 2008 10:45 am

Re: Implementing SEE

Post by Desperado » Sat Aug 13, 2011 5:49 pm

Hi Marco,

well it is always the same when i give code chunks to the public. I get unhappy
with my code, because i am looking more intensive on it, and maybe more carefully.

Although it was on my _improve someday_ todo list, i think now is a better time.

improvements:
==============

a. attacksets
===========

- your proposal makes absolute sense, because i never thought about the _common case_ ! thx 8-)

- in contradiction, the inner loop should compute the new attackdef list in _one_ run, instead of two

b.moves
============

- promotions are handled currently as losing,or neutral ,winning if capture moves
maybe adding promotion piece value if promoPiece cannot be captured (i have to think about it,would be easy solution)

- a real SEE value for ep-capture move should also be easy because
only the captured ep-pawn must be cleared from occupancy.

c: performance: "test" ability (most interested in)
=======================================

- what i really like to have would be an early exit option
- which could be combined with losing,neutral,winning result like -1,0,1.(<0,==0,>0)

So, if anyone has ideas on how to implement the "improvements" especially on point _c_, i am curious.

But the main goal is to keep the code compact, or even to make it more
compact if possible.

Thx in advance.

Michael

Post Reply