/***********************************************************************/
/* 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 */
    }
}