diagram.json

/**
 * bishop.cpp
 * 
 * the MicroChess project: https://github.com/ripred/MicroChess
 * 
 * move generation for bishops
 * 
 */

#include <Arduino.h>
#include "MicroChess.h"

////////////////////////////////////////////////////////////////////////////////////////
// add the moves for a bishop to the proper list (game.moves1 or game.moves2)
void add_bishop_moves(index_t from, index_t col, index_t row, index_t fwd, Color side) {
    Bool continue_nw = 1;
    Bool continue_ne = 1;
    Bool continue_sw = 1;
    Bool continue_se = 1;

    for (unsigned i=0; i < NUM_BISHOP_OFFSETS; i++) {
        offset_t *ptr = pgm_get_far_address(bishop_offsets);
        index_t xoff = ptr[i].x * fwd;
        index_t yoff = ptr[i].y * fwd;
        index_t to_col = col + xoff;
        index_t to_row = row + yoff;
        if (isValidPos(to_col, to_row)) {
            if (xoff < 0 && yoff > 0 && continue_nw) { // going NW
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_nw = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
            else
            if (xoff > 0 && yoff > 0 && continue_nw) { // going NE
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_ne = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
            else
            if (xoff < 0 && yoff < 0 && continue_nw) { // going SW
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_sw = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
            else
            if (xoff > 0 && yoff < 0 && continue_nw) { // going SE
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_se = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
        }
    }
}

bishop.cpp

/**
 * board.cpp
 * 
 * the MicroChess project: https://github.com/ripred/MicroChess
 * 
 * implementation file for the board class
 * 
 */
#include <Arduino.h>
#include "MicroChess.h"
#include "board.h"

spot_t::spot_t() : type(Empty), side(Black), moved(0), check(0) {

}

spot_t::spot_t(Piece p) {
    *this = *((spot_t *) &p); 
}

spot_t::spot_t(uint8_t t, uint8_t s, uint8_t m, uint8_t c) : type(t), side(s), moved(m), check(c) {

}

Piece board_t1::get(unsigned char index) const 
{
    return *((Piece*) &rows[index / 8].cols[index % 8]);
}

void board_t1::set(unsigned char index, Piece const piece) 
{
    rows[index / 8].cols[index % 8] = piece;
}    


Piece board_t2::get(unsigned char index) const 
{
    int const row = index / 8;
    int const col = index % 8;

    board_t2::row_t const &r = rows[row];
    spot_t const &spot = 
        0 == col ? spot_t(r.type1, r.side1, r.moved1, r.check1) :
        1 == col ? spot_t(r.type2, r.side2, r.moved2, r.check2) :
        2 == col ? spot_t(r.type3, r.side3, r.moved3, r.check3) :
        3 == col ? spot_t(r.type4, r.side4, r.moved4, r.check4) :
        4 == col ? spot_t(r.type5, r.side5, r.moved5, r.check5) :
        5 == col ? spot_t(r.type6, r.side6, r.moved6, r.check6) :
        6 == col ? spot_t(r.type7, r.side7, r.moved7, r.check7) :
                    spot_t(r.type8, r.side8, r.moved8, r.check8);

    return *((Piece*) &spot);
}

void board_t2::set(unsigned char index, Piece const piece) 
{
    int const row = index / 8;
    int const col = index % 8;

    switch (col) 
    {
        case 0:
            rows[row].type1 = getType(piece);
            rows[row].side1 = getSide(piece);
            rows[row].moved1 = hasMoved(piece);
            rows[row].check1 = inCheck(piece);
            return;
        
        case 1:
            rows[row].type2 = getType(piece);
            rows[row].side2 = getSide(piece);
            rows[row].moved2 = hasMoved(piece);
            rows[row].check2 = inCheck(piece);
            return;
        
        case 2:
            rows[row].type3 = getType(piece);
            rows[row].side3 = getSide(piece);
            rows[row].moved3 = hasMoved(piece);
            rows[row].check3 = inCheck(piece);
            return;
        
        case 3:
            rows[row].type4 = getType(piece);
            rows[row].side4 = getSide(piece);
            rows[row].moved4 = hasMoved(piece);
            rows[row].check4 = inCheck(piece);
            return;
        
        case 4:
            rows[row].type5 = getType(piece);
            rows[row].side5 = getSide(piece);
            rows[row].moved5 = hasMoved(piece);
            rows[row].check5 = inCheck(piece);
            return;
        
        case 5:
            rows[row].type6 = getType(piece);
            rows[row].side6 = getSide(piece);
            rows[row].moved6 = hasMoved(piece);
            rows[row].check6 = inCheck(piece);
            return;
        
        case 6:
            rows[row].type7 = getType(piece);
            rows[row].side7 = getSide(piece);
            rows[row].moved7 = hasMoved(piece);
            rows[row].check7 = inCheck(piece);
            return;
        
        case 7:
            rows[row].type8 = getType(piece);
            rows[row].side8 = getSide(piece);
            rows[row].moved8 = hasMoved(piece);
            rows[row].check8 = inCheck(piece);
            return;
    }
}

Piece board_t::get(unsigned char index) const 
{
    return board.get(index);
}

void board_t::set(unsigned char index, Piece const piece) 
{
    board.set(index, piece);
}    

void board_t::init() {
    set( 0, makeSpot(  Rook, Black, 0, 0));
    set( 1, makeSpot(Knight, Black, 0, 0));
    set( 2, makeSpot(Bishop, Black, 0, 0));
    set( 3, makeSpot( Queen, Black, 0, 0));
    set( 4, makeSpot(  King, Black, 0, 0));
    set( 5, makeSpot(Bishop, Black, 0, 0));
    set( 6, makeSpot(Knight, Black, 0, 0));
    set( 7, makeSpot(  Rook, Black, 0, 0));
    set( 8, makeSpot(  Pawn, Black, 0, 0));
    set( 9, makeSpot(  Pawn, Black, 0, 0));
    set(10, makeSpot(  Pawn, Black, 0, 0));
    set(11, makeSpot(  Pawn, Black, 0, 0));
    set(12, makeSpot(  Pawn, Black, 0, 0));
    set(13, makeSpot(  Pawn, Black, 0, 0));
    set(14, makeSpot(  Pawn, Black, 0, 0));
    set(15, makeSpot(  Pawn, Black, 0, 0));

    set(48, makeSpot(  Pawn, White, 0, 0));
    set(49, makeSpot(  Pawn, White, 0, 0));
    set(50, makeSpot(  Pawn, White, 0, 0));
    set(51, makeSpot(  Pawn, White, 0, 0));
    set(52, makeSpot(  Pawn, White, 0, 0));
    set(53, makeSpot(  Pawn, White, 0, 0));
    set(54, makeSpot(  Pawn, White, 0, 0));
    set(55, makeSpot(  Pawn, White, 0, 0));

    set(56, makeSpot(  Rook, White, 0, 0));
    set(57, makeSpot(Knight, White, 0, 0));
    set(58, makeSpot(Bishop, White, 0, 0));
    set(59, makeSpot( Queen, White, 0, 0));
    set(60, makeSpot(  King, White, 0, 0));
    set(61, makeSpot(Bishop, White, 0, 0));
    set(62, makeSpot(Knight, White, 0, 0));
    set(63, makeSpot(  Rook, White, 0, 0));
}

Piece board_t::getType(unsigned char from) const 
{
    return getType(get(from));
}


board.cpp

/**
 * board.h
 * 
 * the MicroChess project: https://github.com/ripred/MicroChess
 * 
 */
#ifndef BOARD_INCL
#define BOARD_INCL

#include <math.h>

struct spot_t {
    uint8_t  type : 3,     // one of the Piece types above
             side : 1,     // one of the Color types above
            moved : 1,     // 1 if moved
            check : 1;     // 1 if in check

    spot_t();
    spot_t(Piece p);
    spot_t(uint8_t t, uint8_t s, uint8_t m, uint8_t c);
};

/***
 * board_t version 1
 *
 */
struct board_t1 {
private:
    struct row_t {
        spot_t  cols[8];
    } rows[8];

public:
    Piece get(unsigned char index) const;

    void set(unsigned char index, Piece const piece);
};


/***
 * board_t version 2
 *
 */
struct board_t2 {
private:
    struct row_t {
        uint8_t  type1 : 3,     // one of the Piece types
                 side1 : 1,     // one of the Color types
                moved1 : 1,     // 1 if moved
                check1 : 1,     // 1 if in check

                 type2 : 3,
                 side2 : 1,
                moved2 : 1,
                check2 : 1,

                 type3 : 3,
                 side3 : 1,
                moved3 : 1,
                check3 : 1,

                 type4 : 3,
                 side4 : 1,
                moved4 : 1,
                check4 : 1,

                 type5 : 3,
                 side5 : 1,
                moved5 : 1,
                check5 : 1,

                 type6 : 3,
                 side6 : 1,
                moved6 : 1,
                check6 : 1,

                 type7 : 3,
                 side7 : 1,
                moved7 : 1,
                check7 : 1,

                 type8 : 3,
                 side8 : 1,
                moved8 : 1,
                check8 : 1;

    } rows[8];

public:
    Piece get(unsigned char index) const;

    void set(unsigned char index, Piece const piece);
};


struct board_t {
private:
    board_t2  board;

public:
    Piece get(unsigned char index) const;

    void set(unsigned char index, Piece const piece);
    
    void init();

    Piece getType(unsigned char from) const;
};

#endif // BOARD_INCL


board.h

/**
 * chessutil.cpp
 * 
 * the MicroChess project: https://github.com/ripred/MicroChess
 * 
 * MicroChess utility functions
 * 
 */

#include <Arduino.h>
#include <avr/pgmspace.h>
#include "MicroChess.h"
#include <stdarg.h>

print_t const level = Debug1;

// Bool isValidTest()
// {
// #ifdef TRACE_FAIL
//     auto trace = []() -> int {
//         static char const fmt[] PROGMEM = "\nerror: failed isValidPos(x,y) test 1!\n\n";
//         printf(Always, fmt);
//         return 0;
//     };
// #else
//     auto trace = []() -> int { return 0; };
// #endif
//     for (index_t y=0; y < 8; y++) {
//         for (index_t x=0; x < 8; x++) {
//             if (!isValidPos(x, y)) {
//                 return trace();
//             }
//         }
//     }

//     if (isValidPos(-1, 0) || isValidPos(0, -1) || isValidPos(8, 0) || isValidPos(0, 8)) {
//         return trace();
//     }

//     static char const fmt[] PROGMEM = "passed isValidPos(x,y) tests\n\n";
//     printf(Debug2, fmt);

//     return 1;
// }


Piece getType(Piece b) 
{
    return Type & b;
}

Bool isEmpty(Piece b) 
{
    return getType(b) == Empty;
}


int getValue(Piece b) 
{
    return pieceValues[getType(b)]; 
}


Piece getSide(Piece b) 
{ 
    return (Side & b) >> 3u; 
}


Bool hasMoved(Piece b) 
{ 
    return (Moved & b) == Moved; 
}


Bool inCheck(Piece b) 
{ 
    return (Check & b) == Check; 
}


Piece setType(Piece b, Piece type) 
{ 
    return (b & ~Type) | (type & Type); 
}


Piece setSide(Piece b, Piece side) {
    return (b & ~Side) | ((side << 3u) & Side); 
}


Piece setMoved(Piece b, Bool hasMoved) 
{ 
    return (b & ~Moved) | (hasMoved ? Moved : 0); 
}


Piece setCheck(Piece b, Bool inCheck) 
{ 
    return (b & ~Check) | (inCheck ? Check : 0); 
}


Piece makeSpot(Piece type, Piece side, unsigned char moved, unsigned char inCheck) {
    return setType(0, type) | setSide(0, side) | setMoved(0, moved) | setCheck(0, inCheck);
}


char *getName(Piece b) {
    static char const * names[] = {"Empty", "Pawn", "Knight", "Bishop", "Rook", "Queen", "King"};
    static const int num_names = ARRAYSZ(names);
    static const int type_offset = 0;

    int const type = getType(b);

    if (type < type_offset || type >= type_offset + num_names) {
        return nullptr;
    }

    return (char*) names[type + type_offset];
}


char *getColor(Piece b) 
{ 
    return getSide(b) == White ? (char*) "White" : (char*) "Black"; 
}


const char* addCommas(long int value) {
    static char buff[16];
    snprintf(buff, 16, "%ld", value);
    for (int i = strlen(buff) - 3; i > 0; i -= 3) {
        memmove(&buff[i + 1], &buff[i], strlen(buff) - i);
        buff[i] = ',';
    }
    return buff;
}

int printf(print_t const required, char const * const progmem, ...) {
    char fmt[100] = "";
    for (int i = 0; fmt[i] = pgm_read_byte_near(progmem + i), fmt[i] != 0; i++) {}
    if (level >= required) {
        char buff[100] = "";
        va_list argList;
        va_start(argList, fmt);
        vsnprintf(buff, ARRAYSZ(buff), fmt, argList);
        va_end(argList);
        return Serial.write(buff, strlen(buff));
    }

    return 0;
}

#include <unistd.h>

#ifdef __arm__
// should use uinstd.h to define sbrk but Due causes a conflict
extern "C" char* sbrk(int incr);
#else  // __ARM__
extern char *__brkval;
#endif  // __arm__

int freeMemory() {
    char top;
#ifdef __arm__
    return &top - reinterpret_cast<char*>(sbrk(0));
#elif defined(CORE_TEENSY) || (ARDUINO > 103 && ARDUINO != 151)
    return &top - __brkval;
#else  // __arm__
    return __brkval ? &top - __brkval : &top - __malloc_heap_start;
#endif  // __arm__
}

int freeMem() {
    extern int __heap_start/*, *__brkval */;
    int v;

    return (int)&v - (__brkval == 0  ? (int)&__heap_start : (int) __brkval);
}

void printMemoryStats() {
    // ============================================================
    // startup memory
    int totalRam = 2048;
    // int freeRam = freeMem();
    int freeRam = freeMemory();
    int usedRam = totalRam - freeRam;

    static char const fmt1[] PROGMEM = "Total SRAM = %d\n";
    printf(Debug2, fmt1, totalRam);
    static char const fmt2[] PROGMEM = "Free SRAM = %d\n";
    printf(Debug2, fmt2, freeRam);
    static char const fmt3[] PROGMEM = "Used SRAM = %d\n";
    printf(Debug2, fmt3, usedRam);

    static char const fmt4[] PROGMEM = "sizeof(move_t) = %d\n";
    printf(Debug2, fmt4, sizeof(move_t));
    static char const fmt5[] PROGMEM = "meaning there is room for %d more move_t entries.\n";
    printf(Debug2, fmt5, freeRam / sizeof(move_t) );
    static char const fmt6[] PROGMEM = "or %d more move_t entries per move list.\n";
    printf(Debug2, fmt6, ((freeRam / sizeof(move_t)) / 2) );
}


void show_piece(Piece const p) 
{
    Piece const type = getType(p);
    Color const side = getSide(p);

    static char const fmt[] PROGMEM = "%5s %s";
    printf(Debug1, fmt, 
        (Empty == type ?  "" : (White == side ?  "White" : "Black")), 
        (Empty == type ?  "Empty" :
          Pawn == type ?   "Pawn" :
        Knight == type ? "Knight" :
        Bishop == type ? "Bishop" :
          Rook == type ?   "Rook" :
         Queen == type ?  "Queen" : "King"));
}

void show_pieces() 
{
    static char const fmt1[] PROGMEM = "game.pieces[%2d] = {\n";
    printf(Debug1, fmt1, game.piece_count);
    for (int i = 0; i < game.piece_count; i++) {
        point_t const &loc = game.pieces[i];
        index_t const col = loc.x;
        index_t const row = loc.y;
        Piece  const p = board.get(col + row * 8);
        static char const fmt1[] PROGMEM = "    game.pieces[%2d] = %d, %d: ";
        printf(Debug1, fmt1, i, col, row);
        show_piece(p);
        static char const fmt2[] PROGMEM = "\n";
        printf(Debug1, fmt2);
    }
    static char const fmt2[] PROGMEM = "};\n";
    printf(Debug1, fmt2);
}


void show_move(move_t const &move) {
    index_t const    col = move.from % 8;
    index_t const    row = move.from / 8;
    index_t const   from = col + row * 8;
    Piece   const      p = board.get(from);
    index_t const to_col = move.to % 8;
    index_t const to_row = move.to / 8;

    show_piece(p);

    static char const fmt[] PROGMEM = " from: %d,%d (%c%c) to: %d,%d (%c%c)";
    printf(Debug1, fmt, 
        col,    row,       col + 'A', '8' -    row, 
        to_col, to_row, to_col + 'A', '8' - to_row);
}


chessutil.cpp

/**
 * game.h
 * 
 * the MicroChess project: https://github.com/ripred/MicroChess
 * 
 * header file for MicroChess
 * 
 */
#ifndef GAME_INCL
#define GAME_INCL

#include "board.h"

extern board_t board;

////////////////////////////////////////////////////////////////////////////////////////
// board spot by column and row
struct point_t 
{
public:
    index_t  x : NUM_BITS_PT, 
             y : NUM_BITS_PT;

public:
    point_t() : x(0), y(0) {}
    point_t(index_t X, index_t Y) : x(X), y(Y) {}

};  // point_t


////////////////////////////////////////////////////////////////////////////////////////
// the state of a game
struct game_t 
{
public:
    point_t   pieces[MAX_PIECES];
    move_t    moves1[MAX_MOVES];
    move_t    moves2[MAX_MOVES];
    Piece     taken1[16];
    Piece     taken2[16];
    Bool      white_king_in_check;
    Bool      black_king_in_check;
    move_t    last_move;
    uint8_t   piece_count;
    uint8_t   move_count1;
    uint8_t   move_count2;
    uint8_t   max_moves;
    uint8_t   taken_count1;
    uint8_t   taken_count2;
    uint8_t   eval_ndx,     // board index being currently evaluated
                  turn,     // 0 := Black, 1 := White
              move_num,     // increasing move number
                  done;     // 1 := game over
public:
    // constructor
    game_t()
    {
        init();
    }

    void init()
    {
        // initialize list of pieces in the game
        piece_count = 0;
        for (uint8_t ndx=0; ndx < BOARD_SIZE; ++ndx) {
            if (Empty == getType(board.get(ndx))) continue;
            if (piece_count < MAX_PIECES) {
                pieces[piece_count++] = point_t( ndx % 8, ndx / 8);
            }
        }

        move_count1 = 0;
        move_count2 = 0;

        max_moves = 0;

        taken_count1 = 0;
        taken_count2 = 0;

        last_move = { -1, -1, 0 };

        white_king_in_check = 0;
        black_king_in_check = 0;

        turn = White;
        move_num = 0;

        done = 0;
    }

};  // game_t

#endif // GAME_INCL

game.h

/**
 * king.cpp
 * 
 * the MicroChess project: https://github.com/ripred/MicroChess
 * 
 * move generation for kings
 * 
 */

#include <Arduino.h>
#include "MicroChess.h"

////////////////////////////////////////////////////////////////////////////////////////
// add the moves for a king to the proper list (game.moves1 or game.moves2)
void add_king_moves(index_t from, index_t col, index_t row, index_t fwd, Color side) {
    for (unsigned i=0; i < NUM_KING_OFFSETS; i++) {
        offset_t *ptr = pgm_get_far_address(knight_offsets);
        index_t to_col = col + ptr[i].x * fwd;
        index_t to_row = row + ptr[i].y * fwd;
        if (isValidPos(to_col, to_row)) {
            index_t to = to_col + (to_row * 8);
            Piece const op = board.get(to);
            if (Empty == getType(op) || getSide(op) != side) {
                add_move(side, from, to, 0);
            }
        }
    }
}

king.cpp

/**
 * knight.cpp
 * 
 * the MicroChess project: https://github.com/ripred/MicroChess
 * 
 * move generation for knights
 * 
 */

#include <Arduino.h>
#include "MicroChess.h"

////////////////////////////////////////////////////////////////////////////////////////
// add the moves for a knight to the proper list (game.moves1 or game.moves2)
void add_knight_moves(Piece p, index_t from, index_t col, index_t row, index_t fwd, Color side) {
    for (unsigned i=0; i < NUM_KNIGHT_OFFSETS; i++) {
        offset_t *ptr = pgm_get_far_address(knight_offsets);
        index_t to_col = col + ptr[i].x * fwd;
        index_t to_row = row + ptr[i].y * fwd;
        if (isValidPos(to_col, to_row)) {
            index_t to = to_col + (to_row * 8);
            Piece const op = board.get(to);
            if (Empty == getType(op) || getSide(op) != side) {
                add_move(side, from, to, 0);
            }
        }
    }
}

knight.cpp

/**
 * MicroChess.h
 * 
 * the MicroChess project: https://github.com/ripred/MicroChess
 * 
 * header file for MicroChess
 * 
 */
#ifndef MICROCHESS_INCL
#define MICROCHESS_INCL

#include <Arduino.h>

#pragma pack(1)

#include <stdio.h>
#include <limits.h>
#include <stddef.h>
#include <string.h>
#include <inttypes.h>

typedef unsigned char Color;
typedef unsigned char Piece;
typedef unsigned char Bool;

////////////////////////////////////////////////////////////////////////////////////////
// limits
enum 
{
    MAX_PIECES    =  32,
    MAX_MOVES     = 106,        // R:11 N:8 B:11 Q:22 K:8 B:11 N:8 R:11 P:16

    NUM_BITS_PT   =   5,        // bits per field in point_t struct
    NUM_BITS_SPOT =   7,        // bits per field in move_t struct

    NUM_KNIGHT_OFFSETS =  8,    // number of offsets to check for knight moves
    NUM_BISHOP_OFFSETS = 28,    // number of offsets to check for bishop moves
    NUM_ROOK_OFFSETS   = 28,    // number of offsets to check for rook moves
    NUM_QUEEN_OFFSETS  = 56,    // number of offsets to check for queen moves
    NUM_KING_OFFSETS   =  8,    // number of offsets to check for king moves
};

typedef   int8_t   index_t;

// structure to hold the offsets that a piece can move to
struct offset_t {
    index_t x, y;
};


////////////////////////////////////////////////////////////////////////////////////////
// the offsets a knight can move to
static offset_t const knight_offsets[NUM_KNIGHT_OFFSETS] PROGMEM = {
    { -2, +1 }, { -2, -1 }, { +2, +1 }, { +2, -1 }, 
    { +1, +2 }, { -1, +2 }, { +1, -2 }, { -1, -2 }  
};

////////////////////////////////////////////////////////////////////////////////////////
// the offsets a rook can move to
static offset_t const rook_offsets[NUM_ROOK_OFFSETS] PROGMEM = {
    { -1,  0 }, { -2,  0 }, { -3,  0 }, { -4,  0 }, { -5,  0 }, { -6,  0 }, { -7,  0 },     // W
    { +1,  0 }, { +2,  0 }, { +3,  0 }, { +4,  0 }, { +5,  0 }, { +6,  0 }, { +7,  0 },     // E
    {  0, +1 }, {  0, +2 }, {  0, +3 }, {  0, +4 }, {  0, +5 }, {  0, +6 }, {  0, +7 },     // N
    {  0, -1 }, {  0, -2 }, {  0, -3 }, {  0, -4 }, {  0, -5 }, {  0, -6 }, {  0, -7 }      // S
};

////////////////////////////////////////////////////////////////////////////////////////
// the offsets a bishop can move to
static offset_t const bishop_offsets[NUM_BISHOP_OFFSETS] PROGMEM = {
    { -1, +1 }, { -2, +2 }, { -3, +3 }, { -4, +4 }, { -5, +5 }, { -6, +6 }, { -7, +7 },     // NW
    { +1, +1 }, { +2, +2 }, { +3, +3 }, { +4, +4 }, { +5, +5 }, { +6, +6 }, { +7, +7 },     // NE
    { -1, -1 }, { -2, -2 }, { -3, -3 }, { -4, -4 }, { -5, -5 }, { -6, -6 }, { -7, -7 },     // SW
    { -1, +1 }, { -2, +2 }, { -3, +3 }, { -4, +4 }, { -5, +5 }, { -6, +6 }, { -7, +7 }      // SE
};

////////////////////////////////////////////////////////////////////////////////////////
// the offsets a queen can move to
static offset_t const queen_offsets[NUM_QUEEN_OFFSETS] = {
    { -1,  0 }, { -2,  0 }, { -3,  0 }, { -4,  0 }, { -5,  0 }, { -6,  0 }, { -7,  0 },     // W
    { +1,  0 }, { +2,  0 }, { +3,  0 }, { +4,  0 }, { +5,  0 }, { +6,  0 }, { +7,  0 },     // E
    {  0, +1 }, {  0, +2 }, {  0, +3 }, {  0, +4 }, {  0, +5 }, {  0, +6 }, {  0, +7 },     // N
    {  0, -1 }, {  0, -2 }, {  0, -3 }, {  0, -4 }, {  0, -5 }, {  0, -6 }, {  0, -7 },     // S
    { -1, +1 }, { -2, +2 }, { -3, +3 }, { -4, +4 }, { -5, +5 }, { -6, +6 }, { -7, +7 },     // NW
    { +1, +1 }, { +2, +2 }, { +3, +3 }, { +4, +4 }, { +5, +5 }, { +6, +6 }, { +7, +7 },     // NE
    { -1, -1 }, { -2, -2 }, { -3, -3 }, { -4, -4 }, { -5, -5 }, { -6, -6 }, { -7, -7 },     // SW
    { -1, +1 }, { -2, +2 }, { -3, +3 }, { -4, +4 }, { -5, +5 }, { -6, +6 }, { -7, +7 }      // SE
};

////////////////////////////////////////////////////////////////////////////////////////
// the offsets a king can move to
static offset_t const king_offsets[NUM_KING_OFFSETS] PROGMEM = {
    { -1,  0 }, { -1, +1 }, { +1,  0 }, { +1, +1 }, 
    {  0, +1 }, { -1, -1 }, {  0, -1 }, { +1, -1 }
};

////////////////////////////////////////////////////////////////////////////////////////
// macro to validate a location
// #define DEBUG_TRACE
#ifdef DEBUG_TRACE
#define TRACE_FAIL (printf(Debug3, level, "Failed isValidPos(...) at line: %d in %s\n", __LINE__, __FILE__),0)
#else
#define TRACE_FAIL 1
#endif
#define  isValidPos(col, row) ((col >= 0 && col < 8 && row >= 0 && row < 8) ? 1 : (TRACE_FAIL,0))

// print_t is used to set and control the output printing level
enum print_t {
    Error  =  0,        // always display
    Always =  0,
    Debug0, 
    Debug1, 
    Debug2, 
    Debug3,
    Debug4,
    Never  = 99,        // never display
    None   = 99,
};

// the global setting that affects the level of output detail
extern print_t const level;

// macro to return the number of elements in an array of any data type
#define  ARRAYSZ(A) (sizeof(A) / sizeof(*(A)))

// The max and min range for piece values
#define  MAX_VALUE ((long const)( 0b00000010000000))    // half the value of number of bits the 'value' field in move_t has
#define  MIN_VALUE ((long const)(0 - MAX_VALUE))

// the number of locations on the game board
static unsigned const BOARD_SIZE = 64u;

// The two sides
static Color const White = 1u;
static Color const Black = 0u;

// The Piece types
static Piece const Empty  = 0u;
static Piece const Pawn   = 1u;
static Piece const Knight = 2u;
static Piece const Bishop = 3u;
static Piece const Rook   = 4u;
static Piece const Queen  = 5u;
static Piece const King   = 6u;

// the masks for the Piece bit fields
static Piece const Type     = 0b00000111u;
static Piece const Side     = 0b00001000u;
static Piece const Moved    = 0b00010000u;
static Piece const Check    = 0b00100000u;

// show the game board
void show();

// test the validation macro
// Bool isValidTest();

// get the Type of a Piece
Piece getType(Piece b);

// see if a Piece is Empty
Bool  isEmpty(Piece b);

// get the value of a piece
int   getValue(Piece b);

// get the side for a Piece
Piece getSide(Piece b);

// see if a Piece has moved
Bool  hasMoved(Piece b);

// see if a Piece is in check
Bool  inCheck(Piece b);

// set the Type of a Piece
Piece setType(Piece b, Piece type);

// set the Color of a Piece
Piece setSide(Piece b, Piece side);

// set or reset the flag indicating a Piece as moved
Piece setMoved(Piece b, Bool hasMoved);

// set or reset the flag indicating a Piece is in check
Piece setCheck(Piece b, Bool inCheck);

// construct a Piece value
Piece makeSpot(Piece type, Piece side, Bool moved, Bool inCheck);

char *getName(Piece b);

char *getColor(Piece b);

// const char* addCommas(long int value);

int printf(print_t const required, char const * const fmt, ...);

static long const pieceValues[8] = {
            0,  // empty spot value
        10000,  // pawn value
        30000,  // knight value
        30000,  // bishop value
        50000,  // rook value
        90000,  // queen value
    MAX_VALUE,  // king value
            0   // padded for alignment and increased L1 and L2 cache hit gains
};

#include "board.h"
#include "move.h"
#include "game.h"

void show_move(move_t const &move);
void show_pieces();
void show_piece(Piece const p);

extern game_t game;

void add_move(Color side, index_t from, index_t to, long value);
void add_pawn_moves(Piece p, index_t from, index_t col, index_t row, index_t fwd, Color side);
void add_knight_moves(index_t from, index_t col, index_t row, index_t fwd, Color side);
void add_bishop_moves(index_t from, index_t col, index_t row, index_t fwd, Color side);
void add_rook_moves(index_t from, index_t col, index_t row, index_t fwd, Color side);
void add_queen_moves(index_t from, index_t col, index_t row, index_t fwd, Color side);
void add_king_moves(index_t from, index_t col, index_t row, index_t fwd, Color side);




#endif // MICROCHESS_INCL


MicroChess.h

MicroChess.ino

/**
 * move.h
 * 
 * the MicroChess project: https://github.com/ripred/MicroChess
 * 
 * header file for MicroChess
 * 
 */
#ifndef MOVE_INCL
#define MOVE_INCL

////////////////////////////////////////////////////////////////////////////////////////
// an entry in a move list
struct move_t 
{
public:
    int32_t  from : NUM_BITS_SPOT, 
               to : NUM_BITS_SPOT,
            value : ((sizeof(int32_t) * 8) - (NUM_BITS_SPOT * 2));

public:
    move_t() : from(0), to(0), value(0) { }
    move_t(index_t f, index_t t, long v) : from(f), to(t), value(v) {
        // if (!isValidPos(f%8,f/8) || !isValidPos(t%8,t/8)) {
        //     printf(Always, "error: adding invalid move %d, %d to %d, %d\n", f%8,f/8, t%8,t/8);
        // }
    }

};

#endif // MOVE_INCL

move.h

/**
 * pawn.cpp
 * 
 * the MicroChess project: https://github.com/ripred/MicroChess
 * 
 * move generation for pawns
 * 
 */

#include <Arduino.h>
#include "MicroChess.h"

////////////////////////////////////////////////////////////////////////////////////////
// add the moves for a pawn to the proper list (game.moves1 or game.moves2)
void add_pawn_moves(Piece p, index_t from, index_t col, index_t row, index_t fwd, Color side) {
    // see if we can move 1 spot in front of this pawn
    index_t to_col = col;
    index_t to_row = row + fwd;
    index_t to;
    Piece op = Empty;

    if (isValidPos(to_col, to_row)) {
        // get piece at location 1 spot in front of pawn
        index_t to = to_col + to_row * 8;
        Piece op = board.get(to);
        if (Empty == getType(op)) {
            add_move(side, from, to, 0);

            // see if we can move 2 spots in front of this pawn
            if (!hasMoved(p)) {
                to_col = col;
                to_row = row + fwd + fwd;
                if (isValidPos(to_col, to_row)) {
                    // get piece at location 2 spots in front of pawn
                    to = to_col + to_row * 8;
                    op = board.get(to);
                    if (Empty == getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
        }
    }

    // see if we can capture a piece diagonally to the left
    to_col = col - 1;
    to_row = row + fwd;
    to = to_col + to_row * 8;
    if (isValidPos(to_col, to_row)) {
        // get piece diagonally to the right
        op = board.get(to);
        if (Empty != getType(op) && getSide(op) != side) {
            add_move(side, from, to, 0);
        }
    }

    // see if we can capture a piece diagonally to the right
    to_col = col + 1;
    to_row = row + fwd;
    to = to_col + to_row * 8;
    if (isValidPos(to_col, to_row)) {
        // get piece diagonally to the right
        op = board.get(to);
        if (Empty != op && getSide(op) != side) {
            add_move(side, from, to, 0);
        }
    }

    // check for en-passant on the left
    to_col = col - 1;
    to_row = row + fwd;
    to = to_col + to_row * 8;
    if (isValidPos(to_col, to_row)) {
        // get piece diagonally to the right
        op = board.get(to);
    }
    index_t epx = to_col;
    if (isValidPos(to_col, to_row)) {
        // get piece diagonally to the right
        op = board.get(to);
        if (Empty != getType(op) && getSide(op) != side) {
            index_t last_move_from_row = game.last_move.from / 8;
            index_t last_move_to_col = game.last_move.to % 8;
            index_t last_move_to_row = game.last_move.to / 8;
            if (last_move_to_col == epx && last_move_to_row == row) {
                if (abs(int(last_move_from_row) - int(last_move_to_row)) > 1) {
                    if (getType(op) == Pawn) {
                        add_move(side, from, to, 0);
                    }
                }
            }
        }
    }

    // check for en-passant on the right
    to_col = col - 1;
    to_row = row + fwd;
    to = to_col + to_row * 8;
    if (isValidPos(to_col, to_row)) {
        // get piece diagonally to the right
        op = board.get(to);
    }
    epx = to_col;
    if (isValidPos(to_col, to_row)) {
        // get piece diagonally to the right
        op = board.get(to);
        if (Empty != getType(op) && getSide(op) != side) {
            index_t last_move_from_row = game.last_move.from / 8;
            index_t last_move_to_col = game.last_move.to % 8;
            index_t last_move_to_row = game.last_move.to / 8;
            if (last_move_to_col == epx && last_move_to_row == row) {
                if (abs(int(last_move_from_row) - int(last_move_to_row)) > 1) {
                    if (getType(op) == Pawn) {
                        add_move(side, from, to, 0);
                    }
                }
            }
        }
    }
}

pawn.cpp

/**
 * queen.cpp
 * 
 * the MicroChess project: https://github.com/ripred/MicroChess
 * 
 * move generation for queens
 * 
 */

#include <Arduino.h>
#include "MicroChess.h"

////////////////////////////////////////////////////////////////////////////////////////
// add the moves for a queen to the proper list (game.moves1 or game.moves2)
void add_queen_moves(index_t from, index_t col, index_t row, index_t fwd, Color side) {
    Bool continue_n = 1;
    Bool continue_s = 1;
    Bool continue_e = 1;
    Bool continue_w = 1;
    Bool continue_nw = 1;
    Bool continue_ne = 1;
    Bool continue_sw = 1;
    Bool continue_se = 1;

    for (unsigned i=0; i < NUM_QUEEN_OFFSETS; i++) {
        offset_t *ptr = pgm_get_far_address(queen_offsets);
        index_t xoff = ptr[i].x * fwd;
        index_t yoff = ptr[i].y * fwd;
        index_t to_col = col + xoff;
        index_t to_row = row + yoff;
        if (isValidPos(to_col, to_row)) {
            if (xoff == 0 && yoff > 0 && continue_n) { // going N
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_n = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
            else
            if (xoff == 0 && yoff < 0 && continue_s) { // going S
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_s = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
            else
            if (xoff < 0 && yoff == 0 && continue_w) { // going W
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_w = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
            else
            if (xoff > 0 && yoff == 0 && continue_e) { // going E
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_e = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
            else
            if (xoff < 0 && yoff > 0 && continue_nw) { // going NW
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_nw = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
            else
            if (xoff > 0 && yoff > 0 && continue_ne) { // going NE
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_ne = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
            else
            if (xoff < 0 && yoff < 0 && continue_sw) { // going SW
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_sw = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
            else
            if (xoff > 0 && yoff < 0 && continue_se) { // going SE
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_se = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
        }
    }
}

queen.cpp

/**
 * rook.cpp
 * 
 * the MicroChess project: https://github.com/ripred/MicroChess
 * 
 * move generation for rooks
 * 
 */

#include <Arduino.h>
#include "MicroChess.h"

////////////////////////////////////////////////////////////////////////////////////////
// add the moves for a rook to the proper list (game.moves1 or game.moves2)
void add_rook_moves(index_t from, index_t col, index_t row, index_t fwd, Color side) {
    Bool continue_n = 1;
    Bool continue_s = 1;
    Bool continue_e = 1;
    Bool continue_w = 1;

    for (unsigned i=0; i < NUM_ROOK_OFFSETS; i++) {
        offset_t *ptr = pgm_get_far_address(rook_offsets);
        index_t xoff = ptr[i].x * fwd;
        index_t yoff = ptr[i].y * fwd;
        index_t to_col = col + xoff;
        index_t to_row = row + yoff;
        if (isValidPos(to_col, to_row)) {
            if (xoff == 0 && yoff > 0 && continue_n) { // going N
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_n = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
            else
            if (xoff == 0 && yoff < 0 && continue_s) { // going S
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_s = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
            else
            if (xoff < 0 && yoff == 0 && continue_w) { // going W
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_w = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
            else
            if (xoff > 0 && yoff == 0 && continue_e) { // going E
                index_t to = to_col + (to_row * 8);
                Piece const op = board.get(to);
                if (Empty == getType(op)) {
                    add_move(side, from, to, 0);
                }
                else {
                    // there is a piece there
                    continue_e = 0;

                    // if it is the other side then capture it
                    if (side != getType(op)) {
                        add_move(side, from, to, 0);
                    }
                }
            }
        }
    }
}