Code: Select all
/***************************************************************************/
/* micro-Max, */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller */
/***************************************************************************/
/* - recursive negamax search */
/* - quiescence search with recaptures */
/* - recapture extensions */
/* - (internal) iterative deepening */
/* - best-move-first 'sorting' */
/* - full FIDE rules and move-legality checking */
/* - version 1.6.007- */
/* (input buffer c[] & *P made global, K and N encoding swapped for this) */
#define maxNodes 1000 // orig: 1000000
#define maxItera 20 // orig: 98
int M=136,S=128,I=8000,C=799,Q,O,K,N,Xbest,Ybest;
char L,*P,
w[]={0,1,1,-1,3,3,5,9},
o[]={-16,-15,-17,0,1,16,0,1,16,15,17,0,14,18,31,33,0,
7,-1,6,11,8,3,6,
6,4,5,7,3,5,4,6},
b[129],
n[]=".?+knbrq?*?KNBRQ",
c[9];
D(k,q,l,e,E,z,n)
int k,q,l,e,E,z,n;
{
int j,r,m,v,d,h,i,F,G,s;
char t,p,u,x,y,X,Y,H,B;
q--;
d=X=Y=0;
while(d++<n||z==8&K==I&&(N<maxNodes&d<maxItera|| (K=X,L=Y&~M,d=2)))
{x=B=X;
h=Y&S;
m=d>1?-I:e;
N++;
do{u=b[x];
if(u&k)
{r=p=u&7;
j=o[p+16];
while(r=p>2&r<0?-r:-o[++j])
{A:
y=x;F=G=S;
do{
H=y=h?Y^h:y+r;
if(y&M)break;
m=E-S&&b[E]&&y-E<2&E-y<2 ? I : m;
if(p<3&y==E)H^=16;
t=b[H];
if(t&k|p<3&!(y-x&7)-!t)break;
i=99*w[t&7];
m=i<0?I:m;
if(m>=l)goto C;
if(s=d-(y!=z))
{v=p<6?b[x+8]-b[y+8]:0;
b[G]=b[H]=b[x]=0; // do move
b[y]=u|32;
if(!(G&M)) {b[F]=k+6; v+=30;}
if(p<3)
{v-=9*((x-2&M||b[x-2]-u)+
(x+2&M||b[x+2]-u)-1);
if(y+r+1&S)b[y]|=7,i+=C;
}
v=-D(24-k,-l, m>q? -m:-q,-e-v-i,F,y,s);
if(K-I)
{if(v+I&&x==K&y==L&z==8)
{Q=-e-i; O=F;
if(b[y]-u&7&&P-c>5)b[y]-=c[4]&3; /* under-promotions */
return l;
}v=m;
}
b[G]=k+6; // undo move
b[F]=b[y]=0;
b[x]=u;
b[H]=t;
if(v>m)
m=v, X=x, Y=y|S&F;
if(h){h=0;goto A;}
}
if(x+r-y|u&32|
p>2&(p-3|j-7||
b[G=x+3^r>>1&7]-k-6
||b[G^1]|b[G^2])
)t+=p<5;
else F=y;
}while(!t);
}
}
}while((x=x+9&~M)-B);
C:
if(m>I-M|m<M-I)d=maxItera+1;
if(z==8)printf("%2d ply, %9d searched, %6d by (%2d,%2d)\n",d-1,N,m,Xbest=X,Ybest=Y&0x77);
m=m+I?m:-D(24-k,-I,I,0,S,S,1);
}
return m+=m<e;
}
main()
{
int k=8;
int i,j;
i=8;
while(i--)
{b[i]=(b[i+112]=o[i+24]+8)+8;
b[i+16]=18;
b[i+96]=9;
j=8;
while(j--)b[16*j+i+8]=(K-4)*(K-4)+(j-3.5)*(j-3.5);
}
while(1)
{
N=-1;
if(Xbest!=Ybest) printf("\n %c%d %c%d \n",(97+(Xbest&15)),(8-(Xbest>>4)),(97+(Ybest&15)),(8-(Ybest>>4)));
printf("\n");
while(++N<121)
if (N&8&&(N+=7)) printf(" |%d \n", 8-(N>>4));
else
printf(" %c",n[b[N]&15]);
printf(" ----------------|\n a b c d e f g h |\n ----------------|\n");
printf(k==8?" WHITE ":" BLACK ");
P=c;
while((*P++=getchar())>10);
K=I;
if(*c-10) K=*c-16*c[1]+C, L=c[2]-16*c[3]+C;
k^=D(k,-I,I,Q,O,8,2)-I?0:24;
}
}
Code: Select all
//////////////////////////////////////////
// micro-MaXT chess for NXT
//////////////////////////////////////////
//
// original code by H.G. MULLER
// http://home.hccnet.nl/h.g.muller/max-src2.html
//
// new approach with new ANSI C source 1.6.007 ff.
//////////////////////////////////////////
// pseudo recursion probaly faulty :(
//////////////////////////////////////////
string version ="112";
#define maxNodes 1000 // orig: 10000000
#define maxItera 20 // orig: 98
int I=8000, // "infinity" score
// C=799,
Q; // updated evaluation score
long N, // Node counter
i; // index
int M=136; // 136=0x88: board system
int S=128; // 128=0x80: highest legal square number of b[
int V=112; // 112=0x70: rank mask
char O, // passes e.p. flag to next move at game level
K, L; // man. entered move squares: K=FromSqr, L=ToSqr
char FromBuf=-1 , ToBuf=-1; // dummies for manually entered move squares
char w[]={0,1,1,-1,3,3,5,9}; // piece value {., P+, P-, N, K, B, R, Q}
char o[]= {
-16,-15,-17,0, // 0...
1,16,0, // 4...
1,16,15,17,0, // 7...
14,18,31,33,0, // 12...
7,-1,6,11,8,3,6, // 17...23 : move vectors
6,4,5,7,3,5,4,6} ; // 24...31 : setup first
char b[129]; // b[field-number]= empty=0 or =piece value
string pieces=".?+knbrq?*?KNBRQ"; // pieces for print; UpperCase=white
// .=empty | ?=unused | n...q,N...Q=pieces
char key; // NXT button pressed
int returned_val; // returned value after iteration
// (workaround for pseudo-iteration)
/***************************************************************************/
// Basic I/O
/***************************************************************************/
#define printf1( _x, _y, _format1, _value1) { \
string sval1 = FormatNum(_format1, _value1); \
TextOut(_x, _y, sval1); \
}
void Init(){
SetLongAbort(true);
ResetSleepTimer();
SetSleepTimeout(0);
}
//*****************************************
inline bool keypressed(){
char test;
test=( ButtonPressed(BTN1, false) || ButtonPressed(BTN2, false)
|| ButtonPressed(BTN3, false) || ButtonPressed(BTN4, false));
return test;
}
//*****************************************
inline int readkey() {
int result = -1;
if (ButtonPressed(BTN1, false))
result = BTN1;
else if (ButtonPressed(BTN2, false))
result = BTN2;
else if (ButtonPressed(BTN3, false))
result = BTN3;
else if (ButtonPressed(BTN4, false))
result = BTN4;
//if (result <> -1) while(ButtonPressed(result, false)); // don't wait
return result;
}
/***************************************************************************/
// Sound: PlayNotes
/***************************************************************************/
struct Note
{
unsigned int Frequency;
unsigned int Duration;
};
//*****************************************
Note ChordUp[] = {TONE_C4, 50, TONE_E4, 50, TONE_G4, 50,
TONE_C5, 50, TONE_E5, 50, TONE_G5, 50, TONE_C6, 200};
Note ChordDn[] = {TONE_C6, 50, TONE_G5, 50, TONE_E5, 50,
TONE_C5, 50, TONE_G4, 50, TONE_E4, 50, TONE_C4, 200};
Note Chord[] = {TONE_C4, 50, TONE_E4, 50, TONE_G4, 50, TONE_C5, 50};
Note Beep[] = {TONE_C5, 200};
Note BeepBeep[] = {TONE_C5, 200 , 0, 100, TONE_C5, 200};
Note Blip[] = {TONE_C7, 10 };
Note BlipBlip[] = {TONE_C7, 10, 0, 20, TONE_C7, 10 };
Note Buzz[] = {220, 200 };
Note sdError[] = {TONE_C4, 50, 0, 50, TONE_C4, 50, 0, 50, TONE_C4, 50, 0, 50};
//*****************************************
void PlayNotes(Note data[])
{
for (int i = 0; i < ArrayLen(data); i++) {
Note tmp = data[i];
PlayTone(tmp.Frequency, tmp.Duration);
Wait(tmp.Duration);
}
}
/***************************************************************************/
// GUI
/***************************************************************************/
char fontWi=8, fontHi=8;
int CursPos=120;
bool ChoiceFinished;
string numb2nota(int i){
char file, rank;
string sfile, srank;
file=97+(i&15);
rank=8-(i>>4);
sfile=" ";
sfile[0]=file;
srank=NumToStr(rank);
return (sfile+srank);
}
//*****************************************
void PrintBoard(){
int i;
char x, y, rank, color=0;
string sp;
for (i=0; i<121; i++) { // S= highest field number= a8
rank=7-(i>>4);
y=rank*fontHi;
if (i&8) {
NumOut(0, y, 8-(i>>4)); // (i&8: new rank=> print rank number,
i+=7; // skip the next 7 indices
}
else { // !(i&8): only the first 8 fields of each rank are valid
x=11+(i&15)*fontWi;
sp=SubStr(pieces, b[i]&15,1); // b[i]&15 : piece on field
color=!(b[i]&8); // !(b[i]&8) : color=black
TextOut(x, y, sp, color?0:4 ); // if color==white: write invers
}
}
TextOut(10*fontWi, fontHi, " ");
}
//*****************************************
void MarkPos(int i){
char x, y, rank, color, xp, yp, rankp,colorp=0;
string cs, ps;
color=0;
rank=7-(i>>4);
y=rank*fontHi;
x=11+(i&15)*fontWi;
cs=SubStr(pieces, b[i]&15,1);
if (i&8) cs=" ";
color=!(b[i]&8);
TextOut(x, y, cs, color?4:0);
if ((FromBuf!=-1 )) {
rankp=7-(FromBuf>>4);
yp=rankp*fontHi;
xp=11+(FromBuf&15)*fontWi;
ps=SubStr(pieces, b[FromBuf]&15,1);
colorp=!(b[FromBuf]&8);
TextOut(xp, yp, ps, colorp?4:0);
}
Wait(150);
TextOut(x, y, cs,color? 0:4);
if ((FromBuf!=-1 )) TextOut(xp,yp,ps,colorp?0:4);
Wait(150);
}
//*****************************************
void MoveCursor(char key){
if (key==BTNLEFT) {
if (CursPos==0) CursPos=120;
else
if (CursPos>0) {
CursPos--; if (CursPos&8) CursPos-=8;
}
}
else
if (key==BTNRIGHT){
if (CursPos>=120) CursPos=0;
else
if (CursPos==119) CursPos=120; // border field for choice: auto move!
else {
CursPos++;
if ((CursPos)&8) CursPos+=8;
}
}
TextOut(10*fontWi, fontHi, " ");
TextOut(10*fontWi, 0, " ");
if (!(CursPos&8)) {
TextOut(1+10*fontWi, fontHi, NumToStr(CursPos));
TextOut(1+10*fontWi, 0, numb2nota(CursPos));
}
}
//*****************************************
void MovePiece(){
b[ToBuf]=b[FromBuf];
b[FromBuf]=0;
FromBuf=-1;
ToBuf=-1;
CursPos=120;
ClearScreen();
PrintBoard();
}
//*****************************************
void GetHIDinput(){
key=-1;
ChoiceFinished=false;
if (CursPos==120) TextOut(1+10*fontWi, 0, "auto");
MarkPos(CursPos);
if (keypressed()) {PlayNotes(Blip); key=readkey();}
if ((key==BTNLEFT) || (key==BTNRIGHT)) MoveCursor(key);
else
if (key==BTNCENTER) {
if ((FromBuf==-1 ) && (ToBuf==-1 )) { // auto play
if (CursPos==120) {
PlayNotes(BeepBeep);
ChoiceFinished=true;
}
else // choice: invalid- empty field
if (!b[CursPos]) PlayNotes(sdError);
else // choice: take piece
{
FromBuf=CursPos;
PlayNotes(BlipBlip);
TextOut(1+9* fontWi, 4*fontHi, SubStr(pieces, b[FromBuf]&15,1));
if (FromBuf!=-1) NumOut(10*fontWi, 4*fontHi, FromBuf);
//TextOut(1+10*fontWi, 4*fontHi, numb2nota(FromBuf));
}
}
else
if ((FromBuf!=-1 ) && (ToBuf==-1 )) { // choice:invalid (start=destination)
if (FromBuf==CursPos) PlayNotes(sdError);
else { // choice: destination
PlayNotes(Beep);
ToBuf=CursPos;
if (ToBuf!=-1) NumOut(10*fontWi, 3*fontHi, ToBuf);
//TextOut(1+10*fontWi, 3*fontHi, numb2nota(ToBuf));
}
}
else // choice: ready + move
if ((FromBuf!=-1 ) && (ToBuf!=-1 ) && (FromBuf!=ToBuf)) {
PlayNotes(Chord);
ChoiceFinished=true;
}
}
else
if (key==BTNEXIT) { // choice: undo choice
PlayNotes(sdError);
if ((FromBuf!=-1 ) && (ToBuf!=-1 )) { // choice: undo destination
ToBuf=-1;
TextOut(1+10*fontWi, 3*fontHi, " ");
}
else
if ((FromBuf!=-1 ) && (ToBuf==-1 )) { // choice: undo take piece
FromBuf=-1;
TextOut(1+10*fontWi, 4*fontHi, " ");
}
}
}
/***************************************************************************/
// Push, Popp: save and recall variable stack
/***************************************************************************/
int StackInt[maxItera][10]; // int j,r,m,v,d,h,i,F,G,s;
char StackChar[maxItera][10]; // char t,p,u,x,y,X,Y,H,B,portkey;
void Push(int j,int r,int m,int v,int d,int h,int i,int F,int G, int s,
char t,char p,char u,char x,char y,char X,char Y,char H,char B,
char portkey)
{
int a, iv[10];
char cv[10];
ArrayBuild (iv, j,r,m,v,d,h,i,F,G,s);
ArrayBuild (cv, t,p,u,x,y,X,Y,H,B,portkey);
for (a=maxItera-1;a>=1;a--) {
StackInt[a]=StackInt[a-1];
StackChar[a]=StackChar[a-1];
}
StackInt[0]= iv;
StackChar[0]=cv;
}
//*****************************************
void Popp(int &j,int &r,int &m,int &v,int &d,int &h,int &i,int &F,int &G,int &s,
char &t,char &p,char &u,char &x,char &y,char &X,char &Y,char &H,char &B,
char &portkey)
{
int a;
j=StackInt[0][0]; r=StackInt[0][1]; m=StackInt[0][2];
v=StackInt[0][3]; d=StackInt[0][4]; h=StackInt[0][5];
i=StackInt[0][6]; F=StackInt[0][7]; G=StackInt[0][8]; s=StackInt[0][9];
t=StackChar[0][0]; p=StackChar[0][1]; u=StackChar[0][2];
x=StackChar[0][3]; y=StackChar[0][4]; X=StackChar[0][5];
Y=StackChar[0][6]; H=StackChar[0][7]; B=StackChar[0][8];
portkey=StackChar[0][9];
for (a=0;a<maxItera-1;a++) {
StackInt[a]=StackInt[a+1];
StackChar[a]=StackChar[a+1];
}
}
/***************************************************************************/
// pseudo recursive MiniMax search and move generator (in progress)
/***************************************************************************/
int D(int k,int q,int l,int e,int E,int z,int n)
// recursive minimax search, k=moving side, n=depth
// (q,l)=window, e=current eval. score, E=e.p. sqr.
// e=score, z=prev.dest; return score
{
int j,r,m,v,d,h,i,F,G,s;
char t,p,u,x,y,X,Y,H,B,portkey=0;
NEW_ITERATION:
j=0;r=0;m=0;v=0;d=0;h=0;i=9;F=0;G=0;s=0; // new variable initialization
t=0;p=0;u=0;x=0;y=0;X=0;Y=0;H=0;B=0;
q--;
while(d++<n||z==8&K==I&&(N<maxNodes&d<maxItera|| (K=X,L=Y&~M,d=2)))
{
x=B=X;
h=Y&S;
m=d>1?-I:e;
N++;
do{ // scan board for own piece
u=b[x];
if(u&k) // u&k= own piece
{
r=p=u&7; // p= piece type, e.g. knight=3
// -1 ! before piece vector list
j=o[p+16]; // for j: toggle -r/+r, then ++j
while(r=p>2&r<0?-r:-o[++j]) // loop over directions o[]
{
A:
y=x; // (x,y)=move
F=G=0x80; // (F,G)=castl.R
do{
H=y=h?Y^h:y+r;
if(y&M) break; // board edge hit
m=E-S&&b[E]&&y-E<2&E-y<2?I:m;
if(p<3&y==E)H^=16; // shift capt.sqr. H if e.p.
t=b[H];
if(t&k|p<3&!(y-x&7)-!t) break; // capt. own, bad pawn mode
i=99*w[t&7]; // value of capt. piece t
m=i<0?I:m;
if(m>=l)goto C; // abort on fail high
if(s=d-(y!=z)) // remaining depth(-recapt.)
{
v=p<6?b[x+8]-b[y+8]:0; // center positional pts.
b[G]=0; // do move,
b[H]=0;
b[x]=0;
b[y]=u|32; //strip virgin-bit
// castling: put R & score
if(!(G&M)) { b[F]=k+6; v+=30; } // b[F]=k+6, v+=30;
if(p<3) // p<3 == pawns:
{v-=9*((x-2&M||b[x-2]-u)+ // structure, undefended
(x+2&M||b[x+2]-u)-1); // squares plus bias
// promote p to Q, add score
if(y+r+1&S) // b[y]|=7, i+=C;
{b[y]|=7; i+=799;} // 7= Queen, score for promote
}
/////////////////////////////////////////////////// recursive eval. of reply
// D( k, q, l, e, E, z, n) // "pattern" of D()
// v=-D(24-k, -l, m>q?-m:-q, -e-v-i, F, y, s); // recursive call
///////////////////////////////////////////////////
// FIFO workaround:
//************************************************************************
Push(j,r,m,v,d,h,i,F,G,s, t,p,u,x,y,X,Y,H,B,portkey); // save on LIFO
portkey=1; // for leap back
k=24-k; q=(-l); l=m>q?-m:-q; e=-e-v-i; E=F; z=y; n=s;
//************************************************************************
goto NEW_ITERATION;
END_IT_1:
// there and back again
//************************************************************************
Popp(j,r,m,v,d,h,i,F,G,s, t,p,u,x,y,X,Y,H,B,portkey); // rcl from LIFO
v=-returned_val; // v=-D(): "returned" value
//************************************************************************
if(K-I) // checker: if move found
{
if(v+I && x==K & y==L & z==8)
{
Q=-e-i; // & not in check, signal
O=F;
// if(b[y]-u&7&&P-c>5)b[y]-=c[4]&3; /* *NO* !!! under-promotions */
returned_val=l; // save the value that has to be "returned"
goto RETURN_VALUES; // return l;
//************************************************************************
}
v=m;
}
b[G]=k+6;
b[F]=0; b[y]=0;
b[x]=u;
b[H]=t;
if(v>m)
m=v,X=x,Y=y|S&F;
if(h){h=0;goto A;}
}
if(x+r-y|u&32|
p>2&(p-3|j-7||
b[G=x+3^r>>1&7]-k-6
||b[G^1]|b[G^2])
)t+=p<5;
else F=y;
}while(!t);
}
}
}while((x=x+9&~M)-B);
C:
if((m>I-M)| (m<M-I))d=maxItera+1;
//if(z==8)printf("%2d ply, %9d searched, %6d by (%2x,%2x)\n",d-1,N,m,X,Y&0x77);
ClearScreen();
TextOut(0,7*fontHi, "calculating...");
printf1(0,6*fontHi, "ply %9d", d-1);
printf1(0,5*fontHi, "search %9d", N);
printf1(0,4*fontHi, "move %9d", m);
printf1(0,3*fontHi, "from %3d", X);
printf1(0,2*fontHi, "to %3d", Y&0x77);
////////////////////////////////////////////////
// // best loses K: (stale)mate
// D( k, q, l, e, E, z, n) // "pattern" of D()
// m=m+I?m: -D(24-k,-I, I, 0, S, S, 1); //
// if (!(m+I)) m=-D(24-k,-I, I, 0, S, S, 1); //
////////////////////////////////////////////////
// FIFO workaround:
if (!(m+I)) {
Push(j,r,m,v,d,h,i,F,G,s, t,p,u,x,y,X,Y,H,B,portkey);
portkey=2; // for leap 1 level back
k=24-k; q=-I; l=I; e=0; E=S; z=S; n=1;
goto NEW_ITERATION;
}
END_IT_2:
// there and back again
Popp(j,r,m,v,d,h,i,F,G,s, t,p,u,x,y,X,Y,H,B,portkey);
m=-returned_val; // m=-D(...)
}
m+=m<e;
returned_val=m;
RETURN_VALUES:
if (portkey==0) return returned_val; // return m to main()
else
if (portkey==1) goto END_IT_1; // return m to previos level;
else
if (portkey==2) goto END_IT_2;
}
/***************************************************************************/
// task main
/***************************************************************************/
task main(){
int j,k=8;
Init(); // init NXT Brick
i=8;
while(i--)
{ // Board 1st setup://
b[i+112]=o[i+24]+8;
b[i]=(b[i+112]+8);
b[i+16]=18;
b[i+96]=9;
j=8;
while(j--)
b[16*j+i+8]=(K-4)*(K-4)+(j-3.5)*(j-3.5); // center-pts table
} //(in unused half b[])
while(1){ // play loop
//N=-1;
FromBuf=-1; ToBuf=-1; ChoiceFinished=false; // reset all inputs
ClearScreen(); PrintBoard(); //
CursPos=120; // cursor start position
if (k==8) TextOut(10*fontWi, 7*fontHi,"White"); // color
else TextOut(10*fontWi, 7*fontHi, "Black"); // color
while (!ChoiceFinished) GetHIDinput();
//*********************************************************************
if (FromBuf!=-1) NumOut(10*fontWi, 4*fontHi, FromBuf); // FromBuf for debug
if (ToBuf!=-1) NumOut(10*fontWi, 3*fontHi, ToBuf); // ToBuf for debug
//*********************************************************************
K=I;
if(ToBuf!=-1) // user input!
{ K=FromBuf; L=ToBuf; } // assign dummies
k^=D(k,-I,I,Q,O,8,2)-I?0:24;
Wait(1);
}
}
}
the compiled WIN console .exe file (to show how it could sort of work and might calculate the moves -