Help Needed for Chess Programming

[Dann Corbit]

TSCP is OK to see the basic idea of how to write a chess program.

But it will be a big handicap in the future if it is used as a fundamental design.

Especially if you want an SMP version eventually, TSCP will cause problems if used as a base.

Look at Scorpio to understand basic chess designs. The source is about 188K, which is 3x bigger than TSCP, but I don't think that is a serious handicap.

If you want to write a bitboard program, I would look at Olithink for the most compact expression (if you already understand bit twiddling) and Beowulf for more details (if you need a more expansive explanation).

[Eduardo Waghabi]

There is a mistake here.
TSCP does not use bitboards.

Sorry to disagree Uri, but the source version I have in my machine is a bitboard one. Not rotated bitboards, but bitboard nonetheless.

Code: Select all

/*
 *   BOARD.C
 *   Tom Kerrigan's Simple Chess Program (TSCP)
 *
 *   Copyright 1997 Tom Kerrigan
 */

/*
 *  Simple Bitboard move generator by Michael Sherwin
 */

Code: Select all

        case BISHOP:
          first = first_one(ray_plus_7[fs] & occupied);
          moves = ray_plus_7[fs] & below[first];
          captures = set_mask[first];
          first = first_one(ray_plus_9[fs] & occupied);
          moves |= ray_plus_9[fs] & below[first];
          captures |= set_mask[first];
          first = last_one(ray_minus_7[fs] & occupied);


[Anonymous]

My engine Ayito has the same features as well. Below you can find an automated perft test that I run every now and then just in case. If you can get these figures, chances of having a bug in move generation and/or make and unmake are indeed low.

do{
if (!SinglePeftTest(c++, 4, 1066400,"r1b4r/p2p1ppp/1ppbn2k/4P2P/1PB5/2P2PP1/P7/RNKQ3R w - -")) break;
if (!SinglePeftTest(c++, 4, 1233636,"1q5k/8/1p2n3/p1p1rb2/2Pp3n/PP1P2P1/3B1R2/2R2QK1 b - -")) break;
if (!SinglePeftTest(c++, 4, 1240989,"r3kb1r/pp1bpppp/8/5n2/4n3/4B3/PPP2PPP/RN1K1B1R w kq -")) break;
if (!SinglePeftTest(c++, 5, 1745545,"8/PPP4k/8/8/8/8/4Kppp/8 w - - ")) break;
if (!SinglePeftTest(c++, 4, 1797968,"r3r2k/pp2qp1p/5pb1/8/4P2Q/3PBP2/PP4P1/R2K3R b - -")) break;
if (!SinglePeftTest(c++, 4, 4085603, "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -")) break;
if (!SinglePeftTest(c++, 4, 4466732, "r3k2r/1P1p2P1/1q6/4P3/4p3/6Q1/1p1P2p1/R3K2R w KQkq - 0 1 ")) break;
if (!SinglePeftTest(c++, 6, 11030083,"8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -")) break;
if (!SinglePeftTest(c++, 5, 11677860, "R6R/8/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1 w - - ")) break;
if (!SinglePeftTest(c++, 5, 29014483, "4r1k1/p1p3pp/1bp3r1/5p2/1P6/2PQ1P1b/R2P1P1P/2B2R1K w - -")) break;
if (!SinglePeftTest(c++, 6, 55577643, "3rr1n1/2qb2p1/2p1pk1p/1p3P2/3P1R1Q/1pP5/P5PP/4R1K1 b - -")) break;
if (!SinglePeftTest(c++, 5, 126222830, "1r4r1/1ppn2pk/p1npq2p/4Pp2/P4p1Q/2PBB2R/1PP1KP1P/6R1 w - f6")) break;

end=1;
}while (false);

Regards,

What actually is this code doing? Can anybody explain?

Is it possible that I can write a program without using perft?

And is there any other method so that I can setup my board structure without using 0x88 and bitboards?

Please help.

[Alessandro Scotti]

Is it possible that I can write a program without using perft?

And is there any other method so that I can setup my board structure without using 0x88 and bitboards?

Hello Abhay,
you don't need perft for the moment, it is used to test the move generator and eventually you can come back to it later.
For board representation, you can use a simple 8x8 array, no need at all for 0x88 and bitboards.

[Anonymous]

There is a mistake here.
TSCP does not use bitboards.

I do not recommend tscp but for different reasons.
It has a lot of global variables and I think that it is not the best way for starting a chess program.

Uri

I do agree TSCP isn't that great but what else is there for the new programmer?

In view of so many arguments and counter-arguments, is it a good idea if I still refer TSCP for my programming basics. And please tell what actually does TSCP use: 0x88 or bitboards?

Can you suggest any other engine besides TSCP that uses 0x88 board structure? Are their other ways also besides these two?

What would be more appropriate for a novice like me?

[Anonymous]

Look at Scorpio to understand basic chess designs. The source is about 188K, which is 3x bigger than TSCP, but I don't think that is a serious handicap.

Where can I get the 'source code + engine' for the programs you recommened?

And what interface should I use for the testing purposes?

[Alvaro Begue]

I would start with a one-dimensional array of size 16x12, where the real 8x8 board is centered. This takes care of dealing with the ends of the board very easily, allows for fast column and row separation (because 16 is an easy number to deal with in binary) and also has the nice property of 0x88, which is that the difference between two locations on the board faithfully represents their relationship. This allows for fast attack detection (any article on 0x88 will tell you how).

You should also keep a list of pieces. Let's assume you represent your pieces as wp=0, wn=1, wb=2, wr=3, wq=4, wk=5, bp=6, bn=7, bb=8, br=9, bq=10, bk=11 (you could use 12 for empty and 13 for out-of-the-board). You can keep the current location of all your pieces in 12 lists, like this:
int location[12][16]; // 16 here could be 10, but multiplying by 16 is faster
int num_of_type[12];

So when you want to generate moves, you just loop over piece types and for each type you loop over the piece locations.

I think this is one of the most clear board descriptions, and it's fast enough.

[Dann Corbit]

Look at Scorpio to understand basic chess designs. The source is about 188K, which is 3x bigger than TSCP, but I don't think that is a serious handicap.

Where can I get the 'source code + engine' for the programs you recommened?

http://wbec-ridderkerk.nl/

Click on "Engine Info"

And what interface should I use for the testing purposes?

Winboard and Arean spring to mind.

http://www.tim-mann.org/chess.html

http://www.playwitharena.com/

Jose and SCID are also nice (see Sourceforge)

[H.G.Muller]

If you don't mind obfuscated C-code the following might be a nice example of a chess program. I wrote it to see if I could write a chess program in under 1Kbyte of source code, triggered by a discussion if high-level languages have higher information density than binary executables. I know of a chess program for the KIM-1 6502-based single-board computer, that ran in 1.25KB of RAM, and my own first chess code for 6800 ran in 2KB, hence the 1KB target.

Code: Select all

#define F(I,S,N) for(I=S;I<N;I++)
#define W(A) while(A)
#define C(A) if(A)continue;
#define B(A) if(A)break;

int V=112,M=136,I=4000,C=799,X,Y,i,Q,N,
w[]={0,1,1,3,-1,3,5,9},
o[]={6,3,5,7,4,5,3,6},
g[]={0,3,-1,21,7,11,16,7},
d[]={16,15,17,0,-16,-15,-17,0,1,-1,16,-16,15,-15,17,-17,0,1,-1,16,-16,0,
14,-14,18,-18,31,-31,33,-33,0},
b[128];

char n[]=".?+pkltd?*?PKLTD";

P()
{F(i,0,121)
  printf(" %c",i&8&&(i+=7)?10:n[b[i]&15]);
}

D(k,q,l,e,x,n)
int k,q,l,e,x,n;
{
 int i,j,t,p,u,r,y,m=n>1|q>e?q:e,v,h,z;

 N++;
 F(i,0,120)
 {i=i+8&~8;
  u=b[i];C(!(u&k))
  j=g[p=u&7];
  W(r=d[++j])
  {y=i;
   do
   {y+=r;B(y&M)
    t=b[y];B(t&k)
    B(j<7&&!(r&7)!=!t)
    v=99*w[t&7];
    if(v<0)m=I;
    if(m>=l)return m;
   
    if(h=n-(y!=x))
    {if(p<6)v+=b[i+8]-b[y+8];
     if(p==4)v+=9*(e>C?!((x^y)&68):-3);

     b[i]=0;b[y]=u;
     if(p<3)
     {v-=9*(((i-2)&M||b[i-2]!=u)+((i+2)&M||b[i+2]!=u)-1);
      if(y+r+1&128){b[y]|=7;v+=C;}
     }
     z=-e-v;
     v=-D(24-k,-l,-m,z,y,h);
     if(v>1500)v-=50;
     if(x==9){if(v!=-I&i==X&y==Y){Q=z;return l;}v=m;}
     b[i]=u;b[y]=t;

     if(v>m){m=v;if(x&8){X=i;Y=y;}}
    }
    t+=p<5;if(j<7&&6*k+(y&V)==128)t--;
   }W(!t);
  }
 }
 return m+I?m:-D(24-k,-I,I,0,x,1)/2;
}

main()
{
 int i,j,k=8,*p,c[9],d;

 F(i,0,8)
 {b[i]=(b[i+V]=o[i]+8)+8;b[i+16]=18;b[i+96]=9;
  F(j,0,8)b[16*j+i+8]=(i-4)*(i-4)+(j-3.5)*(j-3.5);
 }

 W(1)
 {P();p=c;W((*p++=getchar())>10);
  if(*c-10){X=c[0]-16*c[1]+C;Y=c[2]-16*c[3]+C;}else
  {d=6;N=0;W(N<4e6)D(k,-I,I,Q,8,d++);}
  if(D(k,-I,I,Q,9,2)==I)k^=24;
 }
}


As you can see, I failed: even if I sacrificed castling and e.p. capture, I could not get it under 1200 bytes (not counting the leading blank space that I inserted for readability, but which this forum sadly deletes...). This version is 1305 characters (80 lines) because I equiped it with move-legality checking on the input move, and wanted it to be able to find the mate when ahead in a KQK end-game.

Since 1KB does not seem feasible, I shfted my target to writing a somewhat less minimalistic code in under 2KB of non-blank source, that does include many features that the program above lacks, but would greatly improve its playing strength, such as iterative deepening, some move sorting, transposition tables, null move and of course full FIDE rules. In the current version there is little more than a totally bare depth-first minimax search not counting recaptures in its ply-depth (so that it automatically does a primitive quiescence search). Nevertheless, it should be able to beat 90% of all humans (if not 99%).

[Uri Blass]

Your program does not work for me

I get warning and some errors

warning C4508: 'P' : function should return a value; 'void' return type assumed
: error C2065: 'k' : undeclared identifier

Note that the following order is wrong and you first need to define variables and later to use them(not the opposite)
D(k,q,l,e,x,n)
int k,q,l,e,x,n;

If you want to define a function or integer D then you need

D(int k,intq,int l,int x,int n)

Note also that main by definition needs to return a value.

after some corrections I still get some warning but I get some code
that let me to play game against myself or play against it when I need to press enter to tell it to move but it does not let me to play enpassent capture or castle so it does not support playing chess and by definition cannot beat most players because it is not going to accept castling moves by them.

Here is the corrected code

Code: Select all

#include "stdio.h"
#define F(I,S,N) for(I=S;I<N;I++)
#define W(A) while(A)
#define C(A) if(A)continue;
#define B(A) if(A)break;

int V=112,M=136,I=4000,C=799,X,Y,i,Q,N,
w[]={0,1,1,3,-1,3,5,9},
o[]={6,3,5,7,4,5,3,6},
g[]={0,3,-1,21,7,11,16,7},
d[]={16,15,17,0,-16,-15,-17,0,1,-1,16,-16,15,-15,17,-17,0,1,-1,16,-16,0,
14,-14,18,-18,31,-31,33,-33,0},
b[128];

char n[]=".?+pkltd?*?PKLTD";

void P()
{F(i,0,121)
printf(" %c",i&8&&(i+=7)?10:n[b[i]&15]);
}

D(int k,int q,int l,int e,int x,int n)
//int k,q,l,e,x,n;
{
int i,j,t,p,u,r,y,m=n>1|q>e?q:e,v,h,z;

N++;
F(i,0,120)
{i=i+8&~8;
u=b[i];C(!(u&k))
j=g[p=u&7];
W(r=d[++j])
{y=i;
do
{y+=r;B(y&M)
t=b[y];B(t&k)
B(j<7&&!(r&7)!=!t)
v=99*w[t&7];
if(v<0)m=I;
if(m>=l)return m;

if(h=n-(y!=x))
{if(p<6)v+=b[i+8]-b[y+8];
if(p==4)v+=9*(e>C?!((x^y)&68):-3);

b[i]=0;b[y]=u;
if(p<3)
{v-=9*(((i-2)&M||b[i-2]!=u)+((i+2)&M||b[i+2]!=u)-1);
if(y+r+1&128){b[y]|=7;v+=C;}
}
z=-e-v;
v=-D(24-k,-l,-m,z,y,h);
if(v>1500)v-=50;
if(x==9){if(v!=-I&i==X&y==Y){Q=z;return l;}v=m;}
b[i]=u;b[y]=t;

if(v>m){m=v;if(x&8){X=i;Y=y;}}
}
t+=p<5;if(j<7&&6*k+(y&V)==128)t--;
}W(!t);
}
}
return m+I?m:-D(24-k,-I,I,0,x,1)/2;
}

int main()
{
int i,j,k=8,*p,c[9],d;

F(i,0,8)
{b[i]=(b[i+V]=o[i]+8)+8;b[i+16]=18;b[i+96]=9;
F(j,0,8)b[16*j+i+8]=(i-4)*(i-4)+(j-3.5)*(j-3.5);
}

W(1)
{P();p=c;W((*p++=getchar())>10);
if(*c-10){X=c[0]-16*c[1]+C;Y=c[2]-16*c[3]+C;}else
{d=6;N=0;W(N<4e6)D(k,-I,I,Q,8,d++);}
if(D(k,-I,I,Q,9,2)==I)k^=24;
}
return 0;
}

[Uri Blass]

beated it easily in the game with no castling and no enpassent.

The only reason that it may beat most of the humans is that most of the humans are not chess players.

[Event "Edited game"]
[Site "URI-AMD"]
[Date "2005.11.23"]
[Round "-"]
[White "-"]
[Black "-"]
[Result "0-1"]

1. c4 e5 2. d4 exd4 3. Qxd4 Nc6 4. Qe3+ Be7 5. Nd2 d6 6. g3 Bf5 7. Bg2 Nb4
8. Be4 Nc2+ 9. Bxc2 Bxc2 10. Qf3 c6 11. h4 d5 12. Qc3 Bf5 13. cxd5 Qxd5 14.
Ngf3 Nf6 15. Nc4 Ne4 16. Qb3 Rd8 17. Be3 Nc5 18. Qc3 Bf6 19. Nce5 Nd7 20.
Bd4 c5 21. Nxd7 Bxd4 22. Qa3 Rxd7 23. Qxa7 Ke7 24. Rc1 Be4 25. Qa3 Bxf3 26.
Qxf3 Bxb2 27. Qxd5 Rxd5 28. Rc4 Ra8 29. a4 b5 30. Re4+ Kd6 31. e3 Rxa4 32.
Rxa4 bxa4 33. e4 Rd4 34. f3 a3 35. f4 Rxe4+ 36. Kf2 a2 37. Kf3 Rc4 38. Rd1+
Kc6 39. h5 Rc1 40. Rd2 a1=Q 41. Rd8 Qa3+ 42. Kg4 Rg1 43. Rc8+ Kd7 44. Rd8+
Kxd8 45. Kf5 Qd3+ 46. Kg4 Rxg3+ 47. Kh4 Bf6#
{Black mates} 0-1

[Alessandro Scotti]

Note that the following order is wrong and you first need to define variables and later to use them(not the opposite)
D(k,q,l,e,x,n)
int k,q,l,e,x,n;

This is actually the original C syntax, which was later changed by (C++ and) ANSI.

[Anonymous]

after some corrections I still get some warning but I get some code
that let me to play game against myself or play against it when I need to press enter to tell it to move but it does not let me to play enpassent capture or castle so it does not support playing chess and by definition cannot beat most players because it is not going to accept castling moves by them.

Is providing the features of enpassent and castling that much difficult? I guess that's why it's not supported in the original code.

Will somebody tell me?

[Reinhard Scharnagl]

Is providing the features of enpassent and castling that much difficult? I guess that's why it's not supported in the original code.

Will somebody tell me?

Special moves have a special way to be executed. It could be done e.g.:

a) en passant: recognizing an e.p. capture, removing the just moved pawn by one step, then executing a regular pawn capture.
preparation: providing an optionally e.p. enabling flag within every ply. Restauring that flag after undoing moves.

b) castling (including Chess960): identifying the correct to be moved rook, moving that rook outside to a secure place, then moving the king to its target square, finally placing the rook on to the next inner square.
preparation: always keeping castling flags updated, restauring that flag after undoing moves, testing the rook not to start or move over or to check threatened squares (source and destination included), checking all squares between king and rook and their target squares (included) to be free from third pieces. Maybe also enable general handling of Chess960 positions and X-FEN strings.

c) underpromotion: changing the piece after the move into another one.
preparation: having a move representation, which encodes also the selected new piece type.

If using a cache, the e.p. and castling flags also have to be registered inside the associated representing hash key.

Reinhard.

[H.G.Muller]

after some corrections I still get some warning but I get some code
that let me to play game against myself or play against it when I need to press enter to tell it to move but it does not let me to play enpassent capture or castle so it does not support playing chess and by definition cannot beat most players because it is not going to accept castling moves by them.

I conceed to most of this criticism. The program as listed does not play proper chess, but another, very similar game. When I would not have implemented the input checking (which I thought such a nice feature... ) I would have gotten away with this, because I would have simply defined that 1. 0-0, ... should be entered as e1f1 <enter> f1g1 <enter> h1f1, and 1. e5 x d6 e.p. as e5d5 <enter> d5e5 <enter> e5d6.

About the C syntax: indeed this is not written in ANSI C, but in UNIX C, as described by Kernighan & Ritchie. The compiler I use eats it without any complaints (gcc under cygwin). For functions implicitly declared as integer it was not considered a crime to not return a value in that C dialect. The rules I set for myself was that my compiler produces an executable that plays as intended. As such I am quite happy that i even don't draw any warnings.

[H.G.Muller]

The only reason that it may beat most of the humans is that most of the humans are not chess players.

Of course. But many people will tell you they know how to play chess, and if they are not club-players but occasionally play a game at home against friends, they usually have a very hard time to beat a program like this. I merely mention it because, even if it the program only beats all non-chess-players, I think it deserves to be qualified as a chess player. That was the point I wanted to make: if one drops the requirement that it should actually be able to win some games, the size could be reduced even more because a random-move generator would suffice. Personally I don't feel that a random-move generator qualifies as a chess program: it must make some attempt to judge the moves and select a good one before it can be called one.

[H.G.Muller]

OK, this is a version that does implement castling and e.p. capture. No minor promotion, though, this is purely an inputproblem (since it is exceedingly unlikely that it will ever encounter a situation where a minor promotion is needed), and therefor not very interesting. It took me some extra 280 charactrs to implement this, i.e. more than 20% extra, which I consider quite a lot for a minor detail of the game. I underlined the changes/additions:

#define F(I,S,N) for(I=S;I<N;I++)
#define W(A) while(A)
#define C(A) if(A)continue;
#define B(A) if(A)break;

int V=112,M=136,I=4e3,C=799,X,Y,i,Q,N,K=128,
w[]={0,1,1,3,-1,3,5,9},
o[]={6,3,5,7,4,5,3,6},
g[]={0,3,-1,21,7,11,16,7},
d[]={16,15,17,0,-16,-15,-17,0,1,-1,16,-16,15,-15,17,-17,0,1,-1,16,-16,0,
14,-14,18,-18,31,-31,33,-33,0},
b[129];

char n[]=".?+nkbrq?*?NKBRQ";

P()
{F(i,0,121)
printf(" %c",i&8&&(i+=7)?10:n[b[i]&15]);
}

D(k,q,l,e,E,x,n)
int k,q,l,e,E,x,n;
{
int i,j,t,p,u,r,y,m=n>1|q>e?q:e,v,h,z,F,G,H;

N++;
F(i,0,120)
{i=i+8&~8;
u=b[i];C(!(u&k))
j=g[p=u&7];
W(r=d[++j])
{y=i;F=G=128;
do
{H=y+=r;B(y&M)
if(y==E)H=y^16;
t=b[H];B(t&k)
B(p<3&&!(r&7)!=!t)
v=99*w[t&7];
if(v<0||E-128&&b[E]&&y-E<2&E-y<2)m=I;
if(m>=l)return m;

if(h=n-(y!=x))
{if(p<6)v+=b[i+8]-b[y+8];
if(p==4)v+=9*(e>C?!((x^y)&68):-3);
b[G]=b[H]=b[i]=0;b[y]=u&31;
if(!(G&M)){b[F]=k+6;v+=55;}
if(p<3)
{v-=10*(((i-2)&M||b[i-2]!=u)+((i+2)&M||b[i+2]!=u)-1);
if(y+r+1&128){b[y]|=7;v+=C;}
}
v=-D(24-k,-l,-m,z=-e-v,F,y,h);
if(v>1500)v-=50;
if(x==9){if(v!=-I&i==X&y==Y){Q=z;K=F;return l;}v=m;}
b[G]=k+38;b[F]=b[y]=0;b[i]=u;b[H]=t;
if(v>m){m=v;if(x&8){X=i;Y=y;}}
}
t+=p<5;
if(j<7&&6*k+(y&V)==128
||(u&~24)==36&&!(j&~9)&&
G&M&&b[G=(i&V)+7-(r>>1&7)]&32
&&!(b[G^1]|b[G^2])
){F=y;t--;}
}W(!t);
}
}
return m+I?m:-D(24-k,-I,I,0,128,x,1)/2;
}

main()
{
int i,j,k=8,*p,c[9],d;

F(i,0,8)
{b[i]=(b[i+V]=o[i]+40)+8;b[i+16]=18;b[i+96]=9;
F(j,0,8)b[16*j+i+8]=(i-4)*(i-4)+(j-3.5)*(j-3.5);
}

W(1)
{P();p=c;W((*p++=getchar())>10);
if(*c-10){X=c[0]-16*c[1]+C;Y=c[2]-16*c[3]+C;}else
{d=6;N=0;W(N<4e6)D(k,-I,I,Q,K,8,d++);
printf("%d ply, %d searched\n",d-2,N);
}
if(D(k,-I,I,Q,K,9,2)==I)k^=24;
}
}

The e.p is the simplest. It needs the capture field H to be different from the destination field y of the moved piece, and an extra argument E to be passed to the next level to inform it that e.p. is possible and where. If the destinaton field y of a pawn is equal to this, we have an e.p. capture and shift the capture field H from its ordinary position coinciding with y. If no e.p. is posible an invalid square number is passed, to prevent a match. A variable F (to be passed to the next level as E) is set to the valid field when a pawn move is elongated. The flag also has to be passed at the game level, from one move (obtained during the legality checking) to the next, for which a global variable K is used.

Castling is more nasty, (and the solution I came up with a good excercise in C operator priorities). It also uses the e.p. variables, since castling fits the pattern of e.p. capture: the normal range of a piece is extended, and at the field which it jumps over it can be captured e.p., (which for a king of course makes the move illegal). The condition for extending the move is thus merged with that for pawns on the 2nd/7th row, checking if it is a king, moving sideways, if the rook is present, and the intervening squares are empty. We also have to be able to distinguish pieces that have moved from virgin pieces, to this end an extra bit (32) in the piece code is set initially and stripped of on moving (&31). If all the tests are passed succesfully, the king-move is extended, and as a side effect the relevant corner was computed and stored as G. G containing a valid square number flags that the move is castling, and (G,F) is then the valid rook move, which has to be performed when the move is tried. (G valid than suppresses a second elongation of the king move, on my first try it did two different kinds of long castling, besides the regular one also one where the king was ending up on b1 and the rook on c1...) Moving a rook back to G when the move is undone is always done, because even if it was no castling G then holds the code of a dummy field that is not part of the board (128, the board array b[] was extended by one element to accomodate this dummy).

The rule that castlings are illegal when the king is in check, ends up in check, or jumps over a field that is in check, is done on the next ply, just like any other move that put the king in check is intercepted there. So the king-capture test line is extended with a check that the e.p. field E contains a rook, and then any captures to that field or the two fields next to it are considered king-captures.

Of course the castling has to recieve some favorable evaluation score (+55 pts) or it would be treated as any other king move (which is discouraged and recieves a 27 pt penalty).

[Dann Corbit]

Code: Select all

#include <stdio.h>

static int      V = 112,
                M = 136,
                I = 4e3,
                C = 799,
                X,
                Y,
                i,
                Q,
                N,
                K = 128,
                w[] = {0, 1, 1, 3, -1, 3, 5, 9},
                o[] = {6, 3, 5, 7, 4, 5, 3, 6},
                g[] = {0, 3, -1, 21, 7, 11, 16, 7},
                d[] = { 16, 15, 17,  0, -16, -15, -17,  0,   1, -1,  16, -16,  15, -15,  17,
                       -17,  0,  1, -1,  16, -16,   0, 14, -14, 18, -18,  31, -31,  33, -33, 0},
                b[129];

static char     n[] = ".?+nkbrq?*?NKBRQ";

void P(void)
{
    for (i = 0; i < 121; i++)
        printf(" %c", i & 8 && (i += 7) ? 10 : n[b[i] & 15]);
}

int D(int k, int q, int l, int e, int E, int x, int n)
{
    int             i,
                    j,
                    t,
                    p,
                    u,
                    r,
                    y,
                    m = n > 1 | q > e ? q : e,
                    v,
                    h,
                    z,
                    F,
                    G,
                    H;

    N++;
    for (i = 0; i < 120; i++) {
        i = i + 8 & ~8;
        u = b[i];
        if (!(u & k))
            continue;
        j = g[p = u & 7];
        while (r = d[++j]) {
            y = i;
            F = G = 128;
            do {
                H = y += r;
                if (y & M)
                    break;
                if (y == E)
                    H = y ^ 16;
                t = b[H];
                if (t & k)
                    break;
                if (p < 3 && !(r & 7) != !t)
                    break;
                v = 99 * w[t & 7];
                if (v < 0 || E - 128 && b[E] && y - E < 2 & E - y < 2)
                    m = I;
                if (m >= l)
                    return m;

                if (h = n - (y != x)) {
                    if (p < 6)
                        v += b[i + 8] - b[y + 8];
                    if (p == 4)
                        v += 9 * (e > C ? !((x ^ y) & 68) : -3);
                    b[G] = b[H] = b[i] = 0;
                    b[y] = u & 31;
                    if (!(G & M)) {
                        b[F] = k + 6;
                        v += 55;
                    }
                    if (p < 3) {
                        v -= 10 * (((i - 2) & M || b[i - 2] != u) + ((i + 2) & M || b[i + 2] != u) - 1);
                        if (y + r + 1 & 128) {
                            b[y] |= 7;
                            v += C;
                        }
                    }
                    v = -D(24 - k, -l, -m, z = -e - v, F, y, h);
                    if (v > 1500)
                        v -= 50;
                    if (x == 9) {
                        if (v != -I & i == X & y == Y) {
                            Q = z;
                            K = F;
                            return l;
                        }
                        v = m;
                    }
                    b[G] = k + 38;
                    b[F] = b[y] = 0;
                    b[i] = u;
                    b[H] = t;
                    if (v > m) {
                        m = v;
                        if (x & 8) {
                            X = i;
                            Y = y;
                        }
                    }
                }
                t += p < 5;
                if (j < 7 && 6 * k + (y & V) == 128
                    || (u & ~24) == 36 && !(j & ~9) &&
                    G & M && b[G = (i & V) + 7 - (r >> 1 & 7)] & 32
                    && !(b[G ^ 1] | b[G ^ 2])
                    ) {
                    F = y;
                    t--;
                }
            }   while (!t);
        }
    }
    return m + I ? m : -D(24 - k, -I, I, 0, 128, x, 1) / 2;
}

int main(void) {
    int             i,
                    j,
                    k = 8,
                   *p,
                    c[9],
                    d;

    for (i = 0; i < 8; i++) {
        b[i] = (b[i + V] = o[i] + 40) + 8;
        b[i + 16] = 18;
        b[i + 96] = 9;
        for (j = 0; j < 8; j++)
            b[16 * j + i + 8] = (i - 4) * (i - 4) + (j - 3.5) * (j - 3.5);
    }

    for (;;) {
        P();
        p = c;
        while ((*p++ = getchar()) > 10);
        if (*c - 10) {
            X = c[0] - 16 * c[1] + C;
            Y = c[2] - 16 * c[3] + C;
        } else {
            d = 6;
            N = 0;
            while (N < 4e6)
                D(k, -I, I, Q, K, 8, d++);
            printf("%d ply, %d searched\n", d - 2, N);
        }
        if (D(k, -I, I, Q, K, 9, 2) == I)
            k ^= 24;
    }
    return 0;
}


[H.G.Muller]

Wow, thanks! The trick apparently is to put 'code' and '/code' layout commands around it. I did not know that (I will try to fix it in my earlier postings...)

By the way, does anyone understand why, if I write b[i] in the code, it does not consider it the beginning of a stretch of italics? Is that because it can not find the closing '/i'?

I realize now that the stale-mate detection might cause logical problems in my simplistic approach: stale-mate does not fit in the logic of fail-high and fail-low cutoffs. The latter assumes that if a refutation move is found (above beta), the search for better alternatives in that node can be discontinued. So on capturing a pawn in a situation where no pawn loss is mandatory, it does not go on to search for the king-capture, assuming that this would only make it worse for the opponent. But this assumption is false. It could be much better for the opponent if we could capture his king: it might mean that his only move was an illegal one after all, so that he is in stale mate, which, if he is sufficiently behind in material, carries a huge positive score.

This problem is only partly solved on including iterative deepening, because even if the first iteration (depth zero, = QS) would only consider recaptures the recapture of a piece that was pinned on the king (but nevertheles moved) might cause a fail high for the loss of the piece, shadowing the king capture. The only solution I see is to force the window open on the first iteration, (beta = +inf) so that no king capture can be missed. My serious engine starts with a separate test to check if the piece that moved on the previous ply happened to be pinned on the king and only then starts working on evaluating recaptures that might lead to fail-high cutoffs, but such a specific test would require a lot of extra, dedicated code...

[Pedro Castro]

draw 3 rep

no mate with queen,

I played whit the board turned and without distinguishing the pieces very well, since I am not accustomed to play this way, but I found the program stronger than many others.

[Event "13:56 24/11/05"]
[Site "?"]
[Date "2005.11.24"]
[Round "?"]
[White "Muller chess 1k"]
[Black "Pedro"]
[Result "1/2-1/2"]

1. c4 e5 2. d4 exd4 3. Qxd4 Nc6 4. Qe3+ Be7 5. Qg3 Bf6 6. Nc3 Nge7 7. Bf4 O-O 8. Bxc7 Qe8 9. O-O-O Nf5 10. Qd3 Qe6 11. Nd5 Ne5 12. Nxf6+ Qxf6 13. Qd5 Ng4 14. Nh3 Ne7 15. Qe4 h5 16. f3 Nh6 17. Rd6 Qf5 18. Qxe7 b6 19. Rd5 Qg6 20. Bd6 Bb7 21. Rg5 Nf5 22. Qxf8+ Rxf8 23. Rxg6 fxg6 24. Bxf8 Kxf8 25. Nf4 Ne3 26. Nxg6+ Kf7 27. Ne5+ Ke6 28. Ng6 Nxc4 29. Nf4+ Kf5 30. Nxh5 g6 31. Ng7+ Ke5 32. Ne8 Ne3 33. g3 g5 34. Kd2 Kd4 35. Nd6 Bc6 36. Rg1 a5 37. Bh3 a4 38. Ra1 b5 39. Nf7 g4 40. Bxg4 b4 41. Ne5 Bb5 42. Bxd7 Bxd7 43. Nxd7 Nc4+ 44. Kc2 Ke3 45. b3 axb3+ 46. Kxb3 Nd2+ 47. Kxb4 Kxe2 48. f4 Kf3 49. Nf6 Kg2 50. Ng4 Kh3 51. Nf2+ Kxh2 52. Rd1 Nf3 53. Ne4 Kh3 54. Ng5+ Kxg3 55. Rd3 Kxf4 56. Nxf3 Ke4 57. Kc4 Kf4 58. Kd4 Kf5 59. Kc4 Ke4 60. a4 Kf5 61. a5 Ke4 62. a6 Kf5 63. Kb4 Ke4 64. Kb3 Kxd3 65. a7 Ke3 66. Kc3 Kxf3 67. a8=Q+ Ke3 68. Kb4 Kd4 69. Ka3 Ke3 70. Ka4 Kd4 71. Qb8 Ke3 72. Qg3+ Kd4 73. Kb5 Ke4 74. Kc5 Kf5 75. Kd5 Kf6 76. Kd6 Kf5 77. Qh4 Kg6 78. Ke6 Kg7 79. Qf6+ Kh7 80. Kd6 Kg8 81. Kd5 Kh7 82. Kd6 Kg8 83. Kd5 Kh7 84. Kd6 1/2-1/2