/*
 * Ataxx analyzer - think about a chosen set of moves from a given rectangular Ataxx board state.
 * Copyright (C) 2004  Mark A. Fitzgerald
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * To contact the author, email at mark DOT fitzgerald2 AT sympatico DOT ca.
 */

/*
 * This program is not in any way interactive.  However, one can set up most any Ataxx board and
 * set of moves to investigate -- modify lines 394-400 to do this.
 */

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

//Factory.
class Move
{
    Move() {}
    Move(int srcRow, int srcCol, int destRow, int destCol)
        : srcRow(srcRow), srcCol(srcCol), destRow(destRow), destCol(destCol) {}

    bool bPass;
    bool bInvalidMove;

public:
    int srcRow, srcCol, destRow, destCol;

    static Move createMove(int srcRow, int srcCol, int destRow, int destCol)
    {
        Move move(srcRow, srcCol, destRow, destCol);
        move.bPass = false; move.bInvalidMove = false;
        assert(move.distance() <= 8 && move.distance() != 0);  //invalid move
        return move;
    }

    static Move createPass()
    {
        Move move;
        move.bPass = true; move.bInvalidMove = false;
        return move;
    }

    static Move createInvalidMove()
    {
        Move move;
        move.bPass = false; move.bInvalidMove = true;
        return move;
    }

    int distance() {
        return (destRow - srcRow) * (destRow - srcRow)
            + (destCol - srcCol) * (destCol - srcCol);
    }

    bool isGrow() { return (distance() <= 2); }
    bool isHop() { return !isGrow(); }
    bool isPass() { return bPass; }
    bool isInvalid() { return bInvalidMove; }

    void printToStdout()
    {
        if (isPass())
        {
            cout << "0";
        }
        else
        {
            if (isHop())
            {
                cout << static_cast<char>('a' + srcRow) << (srcCol+1);
            }
            cout << static_cast<char>('a' + destRow) << (destCol+1);
        }
    }
};

class MoveSequenceAndScore
{
    MoveSequenceAndScore() {}

public:
    vector<Move> moves;
    int score;

    static MoveSequenceAndScore scoreWithoutMove(int score)
    {
        MoveSequenceAndScore mss;
        mss.score = score;
        return mss;
    }

    static MoveSequenceAndScore createMSS(Move move, int score)
    {
        MoveSequenceAndScore mss;
        mss.moves.push_back(move);
        mss.score = score;
        return mss;
    }
};

class MoveAndFlippedNbrs
{
private:
    bool flippedNbrs[3][3];

public:
    Move move;

    MoveAndFlippedNbrs(Move move)
        : move(move)
    {
        for (int deltaRow = -1; deltaRow <= 1; ++deltaRow)
            for (int deltaCol = -1; deltaCol <= 1; ++deltaCol)
                flippedNbrs[deltaRow+1][deltaCol+1] = false;
    }

    void setFlip(int deltaRow, int deltaCol)
    {
        flippedNbrs[deltaRow+1][deltaCol+1] = true;
    }
    bool getFlip(int deltaRow, int deltaCol)
    {
        return flippedNbrs[deltaRow+1][deltaCol+1];
    }
};

//Assumes a two-player game.
class AtaxxGame
{
private:
    vector<vector<int> > board;
    vector<MoveAndFlippedNbrs> movesAndFlips;
    int playerToMove, nRed, nBlue;
    int nCols;  //precalculated, as it is used very frequently (40% of CPU time to call board[0].size frequently!)).

public:
    AtaxxGame(int nRows, int nCols)
    {
        playerToMove = 1;

        assert(nRows > 0 && nCols > 0);

        //Create the board.
        board.resize(nRows);
        for (int iRow = 0; iRow < nRows; ++iRow)
            board.at(iRow).resize(nCols);

        //Blank the board.
        for (int iRow = 0; iRow < nRows; ++iRow)
            for (int iCol = 0; iCol < nCols; ++iCol)
                board.at(iRow).at(iCol) = 0;  //blank

        //Set the four corners of the board, and the piece counts.
        board.at(0).at(0) = 1;  //red
        board.at(0).at(nCols-1) = 2;  //blue
        board.at(nRows-1).at(0) = 2;  //blue
        board.at(nRows-1).at(nCols-1) = 1;  //red
        nRed = nBlue = 2;

        this->nCols = nCols;
    }

    int nMovesMade() { return movesAndFlips.size(); }
    Move getMoveMade(int iMove) { return movesAndFlips.at(iMove).move; }
    int getNRows() { return board.size(); }
    int getNCols() { return nCols; }
    int getPlayerToMove() { return playerToMove; }
    int getTileContents(int iRow, int iCol) { return board[iRow][iCol]; }  //.at(iRow).at(iCol); }
    int getNRed() { return nRed; }
    int getNBlue() { return nBlue; }
    int getNBlank() { return (getNRows() * getNCols()) - getNRed() - getNBlue(); }

    bool gameIsOver()
    {
        if (nMovesMade() >= 2)
        {
            if (getMoveMade(nMovesMade() - 1).isPass()
                && getMoveMade(nMovesMade() - 2).isPass())
            {
                return true;
            }
        }

        if (getNRed() == 0 || getNBlue() == 0 || getNBlank() == 0)
        {
            return true;
        }

        return false;
    }

    //Make the specified move, flip opposing neighbours of the destination tile, then update
    //the player to move.
    void makeMove(Move move)
    {
        MoveAndFlippedNbrs moveAndFlips(move);
        int opposingPlayer = (getPlayerToMove()==1)?2:1;

        if (move.isPass() == false)
        {
            //Make the move.
            if (move.distance() > 2) {
                board.at(move.srcRow).at(move.srcCol) = 0;  //clear the source of a 'hop'.
            } else {
                //It's a 'grow' move.
                if (getPlayerToMove() == 1)
                    ++nRed;
                else
                    ++nBlue;
            }
            board.at(move.destRow).at(move.destCol) = getPlayerToMove();

            //Flip neighbours, then store move and flips.
            for (int nbrRow = move.destRow-1; nbrRow <= move.destRow+1; ++nbrRow)
            {
                if (nbrRow < 0 || nbrRow >= getNRows())
                    continue;
                for (int nbrCol = move.destCol-1; nbrCol <= move.destCol+1; ++nbrCol)
                {
                    if (nbrCol < 0 || nbrCol >= getNCols())
                        continue;
                    if (board.at(nbrRow).at(nbrCol) == opposingPlayer)
                    {
                        //Flip the opposing neighbour.
                        board.at(nbrRow).at(nbrCol) = getPlayerToMove();
                        if (getPlayerToMove() == 1) {
                            ++nRed; --nBlue;
                        } else {
                            ++nBlue; --nRed;
                        }
                        moveAndFlips.setFlip(nbrRow - move.destRow, nbrCol - move.destCol);
                    }
                }
            }
        }

        movesAndFlips.push_back(moveAndFlips);

        //Change the player to move.
        playerToMove = opposingPlayer;
    }

    void undoLastMove()
    {
        assert(movesAndFlips.size() > 0);

        //Unflip neighbours.
        MoveAndFlippedNbrs lastMoveAndFlip = movesAndFlips.back();
        int playerUndoingMove = (getPlayerToMove()==1)?2:1;
        if (lastMoveAndFlip.move.isPass() == false)
        {
            for (int dRow = -1; dRow <= 1; ++dRow)
            {
                for (int dCol = -1; dCol <= 1; ++dCol)
                {
                    if (lastMoveAndFlip.getFlip(dRow, dCol))
                    {
                        board.at(lastMoveAndFlip.move.destRow + dRow)
                            .at(lastMoveAndFlip.move.destCol + dCol) = getPlayerToMove();

                        if (getPlayerToMove() == 1) {
                            ++nRed; --nBlue;
                        } else {
                            ++nBlue; --nRed;
                        }
                    }
                }
            }

            //Remove destination piece.
            board.at(lastMoveAndFlip.move.destRow).at(lastMoveAndFlip.move.destCol) = 0;

            //Restore source piece (redundanct if 'grow', but that okay.)
            if (lastMoveAndFlip.move.isHop()) {
                board.at(lastMoveAndFlip.move.srcRow).at(lastMoveAndFlip.move.srcCol) = playerUndoingMove;
            } else {
                if (playerUndoingMove == 1) {
                    --nRed;
                } else {
                    --nBlue;
                }
            }
        }

        //Reduce history size by 1, and change player to move.
        movesAndFlips.pop_back();
        playerToMove = playerUndoingMove;
    }

    //Only a pass is legal if the player has nowhere to move.  If two passes in a row occur,
    //the game is over, and no further move is legal.
    vector<Move> getLegalMoves()
    {
        vector<Move> legalMoves;

        if (gameIsOver())
            return legalMoves;

        //Find 'grow' moves first.  First, search for a blank tile.
        for (int destRow = 0; destRow < getNRows(); ++destRow) {
            for (int destCol = 0; destCol < getNCols(); ++destCol) {
                if (getTileContents(destRow, destCol) != 0)
                    continue;

                //Then, find a neighbouring source to grow from.
                findNeighbouringSource(destRow, destCol, legalMoves);
            }
        }

        //Now find 'hop' moves.  Do this in a separate loop to perhaps increase alpha-beta efficiency.
        for (int srcRow = 0; srcRow < getNRows(); ++srcRow)
        {
            for (int srcCol = 0; srcCol < getNCols(); ++srcCol)
            {
                if (getTileContents(srcRow, srcCol) != getPlayerToMove())
                    continue;

                for (int destRow = srcRow - 2; destRow <= srcRow + 2; ++destRow)
                {
                    if (destRow < 0 || destRow >= getNRows())
                        continue;
                    for (int destCol = srcCol - 2; destCol <= srcCol + 2; ++destCol)
                    {
                        if (destCol < 0 || destCol >= getNCols())
                            continue;
                        if (getTileContents(destRow, destCol) != 0)
                            continue;

                        //We've found a good 'hop' move?
                        Move candidateMove = Move::createMove(srcRow, srcCol, destRow, destCol);
                        if (candidateMove.isHop())
                            legalMoves.push_back(candidateMove);
                    }
                }
            }
        }

        //If no regular moves exist, a 'pass' is the only legal move.
        if (legalMoves.size() == 0)
            legalMoves.push_back(Move::createPass());

        return legalMoves;
    }

private:
    void findNeighbouringSource(int destRow, int destCol, vector<Move>& legalMoves)
    {
        for (int srcRow = destRow - 1; srcRow <= destRow + 1; ++srcRow)
        {
            if (srcRow < 0 || srcRow >= getNRows())
                continue;
            for (int srcCol = destCol - 1; srcCol <= destCol + 1; ++srcCol)
            {
                if (srcCol < 0 || srcCol >= getNCols())
                    continue;
                if (getTileContents(srcRow, srcCol) != getPlayerToMove())
                    continue;

                legalMoves.push_back(Move::createMove(srcRow, srcCol, destRow, destCol));
                return;
            }
        }
    }
};


static void outputAtxGame(AtaxxGame& atxGame);
static MoveSequenceAndScore minimax(AtaxxGame& atxGame, int nPlies);
static MoveSequenceAndScore minimax_worker(AtaxxGame& atxGame, int nPlies, int nPliesMax,
    int alpha, int beta);

int g_nMovesTried = 0;

int main()
{
    AtaxxGame atxGame(7,2);                         //Set the number of rows and number of columns to any value >= 2.
    atxGame.makeMove(Move::createMove(0,0,1,1));    //If you wish to investigate positions after the opening position, add lines which make moves here.
    //atxGame.makeMove(Move::createMove(6,0,5,1));  //  ...like so.  Remove the first // on the left to enable this line, for example.
    vector<Move> moves;                             // = atxGame.getLegalMoves();  <-- replace the semi-colon after 'moves' with the commented-out code, then delete all moves.push_back() commands to investigate _all_ legal moves from the given position.
    moves.push_back(Move::createMove(6,0,5,0));     //I am investigating a subset of all possible moves here.  Specifically, after 1.a1b1, I am only investigating 1...g1f1
    moves.push_back(Move::createMove(6,0,5,1));     //  and 1...g1f2.
    for (int nPlies = 16; nPlies <= 16; ++nPlies)   //Set the starting (>=1) and ending (>=starting) number of plies to search.
    {
        for (unsigned int iTrialMove = 0; iTrialMove < moves.size(); ++iTrialMove)
        {
            atxGame.makeMove(moves.at(iTrialMove));
            outputAtxGame(atxGame);

            g_nMovesTried = 0;
            MoveSequenceAndScore mss = minimax(atxGame, nPlies);
            cout << "L" << nPlies << " eval value, with " << g_nMovesTried << " moves tried, is "
                << mss.score << "." << endl << "Best line =";
            for (unsigned int iBestLineMove = 0; iBestLineMove < mss.moves.size(); ++iBestLineMove) {
                if (iBestLineMove % 2 == 0)
                    cout << ' ' << ((iBestLineMove/2)+1) << ".";
                cout << ' ';
                mss.moves.at(iBestLineMove).printToStdout();
                atxGame.makeMove(mss.moves.at(iBestLineMove));
            }
            cout << endl << "leads to:" << endl;
            outputAtxGame(atxGame);
            cout << endl;
            for (unsigned int iBestLineMove = 0; iBestLineMove < mss.moves.size(); ++iBestLineMove) {
                atxGame.undoLastMove();
            }
            atxGame.undoLastMove();
        }
    }

    return 0;
}


//Determine the 'best' move.  Hides nPliesMax, alpha, beta details from user.  This is a
//wrapper around minimax_worker, which should/will be 'private' somewhere soon.
static MoveSequenceAndScore minimax(AtaxxGame& atxGame, int nPlies)
{
    return minimax_worker(atxGame, nPlies, nPlies, -100000, 100000);
}

static MoveSequenceAndScore minimax_worker(AtaxxGame& atxGame, int nPlies, int nPliesMax,
    int alpha, int beta)
{
    //these must have absolute values > or < to red win and blue win.
    MoveSequenceAndScore bestMSS = MoveSequenceAndScore::scoreWithoutMove(0);
    bestMSS.score = (atxGame.getPlayerToMove() == 1) ? -10000 : 10000;

    vector<Move> moves = atxGame.getLegalMoves();
    if (moves.size() == 0) {
        //the game is over.
        if (atxGame.getNRed() > atxGame.getNBlue())
            return MoveSequenceAndScore::scoreWithoutMove(1000 + (atxGame.getNRed() - atxGame.getNBlue()));
        else if (atxGame.getNRed() < atxGame.getNBlue())
            return MoveSequenceAndScore::scoreWithoutMove(-1000 - (atxGame.getNBlue() - atxGame.getNRed()));
        else
            return MoveSequenceAndScore::scoreWithoutMove(0);
    }

    for (unsigned int iMove = 0; iMove < moves.size() && alpha <= beta; ++iMove)
    {
        atxGame.makeMove(moves.at(iMove));
        ++g_nMovesTried;

        MoveSequenceAndScore evalValueAndMoveSeq = MoveSequenceAndScore::scoreWithoutMove(0);
        if (nPlies == 1) {
            if (atxGame.gameIsOver()) {
                if (atxGame.getNRed() > atxGame.getNBlue())
                    evalValueAndMoveSeq.score = 1000 + (atxGame.getNRed() - atxGame.getNBlue());
                else if (atxGame.getNRed() < atxGame.getNBlue())
                    evalValueAndMoveSeq.score = -1000 - (atxGame.getNBlue() - atxGame.getNRed());
                else
                    evalValueAndMoveSeq.score = 0;
            } else {
                evalValueAndMoveSeq.score = atxGame.getNRed() - atxGame.getNBlue();

                if (moves.at(iMove).isPass()) {  //check for one player being trap-defeated.
                    if (atxGame.getPlayerToMove() == 1) {  //red has the option to fill
                        int finalDiff = atxGame.getNRed() + atxGame.getNBlank() - atxGame.getNBlue();
                        if (finalDiff > 0) {  //red will win, _if_ red can see that far.
                            evalValueAndMoveSeq.score = 1000 + finalDiff;
                        }
                    } else {
                        int finalDiff = atxGame.getNBlue() + atxGame.getNBlank() - atxGame.getNRed();
                        if (finalDiff > 0) {  //blue will win, _if_ blue can see that far.
                            evalValueAndMoveSeq.score = -1000 - finalDiff;
                        }
                    }
                }
            }
        }
        else {
            evalValueAndMoveSeq = minimax_worker(atxGame, nPlies - 1, nPliesMax, alpha, beta);
        }
        //tack this move onto the sequence.
        evalValueAndMoveSeq.moves.insert(evalValueAndMoveSeq.moves.begin(), moves.at(iMove));

        if (atxGame.getPlayerToMove() == 2 && evalValueAndMoveSeq.score > bestMSS.score)
        {
            //red, the maximizer, just moved.
            bestMSS = evalValueAndMoveSeq;
            if (bestMSS.score > alpha)
               alpha = evalValueAndMoveSeq.score;
        }
        else if (atxGame.getPlayerToMove() == 1 && evalValueAndMoveSeq.score < bestMSS.score)
        {
            //blue, the minimizer, just moved.
            bestMSS = evalValueAndMoveSeq;
            if (bestMSS.score < beta)
               beta = evalValueAndMoveSeq.score;
        }

        atxGame.undoLastMove();
    }

    return bestMSS;
}

//Output the board to stdout.
void outputAtxGame(AtaxxGame& atxGame)
{
    cout << "Moves so far:";
    for (int iMove = 0; iMove < atxGame.nMovesMade(); ++iMove) {
        if (iMove % 2 == 0)
            cout << ' ' << ((iMove/2)+1) << ".";
        cout << ' ';
        atxGame.getMoveMade(iMove).printToStdout();
    }
    cout << endl;

    for (int iRow = 0; iRow < atxGame.getNRows(); ++iRow) {
        for (int iCol = 0; iCol < atxGame.getNCols(); ++iCol) {
            switch (atxGame.getTileContents(iRow,iCol)) {
                case 0:
                    cout << '-'; break;
                case 1:
                    cout << 'r'; break;
                case 2:
                    cout << 'b'; break;
                default:
                    assert(false);
            }
        }
        if (iRow < atxGame.getNRows() - 1)
            cout << endl;
    }
    cout << "   , " << ((atxGame.getPlayerToMove()==1)?'r':'b') << " to move, score is "
        << atxGame.getNRed() << " to " << atxGame.getNBlue() << "." << endl;
}