I wrote an answer to another question about the same subject and a new implementation, but instead of just posting my code there I think it's a good chance to see what can be improved on my own code.
#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.
* - Computer: This place has been marked by the magnificient computer.
* - Human: The dirty human has touched this place.
*/
enum class Mark {
None,
Computer,
Human
};
std::ostream & operator<< (std::ostream & s, Mark m) {
switch (m) {
case Mark::None: return (s << "_");
case Mark::Computer: return (s << "C");
case Mark::Human: return (s << "H");
}
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 computersTurn;
};
bool operator<(State const & lhs, State const & rhs) {
if (lhs.computersTurn == rhs.computersTurn) {
return lhs.board < rhs.board;
}
return lhs.computersTurn; /* The states waiting for the computer 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.computersTurn ? "COMPUTER" : "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.computersTurn ? Mark::Computer : Mark::Human;
state.computersTurn = !state.computersTurn;
return state;
}
/* Possible winners:
* - Human: The human won (or is about to win).
* - Computer: The computer 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,
Computer,
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::Computer) == 3) {
return Winner::Computer;
}
}
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::Computer: 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 computer 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.computersTurn) {
if (begin_tie_moves != std::begin(moves)) {
winner = Winner::Computer;
} 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::Computer;
}
}
/* 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 dirty human";
break;
}
case Winner::Computer: {
std::cout << "the fabolus computer";
break;
}
case Winner::None: {
std::cout << " ... ehm .. seems like there's no winner";
}
}
std::cout << std::endl;
}
int main(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.computersTurn) {
auto const advice = plan.find(state);
if (advice == std::end(plan)) {
fail("No idea what to do, DIE!!!");
}
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;
}
Compiles fine without warnings with g++ -Wall -Wextra --std=c++14 file.cc (g++ (GCC) 5.4.0). Note that I left out "nice human interaction" (regarding e.g. input of moves) on purpose, and concentrated on the "AI code" instead.
