Kursova_3_1

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
#include <map>
#include <tuple>
#include <vector>



/* Error handling made easy. */
[[noreturn]] void fail(char const * message) {
    std::cerr << message << std::endl;
    std::exit(EXIT_FAILURE);
}



/* A mark at a place on the board.
*
* - None:     No one has placed a mark here yet.
* - AI: This place has been marked by the magnificient AI.
* - Human:    The dirty human has touched this place.
*/
enum class Mark {
    None,
    AI,
    Human
};

std::ostream & operator<< (std::ostream & s, Mark m) {
    switch (m) {
    case Mark::None:     return (s << "_");
    case Mark::AI:       return (s << "O");
    case Mark::Human:    return (s << "X");
    }
    fail("Not reached");
}



/* A board is just 3 rows of each 3 marks. */
using Board = std::array<Mark, 3 * 3>;

Board make_empty_board(void) {
    Board b;
    std::fill(std::begin(b), std::end(b), Mark::None);
    return b;
}

std::ostream & operator<<(std::ostream & o, Board const & b) {
    auto from = std::begin(b);
    auto to = from;
    for (unsigned i = 0; i < 3; ++i) {
        std::advance(to, 3);
        std::copy(from, to, std::ostream_iterator<Mark>(o, "|"));
        o << '\n';
        std::advance(from, 3);
    }
    return o;
}



/* A state consists of the board (state) and a boolean to tell
* us who's turn it is.
*/
struct State {
    Board board;
    bool AITurn;
};

bool operator<(State const & lhs, State const & rhs) {
    if (lhs.AITurn == rhs.AITurn) {
        return lhs.board < rhs.board;
    }
    return lhs.AITurn; /* The states waiting for the AI to
                              * make a turn are ordered before the
                              * states waiting for the human to make a
                              * turn. */
}

std::ostream & operator<<(std::ostream & stream, State const & state) {
    stream << (state.AITurn ? "AI" : "HUMAN") << '\n';
    return stream << state.board;
}



/* A move is just the index on which to place a mark. */
using Move = unsigned;

std::vector<Move> possible_moves(State const & state) {
    std::vector<Move> moves;
    unsigned index = 0;
    for (auto const place : state.board) {
        if (place == Mark::None) {
            moves.emplace_back(index);
        }
        ++index;
    }
    return moves;
}

State make_move(State state, Move move) {
    if (move >= state.board.size() || state.board[move] != Mark::None) {
        fail("Invalid move");
    }
    state.board[move] = state.AITurn ? Mark::AI : Mark::Human;
    state.AITurn = !state.AITurn;
    return state;
}



/* Possible winners:
* - Human: The human won (or is about to win).
* - AI: The AI won (or is about to win).
* - None: Its a tie or it's not yet sure who's about to win.
*/
enum class Winner {
    Human,
    AI,
    None
};

Winner determine_winner(State const & state) {
    Board const & b = state.board;
    Mark const lines[][3] = {
        /* Horizontal */
        { b[0], b[1], b[2] },
        { b[3], b[4], b[5] },
        { b[6], b[7], b[8] },
        /* Vertical */
        { b[0], b[3], b[6] },
        { b[1], b[4], b[7] },
        { b[2], b[5], b[8] },
        /* Cross */
        { b[0], b[4], b[8] },
        { b[6], b[4], b[2] }
    };
    for (auto line : lines) {
        if (std::count(line, line + 3, Mark::Human) == 3) {
            return Winner::Human;
        }
        if (std::count(line, line + 3, Mark::AI) == 3) {
            return Winner::AI;
        }
    }
    return Winner::None;
}


/* Partition the given range into 3 groups, according to the given selector.
*
* Let r be the result of partition3(from, to, selector); Then the
* first group is in the range [from, std::get<0>(r)) and consists of
* those elements for which the selector returned a negative
* value. The "mid" group is in the range [std::get<0>(r),
* std::get<1>(r)) and consists of those elements for which the
* selector returned 0. The "end" group is in the range
* [std::get<1>(r), to) and consists of those elements which are not
* part of another group.
*
* For each element the selector will be called exactly once.
*/
template<typename Iterator, typename Selector>
std::tuple<Iterator, Iterator> partition3(Iterator from,
    Iterator to,
    Selector selector) {
    Iterator startMidGroup = from;
    Iterator startEndGroup = to;
    while (from != startEndGroup) {
        auto const selection = selector(*from);
        if (selection < 0) {
            std::iter_swap(from, startMidGroup);
            ++startMidGroup;
            ++from;
        }
        else if (selection == 0) {
            ++from;
        }
        else {
            --startEndGroup;
            std::iter_swap(from, startEndGroup);
        }
    }
    return std::make_tuple(startMidGroup, startEndGroup);
}



/* An advice, to be stored as "answer" to a State in the Plan.

* The move is the Move that is recommended, and the winner member
* shows whether it can be said for sure who is going to win (if the
* aforementioned move is made).
*/
struct Advice {
    Move move;
    Winner winner;
};



/* The Plan is just a mapping from States to Advices. */
using Plan = std::map<State, Advice>;



/* Core function, decides which move is best in the given state and
* stores this information in the Plan.
*
* Furthermore, the function computes the outcome of the game assuming
* perfect play of both parties. This is stored in the Plan, too, and
* also returned (to be used in the very same function, as this
* function recursively calls itself).
*/
Winner solve_state(Plan & plan, State const & state) {
    /* Look whether this particular state has already been
    * considered. If so, bail out.
    */
    auto const precomputed = plan.find(state);
    if (precomputed != plan.end()) {
        return precomputed->second.winner;
    }
    /* Look whether the game is over. Either because somebody won, or
    * because there are no possible moves anymore.
    */
    auto winner = determine_winner(state);
    auto moves = possible_moves(state);
    if (winner != Winner::None || moves.empty()) {
        return winner;
    }
    /* Make all possible moves, and solve the resulting states. The
    * moves are partitioned according to the outcome of the game after
    * the respective move.
    */
    auto const selector = [&plan, &state](auto const move) {
        auto const result = solve_state(plan, make_move(state, move));
        switch (result) {
        case Winner::AI: return -1;
        case Winner::None:     return  0;
        case Winner::Human:    return  1;
        }
        fail("Not reached");
    };
    auto const partitioning =
        partition3(std::begin(moves), std::end(moves), selector);
    /* [begin(moves), begin_tie_moves): Moves where the AI wins.
    * [begin_tie_moves, begin_human_moves): Moves which results in a tie.
    * [begin_human_moves, end(moves)): Moves where the human wins.
    */
    auto const begin_tie_moves = std::get<0>(partitioning);
    auto const begin_human_moves = std::get<1>(partitioning);
    /* Try to make a move that lets the current player win. If that's
    * not possible chose a move that results in a tie. Else there's no
    * choice but to lose.
    */
    Move move;
    if (state.AITurn) {
        if (begin_tie_moves != std::begin(moves)) {
            winner = Winner::AI;
        }
        else if (begin_human_moves != std::begin(moves)) {
            winner = Winner::None;
        }
        else {
            winner = Winner::Human;
        }
        move = moves[0];
    }
    else {
        if (begin_human_moves != std::end(moves)) {
            move = *begin_human_moves;
            winner = Winner::Human;
        }
        else if (begin_tie_moves != std::end(moves)) {
            move = *begin_tie_moves;
            winner = Winner::None;
        }
        else {
            move = moves[0];
            winner = Winner::AI;
        }
    }
    /* Store the results in the plan, to be used by the AI during the
    * game or in other solve_state calls.
    */
    plan[state] = { move, winner };
    return winner;
}



/* Solve every possible state, return the plan that's build up in the
* course of this.
*/
Plan calculate_plan(void) {
    Plan plan;
    solve_state(plan, { make_empty_board(), true });
    solve_state(plan, { make_empty_board(), false });
    return plan;
}



void report_winner(Winner winner) {
    std::cout << "AAAAAAnd the winner is ";
    switch (winner) {
    case Winner::Human: {
        std::cout << "the human";
        break;
    }
    case Winner::AI: {
        std::cout << "the AI";
        break;
    }
    case Winner::None: {
        std::cout << " ... ehm .. seems like there's no winner";
    }
    }
    std::cout << std::endl;
}



int tictactoe(int, char**) {
    auto const plan = calculate_plan();
    /* Play one round of the game. */
    State state = { make_empty_board(), false };
    auto moves = possible_moves(state);
    auto winner = determine_winner(state);
    while (moves.size() != 0 && winner == Winner::None) {
        std::cout << state << std::endl;
        if (state.AITurn) {
            auto const advice = plan.find(state);
            if (advice == std::end(plan)) {
                fail("No idea what to do?");
            }
            std::cout << "Making move " << advice->second.move << std::endl;
            state = make_move(state, advice->second.move);
        }
        else {
            int choice = 0;
            std::cout << "Where do you place your mark? ";
            std::cin >> choice;
            if (!std::cin) {
                fail("Ok, just forget it!");
            }
            state = make_move(state, choice);
        }
        moves = possible_moves(state);
        winner = determine_winner(state);
    }
    report_winner(winner);
    return EXIT_SUCCESS;
}