fanorona-bot/source/Game.cpp

#include <iostream>
#include <climits>
#include <chrono>

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

std::array<Vector, 8> Game::neighbours;
std::array<Vector, 9 * 5> Game::fieldVectors;
long int Game::selectionTime = 0;
long int Game::moveTime = 0;
int Game::turns = 0;
int Game::moves = 0;

Game::Game() : active(-1, -1), mustTake(false) {
    // sets the basic game up:
    // 0 - start game
    // 1 - player vs ai
    // 0 - player starts
    std::cout << "0\n1\n0\n";
    
    // allows for each neighbor iterating
    neighbours[0].set(1, 0);
    neighbours[1].set(0, 1);
    neighbours[2].set(-1, 0);
    neighbours[3].set(0, -1);
    neighbours[4].set(1, 1);
    neighbours[5].set(-1, 1);
    neighbours[6].set(1, -1);
    neighbours[7].set(-1, -1);

    // allows for each for all fields 
    uint index = 0;
    for(uint y = 0; y < 5; y++) {
        for(uint x = 0; x < 9; x++) {
            fieldVectors[index++].set(x, y);
        }
    }
}

void Game::readLine() {
    String line;
    while(true) {
        // read input by each character
        char c = std::cin.get();
        if(c == '\n') {
            // parse the command if the line ended
            if(parseLine(line)) {
                return;
            }
            // clear the buffer for the next command
            line.clear();
        } else if(c != '\r') {
            // line carriages are ignored
            line.append(c);
        }
    }
}

bool Game::parseLine(const String& line) {
    // identify when the server expects an answer or a new game field is available
    if(line == "   0   1   2   3   4   5   6   7   8") {
        fields.read();
        fields.print(active);
    } else if(line == "Please enter origin x-axis") {
        makeSelection();
    } else if(line == "Please enter destination x-axis") {
        makeMove();
    } else if(line == "Please enter wether you want to Withdraw or Approach [W/A]") {
        takeStone();
    } else if(line == "Do you want to continue with your turn [Y/N]?") {
        // we always want to continue if possible
        std::cout << "Y\n";
    } else if(line == "************************Player 1 won!**********************" ||
            line == "************************Player 2 won!**********************") {
        // stop the game if anybody wins - the server does not do that
        std::cerr << line << "\n";
        
        //std::cerr << "Turns: " << turns << "\n";
        //std::cerr << "Moves: " << moves << "\n";
        //std::cerr << "Total selection time: " << selectionTime << "\n";
        //std::cerr << "Total move time: " << moveTime << "\n";
        std::cerr << turns << "," << moves << "," << selectionTime << "," << moveTime << "\n";
        return true;
    }
    return false;
}

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

bool Game::areNeighbors(const Vector& from, const Vector& to) const {
    // fields are not neighbors with themselves
    if(from == to) {
        return false;
    }
    Vector diff = from - to;
    // fields with a bigger distance than one cannot be neighbors
    if(diff.x < -1 || diff.x > 1 || diff.y < -1 || diff.y > 1) {
        return false;
    }
    // either left, right, upper or lower neighbor
    if(diff.x == 0 || diff.y == 0) {
        return true;
    }
    // check if the field has diagonal connections (both coords are either even or uneven numbers)
    return (from.x & 1) == (from.y & 1);
}

uint Game::removeLine(const Vector& from, const Vector& to, Fields::State state) {
    // walk along the line and removes opponent stones
    Vector current = to;
    Vector unit = to - from;
    // counter for removed stones
    uint rank = 0;
    while(true) {
        current += unit;
        // stop removing on wrong stones or the end of the game field
        if(!isInRange(current) || !fields.hasState(current, state)) {
            return rank;
        }
        fields.setState(current, Fields::EMPTY);
        rank++;
    }
}

uint Game::getRank(const Vector& from, const Vector& to, Fields::State state) const {
    // same as removeLine but the removable stones are only counted
    Vector current = to;
    Vector unit = to - from;
    uint rank = 0;
    while(true) {
        current += unit;
        if(!isInRange(current) || !fields.hasState(current, state)) {
            return rank;
        }
        rank++;
    }
}

uint Game::getStoneTakes(const Vector& from, const Vector& to) const {
    // an invalid turn cannot take any stones
    if(!isInRange(to) || !fields.hasState(to, Fields::EMPTY) || !areNeighbors(from, to) ||
            lastLocations.contains(to) || (to - from) == direction) {
        return 0;
    }
    // the turn must take stones
    Fields::State enemy = (fields.hasState(from, Fields::BLACK) ? Fields::WHITE : Fields::BLACK);
    if(getRank(from, to, enemy) == 0 && getRank(to, from, enemy) == 0) {
        return 0;
    }
    // actually do the turn on a copied game, store the rank (= taken stones)
    Game copy = *this;
    uint rank = copy.move(from, to);
    // recursively check all neighbors on the copied game for another move, take the best move
    uint maxRank = 0;
    for(Vector& m : neighbours) {
        uint rank = copy.getStoneTakes(to, to + m);
        if(rank > maxRank) {
            maxRank = rank;
        }
    }
    return rank + maxRank;
}

uint Game::getStoneFreedom(const Vector& from, Fields::State state) const {
    // no freedom if the stone is not yours
    if(!fields.hasState(from, state)) {
        return 0;
    }
    // count directions the stone can move to
    uint counter = 0;
    for(const Vector& m : neighbours) {
        Vector to = from + m;
        if(isInRange(to) && areNeighbors(from, to) && fields.hasState(to, Fields::EMPTY)) {
            counter++;
        }
    }
    return counter;
}

uint Game::getFreedom(Fields::State state) const {
    uint sum = 0;
    for(const Vector& v : fieldVectors) {
        sum += getStoneFreedom(v, state);
    }
    return sum;
}

uint Game::move(const Vector& from, const Vector& to) {
    // remember direction to block the same move
    direction = to - from;
    // remember the old location to block moving to it again
    lastLocations.add(from);
    // actually from the stone
    fields.setState(to, fields.getState(from));
    fields.setState(from, Fields::EMPTY);
    // get the enemy by inverting the goal state
    Fields::State enemy = (fields.hasState(to, Fields::BLACK) ? Fields::WHITE : Fields::BLACK);
    // compare quality of the two sides, take better side
    uint rankA = getRank(from, to, enemy);
    uint rankB = getRank(to, from, enemy);
    if(rankA >= rankB) {
        return removeLine(from, to, enemy);
    }
    return removeLine(to, from, enemy);
}

void Game::makeSelection() {
    // add statistics
    ssize_t time = getNanos();
    turns++;
    // new turn starts - reset previously blocked turns
    lastLocations.clear();
    direction.set(0, 0);
    // remember if the following turn must take a stone
    mustTake = isTakingPossible();
    // calculate rank for all possible selections, take best selection
    Vector selection(0, 0);
    int maxRank = INT_MIN;
    for(Vector& to : fieldVectors) {
        if(!fields.hasState(to, Fields::EMPTY)) {
            continue;
        }
        // scan neighbors of empty fields for white stones
        for(Vector& m : neighbours) {
            Vector from = to + m;
            // prevent invalid stone locations
            if(!isInRange(from) || !fields.hasState(from, Fields::WHITE) || !areNeighbors(from, to)) {
                continue;
            }
            // prevent non taking turns if taking is a must
            if(mustTake && getRank(from, to, Fields::BLACK) + getRank(to, from, Fields::BLACK) == 0) {
                continue;
            }
            // calculate rank and potentially store the new max value
            int rank = getQuality(from, to);
            if(rank > maxRank) {
                maxRank = rank;
                selection = from;
            }
        }
    }
    // mark the stone as active
    active = selection;
    // add selection time to statistics, do not measure IO
    selectionTime += getNanos() - time;
    // send the selection to the server
    std::cerr << "Selecting (" << selection.x << ", " << selection.y << ")\n";
    // print the selection and the current game field for logging purposes
    fields.print(active);
    std::cout << selection.x << "\n" << selection.y << "\n";
}

void Game::makeMove() {
    // add statistics
    ssize_t time = getNanos();
    moves++;
    // check all neighbors of active selection and choose the move with the highest rank
    Vector maxTo(0, 0);
    int maxRank = INT_MIN;
    for(Vector& m : neighbours) {
        Vector to = active + m;
        // prevent invalid moves
        if(!isInRange(to) || !fields.hasState(to, Fields::EMPTY) || lastLocations.contains(to) ||
                !areNeighbors(active, to) || m == direction) {
            continue;
        }
        // if this is not the first move or a must take move - prevent non taking move
        if(!lastLocations.isEmpty() || mustTake) {
            int rank = getRank(active, to, Fields::BLACK) + getRank(to, active, Fields::BLACK);
            if(rank == 0) {
                continue;
            }
        }
        // calculate rank and potentially store the new max value
        int rank = getQuality(active, to);
        if(rank > maxRank) {
            maxRank = rank;
            maxTo = to;
        }
    }
    // remember the old location to prevent moving to it
    lastLocations.add(active);
    // remember the direction to prevent moving in it again
    direction = maxTo - active;
    // mark the location as active
    active = maxTo;
    // add selection time to statistics, do not measure IO
    moveTime += getNanos() - time;
    // send the move to the server
    std::cerr << "Move to (" << maxTo.x << ", " << maxTo.y << ")\n";
    // log the move
    std::cout << maxTo.x << "\n" << maxTo.y << "\n";
}

void Game::takeStone() {
    // calculate the better taking side ...
    uint rankA = getRank(active, active + direction, Fields::BLACK);
    uint rankB = getRank(active + direction, active, Fields::BLACK);
    // and send it to the server
    if(rankA >= rankB) {
        std::cout << "W\n";
    } else {
        std::cout << "A\n";
    }
}

int Game::getQuality(const Vector& from, const Vector& to) const {
    // base quality is how much stones this turn can take (+ following moves)
    int quality = getStoneTakes(from, to);
    // actually do the turn on a copy
    Game copy = *this;
    copy.move(from, to);
    // reset previous location and direction to simulate an opponent turn
    copy.lastLocations.clear();
    copy.direction.set(0, 0);
    // calculate white and black freedom on the potential new board
    int whiteFreedom = copy.getFreedom(Fields::WHITE);
    int blackFreedom = copy.getFreedom(Fields::BLACK);
    // calculates the strongest opponent turn
    uint maxRank = copy.getBestEnemyRank();
    // opponent count is important in the endgame
    int black = countBlack();
    if(black >= 8) {
        black = 1;
    }
    // finalize the quality formula
    return quality - maxRank * black + (whiteFreedom - blackFreedom) / 4;
}

int Game::countBlack() const {
    int counter = 0;
    for(Vector& v : fieldVectors) {
        counter += fields.hasState(v, Fields::BLACK);
    }
    return counter;
}

bool Game::isTakingPossible() const {
    // scan all fields for possible taking moves
    for(Vector& to : fieldVectors) {
        if(!fields.hasState(to, Fields::EMPTY)) {
            continue;
        }
        // check if any white neighbored stone can move to the found empty stone
        for(Vector& m : neighbours) {
            Vector from = to + m;
            if(!isInRange(from) || !areNeighbors(from, to) || !fields.hasState(from, Fields::WHITE)) {
                continue;
            }
            // return true if the white stone can take black stones in any direction
            if(getRank(from, to, Fields::BLACK) + getRank(to, from, Fields::BLACK) > 0) {
                return true;
            }
        }
    }
    return false;
}

uint Game::getBestEnemyRank() const {
    uint maxRank = 0;
    // scan all fields for best rank
    for(Vector& to : fieldVectors) {
        if(!fields.hasState(to, Fields::EMPTY)) {
            continue;
        }
        // scan neighbors of found empty fields
        for(Vector& m : neighbours) {
            Vector from = to + m;
            // prevent invalid moves
            if(!isInRange(from) || !fields.hasState(from, Fields::BLACK)) {
                continue;
            }
            // calculate and store the potentially better rank
            uint rank = getStoneTakes(from, to);
            if(rank > maxRank) {
                maxRank = rank;
            }
        }
    }
    return maxRank;
}

long int Game::getNanos() {
    return std::chrono::high_resolution_clock::now().time_since_epoch().count();
}