Author: Dieter Buerssner
Date: 05:44:59 02/11/06
Go up one level in this thread
I tried the chess problem yesterday night and failed. It took me almost 2 hours,
to write the program, but it was buggy. I needed another 1 1/2 hour just now,
and it seemed to work in 4 simple test cases I tried.
I could have been faster. No wonder, especially the move generator took time. I
started with the pawn moves. First I thought, I will just write code for all
cases especially: black to move, white to move, for each forward, capture left
and right, and of course for all moves check for promotion. I thought with copy
and paste, it should be rather fast, although many lines of code. When I tried
to compile, braces were not matching, and the code snippet was so long and in
parts wrong indented, that it was not easy to figure out. I did not want to use
indent (I guess it was not available in the test). At that moment, it was almost
clear, that the time would not be enough, if I don't get it correct immediately.
After having a clearer thought, I rewrote it more generally more or less with
only promotion needing specific coding.
Move generation for pieces was easier. It turned out, that it had a bug, but
that was easy to find when I printed the first move list. The sliding pieces did
move through opponent pieces. It also showed another bug in the input, which I
could spot in a second.
Another easy to fix bug: I intended upper case letters for white and white to
move. But I used lower case letters instead. (I did not see in the description
of the problem, which was intended in the contest)
Then it was also clear to me, that I did not handle stalemate correctly. Needed
some minutes to get this right. Fortunately it was found in my second test
position (which was also designed with the stalemate problem in mind).
.......k
.....P..
.......K
........
........
........
........
........
The program first thought h6g6 is mate.
The idea of the program was: do an almost normal 3 ply search. However last ply
is handled in the move generator, which will indicate when a king capture is
possible.
No idea if the program is correct now. I just googled for "mate in one", and
tried
type m1.txt
....R..B
...Bb...
r....q.p
....k...
..K.N..N
.....Pr.
...Q....
.b..R...
a < m1.txt
....R..B
...Bb...
r....q.p
....k...
..K.NP.N
......r.
...Q....
.b..R...
The program should also take slightly different input.
Summary: no way, I could have solved it during the contest. Perhaps I would have
been faster a couple of years ago, when I had more practice and better tools. My
editing skills got slower for programming languages, I also used an editor, that
I did not know too well. But even then, 2 hours would not be enough, and of
course one had no 2 hours in the contest.
Here it is, I wrote some times as comments inside. Note, no globals beside read
only data:
Regards,
Dieter
/* 20:02 */
#include <stdio.h>
#include <stdlib.h>
typedef struct position
{
int b[8][8];
int c[8][8];
} POSITION;
typedef struct move
{
int fc;
int fr;
int tc;
int tr;
int p;
} MOVE;
void read_pos(POSITION *p)
{
int r, c, pc;
for (r=7; r>=0; r--)
{
for (c=0; c<8; c++)
{
pc = getchar();
switch (pc)
{
/* Bug: colors inverted */
case 'p': p->c[r][c] = 1; p->b[r][c] = 1; break;
case 'n': p->c[r][c] = 1; p->b[r][c] = 2; break;
case 'b': p->c[r][c] = 1; p->b[r][c] = 3; break;
case 'r': p->c[r][c] = 1; p->b[r][c] = 4; break;
case 'q': p->c[r][c] = 1; p->b[r][c] = 5; break;
case 'k': p->c[r][c] = 1; p->b[r][c] = 6; break;
case 'P': p->c[r][c] = 0; p->b[r][c] = 1; break;
case 'N': p->c[r][c] = 0; p->b[r][c] = 2; break;
case 'B': p->c[r][c] = 0; p->b[r][c] = 3; break;
case 'R': p->c[r][c] = 0; p->b[r][c] = 4; break;
case 'Q': p->c[r][c] = 0; p->b[r][c] = 5; break;
case 'K': p->c[r][c] = 0; p->b[r][c] = 6; break;
default: p->c[r][c] = 2; p->b[r][c] = 0; break;
}
/* bug: had getchar() here */
}
getchar();
}
}
/* 20:13 */
struct move_dirs {
int ri;
int ci;
int slide;
};
struct move_dirs bd[] =
{{1,1,1}, {1,-1,1}, {-1,1,1}, {-1,-1,1}, {0,0,0}};
struct move_dirs rd[] =
{{1,0,1}, {0,1,1}, {-1,0,1}, {0,-1,1}, {0,0,0}};
struct move_dirs qd[] =
{{1,1,1}, {1,-1,1}, {-1,1,1}, {-1,-1,1},
{1,0,1}, {0,1,1}, {-1,0,1}, {0,-1,1}, {0,0,0}};
struct move_dirs kd[] =
{{1,1,0}, {1,-1,0}, {-1,1,0}, {-1,-1,0},
{1,0,0}, {0,1,0}, {-1,0,0}, {0,-1,0}, {0,0,0}};
struct move_dirs nd[] =
{{1,2,0}, {1,-2,0}, {-1,2,0}, {-1,-2,0},
{2,1,0}, {2,-1,0}, {-2,1,0}, {-2,-1,0}, {0,0,0}};
struct move_dirs *dirs[] = {0, 0, nd, bd, rd, qd, kd};
/* pass position by value to save some type strokes */
int generate_moves(POSITION p, MOVE m[], int s)
{
int r, c, nm =0, i, lr, lc, d, ci;
struct move_dirs *md;
for (r=0; r<8; r++)
{
for (c=0; c<8; c++)
{
if (p.c[r][c] == s)
{
if (p.b[r][c]==1)
{
d = (s==0? 1 : -1);
for (ci=-1; ci<=1; ci++)
if (c+ci>=0 && c+ci<=7 && p.c[r+d][c+ci] == (ci==0?2:(s^1)))
{
if (p.b[r+d][c+ci] == 6)
return -1;
if (r+d>0&&r+d<7)
{
m[nm].fc = c; m[nm].fr = r;
m[nm].tc = c+ci; m[nm].tr = r+d; m[nm].p = 0;
nm++;
}
else
for (i=2; i<=5; i++)
{
m[nm].fc = c; m[nm].fr = r;
m[nm].tc = c+ci; m[nm].tr = r+d; m[nm].p = i;
nm++;
}
}
}
else
{
md = dirs[p.b[r][c]];
for (i=0; md[i].ci !=0 || md[i].ri !=0 ; i++)
{
for (lc=c+md[i].ci, lr=r+md[i].ri;
lc >= 0 && lc <=7 && lr >=0 && lr <=7;
lc += md[i].ci, lr += md[i].ri)
{
if (p.b[lr][lc] == 0 || p.c[lr][lc] == (s^1))
{
m[nm].fc = c; m[nm].fr = r;
m[nm].tc = lc; m[nm].tr = lr; m[nm].p = 0;
if (p.b[lr][lc] == 6)
return -1;
nm++;
/* Bug: forgot next break */
if (p.c[lr][lc] == (s^1))
break;
}
else
break;
if (md[0].slide == 0)
break;
}
}
}
}
}
}
return nm;
}
void make_move(POSITION *p, MOVE m)
{
p->b[m.tr][m.tc]=m.p?m.p:p->b[m.fr][m.fc];
p->c[m.tr][m.tc]=p->c[m.fr][m.fc];
p->b[m.fr][m.fc]=0;
p->c[m.fr][m.fc]=2;
}
/* 21:20 */
int l[7][3] = {{'.', '.', '.'}, {'P', 'p', '.'}, {'N', 'n', '.'}, {'B', 'b',
'.'},
{'R', 'r', '.'}, {'Q', 'q', '.'}, {'K', 'k', '.'}};
void print_pos(POSITION *p)
{
int r, c;
for (r=7; r>=0; r--)
{
for (c=0; c<8; c++)
putchar(l[p->b[r][c]][p->c[r][c]]);
putchar('\n');
}
}
int search(POSITION *p, int stm, int d)
{
POSITION sp;
MOVE m[512];
int i, nm, s, b;
/* print_pos(p); */
nm = generate_moves(*p, m, stm);
/* for (i=0; i<30;i++)
printf("%c%d%c%d%d\n", m[i].fc+'a', m[i].fr+1, m[i].tc+'a', m[i].tr+1,
m[i].p);
printf("%d %d %d\n", nm, d, stm); */
if (d == 0)
return (nm >= 0 ? 0 : 1);
if (nm < 0)
return -1;
sp = *p;
b = -2;
for (i=0; i<nm; i++)
{
make_move(p, m[i]);
s = -search(p, stm^1, d-1);
b = s > b ? s : b;
*p=sp;
}
if (d == 1 && b == -1 && generate_moves(*p, m, stm^1) < 0) /* bug fixed:
stalemate */
{
print_pos(p);
exit(0);
}
return b;
}
/* 21:50 */
int main(void)
{
POSITION p;
read_pos(&p);
search(&p, 0, 2);
return 1;
}
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.