1/*
2    Sjeng - a chess variants playing program
3    Copyright (C) 2001 Gian-Carlo Pascutto
4
5    This program is free software; you can redistribute it and/or modify
6    it under the terms of the GNU General Public License as published by
7    the Free Software Foundation; either version 2 of the License, or
8    (at your option) any later version.
9
10    This program is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13    GNU General Public License for more details.
14
15    You should have received a copy of the GNU General Public License
16    along with this program; if not, write to the Free Software
17    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18
19    File: see.c
20    Purpose: do static exchange evaluation
21
22*/
23
24#include "sjeng.h"
25#include "extvars.h"
26
27typedef struct
28{
29  int piece;
30  int square;
31} see_data;
32
33see_data see_attackers[2][16];
34int see_num_attackers[2];
35
36void setup_attackers (int square) {
37
38  /* this function calculates attack information for a square */
39
40  static const int rook_o[4] = {12, -12, 1, -1};
41  static const int bishop_o[4] = {11, -11, 13, -13};
42  static const int knight_o[8] = {10, -10, 14, -14, 23, -23, 25, -25};
43  register int a_sq, b_sq, i;
44  int numw = see_num_attackers[WHITE], numb = see_num_attackers[BLACK];
45
46  /* rook-style moves: */
47  for (i = 0; i < 4; i++)
48    {
49      a_sq = square + rook_o[i];
50      b_sq = board[a_sq];
51
52      /* the king can attack from one square away: */
53      if (b_sq == wking)
54	{
55	  see_attackers[WHITE][numw].piece = b_sq;
56	  see_attackers[WHITE][numw].square = a_sq;
57	  numw++;
58	  break;
59	}
60      else if (b_sq == bking)
61	{
62	  see_attackers[BLACK][numb].piece = b_sq;
63	  see_attackers[BLACK][numb].square = a_sq;
64	  numb++;
65	  break;
66	}
67      else
68	{
69	  /* otherwise, check for sliding pieces: */
70	  while (b_sq != frame)
71	    {
72	      if (b_sq == wrook || b_sq == wqueen)
73		{
74		  see_attackers[WHITE][numw].piece = b_sq;
75		  see_attackers[WHITE][numw].square = a_sq;
76		  numw++;
77		  break;
78		}
79	      else if (b_sq == brook || b_sq == bqueen)
80		{
81		  see_attackers[BLACK][numb].piece = b_sq;
82		  see_attackers[BLACK][numb].square = a_sq;
83		  numb++;
84		  break;
85		}
86	      else if (b_sq != npiece) break;
87	      a_sq += rook_o [i];
88	      b_sq = board[a_sq];
89	    }
90	}
91    }
92
93  /* bishop-style moves: */
94  for (i = 0; i < 4; i++)
95    {
96      a_sq = square + bishop_o[i];
97      b_sq = board[a_sq];
98      /* check for pawn attacks: */
99      if (b_sq == wpawn && i%2)
100	{
101	  see_attackers[WHITE][numw].piece = b_sq;
102	  see_attackers[WHITE][numw].square = a_sq;
103	  numw++;
104	  break;
105	}
106      else if (b_sq == bpawn && !(i%2))
107	{
108	  see_attackers[BLACK][numb].piece = b_sq;
109	  see_attackers[BLACK][numb].square = a_sq;
110	  numb++;
111	  break;
112	}
113      /* the king can attack from one square away: */
114      else if (b_sq == wking)
115	{
116	  see_attackers[WHITE][numw].piece = b_sq;
117	  see_attackers[WHITE][numw].square = a_sq;
118	  numw++;
119	  break;
120	}
121      else if (b_sq == bking)
122	{
123	  see_attackers[BLACK][numb].piece = b_sq;
124	  see_attackers[BLACK][numb].square = a_sq;
125	  numb++;
126	  break;
127	}
128      else
129	{
130	  while (b_sq != frame) {
131	    if (b_sq == wbishop || b_sq == wqueen)
132	      {
133	        see_attackers[WHITE][numw].piece = b_sq;
134	        see_attackers[WHITE][numw].square = a_sq;
135		numw++;
136		break;
137	      }
138	    else if (b_sq == bbishop || b_sq == bqueen)
139	      {
140	        see_attackers[BLACK][numb].piece = b_sq;
141		see_attackers[BLACK][numb].square = a_sq;
142		numb++;
143		break;
144	      }
145	    else if (b_sq != npiece) break;
146	    a_sq += bishop_o [i];
147	    b_sq = board[a_sq];
148	  }
149	}
150    }
151
152  /* knight-style moves: */
153  for (i = 0; i < 8; i++)
154    {
155      a_sq = square + knight_o[i];
156      b_sq = board[a_sq];
157      if (b_sq == wknight)
158	{
159	  see_attackers[WHITE][numw].piece = b_sq;
160	  see_attackers[WHITE][numw].square = a_sq;
161	  numw++;
162	}
163      else if (b_sq == bknight)
164	{
165	  see_attackers[BLACK][numb].piece = b_sq;
166	  see_attackers[BLACK][numb].square = a_sq;
167	  numb++;
168	}
169    }
170
171  see_num_attackers[WHITE] = numw;
172  see_num_attackers[BLACK] = numb;
173}
174
175void findlowest(int color, int next)
176{
177  int lowestp;
178  int lowestv;
179  see_data swap;
180  int i;
181
182  lowestp = next;
183  lowestv = abs(material[see_attackers[color][next].piece]);
184
185  for (i = next; i < see_num_attackers[color]; i++)
186    {
187      if (abs(material[see_attackers[color][i].piece]) < lowestv)
188	{
189	  lowestp = i;
190	  lowestv = abs(material[see_attackers[color][i].piece]);
191	}
192    }
193
194  /* lowestp now points to the lowest attacker, which we swap with next */
195  swap = see_attackers[color][next];
196  see_attackers[color][next] = see_attackers[color][lowestp];
197  see_attackers[color][lowestp] = swap;
198}
199
200
201int see(int color, int square, int from)
202{
203  int sside;
204  int caps[2];
205  int value;
206  int origpiece;
207  int ourbestvalue;
208  int hisbestvalue;
209
210  /* reset data */
211  see_num_attackers[WHITE] = 0;
212  see_num_attackers[BLACK] = 0;
213
214  /* remove original capturer from board, exposing his first xray-er */
215  origpiece = board[from];
216  board[from] = npiece;
217
218  see_num_attackers[color]++;
219  see_attackers[color][0].piece = origpiece;
220  see_attackers[color][0].square = from;
221
222  /* calculate all attackers to square */
223  setup_attackers(square);
224
225  /* initially we gain the piece we are capturing */
226  value = abs(material[board[square]]);
227
228  /* free capture ? */
229  if (!see_num_attackers[!color])
230    {
231      board[from] = origpiece;
232      return value;
233    }
234  else
235    {
236      /* we can never get a higher SEE score than the piece we just captured */
237      /* so that is the current best value for our opponent */
238      /* we arent sure of anything yet, so -INF */
239      hisbestvalue = value;
240      ourbestvalue = -INF;
241    }
242
243  caps[color] = 1;
244  caps[!color] = 0;
245
246  /* start with recapture */
247  sside = !color;
248
249  /* continue as long as there are attackers */
250  while (caps[sside] < see_num_attackers[sside])
251    {
252      /* resort capturelist of sside to put lowest attacker in next position */
253      findlowest(sside, caps[sside]);
254
255      if (sside == color)
256	{
257	  /* capturing more */
258	  /* we capture the opponents recapturer */
259	  value += abs(material[see_attackers[!sside][caps[!sside]-1].piece]);
260
261	  /* if the opp ran out of attackers we can stand pat now! */
262	   if (see_num_attackers[!sside] <= caps[!sside] && value > ourbestvalue)
263	    ourbestvalue = value;
264
265	  /* our opponent can always stand pat now */
266	  if (value < hisbestvalue) hisbestvalue = value;
267	}
268      else
269	{
270	  /* recapture by opp */
271	  /* we lose whatever we captured with in last iteration */
272	  value -= abs(material[see_attackers[!sside][caps[!sside]-1].piece]);
273
274	  /* we can stand pat if we want to now */
275	  /* our best score goes up, opponent is unaffected */
276
277	  if (value > ourbestvalue)
278	    {
279	      ourbestvalue = value;
280	    }
281
282	  if (see_num_attackers[!sside] <= caps[!sside] && value < hisbestvalue)
283	    hisbestvalue = value;
284	}
285
286      /* keep track of capture count */
287      caps[sside]++;
288
289      /* switch sides */
290      sside ^= 1;
291
292    }
293
294  /* restore capturer */
295  board[from] = origpiece;
296
297  /* we return our best score now, keeping in mind that
298     it can never we better than the best for our opponent */
299  return (ourbestvalue > hisbestvalue) ? hisbestvalue : ourbestvalue;
300}
301