[unix-history] / usr / src / games / chess / move.c

/* move generator hes@log-sv.se 890318
   Modified: 890606 NEWMOVE Levels 1-6 for easier debugging */
#include "move.h"
#include "gnuchess.h"

short distdata[64][64];
short taxidata[64][64];

void Initialize_dist() {
register short a,b,d,di;

  /* init taxi and dist data */
  for(a=0;a<64;a++)
    for(b=0;b<64;b++) {
      d = abs(column[a]-column[b]);
      di = abs(row[a]-row[b]);
      taxidata[a][b] = d + di;
      distdata[a][b] = (d > di ? d : di);
    };
}

#if (NEWMOVE > 1)
struct sqdata posdata[3][8][64][64];

static short direc[8][8] = {
    0,  0,  0,  0,  0,  0,  0,  0, /* no_piece = 0 */
  -10,-11, -9,  0,  0,  0,  0,  0, /* wpawn    = 1 */
  -21,-19,-12, -8, 21, 19, 12,  8, /* knight   = 2 */
  -11, -9, 11,  9,  0,  0,  0,  0, /* bishop   = 3 */
  -10, -1, 10,  1,  0,  0,  0,  0, /* rook     = 4 */
  -11, -9,-10, -1, 11,  9, 10,  1, /* queen    = 5 */
  -11, -9,-10, -1, 11,  9, 10,  1, /* king     = 6 */
    0,  0,  0,  0,  0,  0,  0,  0};/* no_piece = 7 */

static short dc[3] = {-1,1,0};

static short max_steps [8] = {0,2,1,7,7,7,1,0};

static short unmap[120] = {
  -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  -1, 0, 1, 2, 3, 4, 5, 6, 7,-1,
  -1, 8, 9,10,11,12,13,14,15,-1,
  -1,16,17,18,19,20,21,22,23,-1,
  -1,24,25,26,27,28,29,30,31,-1,
  -1,32,33,34,35,36,37,38,39,-1,
  -1,40,41,42,43,44,45,46,47,-1,
  -1,48,49,50,51,52,53,54,55,-1,
  -1,56,57,58,59,60,61,62,63,-1,
  -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  -1,-1,-1,-1,-1,-1,-1,-1,-1,-1};

void Initialize_moves() {
  short c,ptyp,po,p0,d,di,s;
  struct sqdata *p;
  short dest[8][8];
  short steps[8];
  short sorted[8];

  /* init posdata */
  for(c=0;c<3;c++)
    for(ptyp=0;ptyp<8;ptyp++)
      for(po=0;po<64;po++)
	for(p0=0;p0<64;p0++) {
	  posdata[c][ptyp][po][p0].nextpos = po;
	  posdata[c][ptyp][po][p0].nextdir = po;
	};
  /* dest is a function of dir and step */
  for(c=0;c<2;c++)
    for(ptyp=1;ptyp<7;ptyp++)
      for(po=21;po<99;po++)
	if (unmap[po] >= 0) {
          p = posdata[c][ptyp][unmap[po]];
	  for(d=0;d<8;d++) {
	    dest[d][0] = unmap[po];
	    if (dc[c]*direc[ptyp][d] != 0) {
	      p0=po;
	      for(s=0;s<max_steps[ptyp];s++) {
		p0 = p0 + dc[c]*direc[ptyp][d];
		/* break if (off board) or
		   (pawns move two steps from home square) */
		if (unmap[p0] < 0 ||
		    (ptyp == pawn && s>0 && (d>0 || Stboard[unmap[po]] != ptyp)))
		  break;
		else
		  dest[d][s] = unmap[p0];
	      }
	    }
	    else s=0;
	    /* sort dest in number of steps order */
	    steps[d] = s;
	    for(di=d;di>0;di--)
	      if (steps[sorted[di-1]] < s)
		sorted[di] = sorted[di-1];
	      else
		break;
	    sorted[di] = d;
	  }
	  /* update posdata, pawns have two threads (capture and no capture) */
	  p0=unmap[po];
	  if (ptyp == pawn) {
	    for(s=0;s<steps[0];s++) {
	      p[p0].nextpos = dest[0][s];
	      p0 = dest[0][s];
	    }
	    p0=unmap[po];
	    for(d=1;d<3;d++) {
	      p[p0].nextdir = dest[d][0];
	      p0 = dest[d][0];
	    }
	  }
	  else {
	    p[p0].nextdir = dest[sorted[0]][0];
	    for(d=0;d<8;d++)
	      for(s=0;s<steps[sorted[d]];s++) {
		p[p0].nextpos = dest[sorted[d]][s];
		p0 = dest[sorted[d]][s];
		if (d < 7)
		  p[p0].nextdir = dest[sorted[d+1]][0];
		/* else is already initialised */
	      }
	  }
#ifdef DEBUG
	  printf("Ptyp:%d Position:%d\n{",ptyp,unmap[po]);
	  for(p0=0;p0<63;p0++) printf("%d,",p[p0].nextpos);
	  printf("%d};\n",p[63].nextpos);
	  for(p0=0;p0<63;p0++) printf("%d,",p[p0].nextdir);
	  printf("%d};\n",p[63].nextdir);
#endif DEBUG
	}
}
#endif


#if (NEWMOVE > 2)
int SqAtakd(sq,side)
short sq,side;

/*
  See if any piece with color 'side' ataks sq. First check pawns
  Then Queen, Bishop, Rook and King and last Knight.
*/

{
  register short u;
  register struct sqdata *p;

  p = posdata[1-side][pawn][sq];
  u = p[sq].nextdir; /* follow captures thread */
  while (u != sq) {
    if (board[u] == pawn && color[u] == side) return(true);
    u = p[u].nextdir;
  }
  /* king capture */
  if (distance(sq,PieceList[side][0]) == 1) return(true);
  /* try a queen bishop capture */
  p = posdata[side][bishop][sq];
  u = p[sq].nextpos;
  while (u != sq) {
    if (color[u] == neutral) {
      u = p[u].nextpos;
    }
    else {
      if (color[u] == side && 
	  (board[u] == queen || board[u] == bishop))
	return(true);
      u = p[u].nextdir;
    }
  }
  /* try a queen rook capture */
  p = posdata[side][rook][sq];
  u = p[sq].nextpos;
  while (u != sq) {
    if (color[u] == neutral) {
      u = p[u].nextpos;
    }
    else {
      if (color[u] == side && 
	  (board[u] == queen || board[u] == rook))
	return(true);
      u = p[u].nextdir;
    }
  }
  /* try a knight capture */
  p = posdata[side][knight][sq];
  u = p[sq].nextpos;
  while (u != sq) {
    if (color[u] == neutral) {
      u = p[u].nextpos;
    }
    else {
      if (color[u] == side && board[u] == knight) return(true);
      u = p[u].nextdir;
    }
  }
  return(false);
}
#endif

#if (NEWMOVE > 3)
BRscan(sq,s,mob)
short sq,*s,*mob;
/*
   Find Bishop and Rook mobility, XRAY attacks, and pins. Increment the 
   hung[] array if a pin is found. 
*/
{
  register short u,piece,pin;
  register struct sqdata *p;
  short *Kf;

  Kf = Kfield[c1];
  *mob = 0;
  piece = board[sq];
  p = posdata[color[sq]][piece][sq];
  u = p[sq].nextpos;
  pin = -1; /* start new direction */
  while (u != sq) {
    *s += Kf[u];
    if (color[u] == neutral) {
      (*mob)++;
      if (p[u].nextpos == p[u].nextdir) pin = -1; /* oops new direction */
      u = p[u].nextpos;
    }
    else if (pin < 0) {
      if (board[u] == pawn || board[u] == king)
	u = p[u].nextdir;
      else {
	if (p[u].nextpos != p[u].nextdir)
	  pin = u; /* not on the edge and on to find a pin */
	u = p[u].nextpos;
      }
    }
    else if (color[u] == c2 && (board[u] > piece || atk2[u] == 0))
      {
	if (color[pin] == c2)
	  {
	    *s += PINVAL;
	    if (atk2[pin] == 0 ||
		atk1[pin] > control[board[pin]]+1)
	      ++hung[c2];
	  }
	else *s += XRAY;
	pin = -1; /* new direction */
	u = p[u].nextdir;
      }
    else {
      pin = -1; /* new direction */
      u = p[u].nextdir;
    }
  }
}
#endif

#if (NEWMOVE >= 5)
CaptureList(side,xside,ply)
short side,xside,ply;
{
  register short u,sq;
  register struct sqdata *p;
  short i,piece,*PL;
  struct leaf *node;
  
  TrPnt[ply+1] = TrPnt[ply];
  node = &Tree[TrPnt[ply]];
  PL = PieceList[side];
  for (i = 0; i <= PieceCnt[side]; i++)
    {
      sq = PL[i];
      piece = board[sq];
      p = posdata[side][piece][sq];
      if (piece == pawn) {
	u = p[sq].nextdir; /* follow captures thread */
	while (u != sq) {
	  if (color[u] == xside) {
            node->f = sq; node->t = u;
            node->flags = capture;
            if (u < 8 || u > 55)
              {
                node->flags |= promote;
                node->score = valueQ;
              }
	    else
              node->score = value[board[u]] + svalue[board[u]] - piece;
            ++node;
            ++TrPnt[ply+1];
           }
	  u = p[u].nextdir;
	}
      }
      else {
	u = p[sq].nextpos;
	while (u != sq) {
          if (color[u] == neutral)
          u = p[u].nextpos;
          else {
          if (color[u] == xside) {
              node->f = sq; node->t = u;
              node->flags = capture;
              node->score = value[board[u]] + svalue[board[u]] - piece;
              ++node;
              ++TrPnt[ply+1];
             }
	   u = p[u].nextdir;
	 }
       }
     }
   }
}
#endif

#if (NEWMOVE > 5)
GenMoves(ply,sq,side,xside)
     short ply,sq,side,xside;
 
/*
  Generate moves for a piece. The moves are taken from the
  precalulated array posdata. If the board is free, next move
  is choosen from nextpos else from nextdir.
*/
 
{
  register short u,piece;
  register struct sqdata *p;
	 
  piece = board[sq];
  p = posdata[side][piece][sq];
  if (piece == pawn) {
    u = p[sq].nextdir; /* follow captures thread */
    while (u != sq) {
      if (color[u] == xside) LinkMove(ply,sq,u,xside);
      u = p[u].nextdir;
    }
    u = p[sq].nextpos; /* and follow no captures thread */
    while (u != sq) {
      if (color[u] == neutral && (u != sq+16 || color[u-8] == neutral)
          && (u != sq-16 || color[u+8] == neutral)) {
        LinkMove(ply,sq,u,xside);
      }
      u = p[u].nextpos;
    }
  }  
  else {
    u = p[sq].nextpos;
    while (u != sq) {
      if (color[u] == neutral) {
        LinkMove(ply,sq,u,xside);
        u = p[u].nextpos;
      }
      else {
        if (color[u] == xside) LinkMove(ply,sq,u,xside);
	u = p[u].nextdir;
      }
    }
  }    
} 
#endif
Commit	Line	Data
45f5ec6a KB	1	/* move generator hes@log-sv.se 890318
	2	Modified: 890606 NEWMOVE Levels 1-6 for easier debugging */
	3	#include "move.h"
	4	#include "gnuchess.h"
	5
	6	short distdata[64][64];
	7	short taxidata[64][64];
	8
	9	void Initialize_dist() {
	10	register short a,b,d,di;
	11
	12	/* init taxi and dist data */
	13	for(a=0;a<64;a++)
	14	for(b=0;b<64;b++) {
	15	d = abs(column[a]-column[b]);
	16	di = abs(row[a]-row[b]);
	17	taxidata[a][b] = d + di;
	18	distdata[a][b] = (d > di ? d : di);
	19	};
	20	}
	21
	22	#if (NEWMOVE > 1)
	23	struct sqdata posdata[3][8][64][64];
	24
	25	static short direc[8][8] = {
	26	0, 0, 0, 0, 0, 0, 0, 0, /* no_piece = 0 */
	27	-10,-11, -9, 0, 0, 0, 0, 0, /* wpawn = 1 */
	28	-21,-19,-12, -8, 21, 19, 12, 8, /* knight = 2 */
	29	-11, -9, 11, 9, 0, 0, 0, 0, /* bishop = 3 */
	30	-10, -1, 10, 1, 0, 0, 0, 0, /* rook = 4 */
	31	-11, -9,-10, -1, 11, 9, 10, 1, /* queen = 5 */
	32	-11, -9,-10, -1, 11, 9, 10, 1, /* king = 6 */
	33	0, 0, 0, 0, 0, 0, 0, 0};/* no_piece = 7 */
	34
	35	static short dc[3] = {-1,1,0};
	36
	37	static short max_steps [8] = {0,2,1,7,7,7,1,0};
	38
	39	static short unmap[120] = {
	40	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	41	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	42	-1, 0, 1, 2, 3, 4, 5, 6, 7,-1,
	43	-1, 8, 9,10,11,12,13,14,15,-1,
	44	-1,16,17,18,19,20,21,22,23,-1,
	45	-1,24,25,26,27,28,29,30,31,-1,
	46	-1,32,33,34,35,36,37,38,39,-1,
	47	-1,40,41,42,43,44,45,46,47,-1,
	48	-1,48,49,50,51,52,53,54,55,-1,
	49	-1,56,57,58,59,60,61,62,63,-1,
	50	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
	51	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
	52
	53	void Initialize_moves() {
	54	short c,ptyp,po,p0,d,di,s;
	55	struct sqdata *p;
	56	short dest[8][8];
	57	short steps[8];
	58	short sorted[8];
	59
	60	/* init posdata */
	61	for(c=0;c<3;c++)
	62	for(ptyp=0;ptyp<8;ptyp++)
	63	for(po=0;po<64;po++)
	64	for(p0=0;p0<64;p0++) {
65	posdata[c][ptyp][po][p0].nextpos = po;
66	posdata[c][ptyp][po][p0].nextdir = po;
67	};
68	/* dest is a function of dir and step */
69	for(c=0;c<2;c++)
70	for(ptyp=1;ptyp<7;ptyp++)
71	for(po=21;po<99;po++)
72	if (unmap[po] >= 0) {
73	p = posdata[c][ptyp][unmap[po]];
74	for(d=0;d<8;d++) {
75	dest[d][0] = unmap[po];
76	if (dc[c]*direc[ptyp][d] != 0) {
77	p0=po;
78	for(s=0;s<max_steps[ptyp];s++) {
79	p0 = p0 + dc[c]*direc[ptyp][d];
80	/* break if (off board) or
81	(pawns move two steps from home square) */
82	if (unmap[p0] < 0 \|\|
83	(ptyp == pawn && s>0 && (d>0 \|\| Stboard[unmap[po]] != ptyp)))
84	break;
85	else
86	dest[d][s] = unmap[p0];
87	}
88	}
89	else s=0;
90	/* sort dest in number of steps order */
91	steps[d] = s;
92	for(di=d;di>0;di--)
93	if (steps[sorted[di-1]] < s)
94	sorted[di] = sorted[di-1];
95	else
96	break;
97	sorted[di] = d;
98	}
99	/* update posdata, pawns have two threads (capture and no capture) */
100	p0=unmap[po];
101	if (ptyp == pawn) {
102	for(s=0;s<steps[0];s++) {
103	p[p0].nextpos = dest[0][s];
104	p0 = dest[0][s];
105	}
106	p0=unmap[po];
107	for(d=1;d<3;d++) {
108	p[p0].nextdir = dest[d][0];
109	p0 = dest[d][0];
110	}
111	}
112	else {
113	p[p0].nextdir = dest[sorted[0]][0];
114	for(d=0;d<8;d++)
115	for(s=0;s<steps[sorted[d]];s++) {
116	p[p0].nextpos = dest[sorted[d]][s];
117	p0 = dest[sorted[d]][s];
118	if (d < 7)
119	p[p0].nextdir = dest[sorted[d+1]][0];
120	/* else is already initialised */
121	}
122	}
123	#ifdef DEBUG
124	printf("Ptyp:%d Position:%d\n{",ptyp,unmap[po]);
125	for(p0=0;p0<63;p0++) printf("%d,",p[p0].nextpos);
126	printf("%d};\n",p[63].nextpos);
127	for(p0=0;p0<63;p0++) printf("%d,",p[p0].nextdir);
128	printf("%d};\n",p[63].nextdir);
129	#endif DEBUG
130	}
131	}
132	#endif
133
134
135	#if (NEWMOVE > 2)
136	int SqAtakd(sq,side)
137	short sq,side;
138
139	/*
140	See if any piece with color 'side' ataks sq. First check pawns
141	Then Queen, Bishop, Rook and King and last Knight.
142	*/
143
144	{
145	register short u;
146	register struct sqdata *p;
147
148	p = posdata[1-side][pawn][sq];
149	u = p[sq].nextdir; /* follow captures thread */
150	while (u != sq) {
151	if (board[u] == pawn && color[u] == side) return(true);
152	u = p[u].nextdir;
153	}
154	/* king capture */
155	if (distance(sq,PieceList[side][0]) == 1) return(true);
156	/* try a queen bishop capture */
157	p = posdata[side][bishop][sq];
158	u = p[sq].nextpos;
159	while (u != sq) {
160	if (color[u] == neutral) {
161	u = p[u].nextpos;
162	}
163	else {
164	if (color[u] == side &&
165	(board[u] == queen \|\| board[u] == bishop))
166	return(true);
167	u = p[u].nextdir;
168	}
169	}
170	/* try a queen rook capture */
171	p = posdata[side][rook][sq];
172	u = p[sq].nextpos;
173	while (u != sq) {
174	if (color[u] == neutral) {
175	u = p[u].nextpos;
176	}
177	else {
178	if (color[u] == side &&
179	(board[u] == queen \|\| board[u] == rook))
180	return(true);
181	u = p[u].nextdir;
182	}
183	}
184	/* try a knight capture */
185	p = posdata[side][knight][sq];
186	u = p[sq].nextpos;
187	while (u != sq) {
188	if (color[u] == neutral) {
189	u = p[u].nextpos;
190	}
191	else {
192	if (color[u] == side && board[u] == knight) return(true);
193	u = p[u].nextdir;
194	}
195	}
196	return(false);
197	}
198	#endif
199
200	#if (NEWMOVE > 3)
201	BRscan(sq,s,mob)
202	short sq,s,mob;
203	/*
204	Find Bishop and Rook mobility, XRAY attacks, and pins. Increment the
205	hung[] array if a pin is found.
206	*/
207	{
208	register short u,piece,pin;
209	register struct sqdata *p;
210	short *Kf;
211
212	Kf = Kfield[c1];
213	*mob = 0;
214	piece = board[sq];
215	p = posdata[color[sq]][piece][sq];
216	u = p[sq].nextpos;
217	pin = -1; /* start new direction */
218	while (u != sq) {
219	*s += Kf[u];
220	if (color[u] == neutral) {
221	(*mob)++;
222	if (p[u].nextpos == p[u].nextdir) pin = -1; /* oops new direction */
223	u = p[u].nextpos;
224	}
225	else if (pin < 0) {
226	if (board[u] == pawn \|\| board[u] == king)
227	u = p[u].nextdir;
228	else {
229	if (p[u].nextpos != p[u].nextdir)
230	pin = u; /* not on the edge and on to find a pin */
231	u = p[u].nextpos;
232	}
233	}
234	else if (color[u] == c2 && (board[u] > piece \|\| atk2[u] == 0))
235	{
236	if (color[pin] == c2)
237	{
238	*s += PINVAL;
239	if (atk2[pin] == 0 \|\|
240	atk1[pin] > control[board[pin]]+1)
241	++hung[c2];
242	}
243	else *s += XRAY;
244	pin = -1; /* new direction */
245	u = p[u].nextdir;
246	}
247	else {
248	pin = -1; /* new direction */
249	u = p[u].nextdir;
250	}
251	}
252	}
253	#endif
254
255	#if (NEWMOVE >= 5)
256	CaptureList(side,xside,ply)
257	short side,xside,ply;
258	{
259	register short u,sq;
260	register struct sqdata *p;
261	short i,piece,*PL;
262	struct leaf *node;
263
264	TrPnt[ply+1] = TrPnt[ply];
265	node = &Tree[TrPnt[ply]];
266	PL = PieceList[side];
267	for (i = 0; i <= PieceCnt[side]; i++)
268	{
269	sq = PL[i];
270	piece = board[sq];
271	p = posdata[side][piece][sq];
272	if (piece == pawn) {
273	u = p[sq].nextdir; /* follow captures thread */
274	while (u != sq) {
275	if (color[u] == xside) {
276	node->f = sq; node->t = u;
277	node->flags = capture;
278	if (u < 8 \|\| u > 55)
279	{
280	node->flags \|= promote;
281	node->score = valueQ;
282	}
283	else
284	node->score = value[board[u]] + svalue[board[u]] - piece;
285	++node;
286	++TrPnt[ply+1];
287	}
288	u = p[u].nextdir;
289	}
290	}
291	else {
292	u = p[sq].nextpos;
293	while (u != sq) {
294	if (color[u] == neutral)
295	u = p[u].nextpos;
296	else {
297	if (color[u] == xside) {
298	node->f = sq; node->t = u;
299	node->flags = capture;
300	node->score = value[board[u]] + svalue[board[u]] - piece;
301	++node;
302	++TrPnt[ply+1];
303	}
304	u = p[u].nextdir;
305	}
306	}
307	}
308	}
309	}
310	#endif
311
312	#if (NEWMOVE > 5)
313	GenMoves(ply,sq,side,xside)
314	short ply,sq,side,xside;
fa9be3df	315
45f5ec6a KB	316	/*
	317	Generate moves for a piece. The moves are taken from the
	318	precalulated array posdata. If the board is free, next move
	319	is choosen from nextpos else from nextdir.
	320	*/
fa9be3df	321
45f5ec6a KB	322	{
	323	register short u,piece;
	324	register struct sqdata *p;
fa9be3df	325
45f5ec6a KB	326	piece = board[sq];
	327	p = posdata[side][piece][sq];
	328	if (piece == pawn) {
	329	u = p[sq].nextdir; /* follow captures thread */
	330	while (u != sq) {
	331	if (color[u] == xside) LinkMove(ply,sq,u,xside);
	332	u = p[u].nextdir;
	333	}
	334	u = p[sq].nextpos; /* and follow no captures thread */
	335	while (u != sq) {
fa9be3df KB	336	if (color[u] == neutral && (u != sq+16 \|\| color[u-8] == neutral)
	337	&& (u != sq-16 \|\| color[u+8] == neutral)) {
	338	LinkMove(ply,sq,u,xside);
	339	}
45f5ec6a KB	340	u = p[u].nextpos;
45f5ec6a KB	341	}
fa9be3df	342	}
45f5ec6a KB	343	else {
	344	u = p[sq].nextpos;
	345	while (u != sq) {
	346	if (color[u] == neutral) {
fa9be3df KB	347	LinkMove(ply,sq,u,xside);
fa9be3df KB	348	u = p[u].nextpos;
45f5ec6a KB	349	}
45f5ec6a KB	350	else {
fa9be3df	351	if (color[u] == xside) LinkMove(ply,sq,u,xside);
45f5ec6a KB	352	u = p[u].nextdir;
	353	}
	354	}
fa9be3df KB	355	}
fa9be3df KB	356	}
45f5ec6a	357	#endif