fanorona-server-bot/Game.cpp

#include <iostream>

#include "Game.h"
#include "Types.h"

Game::Game() : activeX(-1), activeY(-1), directionX(0), directionY(0), state(SELECTION), lastLocation(0) {
    reset();
}

void Game::reset() {
    state = SELECTION;
    lastLocation = 0;
    activeX = -1;
    activeY = -1;
    for(uint x = 0; x < 9; x++) {
        for(uint y = 0; y < 5; y++) {
            fields[x][y] = (y > 2 ? WHITE : BLACK);
        }
    }
    fields[0][2] = WHITE;
    fields[2][2] = WHITE;
    fields[4][2] = EMPTY;
    fields[5][2] = WHITE;
    fields[7][2] = WHITE;
}

void Game::reset(String& output) {
    reset();
    output.append("Fanorona Game\n\r");
    print(output);
    output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rHuman turn\n\rselect stone: ");
}

void Game::print(String& s) const {
    s.append("\n\r  0 1 2 3 4 5 6 7 8\n\r");
    printLine(s, 0);
    s.append("  |\\|/|\\|/|\\|/|\\|/|\n\r");
    printLine(s, 1);
    s.append("  |/|\\|/|\\|/|\\|/|\\|\n\r");
    printLine(s, 2);
    s.append("  |\\|/|\\|/|\\|/|\\|/|\n\r");
    printLine(s, 3);
    s.append("  |/|\\|/|\\|/|\\|/|\\|\n\r");
    printLine(s, 4);
    s.append("\n\r");
}

void Game::printLine(String& s, int index) const {
    static const char map[] = {
        '#', 'O', '.'
    };
    s.append(index + '0').append(' ');
    for(int x = 0; x < 8; x++) {
        if(x == activeX && index == activeY) {
            s.append("*-");
            continue;
        }
        s.append(map[fields[x][index]]).append('-');
    }
    if(8 == activeX && index == activeY) {
        s.append('*');
    } else {
        s.append(map[fields[8][index]]);
    }
    s.append("\n\r");
}

bool Game::parseLocation(const String& input, int& x, int& y) {
    if(input.getLength() <= 2 || !isDigit(input[0]) || input[1] != ' ' || !isDigit(input[2])) {
        return true;
    }
    x = input[0] - '0';
    y = input[2] - '0';
    return x >= 9 || y >= 6;
}

bool Game::parse(const String& input, String& output) {
    switch(state) {
        case SELECTION:
            parseSelection(input, output);
            break;
        case MOVE:
            parseMove(input, output);
            break;
        case ANOTHER_MOVE:
            parseAnotherMove(input, output);
            break;
        case REMOVE_SELECTION:
            parseRemoveSelection(input, output);
            break;
    }
    return shouldEnd();
}

void Game::parseSelection(const String& input, String& output) {
    int x;
    int y;
    if(parseLocation(input, x, y) || fields[x][y] != WHITE) {
        output.append("please choose white stone.\n\r");
        print(output);
        output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rHuman turn\n\rselect stone: ");
        return;
    }
    state = MOVE;
    activeX = x;
    activeY = y;
    print(output);
    output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rselect location to move: ");
}

void Game::parseMove(const String& input, String& output) {
    int x;
    int y;
    if(parseLocation(input, x, y)) {
        output.append("invalid move location.\n\r");
        print(output);
        output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rselect location to move: ");
        return;
    }
    if(fields[x][y] == WHITE) {
        activeX = x;
        activeY = y;
        print(output);
        output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rselect location to move: ");
        return;
    }
    if(fields[x][y] != EMPTY || !areNeighbours(activeX, activeY, x, y)) {
        output.append("invalid move location.\n\r");
        print(output);
        output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rselect location to move: ");
        return;
    }
    directionX = x - activeX;
    directionY = y - activeY;
    if(markHitSides(activeX, activeY, x, y, BLACK)) {
        state = REMOVE_SELECTION;
        print(output);
        output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rselect stone to take: ");
        return;
    }
    lastLocation = 0;
    move(activeX, activeY, x, y);

    bool removed = false;
    removed = removeLine(x, y, activeX, activeY, BLACK) || removed;
    removed = removeLine(activeX, activeY, x, y, BLACK) || removed;

    activeX = x;
    activeY = y;
    print(output);
    output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\r");
    print(output);
    if(removed && isAnotherTurnPossible(BLACK)) {
        state = ANOTHER_MOVE;
        output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rselect location to move: ");
        return;
    }
    state = SELECTION;
    output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rAI turn\n\r");
    activeX = -1;
    activeY = -1;
    botMove(output);
}

void Game::parseAnotherMove(const String& input, String& output) {
    int x;
    int y;
    if(parseLocation(input, x, y) || !canMoveActiveStoneTo(x - activeX, y - activeY, BLACK)) {
        output.append("invalid move location.\n\r");
        print(output);
        output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rselect location to move: ");
        return;
    }
    directionX = x - activeX;
    directionY = y - activeY;
    if(markHitSides(activeX, activeY, x, y, BLACK)) {
        state = REMOVE_SELECTION;
        print(output);
        output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rselect stone to take: ");
        return;
    }
    move(activeX, activeY, x, y);

    bool removed = false;
    removed = removeLine(x, y, activeX, activeY, BLACK) || removed;
    removed = removeLine(activeX, activeY, x, y, BLACK) || removed;

    activeX = x;
    activeY = y;
    print(output);
    output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\r");
    print(output);
    if(removed && isAnotherTurnPossible(BLACK)) {
        output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rselect location to move: ");
        return;
    }
    state = SELECTION;
    output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rAI turn\n\r");
    activeX = -1;
    activeY = -1;
    botMove(output);
}

void Game::parseRemoveSelection(const String& input, String& output) {
    int x;
    int y;
    if(parseLocation(input, x, y) || !((hitA.x == x && hitA.y == y) || (hitB.x == x && hitB.y == y))) {
        output.append("invalid take location.\n\r");
        print(output);
        output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rselect stone to take: ");
        return;
    }
    int mx = activeX + directionX;
    int my = activeY + directionY;

    move(activeX, activeY, mx, my);

    if(mx + directionX == x && my + directionY == y) {
        removeLine(activeX, activeY, mx, my, BLACK);
    } else {
        removeLine(mx, my, activeX, activeY, BLACK);
    }

    activeX = mx;
    activeY = my;
    print(output);
    if(isAnotherTurnPossible(BLACK)) {
        state = ANOTHER_MOVE;
        output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rselect location to move: ");
        return;
    }
    state = SELECTION;
    output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rAI turn\n\r");
    activeX = -1;
    activeY = -1;
    botMove(output);
}

void Game::move(int fromX, int fromY, int toX, int toY) {
    addLocation(fromX, fromY);
    fields[fromX][fromY] = EMPTY;
    fields[toX][toY] = WHITE;
}

bool Game::isDigit(char c) const {
    return c >= '0' && c <= '9';
}

bool Game::isInRange(int x, int y) const {
    return x >= 0 && x <= 8 && y >= 0 && y <= 4;
}

bool Game::areNeighbours(int x, int y, int x2, int y2) const {
    if(x == x2 && y == y2) {
        return false;
    }
    int diffX = x - x2;
    int diffY = y - y2;
    if(diffX < -1 || diffX > 1 || diffY < -1 || diffY > 1) {
        return false;
    }
    if(diffX == 0 || diffY == 0) {
        return true;
    }
    return !((x & 1) ^ (y & 1));
}

bool Game::removeLine(int x, int y, int x2, int y2, FieldState remove) {
    int diffX = x2 - x;
    int diffY = y2 - y;
    bool removed = false;
    while(true) {
        x2 += diffX;
        y2 += diffY;
        if(!isInRange(x2, y2) || fields[x2][y2] != remove) {
            return removed;
        }
        removed = true;
        fields[x2][y2] = EMPTY;
    }
}

int Game::getRank(int x, int y, int x2, int y2) const {
    int diffX = x2 - x;
    int diffY = y2 - y;
    int rank = 0;
    while(true) {
        x2 += diffX;
        y2 += diffY;
        if(!isInRange(x2, y2) || fields[x2][y2] != WHITE) {
            return rank;
        }
        rank++;
    }
}

void Game::botMove(String& output) {
    if(shouldEnd()) {
        return;
    }

    Location from;
    Location to;
    Location takeFrom;
    Location takeTo;
    int rank = -1;

    for(int bx = 0; bx < 9; bx++) {
        for(int by = 0; by < 5; by++) {
            if(fields[bx][by] != EMPTY) {
                continue;
            }
            for(int mx = -1; mx <= 1; mx++) {
                for(int my = -1; my <= 1; my++) {
                    int x = bx + mx;
                    int y = by + my;
                    if((mx == 0 && my == 0) || !isInRange(x, y) || !areNeighbours(bx, by, x, y) || fields[x][y] != BLACK) {
                        continue;
                    }
                    int rankA = getRank(bx, by, x, y);
                    int rankB = getRank(x, y, bx, by);
                    if(rankA > rank) {
                        from = {x, y};
                        to = {bx, by};
                        takeFrom = {bx, by};
                        takeTo = {x, y};
                        rank = rankA;
                    }
                    if(rankB > rank) {
                        from = {x, y};
                        to = {bx, by};
                        takeFrom = {x, y};
                        takeTo = {bx, by};
                        rank = rankB;
                    }
                }
            }
        }
    }
    lastLocation = 0;
    while(rank != -1) {
        fields[from.x][from.y] = EMPTY;
        fields[to.x][to.y] = BLACK;
        if(!removeLine(takeFrom.x, takeFrom.y, takeTo.x, takeTo.y, WHITE)) {
            break;
        }

        activeX = to.x;
        activeY = to.y;
        print(output);

        addLocation(from.x, from.y);
        directionX = to.x - from.x;
        directionY = to.y - from.y;

        int x = to.x;
        int y = to.y;
        rank = -1;
        for(int mx = -1; mx <= 1; mx++) {
            for(int my = -1; my <= 1; my++) {
                if((mx == 0 && my == 0) || !canMoveActiveStoneTo(mx, my, WHITE)) {
                    continue;
                }
                int bx = x + mx;
                int by = y + my;

                int rankA = getRank(bx, by, x, y);
                int rankB = getRank(x, y, bx, by);
                if(rankA > rank) {
                    from = {x, y};
                    to = {bx, by};
                    takeFrom = {bx, by};
                    takeTo = {x, y};
                    rank = rankA;
                }
                if(rankB > rank) {
                    from = {x, y};
                    to = {bx, by};
                    takeFrom = {x, y};
                    takeTo = {bx, by};
                    rank = rankB;
                }
            }
        }
    }

    activeX = -1;
    activeY = -1;
    print(output);
    print(output);
    output.append("Human Color: White(O)\n\rAIColor: Black(#)\n\rHuman turn\n\rselect stone: ");
}

void Game::addLocation(int x, int y) {
    if(lastLocation >= lastLocations.size()) {
        // safely to ignore, such long turns will never happen
        return;
    }
    lastLocations[lastLocation].x = x;
    lastLocations[lastLocation].y = y;
    lastLocation++;
}

bool Game::isInQueue(int x, int y) const {
    for(uint i = 0; i < lastLocation; i++) {
        if(lastLocations[i].x == x && lastLocations[i].y == y) {
            return true;
        }
    }
    return false;
}

bool Game::canMoveActiveStoneTo(int dirX, int dirY, FieldState enemy) const {
    if(directionX == dirX && directionY == dirY) {
        return false;
    }
    int newX = activeX + dirX;
    int newY = activeY + dirY;
    int hitAX = activeX - dirX;
    int hitAY = activeY - dirY;
    int hitBX = activeX + 2 * dirX;
    int hitBY = activeY + 2 * dirY;
    if((!isInRange(hitAX, hitAY) || fields[hitAX][hitAY] != enemy) && (!isInRange(hitBX, hitBY) || fields[hitBX][hitBY] != enemy)) {
        return false;
    }
    return isInRange(newX, newY) && areNeighbours(activeX, activeY, newX, newY) &&
            fields[newX][newY] == EMPTY && !isInQueue(newX, newY);
}

bool Game::isAnotherTurnPossible(FieldState enemy) const {
    return canMoveActiveStoneTo(-1, -1, enemy) || canMoveActiveStoneTo(0, -1, enemy) || canMoveActiveStoneTo(1, -1, enemy) ||
            canMoveActiveStoneTo(-1, 0, enemy) || canMoveActiveStoneTo(1, 0, enemy) ||
            canMoveActiveStoneTo(-1, 1, enemy) || canMoveActiveStoneTo(0, 1, enemy) || canMoveActiveStoneTo(1, 1, enemy);
}

bool Game::markHitSides(int x1, int y1, int x2, int y2, FieldState state) {
    hitA.x = x1 + (x1 - x2);
    hitA.y = y1 + (y1 - y2);
    hitB.x = x2 + (x2 - x1);
    hitB.y = y2 + (y2 - y1);
    return isInRange(hitA.x, hitA.y) && isInRange(hitB.x, hitB.y) &&
            areNeighbours(x1, y1, hitA.x, hitA.y) && areNeighbours(x2, y2, hitB.x, hitB.y) &&
            fields[hitA.x][hitA.y] == state && fields[hitB.x][hitB.y] == state;
}

bool Game::shouldEnd() const {
    int player = 0;
    int ai = 0;
    for(uint x = 0; x < 9; x++) {
        for(uint y = 0; y < 5; y++) {
            player += fields[x][y] == WHITE;
            ai += fields[x][y] == BLACK;
        }
    }
    return player == 0 || ai == 0;
}