Author: Gian-Carlo Pascutto
Date: 17:20:25 10/01/01
Go up one level in this thread
On October 01, 2001 at 15:53:32, Steve Maughan wrote:
>Thanks!! That was the insight I needed. I was struggling with the ordering of
>the moves when there was an xray attack. Your way does this dynamically and
>with low overhead.
Actually, I thought the same way originally.
Sjeng doesn't use bitboards and calculating attacks is very expensive, so
I tried to avoid it as much as possible and didn't consider xray attacks.
Then, I added them just to test. (After each capture I check if there was
a possible attacker behind the piece that captured). It takes maybe 0.1% of the
total running time. So I definetly keep it for now ;)
I've put my SEE routine below, in case you're interested
/*
Sjeng - a chess variants playing program
Copyright (C) 2001 Gian-Carlo Pascutto
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
File: see.c
Purpose: do static exchange evaluation
*/
#include "sjeng.h"
#include "extvars.h"
typedef struct
{
int piece;
int square;
} see_data;
see_data see_attackers[2][16];
int see_num_attackers[2];
void setup_attackers (int square)
{
static const int bishop_o[4] = {11, -11, 13, -13};
static const int knight_o[8] = {10, -10, 14, -14, 23, -23, 25, -25};
static const int rook_o[4] = {12, -12, 1, -1};
register int a_sq, b_sq, i;
int numw = see_num_attackers[WHITE], numb = see_num_attackers[BLACK];
/* bishop-style moves: */
for (i = 0; i < 4; i++)
{
a_sq = square + bishop_o[i];
b_sq = board[a_sq];
/* check for pawn attacks: */
if (b_sq == wpawn && i%2)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = a_sq;
numw++;
break;
}
else if (b_sq == bpawn && !(i%2))
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = a_sq;
numb++;
break;
}
/* the king can attack from one square away: */
else if (b_sq == wking)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = a_sq;
numw++;
break;
}
else if (b_sq == bking)
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = a_sq;
numb++;
break;
}
else
{
while (b_sq != frame) {
if (b_sq == wbishop || b_sq == wqueen)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = a_sq;
numw++;
break;
}
else if (b_sq == bbishop || b_sq == bqueen)
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = a_sq;
numb++;
break;
}
else if (b_sq != npiece) break;
a_sq += bishop_o [i];
b_sq = board[a_sq];
}
}
}
/* knight-style moves: */
for (i = 0; i < 8; i++)
{
a_sq = square + knight_o[i];
b_sq = board[a_sq];
if (b_sq == wknight)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = a_sq;
numw++;
}
else if (b_sq == bknight)
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = a_sq;
numb++;
}
}
/* rook-style moves: */
for (i = 0; i < 4; i++)
{
a_sq = square + rook_o[i];
b_sq = board[a_sq];
/* the king can attack from one square away: */
if (b_sq == wking)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = a_sq;
numw++;
break;
}
else if (b_sq == bking)
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = a_sq;
numb++;
break;
}
else
{
/* otherwise, check for sliding pieces: */
while (b_sq != frame)
{
if (b_sq == wrook || b_sq == wqueen)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = a_sq;
numw++;
break;
}
else if (b_sq == brook || b_sq == bqueen)
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = a_sq;
numb++;
break;
}
else if (b_sq != npiece) break;
a_sq += rook_o [i];
b_sq = board[a_sq];
}
}
}
see_num_attackers[WHITE] = numw;
see_num_attackers[BLACK] = numb;
}
void add_dia_attackers(int tsq, int fsq)
{
register int b_sq;
int numw = see_num_attackers[WHITE], numb = see_num_attackers[BLACK];
if (diagl[tsq] == diagl[fsq])
{
if (fsq > tsq)
{
for (fsq += 13 ; fsq == npiece; fsq += 13);
b_sq = board[fsq];
if (b_sq == wbishop || b_sq == wqueen)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = fsq;
see_num_attackers[WHITE]++;
}
else if (b_sq == bbishop || b_sq == bqueen)
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = fsq;
see_num_attackers[BLACK]++;
}
}
else
{
for (fsq -= 13; fsq == npiece; fsq -= 13);
b_sq = board[fsq];
if (b_sq == wbishop || b_sq == wqueen)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = fsq;
see_num_attackers[WHITE]++;
}
else if (b_sq == bbishop || b_sq == bqueen)
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = fsq;
see_num_attackers[BLACK]++;
}
}
}
else if (diagr[tsq] == diagr[fsq])
{
if (fsq > tsq)
{
for (fsq += 11; fsq == npiece; fsq += 11);
b_sq = board[fsq];
if (b_sq == wbishop || b_sq == wqueen)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = fsq;
see_num_attackers[WHITE]++;
}
else if (b_sq == bbishop || b_sq == bqueen)
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = fsq;
see_num_attackers[BLACK]++;
}
}
else
{
for (fsq -= 11; fsq == npiece; fsq -= 11);
b_sq = board[fsq];
if (b_sq == wbishop || b_sq == wqueen)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = fsq;
see_num_attackers[WHITE]++;
}
else if (b_sq == bbishop || b_sq == bqueen)
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = fsq;
see_num_attackers[BLACK]++;
}
}
}
}
void add_hor_attackers(int tsq, int fsq)
{
register int b_sq;
int numw = see_num_attackers[WHITE], numb = see_num_attackers[BLACK];
if (file[tsq] == file[fsq])
{
if (fsq > tsq)
{
for (fsq += 12; fsq == npiece; fsq += 12);
b_sq = board[fsq];
if (b_sq == wrook || b_sq == wqueen)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = fsq;
see_num_attackers[WHITE]++;
}
else if (b_sq == brook || b_sq == bqueen)
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = fsq;
see_num_attackers[BLACK]++;
}
}
else
{
for (fsq -= 12; fsq == npiece; fsq -= 12);
b_sq = board[fsq];
if (b_sq == wrook || b_sq == wqueen)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = fsq;
see_num_attackers[WHITE]++;
}
else if (b_sq == brook || b_sq == bqueen)
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = fsq;
see_num_attackers[BLACK]++;
}
}
}
else if (rank[tsq] == rank[fsq])
{
if (fsq > tsq)
{
for (fsq++; fsq == npiece; fsq += 1);
b_sq = board[fsq];
if (b_sq == wrook || b_sq == wqueen)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = fsq;
see_num_attackers[WHITE]++;
}
else if (b_sq == brook || b_sq == bqueen)
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = fsq;
see_num_attackers[BLACK]++;
}
}
else
{
for (fsq--; fsq == npiece; fsq -= 1);
b_sq = board[fsq];
if (b_sq == wrook || b_sq == wqueen)
{
see_attackers[WHITE][numw].piece = b_sq;
see_attackers[WHITE][numw].square = fsq;
see_num_attackers[WHITE]++;
}
else if (b_sq == brook || b_sq == bqueen)
{
see_attackers[BLACK][numb].piece = b_sq;
see_attackers[BLACK][numb].square = fsq;
see_num_attackers[BLACK]++;
}
}
}
}
void findlowest(int color, int next)
{
int lowestp;
int lowestv;
see_data swap;
int i;
lowestp = next;
lowestv = abs(material[see_attackers[color][next].piece]);
for (i = next; i < see_num_attackers[color]; i++)
{
if (abs(material[see_attackers[color][i].piece]) < lowestv)
{
lowestp = i;
lowestv = abs(material[see_attackers[color][i].piece]);
}
}
/* lowestp now points to the lowest attacker, which we swap with next */
swap = see_attackers[color][next];
see_attackers[color][next] = see_attackers[color][lowestp];
see_attackers[color][lowestp] = swap;
}
int see(int color, int square, int from)
{
int sside;
int caps[2];
int value;
int origpiece;
int ourbestvalue;
int hisbestvalue;
int csq;
/* reset data */
see_num_attackers[WHITE] = 0;
see_num_attackers[BLACK] = 0;
/* remove original capturer from board, exposing his first xray-er */
origpiece = board[from];
board[from] = npiece;
see_num_attackers[color]++;
see_attackers[color][0].piece = origpiece;
see_attackers[color][0].square = from;
/* calculate all attackers to square */
setup_attackers(square);
/* initially we gain the piece we are capturing */
value = abs(material[board[square]]);
/* free capture ? */
if (!see_num_attackers[!color])
{
board[from] = origpiece;
return value;
}
else
{
/* we can never get a higher SEE score than the piece we just captured */
/* so that is the current best value for our opponent */
/* we arent sure of anything yet, so -INF */
hisbestvalue = value;
ourbestvalue = -INF;
}
caps[color] = 1;
caps[!color] = 0;
/* start with recapture */
sside = !color;
/* continue as long as there are attackers */
while (caps[sside] < see_num_attackers[sside])
{
/* resort capturelist of sside to put lowest attacker in next position */
findlowest(sside, caps[sside]);
if (sside == color)
{
/* capturing more */
/* we capture the opponents recapturer */
value += abs(material[see_attackers[!sside][caps[!sside]-1].piece]);
csq = see_attackers[!sside][caps[!sside]-1].square;
if (diagl[csq] == diagl[square] || diagr[csq] == diagr[square])
{
add_dia_attackers(square, see_attackers[!sside][caps[!sside]-1].square);
}
else if (file(csq) == file(square) || rank(csq) == rank(square))
{
add_hor_attackers(square, see_attackers[!sside][caps[!sside]-1].square);
}
/* if the opp ran out of attackers we can stand pat now! */
if (see_num_attackers[!sside] <= caps[!sside] && value > ourbestvalue)
ourbestvalue = value;
/* our opponent can always stand pat now */
if (value < hisbestvalue) hisbestvalue = value;
if (ourbestvalue >= hisbestvalue) break;
}
else
{
/* recapture by opp */
/* we lose whatever we captured with in last iteration */
value -= abs(material[see_attackers[!sside][caps[!sside]-1].piece]);
if (caps[!sside] > 1)
{
csq = see_attackers[!sside][caps[!sside]-1].square;
if (diagl[csq] == diagl[square] || diagr[csq] == diagr[square])
{
add_dia_attackers(square, see_attackers[!sside][caps[!sside]-1].square);
}
else if (file(csq) == file(square) || rank(csq) == rank(square))
{
add_hor_attackers(square, see_attackers[!sside][caps[!sside]-1].square);
}
}
/* we can stand pat if we want to now */
/* our best score goes up, opponent is unaffected */
if (value > ourbestvalue)
{
ourbestvalue = value;
}
if (see_num_attackers[!sside] <= caps[!sside] && value < hisbestvalue)
hisbestvalue = value;
if (ourbestvalue >= hisbestvalue) break;
}
/* keep track of capture count */
caps[sside]++;
/* switch sides */
sside ^= 1;
}
/* restore capturer */
board[from] = origpiece;
/* we return our best score now, keeping in mind that
it can never we better than the best for our opponent */
return (ourbestvalue > hisbestvalue) ? hisbestvalue : ourbestvalue;
}
--
GCP
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.