6
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

Prefer using exceptions to exit

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

I would always throw an exception in preference to exiting the code. In the best case this causes the exact same behavior and causes the program to exit. BUT it also unwinds the stack forcing a clean termination and resource clean up. Also if you code is part of another program (ie this is just one of many games that can be played) you want your game to exit but you don't want the control program to go down. Using an exception allows this as the control program can catch the exception generate an appropriate user message log the error and allow the user to choose an alternative program.

###Switch should have a default:

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");
  }
  // The problem with this fail() is that it is already too late.
  // A switch that has no matching case statement results in 
  // undefined behavior. You should always put a default clause in
  // the switch just to catch this situation (some maintainer may
  // add other option to Mark).
  fail("Not reached");
}

The code should look like this:

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");
    default:             break;  // Just add this line.
  }
  fail("Not reached");
}


###Prefer not to use global variables.

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

Prefer to use local variables and pass the board as parameter to your functions. A tiny bit of extra work (but by using encapsulation this work is removed see next comment).

Encapsulation

This is indicative of not encapsulating your code into a class.

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

But having this just means your code is tied to this one board. You can make your code much neater and thus much more re-usable by encapsulating this information into a class with methods to manipulate the state of the board.

Also by using encapsulation you will prevent accidently modification of the board by other parts of the code becuase you can protect the state of the object by making it private.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your review. I'm a bit confused because I don't have any global variables in my code (apart from std::cout etc of course), do I? Regarding making Board a class: I was unsure about that. Does it really bring much benefit in this case? A "data class" with only a single member (Moreover board.board is rather ugly) ... and std::array<Mark, 9> is already a rather "unique" type. \$\endgroup\$ – Daniel Jour Oct 24 '16 at 16:40
  • \$\begingroup\$ Clarification: The code shown in "Prefer not to use global variables" isn't a variable declaration but a using declaration ("modern typedef"). Actual boards are passed as part of State as parameters. \$\endgroup\$ – Daniel Jour Oct 24 '16 at 16:55
  • \$\begingroup\$ Yep my mistake. \$\endgroup\$ – Martin York Oct 24 '16 at 17:31
  • 1
    \$\begingroup\$ Yes there is an advantage to making Board a class. There is more than one method there. make_empty_board() , possible_moves(), make_move(), determine_winner() all seem part of the board. The class State seems like a good contender for holding the taking turns part and deciding how/what to play next. I would also sub class Player which can have two subclasses Human or Computer so you can plug in two humans or two AI into the State object. \$\endgroup\$ – Martin York Oct 24 '16 at 17:36
  • 1
    \$\begingroup\$ "A switch that has no matching case statement results in undefined behavior." Hm, I was surprised to read this, so I looked in the standard and it actually is wrong: "If no case matches and if there is no default then none of the statements in the switch is executed." [ $6.4.2/5 N4296] I actually omitted the default on purpose: Some compilers (g++ and clang++ at least IIRC) warn about a switch without a default and non exhaustive enumerations (in case I'd ever need to add something to Mark). \$\endgroup\$ – Daniel Jour Oct 25 '16 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.