/***********************************************************************/
/* The Chessiverse, version 1.1.2, by H.G. Muller */
/* Program to evolve a set of program organisms running on a simple */
/* virtual machines, through a genetic algorithm, to develop a certain */
/* game-playing skill. The programs are paired to play each other, and */
/* all the environment does is supply game situations and perform the */
/* moves after judging their legality. */
/***********************************************************************/
/* 1.0.1: OUT instruction in interpreter as wrong if mode != 7 */
/* 1.0.2: Nr of accessible ports BRDSIZE+2 in stead of BRDSIZE */
/* 1.1.0: INP & IDX instruction nw opcode, IDX @ for INP */
/* 1.1.1: @-mode bug corrected on rmw-instructions */
/* Save and Restore also save Season and Seed */
/* Remove piece from old square after move */
/* Restart from file if flag argument requests so */
/* 1.1.2: LegalMove Slider[PieceType] in stead of Slider[Piece] */
/* PNR initialized to 0 */
/* BIT instruction added, opcode for LD changed */
/* Yet to do: properly implement shifts (carry setting & ASR) */
#include <stdio.h>
/* Parametric description of tournament */
#define CHAMBERS 1 /* number of different enironments */
#define BOARDS 50
#define PROGRAMS (2*BOARDS) /* number of programs per chamber */
#define ROUNDS 100 /* number of games per season */
#define RECORD 1000 /* save every so many seasons */
#define BRDSIZE 64 /* size of game board */
#define TWEIGHT 0 /* weight of CPU time in score */
#define TLIMIT 1000 /* timeout in nr of instructions */
/* Description of virtual machines */
#define DATAMEM 0x1000
#define PROGMEM 0x1000
#define FRAME 0x100 /* size of local-variables stack frame */
/* piece encodings in environment */
#define WHITE 8
#define BLACK 16
#define WPAWN 1
#define BPAWN 2
#define KNIGHT 3
#define BISHOP 4
#define ROOK 5
#define QUEEN 6
#define KING 7
/* Breeding parameters */
#define SURVIVORS 25
#define IMPORTS 0
#define PARENTS (SURVIVORS + IMPORTS)
#define MUTATIONS 40
unsigned short int Prog[CHAMBERS][PROGRAMS][PROGMEM];
unsigned char Data[DATAMEM];
unsigned char OutBuf[256];
char Table[BOARDS][BRDSIZE+2]; /* chess boads, incl. stm and cnt30 */
int Unpaired[PROGRAMS]; /* auxilary array to pair programs */
int Player[PROGRAMS]; /* players assigned to various boards */
int Ranking[CHAMBERS][PROGRAMS]; /* program nrs sorted by resuts */
double Score[PROGRAMS]; /* score of tournament in progress */
int Length[PROGRAMS]; /* nr of valid moves played */
int Season; /* counter for nr of seasons played */
int Seq; /* sequence number for new programs */
char Restart;
unsigned short int bench[] =
{ 0x773F, 0x9800, 0x9700, 0xD000, 0xD200, 0xD200, 0xD200, 0x9808,
0xA800, 0x9702, 0x2008, 0xE101, 0xE805, 0x8000, 0xA700,
0x4701, 0xA700, 0
};
unsigned long long int Seed = 0x55555555;
int Draw(int n)
/* generate random integer from 0 to n-1 */
{
Seed = Seed * 0x20001083;
return ((Seed>>48)*n >> 16);
}
int Run(unsigned short int *Code, unsigned char *Port,
int MaxPort, int OPlim, int Ilim)
/* interpret virtual-machine code passed in 'Code' for 'Ilim' */
/* instructions, or until 'OPlim' outputs are produced. */
{
unsigned int SP, PC, IX, IR, ADR, ACCU, CC, VAL, PNR, Opcode;
int i, j, k, h, Mode, Optr=0, Icnt=0;
for(i=0; i<DATAMEM; i++) Data[i] = 0; /* clear data memory */
PC = 0x200; SP = DATAMEM - FRAME; /* initialize registers */
IX = ADR = PNR = 0;
while(1)
{
if(Icnt++ > Ilim) return Icnt; /* Stop when time-out */
PC &= PROGMEM-1;
IR = Code[PC++]; /* fetch next instruction */
Opcode = IR>>11;
if(Opcode >= 26) /* jump, branch or reg-mode */
{ /* have deviating formats */
if(Opcode >= 30) /* JSR <address> */
{
SP -= FRAME; /* reserve new stack frame */
if(SP<0x100) return TLIMIT; /* stack overflow */
Data[SP+8] = PC; /* save return address */
Data[SP+9] = PC>>8;
PC = IR & (PROGMEM-1); /* load program counter */
continue;
}
Mode = IR>>8 & 7;
switch(Opcode)
{
case 26: /* accumulator unaries */
switch(Mode)
{
case 0: CC = ++ACCU; break; /* INC %a */
case 1: CC = --ACCU; break; /* DEC %a */
case 2: CC = ACCU <<= 1; break; /* LSL %a */
case 3: CC = ACCU >>= 1; break; /* LSR %a */
case 4: CC = ACCU >>= 1; break; /* ASR %a */
case 5: CC = ACCU = -ACCU; break; /* NEG %a */
case 6: CC = ACCU = ~ACCU; break; /* COM %a */
case 7: CC = ACCU = 0; break; /* CLR %a */
} continue;
case 27: /* RTS */
PC = Data[SP+8] + (Data[SP+9]<<8);
if(SP >= DATAMEM-FRAME) return TLIMIT; /* stack underflow */
SP += FRAME; continue;
case 28: /* conditional branches */
switch(Mode)
{ /* Branch forward if condition true */
case 0: if(CC==0 ) PC += IR & 0xFF; continue; /*BEQ*/
case 1: if(CC!=0 ) PC += IR & 0xFF; continue; /*BNE*/
case 2: if((CC&0x80)==0 ) PC += IR & 0xFF; continue; /*BPL*/
case 3: if((CC&0x80)!=0 ) PC += IR & 0xFF; continue; /*BMI*/
case 4: if((CC&~0xFF)==0) PC += IR & 0xFF; continue; /*BCC*/
case 5: if((CC&~0xFF)!=0) PC += IR & 0xFF; continue; /*BCS*/
case 6: if((CC^CC>>8)&0x80==0) PC += IR & 0xFF; continue;
case 7: if((CC^CC>>8)&0x80!=0) PC += IR & 0xFF; continue;
}
case 29: /* SOB ctr, <backward> */
if(Data[SP+Mode]--) PC -= IR & 0xFF;
continue;
}
}
if(Opcode>21) continue;
/* Normal addressing mode, calculate address and fetch data */
Mode = IR>>8 & 7;
h = 0;
switch(Mode)
{
case 1: /* adjust offset for access */
case 2: /* of deeper stack frames */
case 3:
h = Mode * FRAME;
case 0: /* local-frame address */
case 6: /* add stack pointer */
h += SP;
case 4: /* base address + indexing */
case 5:
h += (IX + IR) & 0xFF; IX = 0;
ADR = h & DATAMEM-1; /* prevent memory violation */
if(Mode>4) ADR = Data[ADR]; /* mode 5&6: indirection */
VAL = Data[ADR]; break; /* fetch data */
case 7:
VAL = IR & 0xFF; /* immediate mode */
PNR = (VAL + IX) & 0xFF; /* Port number */
if(IX) VAL = Code[PNR]; /* or constant-table mode */
}
/* perform operation, remembr result in CC for branching */
switch(Opcode)
{
/* binary operations, performed in accumulator */
case 0: CC = ACCU += VAL; continue; /* ADD <memory> */
case 2: CC = ACCU -= VAL; continue; /* SUB <memory> */
case 4: CC = ACCU &= VAL; continue; /* AND <memory> */
case 6: CC = ACCU |= VAL; continue; /* OR <memory> */
case 8: CC = ACCU ^= VAL; continue; /* XOR <memory> */
case 10: CC = ACCU = (char) ACCU * (char) VAL;
continue; /* MUL <memory> */
case 12: CC = ACCU *= VAL; continue; /* UML <memory> */
case 14: CC = ACCU = VAL; continue; /* LD <memory> */
case 16: CC = ACCU & VAL; continue; /* BIT <memory> */
case 18: if(Mode==7) /* INP <port> */
{ CC = ACCU = PNR < MaxPort ? Port[PNR] : Draw(256);
IX = 0;
} continue;
case 20: if(Mode==7)
{ OutBuf[Optr++] = ACCU; /* OUT <port> */
if(Optr>=OPlim) return Icnt; /* enough output */
} continue;
/* unary operators, directly in memory (read-modify-write) */
case 1: Data[ADR] = CC = Data[ADR] + 1; continue; /* INC <memory> */
case 3: Data[ADR] = CC = Data[ADR] - 1; continue; /* DEC <memory> */
case 5: Data[ADR] = CC = Data[ADR] <<1; continue; /* LSL <memory> */
case 7: Data[ADR] = CC = Data[ADR] >>1; continue; /* LSR <memory> */
case 9: Data[ADR] = CC = Data[ADR] >>1; continue; /* ASR <memory> */
case 11: Data[ADR] = CC = -Data[ADR]; continue; /* NEG <memory> */
case 13: Data[ADR] = CC = ~Data[ADR]; continue; /* COM <memory> */
case 15: Data[ADR] = CC = 0; continue; /* CLR <memory> */
case 17: CC = Data[ADR]; continue; /* TST <memory> */
case 19: Data[ADR] = CC = ACCU; continue; /* ST <memory> */
case 21: IX = 0x8000 | Data[ADR]; continue; /* IDX <memory> */
}
}
}
void Sort(int Start, int Stop, int Rank[])
/* Quicksort according to score */
{
int i, j, m, n;
double Edge;
if(Stop-Start < 2) return; /* only one element, done! */
i = Start; j = Stop-1;
Edge = Score[Rank[i]];
while(Score[Rank[++i]] == Edge) if(i>=j) return; /* all equal */
Edge = (Score[Rank[i]] + Edge)/2.;
if(Score[Rank[i]] > Edge) i = Start;
while(1)
{
while(Score[Rank[i]] > Edge) i++;
while(Score[Rank[j]] <= Edge && j>i) j--;
if(j<=i) break;
n = Rank[i]; Rank[i] = Rank[j]; Rank[j] = n;
}
Sort(Start, i, Rank);
Sort(i, Stop, Rank);
}
void IniBoard(char *board, int chamber)
/* Initialize new game according to chamber rules */
{
int i, j;
for(i=0; i<BRDSIZE+2; i++) board[i] = 0;
switch(chamber)
{ /* add rules for other chambers here */
default:
/* Position of KQK end-game */
board[Draw(64)+2] = WHITE + QUEEN;
i = Draw(64);
board[i+2] = WHITE + KING;
j = Draw(63); if(j>=i) j++; /* make sure Kings do not */
board[j+2] = BLACK + KING; /* end up on same square */
board[0] = Draw(2); /* randomize side to move */
}
}
char Dir[] = {0,0,4,22,17,8,13,13};
char Slider[] = {0,0,0,0,1,1,1,0};
char Xvec[] = {0,1,-1,0, 0,1,-1,0, 1,0,-1, 0,0, 1,0,-1, 0,1,-1, 1,-1,0,
2,-2,1,-1, 2,-2, 1,-1,0};
char Yvec[] = {1,0, 0,0,-1,0, 0,0, 0,1, 0,-1,0, 0,1, 0,-1,1, 1,-1,-1,0,
1, 1,2, 2,-1,-1,-2,-2,0};
int LegalMove(char *Board, unsigned char *Move)
/* perform move if legal and check for K-capture */
/* Return -1, 0 or 1 for illegal, ongoing or won */
{
int Color, Piece, PieceType, Victim, Xco, Yco, ToSquare, Ray, i;
Color = Board[0]*8 + 8; /* 8 or 16 */
if(Move[0] >= BRDSIZE || Move[1] >= BRDSIZE)
return(-1); /* invalid syntax */
Piece = Board[Move[0]+2];
if((Piece&24) != Color)
return(-1); /* no piece of us */
PieceType = Piece & 7; /* extract type */
for(i = Dir[PieceType]; Xvec[i]|Yvec[i]; i++)
{
Xco = Move[0]&7;
Yco = Move[0]&070;
do{
Xco += Xvec[i];
Yco += Yvec[i];
if(Xco&~7|Yco&~070) break; /* off board */
ToSquare = Xco|Yco;
Victim = Board[ToSquare+2];
if(Victim&Color) break; /* capt. own */
if(Piece <= 2 && (Victim != 0 && Xvec[i] == 0 ||
Victim == 0 && Xvec[i] != 0))
break; /* Bad Pawn mode */
if(ToSquare == Move[1]) /* move found */
{ /* perform move */
if(PieceType == 1 && Yco == 070 ||
PieceType == 2 && Yco == 0)
Piece = Color + QUEEN; /* Promote to Queen */
Board[ToSquare+2] = Piece; /* move to new pos. */
Board[Move[0]+2] = 0; /* Remove old piece */
Board[1]++; /* 30-move counter */
if(Victim || PieceType <= 2) Board[1] = 0;
if((Victim&7) == KING) return 1; /* King captured */
return 0; /* signal caller that move was legal */
}
Ray = Slider[PieceType];
if(Xvec[i] == 0 && (PieceType == 1 && Yco == 020 ||
PieceType == 2 && Yco == 050) )
Ray++; /* extend Pawn */
} while(Victim==0 && Ray);
i++;
}
return(-1); /* move not found among legal ones */
}
void Offspring(int nr, int chamber, int PoolSize)
/* create a new genome in entry nr of the specified chamber */
{
int i, l, j, k, m, n, mode, opc;
l = Draw(PoolSize); l=Ranking[chamber][l]; /* principal parent */
for(j=0; j<PROGMEM; j++) /* copy its genome */
Prog[chamber][nr][j] = Prog[chamber][l][j];
mode = Draw(10);
switch(mode)
{
case 0: /* Crossing Over: import coresponding code chunk */
k = (Draw(16)+1)<<Draw(6); /* select length of duplicate */
j = Draw(PROGMEM-k); /* random initial address */
/* select secondary parent != l */
i = Draw(PoolSize-1); if(i>=l) i++; i = Ranking[chamber][i];
k += j; /* end address of copied code */
while(j<k) /* make the copy */
{ Prog[chamber][nr][j] = Prog[chamber][i][j]; j++; }
break;
case 1:
k = (Draw(16)+1)<<Draw(6); /* select displacement */
j = Draw(PROGMEM-k); /* random address */
if(Draw(3)<2) { j += k; k = -k; }
/* Adjust branches & jumps in first (unshifted) part */
for(i=0; i<j; i++)
{
opc = Prog[chamber][nr][i];
if(opc >= 0xF000)
{ /* adjust JSR targets to second half */
if((opc & 0xFFF) >= j)
Prog[chamber][nr][i] += k;
} else if((opc & 0xF800) == 0xE000)
{ /* adjust targets conditional branch over deletion */
if(i+1+(opc&0xFF) >= j)
Prog[chamber][nr][i] += k;
}
}
/* Relocate code after insertion/deletion */
for(i=j; i<PROGMEM; i++)
{
opc = Prog[chamber][nr][i];
if(opc >= 0xF000)
{ /* adjust JSR targets to second half */
if((opc & 0xFFF) >= j)
Prog[chamber][nr][i] += k;
} else if((opc & 0xF800) == 0xE800)
{ /* adjust targets of loop branches over deletion */
if(i+1-(opc&0xFF) < j)
Prog[chamber][nr][i] += k;
}
}
/* Perform actual move, direction to prevent self overwrite*/
if(k<0)
{ /* deletion */
for(i=j; i<PROGMEM; i++)
Prog[chamber][nr][i+k] = Prog[chamber][nr][i];
j = PROGMEM + k; k = -k;
} else
{
for(i=PROGMEM-1; i>=j+k; i--)
Prog[chamber][nr][i] = Prog[chamber][nr][i-k];
}
/* Import code to fill gap at beginning or end */
m = Draw(PoolSize);
m = Ranking[chamber][m]; /* secondary parent */
n = Draw(PROGMEM-k);
for(i=j; i<j+k; i++)
Prog[chamber][nr][i] = Prog[chamber][m][n++];
break;
default: /* make a number of point mutations */
k = Draw(MUTATIONS)+1;
/* k = Draw(Prog[chamber][nr][0x100]&0xFF)+10;*/
while(k--)
{
j = Draw(PROGMEM);
if(Draw(2)<1) /* either random new value */
Prog[chamber][nr][j] = Draw(0x10000);
else /* or single-bit toggle */
Prog[chamber][nr][j] ^= 1<<Draw(16);
}
}
Prog[chamber][nr][0x101] = ++Seq;
Prog[chamber][nr][0x102] = Seq>>16;
}
void Save()
/* Save complete state of Chessiverse */
{
FILE *f;
int i, j, k;
f = fopen("chessi.sav", "wb");
if(f == NULL) return;
fwrite((void *) &Seed, sizeof Seed, 1, f);
fwrite((void *) &Season, sizeof Season, 1, f);
for(i=0; i<CHAMBERS; i++)
for(j=0; j<SURVIVORS; j++)
{
k = Ranking[i][j];
fwrite((void *) Prog[i][k], sizeof (short int), PROGMEM, f);
}
fclose(f);
}
void Restore()
/* Read in saved state for restart */
{
FILE *f;
int i, j, k;
f = fopen("chessi.sav", "rb");
if(f == NULL) return;
fread((void *) &Seed, sizeof Seed, 1, f);
fread((void *) &Season, sizeof Season, 1, f);
for(i=0; i<CHAMBERS; i++)
{
for(j=0; j<PROGRAMS; j++) Ranking[i][j] = j;
for(j=0; j<SURVIVORS; j++)
{
fread((void *) Prog[i][k], sizeof (short int), PROGMEM, f);
}
}
fclose(f);
}
void PlayChamber(int c, int Rnds)
{
int i, j, k, n, Available=PROGRAMS, Winner, Result;
/* Clear scores, all progs available, all boards empty */
for(i=0; i<PROGRAMS; i++)
{ Score[i] = 0; Length[i] = 0;
Unpaired[i] = Ranking[c][i] = i;
Player[i] = -1;
}
/* Play number of rounds */
for(j=0; j<Rnds; j++)
{
/* Attach all progs to a board */
for(i=0; i<BOARDS; i++)
{
/* If abandoned, reset game according to chamber */
if(Player[2*i]<0 && Player[2*i+1]<0)
IniBoard(Table[i], c);
/* Find player to man each side */
for(k=2*i; k<2*i+2; k++)
if(Player[k]<0)
{
n = Draw(Available);
Player[k] = Unpaired[n];
Unpaired[n] = Unpaired[--Available];
}
}
/* Play game on each board */
for(i=0; i<BOARDS; i++)
{
/* Play moves until game is won or resigned */
while(1)
{
/* figure out who is to move */
k = 2*i + (Table[i][0] == 1);
n = Run(Prog[c][Player[k]], Table[i], BRDSIZE+2, 2, TLIMIT);
Score[Player[k]] -= TWEIGHT*n;
if(n >= TLIMIT || (Result=LegalMove(Table[i], OutBuf)) < 0)
{ /* k forfeits game and leaves, but winner stays */
Unpaired[Available++] = Player[k];
Player[k] = -1;
Winner = Player[k^1];
Score[Winner] += 2;
/* side to move changes to prevent free-loading */
Table[i][0] ^= 1;
break;
} else
if(Table[i][1]++ > 60 || Result > 0)
{ /* Game ended, both leave */
if(Result > 0)
{
Winner = Player[k];
Score[Winner] += 2;
} else
{ Score[Player[k]]++;
Score[Player[k^1]]++;
}
Unpaired[Available++] = Player[k];
Player[k] = -1;
Unpaired[Available++] = Player[k^1];
Player[k^1] = -1;
break;
}
/* Game continues after legal move; change side */
Table[i][0] ^= 1;
Length[Player[k]]++;
Score[Player[k]] += 0.001;
}
}
}
/* Make ranking */
Sort(0, PROGRAMS, Ranking[c]);
/*printf("Chamber %d:\n", c);*/
for(i=0;i<PROGRAMS&&i<5;i++)
printf(" %3d with %10.3f %6.3f %10d %3d\n",
Ranking[c][i], Score[Ranking[c][i]],
Length[Ranking[c][i]]/(double) ROUNDS,
Prog[c][Ranking[c][i]][0x101]|
Prog[c][Ranking[c][i]][0x102]<<16,
Prog[c][Ranking[c][i]][0x100]&0xFF);
}
void PlaySeason()
{
int i, j, k, m, n;
printf("New Season %d\n", Season++);
/* Play all chambers */
for(i=0; i<CHAMBERS; i++) PlayChamber(i, ROUNDS);
/* Restart */
if(Restart) { Restore(); Restart = 0; }
/* Save state */
if(Season % RECORD == 1) Save();
/* Migrate some survivors between chambers */
if(CHAMBERS>1)
for(i=0; i<CHAMBERS; i++)
{
for(j=SURVIVORS; j<PARENTS; j++)
{ /* choose random chamber != i and survivor therein */
n = Draw(CHAMBERS-1); if(n>=i) n++;
m = Draw(SURVIVORS); m = Ranking[n][m];
for(k=0; k<PROGMEM; k++) /* and copy program */
Prog[i][j][k] = Prog[n][m][k];
}
}
/* Breed with survivors and iported migrants */
for(i=0; i<CHAMBERS; i++)
for(j=PARENTS; j<PROGRAMS; j++)
Offspring(Ranking[i][j], i, PARENTS);
}
main(int argc, char **argv)
{
int i, j, k;
for(i=0; i<CHAMBERS; i++)
for(j=0; j<PROGRAMS; j++)
{
for(k=0; k<PROGMEM; k++) Prog[i][j][k] = Draw(0x10000);
Prog[i][j][0x101] = ++Seq;
Prog[i][j][0x102] = Seq>>16;
}
if(argc > 1 && argv[1] != NULL && argv[1][0] == '-' && argv[1][1] == 'r')
Restart++;
/* for(k=0; bench[k]; k++) Prog[0][0][k+0x200] = bench[k];*/
while(1)
{
/* Play one season in each Chamber */
PlaySeason();
/* output diagnostics */
}
}