/*
    File: board.h

    Content on and manipulation of a chess board implemented as 10x12 squares,
    with default out_of_border values.

    "magic" numbers will be used, they aren't magic if you know this structure.
    Source way too messy with a lot of variable names and variable calculations instead of plain numbers.

    Author: Ken Rouwas
    Date 2017-09-14
*/

#pragma once

#include <array>

namespace Chess{

    const size_t board_size = 10*12;

    enum class Color { white, black, none };

    enum class Piece {
        king,       // a king without castle potential
        king_castle,    // a king with castle potential
        queen,
        pawn,       // a pawn without en passant potential
        pawn_en_passant, // a pawn with en passant potential
        rook,
        rook_castle,
        knight,
        bishop,
        none,
        out_of_board    // Illegal position
    };

    struct Square {
        Color piece_color;
        Piece piece;
        Square(Piece, Color);
        Square();
    };

    class Board {
        private:
            std::array<Square, board_size> squares;
        public:
            void set(const size_t where, Square);
            Square get(const size_t where) const;
    };

    void init_classic_board(Board&);

}

// File: board.cpp

#include "board.h"


namespace Chess {
    Square::Square(Piece p, Color c){
        piece = p;
        piece_color = c;
    }

    Square::Square(){
        piece = Piece::out_of_board;
        piece_color = Color::none;
    }


    void Board::set(const size_t where, Square s) {
        if (where >= board_size)
            return;
        squares[where] = s;
    }

    Square Board::get(const size_t where) const {
        if (where >= board_size)
            return Square (Piece::out_of_board, Color::none);
        return squares[where];
    }

    void init_classic_board(Board& b) {
        // Place pawns
        for(size_t i = 0; i < 8; ++i){
            b.set(31 /*col 1, 2nd row*/ + i, Square(Piece::pawn, Color::black));
            b.set(81 /*col 1, 7th row*/ + i, Square(Piece::pawn, Color::white));
        }

        // Place the rest but with s/kings/queens
        int w = 0;
        for( auto p : {Piece::rook_castle, Piece::knight, Piece::bishop, Piece::queen} ) {
            b.set(21+w, Square(p, Color::black));
            b.set(28 /*col 8, 1st row*/ - w, Square(p, Color::black));
            b.set(91 /*col 1, 8th row*/ + w, Square(p, Color::white));
            b.set(98 /*col 8, 8th row*/ - w, Square(p, Color::white));
            ++w;
        }

        // Place kings
        b.set(25, Square(Piece::king_castle, Color::black));
        b.set(95, Square(Piece::king_castle, Color::white));

        // Empty squares inbetween the pieces
        for(int x=0; x < 8; ++x)
            for(int y=0; y < 4; ++y)
                b.set(41+x+y*10,Square(Piece::none, Color::none));
    }

}

/*
    File: move.h

    Move utils and move history utils.
    Assumes that a history list and the board it's used with are consistent.

    Boardhistory:
    A move event consists of a series of board changes and a "move done",
    namely BoardChange.where == (boardsize = move_done), which is pushed last for each move event.

    Author: Ken Rouwas
    Date 2017-09-14
*/

#pragma once

#include <list>
#include <vector>

#include "board.h"

namespace Chess {

    const size_t move_done = board_size;

    struct Move {
        ssize_t from, to;
        Move(ssize_t, ssize_t);
        Move();
    };

    struct BoardChange {
        size_t where;
        Square old_square;
    };

    using Boardhistory = std::list<BoardChange>;
    using MoveSet = std::vector<Move>;

    void undo_move(Board&, Boardhistory&);

    /* Castling is identified by king move to its castling destination if permitted.
       Pawn promotion move deduced.
       All other moves are unconditional moves.
    */
    void do_move(Move, Board&, Boardhistory&, Piece pawn_promotion = Piece::queen);

    MoveSet valid_moves(Board&, Color turn); // This is the move generator

}

#include <iostream>
#include "move.h"

// Read move.h for specifications

namespace Chess {

    Move::Move(ssize_t _from, ssize_t _to) {
        from = _from;
        to = _to;
    }

    Move::Move(){}

    void undo_move(Board& b, Boardhistory& ml){
        if(!ml.size())
            return;
        if(ml.back().where == move_done)
            ml.pop_back();

        while(ml.size() && ml.back().where != move_done){
            b.set( ml.back().where, ml.back().old_square );
            ml.pop_back();
        }
    }

    static void do_change(Board& b, Boardhistory& bh, size_t where, Square new_square) {
        BoardChange change;
        change.old_square = b.get(where);
        change.where = where;
        bh.push_back(change);
        b.set(where, new_square);
    }

    void do_move(Move m, Board& b, Boardhistory& bh, Piece pawn_promotion){
        // Pawn promotion
        if(b.get(m.from).piece == Piece::pawn && m.to/10 == 2)
                do_change(b, bh, m.from, Square(pawn_promotion, Color::white));

        if(b.get(m.from).piece == Piece::pawn && m.to/10 == 9)
                do_change(b, bh, m.from, Square(pawn_promotion, Color::black));

        // Move rook if castling
        if(b.get(m.from).piece == Piece::king_castle && (m.from-m.to == 2 || m.from-m.to == -2)){
            if(m.to == 23){
                do_change(b, bh, 21, Square(Piece::none, Color::none));
                do_change(b, bh, 24, Square(Piece::rook, Color::black));
            }

            if(m.to == 27){
                do_change(b, bh, 28, Square(Piece::none, Color::none));
                do_change(b, bh, 26, Square(Piece::rook, Color::black));
            }

            if(m.to == 93){
                do_change(b, bh, 91, Square(Piece::none, Color::none));
                do_change(b, bh, 94, Square(Piece::rook, Color::white));
            }

            if(m.to == 97){
                do_change(b, bh, 98, Square(Piece::none, Color::none));
                do_change(b, bh, 96, Square(Piece::rook, Color::white));
            }
        }


        Piece pawn_replaced = b.get(m.to).piece;
        // Regular piece move
        do_change(b, bh, m.to, b.get(m.from));
        do_change(b, bh, m.from, Square(Piece::none, Color::none));


         // Pawn replaced empty square
        if(b.get(m.to).piece == Piece::pawn && pawn_replaced == Piece::none) {
            // En passant move
            if(b.get(m.from-1).piece == Piece::pawn_en_passant && (m.from-m.to == 11 || m.from-m.to == -9))
                do_change(b, bh, m.from-1, Square(Piece::none, Color::none));
            else if (b.get(m.from+1).piece == Piece::pawn_en_passant  && (m.from-m.to == 9 || m.from-m.to == -11))
                do_change(b, bh, m.from+1, Square(Piece::none, Color::none));
        }


        // clear flag of pawns with en passant potential
        for(size_t i=1; i < 9; ++i){
            if(b.get(50+i).piece == Piece::pawn_en_passant)
                do_change(b, bh, 50+i, Square(Piece::pawn, Color::black));
            if(b.get(60+i).piece == Piece::pawn_en_passant)
                do_change(b, bh, 60+i, Square(Piece::pawn, Color::white));
        }

        // Give two-square moved pawns en passant flag
        if(b.get(m.to).piece == Piece::pawn) {
            if(m.from/10 == 3 && m.to/10 == 5)
                do_change(b, bh, m.to, Square(Piece::pawn_en_passant, Color::black));

            if(m.from/10 == 8 && m.to/10 == 6)
                do_change(b, bh, m.to, Square(Piece::pawn_en_passant, Color::white));
        }

        // Lose castling potential
        if(b.get(m.to).piece == Piece::king_castle)
            do_change(b, bh, m.to, Square(Piece::king, b.get(m.to).piece_color));
        if(b.get(m.to).piece == Piece::rook_castle)
            do_change(b, bh, m.to, Square(Piece::rook, b.get(m.to).piece_color));

        BoardChange done;
        done.where = move_done;
        bh.push_back(done);
    }

    MoveSet valid_moves(Board& b, Color turn){
        MoveSet ret;
        Color enemy_color = (turn == Color::white) ? Color::black : Color::white;
        int pawn_dir = (turn == Color::white) ? -1 : 1;


        for(size_t from = 21 /*skip padding*/; from < 99 /*padding after this*/ ; ++from){
            if(b.get(from).piece_color == turn){
                switch(b.get(from).piece){
                    case Piece::king_castle:
                        if(from == 95 && b.get(96).piece == Piece::none && b.get(97).piece == Piece::none && b.get(98).piece == Piece::rook_castle)
                            ret.push_back(Move(from, 97));
                        if(from == 25 && b.get(26).piece == Piece::none && b.get(27).piece == Piece::none && b.get(28).piece == Piece::rook_castle)
                            ret.push_back(Move(from, 27));
                        if(from == 95 && b.get(94).piece == Piece::none && b.get(93).piece == Piece::none && b.get(92).piece == Piece::none && b.get(91).piece == Piece::rook_castle)
                            ret.push_back(Move(from, 93));
                        if(from == 25 && b.get(24).piece == Piece::none && b.get(23).piece == Piece::none && b.get(22).piece == Piece::none && b.get(21).piece == Piece::rook_castle)
                            ret.push_back(Move(from, 23));
                    // fallthrough
                    case Piece::king:
                        for(auto to : {from-11, from-10, from-9,from-1, from+1, from+9, from+10,from+11}) {
                            if(b.get(to).piece_color == turn || b.get(to).piece == Piece::out_of_board)
                                continue;
                            ret.push_back(Move(from, to));
                        }
                        break;
                    case Piece::pawn:
                        if(b.get(from+pawn_dir*11).piece_color == enemy_color)
                            ret.push_back(Move(from, from+pawn_dir*11));
                        if(b.get(from+pawn_dir*9).piece_color == enemy_color)
                            ret.push_back(Move(from, from+pawn_dir*9));
                        if(b.get(from+pawn_dir*10).piece == Piece::none)
                            ret.push_back(Move(from, from+pawn_dir*10));
                        if(b.get(from+pawn_dir*10).piece == Piece::none && b.get(from+pawn_dir*20).piece == Piece::none){
                            size_t row = from/10;
                            if((row == 3 && pawn_dir == 1) || (row == 8 && pawn_dir == -1))
                                ret.push_back(Move(from, from+pawn_dir*20));
                        }
                        if(b.get(from-1).piece == Piece::pawn_en_passant && pawn_dir == -1)
                            ret.push_back( Move(from, from-11) );
                        if(b.get(from+1).piece == Piece::pawn_en_passant && pawn_dir == -1)
                            ret.push_back( Move(from, from-9) );
                        if(b.get(from-1).piece == Piece::pawn_en_passant && pawn_dir == 1)
                            ret.push_back( Move(from, from+9) );
                        if(b.get(from+1).piece == Piece::pawn_en_passant && pawn_dir == 1)
                            ret.push_back( Move(from, from+11) );
                        break;
                    case Piece::knight:
                        for(auto to : {from+8, from+12, from+19, from+21, from-8, from-12, from-21, from-19}) {
                            if(b.get(to).piece_color == turn || b.get(to).piece == Piece::out_of_board)
                                continue;
                            ret.push_back(Move(from, to));
                        }
                        break;
                    case Piece::queen:
                    //fallthrough
                    case Piece::rook:
                    case Piece::rook_castle:
                        for(int dd : {1,-1,10,-10})
                            for(int d=dd; b.get(from+d).piece_color != b.get(from).piece_color && b.get(from+d).piece != Piece::out_of_board ;d+=dd) {
                                ret.push_back(Move(from, from+d));
                                if(b.get(from+d).piece != Piece::none)
                                    break;
                            }
                    if(b.get(from).piece != Piece::queen)
                        break;
                    case Piece::bishop:
                        for(int dd : {9,11,-9,-11})
                            for(int d=dd; b.get(from+d).piece_color != b.get(from).piece_color && b.get(from+d).piece != Piece::out_of_board ;d+=dd) {
                                ret.push_back(Move(from, from+d));
                                if(b.get(from+d).piece != Piece::none)
                                    break;
                            }
                        break;
                    default: // warnings unwanted
                    break;
                }
            }
        }
        return ret;
    }
}

/*
    // File: main.cpp

    TODO: don't allow moves that leaves king in check, and count check-mate as victory. Hence, perft will be off by a few.
    TODO: prompt pawn promotion, instead of the default queen.
    TODO: handle cases of no valid moves
*/

#include <iostream>
#include <ctime>
#include "board.h"
#include "move.h"
#include "gui.h"
#include "ai.h"

using namespace Chess;


unsigned long perft(Board &b, Boardhistory &h, int depth, Color turn) {
    turn = (turn == Color::white) ? Color::black : Color::white;
    if(!depth)
        return 1;
    int leafs = 0;
    for(Move m : valid_moves(b, turn)){
        if(b.get(m.to).piece == Piece::king || b.get(m.to).piece == Piece::king_castle){
            ++leafs;
            continue;
        }
        do_move(m,b,h);
        leafs += perft(b,h,depth-1,turn);
        undo_move(b,h);
    }
    return leafs;
}


int main(){
    std::cout<<"nChesscpu 1.0nn";
    std::cout<<"Commands:nyxyx: fromto move.n0: regret move (last AI move will be reverted as well).n1: change color (AI will make this move)n2: exit.nn";
    Board b;
    Boardhistory h;
    init_classic_board(b);

    Color turn = Color::white;
    Color ai_color = Color::black;

    bool ai_has_king = true;
    bool human_has_king = true;


    if(false) {
        unsigned long t = time(0);
        std::cout<<"DEBUG: Perft(5) result (expecting 4897256): "<<perft(b,h,5,Color::black);
        t = time(0) - t;
        std::cout<<"nTime "<<t<<"n";
        return 0;
    }

    if(false){
        Move mv;
        unsigned long t = time(0);
        ai_move(b, h, turn, 7, mv);
        t = time(0) - t;
        std::cout<<"nAI Time: "<<t<<"n";
        return 0;
    }

    Move mv {0,0};
    while(ai_has_king && human_has_king){
        print_board(b, mv);
        if(turn == ai_color)
            ai_move(b, h, turn, 7, mv);
        else
            mv = read_move(valid_moves(b, turn), turn);

        if(mv.from == 0) {
            undo_move(b,h);
            undo_move(b,h);
            continue;
        } else if (mv.from == 1) {
            ai_color = ai_color == Color::white ? Color::black : Color::white;
            continue;
        } else if (mv.from == 2) {
            human_has_king = false;
            break;
        }

        do_move(mv, b, h);
        turn = turn == Color::white ? Color::black : Color::white;

        ai_has_king = human_has_king = false;
        for(size_t i = 21; i < 99; ++i) { // board.h about these magic numbers
            if(b.get(i).piece == Piece::king || b.get(i).piece == Piece::king_castle) {
                if(b.get(i).piece_color == ai_color) {
                    ai_has_king = true;
                } else {
                    human_has_king = true;
                }
            }
        }

    }
    print_board(b, mv);

    std::cout<<"nn";
    if(!human_has_king)
        std::cout<<"You lose.";
    if(!ai_has_king)
        std::cout<<"You win.";
    std::cout<<"nnBye!nn";
}

/*
    File: ai.h

    Takes a board, returns an heuristically optimized move.

    Author: Ken Rouwas
    Date 2017-09-14
*/

#pragma once

#include "move.h"

namespace Chess {
    int ai_move(Board& b, Boardhistory& bh, Color turn, int depth, Move& _bm, int alpha = -400, int beta = 400);
}

// See board.h on "magic numbers"
// File: ai.cpp

#include "ai.h"
#include <random>
#include <algorithm>
#include <iostream>


namespace Chess {
    std::mt19937 mt(time(0));


    void moveorder(MoveSet& ms) {
        std::random_shuffle(ms.begin(), ms.end());
    }

    static int evaluate_leaf(const Board& b) {
        int sum = 0;
        for(size_t i = 21; i < 99; ++i) {
            if(b.get(i).piece_color == Color::none)
                continue;
            int c = b.get(i).piece_color == Color::white ? 1 : -1;
            int v = 0;
            switch(b.get(i).piece){
                case Piece::pawn:
                case Piece::pawn_en_passant:
                    v = 1;
                    break;
                case Piece::rook:
                case Piece::rook_castle:
                    v = 5;
                    break;
                case Piece::knight:
                case Piece::bishop:
                    v = 3;
                    break;
                case Piece::queen:
                    v = 9;
                    break;
                default:
                break;
            }
            sum += c*v;
        }
        return sum;
    }

    static Color flipped_turn(Color turn) {
        if(turn == Color::white)
            return Color::black;
        return Color::white;
    }

    int ai_move(Board& b, Boardhistory& bh, Color turn, int depth, Move& _bm, int alpha, int beta) {
            /*
            MoveSet valid = valid_moves(b, turn);
            _bm = valid[mt()%valid.size()];
            return 0;
            */

        Move best_move;
        int best_score = turn == Color::white ? -300 : 300;
        if(!depth)
            return evaluate_leaf(b);

        MoveSet vmoves = valid_moves(b, turn);
        moveorder(vmoves);
                //int progress = 0; // Temporary hack to show progress
        for(Move m : vmoves){
                //if(depth == 8) // Temporary hack to show progress
                //  std::cout<<"r"<<++progress<<"/"<<vmoves.size()<<std::flush;

            if(b.get(m.to).piece == Piece::king || b.get(m.to).piece == Piece::king_castle){
                best_score = turn==Color::white ? 200+depth : -200-depth;
                best_move = m;
                break;
            }

            do_move(m, b, bh);
            int new_score = ai_move(b, bh, flipped_turn(turn), depth-1, _bm, alpha, beta);
            undo_move(b,bh);

            if((turn == Color::white && new_score > best_score) || (turn == Color::black && new_score < best_score)){
                best_move = m;
                best_score = new_score;

                if(turn == Color::black) {
                    beta = new_score;
                    if(beta <= alpha)
                        break;
                }

                if(turn == Color::white) {
                    alpha = new_score;
                    if(alpha >= beta)
                        break;
                }
            }

        }
        _bm = best_move;
        return best_score;

    }
}

/*
    File: gui.h

    Interactive graphical interface of a chess board.

    This is temporarily a quick and dirty solution.

    Author: Ken Rouwas
    Date 2017-09-15
*/

#pragma once

#include <vector>
#include "board.h"
#include "move.h"

namespace Chess {

    void print_board(const Board&, Move last_move);

    /* Returns when one of the provided valid moves is read */
    Move read_move(const MoveSet& valid_moves, Color turn);

}

// File: gui.cpp
// This is quick, ugly, pragmatic, temporary.

#include <iostream>
#include <cctype>
#include <map>
#include "gui.h"



namespace Chess {

    using namespace std;

    static const std::map<Piece, char> sprites = {
        { Piece::pawn,      'A' },
        { Piece::pawn_en_passant,   'P' },
        { Piece::rook,      'H' },
        { Piece::rook_castle,   'H' },
        { Piece::knight,        'F' },
        { Piece::bishop,        'I' },
        { Piece::king,      'K' },
        { Piece::king_castle,   'K' },
        { Piece::none,      '+' },
        { Piece::out_of_board,      '#' },
        { Piece::queen,         'Q' }
    };

    void print_board(const Board& b, Move last_move) {
        cout<<"n   1 2 3 4 5 6 7 8";
        for(ssize_t i=20; i < (ssize_t)board_size; ++i){
            if(i%10 == 9)
                continue;
            if(i/10 == 10)
                break;
            if(i%10 == 0) {
                cout<<"n "<<i/10<<" ";
                continue;
            }
            char s = sprites.at(b.get(i).piece);
            if(b.get(i).piece_color == Color::black)
                s = tolower(s);
            cout<<s;
            if(last_move.from == i || last_move.to == i)
                cout<<'<';
            else
                cout<<' ';
        }
        cout<<"n"<<endl;
    }

    Move read_move(const MoveSet& valid_moves, Color turn) {
        if(cin.fail()) {
            cin.clear();
            string dummy;
            cin >> dummy;
        }

        int in;
        Move ret;
        cout<<"Your move, "<<( turn == Color::white ? "white" : "black" )<<": ";
        cin>>in;

        // Command to undo 1 or 2 moves (2 to revert AI+own)
        if(in == 0 || in == 1 || in == 2){
            ret.from = in;
            return ret;
        }

        ret.to  = in%10+in/10%10*10;
        in /= 100;
        ret.from  = in%10+in/10%10*10;

        for(const auto m : valid_moves)
            if(m.from == ret.from && m.to == ret.to)
                return ret;
        cout<<"Invalid moven";
        return read_move(valid_moves, turn);
    }

}

if (m.to == 23) { // why 23? What is its meaning?
    do_change(b, bh, 21, Square(Piece::none, Color::none)); // why 21?
    do_change(b, bh, 24, Square(Piece::rook, Color::black)); // why 24?
}

void init_classic_board(Board&);

Board b = init_classic_board();

static const std::map<Piece, char> sprites = {
    { Piece::pawn,      '        A' },
    { Piece::pawn_en_passant,   'P' },
    { Piece::rook,              'H' },
    { Piece::rook_castle,       'H' },
    { Piece::knight,            'F' },
    { Piece::bishop,            'I' },
    { Piece::king,              'K' },
    { Piece::king_castle,       'K' },
    { Piece::none,              '+' },
    { Piece::out_of_board,      '#' },
    { Piece::queen,             'Q' }
};

static const std::map<Piece, char> sprites = {
    { Piece::pawn,      'A' },
    { Piece::pawn_en_passant,   'P' },
    { Piece::rook,      'H' },
    { Piece::rook_castle,   'H' },
    { Piece::knight,        'F' },
    { Piece::bishop,        'I' },
    { Piece::king,      'K' },
    { Piece::king_castle,   'K' },
    { Piece::none,      '+' },
    { Piece::out_of_board,      '#' },
    { Piece::queen,         'Q' }
};