Empirical
Othello.h
Go to the documentation of this file.
1 
13 #ifndef EMP_GAME_OTHELLO_H
14 #define EMP_GAME_OTHELLO_H
15 
16 #include <fstream>
17 #include <iostream>
18 #include <iomanip>
19 #include <unordered_map>
20 
21 #include "../base/array.h"
22 #include "../base/assert.h"
23 #include "../base/vector.h"
24 #include "../tools/math.h"
25 
26 namespace emp {
32 
34  struct Othello_Base {
35  enum Player { NONE=0, DARK, LIGHT };
36  enum Facing { N, NE, E, SE, S, SW, W, NW };
37  static constexpr size_t NUM_DIRECTIONS = 8;
38  };
39 
41  template <size_t BOARD_SIZE>
42  class Othello_Game : public Othello_Base {
43  public:
44  static constexpr size_t NUM_CELLS = BOARD_SIZE * BOARD_SIZE;
46  using board_t = std::array<Player, NUM_CELLS>;
47 
48  struct Index {
49  size_t pos;
50 
51  Index() : pos(NUM_CELLS) { ; } // Default constructor is invalid position.
52  Index(size_t _pos) : pos(_pos) { emp_assert(pos <= NUM_CELLS); }
53  Index(size_t x, size_t y) : pos() { Set(x,y); }
54  Index(const Index & _in) : pos(_in.pos) { emp_assert(pos <= NUM_CELLS); }
55 
56  operator size_t() const { return pos; }
57  size_t x() const { return pos % BOARD_SIZE; }
58  size_t y() const { return pos / BOARD_SIZE; }
59  void Set(size_t x, size_t y) { pos = (x<BOARD_SIZE && y<BOARD_SIZE) ? (x+y*BOARD_SIZE) : NUM_CELLS; }
60  bool IsValid() const { return pos < NUM_CELLS; }
61 
63  Index faced_id;
64  switch(dir) {
65  case Facing::N: { faced_id.Set(x() , y() - 1); break; }
66  case Facing::S: { faced_id.Set(x() , y() + 1); break; }
67  case Facing::E: { faced_id.Set(x() + 1, y() ); break; }
68  case Facing::W: { faced_id.Set(x() - 1, y() ); break; }
69  case Facing::NE: { faced_id.Set(x() + 1, y() - 1); break; }
70  case Facing::NW: { faced_id.Set(x() - 1, y() - 1); break; }
71  case Facing::SE: { faced_id.Set(x() + 1, y() + 1); break; }
72  case Facing::SW: { faced_id.Set(x() - 1, y() + 1); break; }
73  }
74  return faced_id;
75  }
76  };
77 
78  protected:
79  std::array<Facing, NUM_DIRECTIONS> ALL_DIRECTIONS;
81 
82  bool over = false;
85 
87  static size_t GetNeighborIndex(Index pos, Facing dir) {
88  return (((size_t) pos) * NUM_DIRECTIONS) + (size_t) dir;
89  }
90 
91  public:
92  Othello_Game() : ALL_DIRECTIONS({ Facing::N, Facing::NE, Facing::E, Facing::SE, Facing::S, Facing::SW, Facing::W, Facing::NW })
93  , neighbors(BuildNeighbors()), cur_player(Player::DARK), game_board() {
94  emp_assert(BOARD_SIZE >= 4);
95  Reset();
96  }
97 
98  ~Othello_Game() { ; }
99 
100  static constexpr Index GetIndex(size_t x, size_t y) { return Index(x, y); }
101 
103  void Reset() {
104  // Reset the board.
105  for (size_t i = 0; i < NUM_CELLS; ++i) game_board[i] = Player::NONE;
106 
107  // Setup Initial board
108  // ........
109  // ...LD...
110  // ...DL...
111  // ........
112  SetPos({BOARD_SIZE/2 - 1, BOARD_SIZE/2 - 1}, Player::LIGHT);
113  SetPos({BOARD_SIZE/2 - 1, BOARD_SIZE/2 }, Player::DARK);
114  SetPos({BOARD_SIZE/2, BOARD_SIZE/2 - 1}, Player::DARK);
115  SetPos({BOARD_SIZE/2, BOARD_SIZE/2 }, Player::LIGHT);
116 
117  over = false;
118  cur_player = Player::DARK;
119  }
120 
121  constexpr size_t GetBoardWidth() const { return BOARD_SIZE; }
122  size_t GetNumCells() const { return NUM_CELLS; }
123  Player GetCurPlayer() const { return cur_player; }
124 
126  Player GetOpponent(Player player) const {
127  emp_assert(IsValidPlayer(player));
128  return (player == Player::DARK) ? Player::LIGHT : Player::DARK;
129  }
130 
132  bool IsValidPlayer(Player player) const { return (player == Player::DARK) || (player == Player::LIGHT); }
133 
134  auto BuildNeighbors() {
135  emp::vector<Index> neighbors;
136 
137  if (neighbors.size() == 0) {
138  neighbors.resize(NUM_CELLS * NUM_DIRECTIONS);
139  for (size_t posID = 0; posID < NUM_CELLS; ++posID) {
140  Index pos(posID);
141  for (Facing dir : ALL_DIRECTIONS) {
142  neighbors[GetNeighborIndex(posID, dir)] = pos.CalcNeighbor(dir);
143  }
144  }
145  }
146 
147  return neighbors;
148  }
149 
152  Index GetNeighbor(Index id, Facing dir) const {
153  if (!id.IsValid()) return Index();
154  return neighbors[GetNeighborIndex(id, dir)];
155  }
156 
159  emp_assert(id.IsValid());
160  return game_board[id];
161  }
162 
163  board_t & GetBoard() { return game_board; }
164  const board_t & GetBoard() const { return game_board; }
165 
167  bool IsValidMove(Player player, Index pos) {
168  emp_assert(IsValidPlayer(player));
169  if (!pos.IsValid()) return false; // Is pos even on the board?
170  if (GetPosOwner(pos) != Player::NONE) return false; // Is pos empty?
171  return HasValidFlips(player, pos); // Will any tiles flip?
172  }
173 
174  bool IsOver() const { return over; }
175 
179  emp::vector<Index> flip_list;
180  size_t prev_len = 0;
181  const Player opponent = GetOpponent(player);
182  for (Facing dir : ALL_DIRECTIONS) {
183  Index neighbor_pos = GetNeighbor(pos, dir);
184  // Collect opponent spaces in this direction.
185  while (neighbor_pos.IsValid() && GetPosOwner(neighbor_pos) == opponent) {
186  flip_list.emplace_back(neighbor_pos);
187  neighbor_pos = GetNeighbor(neighbor_pos, dir);
188  }
189  // If this line didn't end in current color, throw out everything we found.
190  if (!neighbor_pos.IsValid() || GetPosOwner(neighbor_pos) == Player::NONE) { flip_list.resize(prev_len); }
191  // Otherwise keep it and update the locked in flips.
192  else { prev_len = flip_list.size(); }
193  }
194  return flip_list;
195  }
196 
198  size_t GetFlipCount(Player player, Index pos) {
199  size_t flip_count = 0;
200  const Player opponent = GetOpponent(player);
201  for (Facing dir : ALL_DIRECTIONS) {
202  // Collect opponent spaces in this direction.
203  size_t dir_count = 0;
204  Index neighbor_pos = GetNeighbor(pos, dir);
205  while (neighbor_pos.IsValid() && GetPosOwner(neighbor_pos) == opponent) {
206  dir_count++;
207  neighbor_pos = GetNeighbor(neighbor_pos, dir);
208  }
209  // If this line ended in the correct color, add this direction to the total_count.
210  if (neighbor_pos.IsValid() && GetPosOwner(neighbor_pos) == player) { flip_count += dir_count; }
211  }
212  return flip_count;
213  }
214 
216  bool HasValidFlips(Player player, Index pos) {
217  const Player opponent = GetOpponent(player);
218  for (Facing dir : ALL_DIRECTIONS) { // Loop through directions to explore
219  Index neighbor_pos = GetNeighbor(pos, dir); // Start at first neighbor.
220  size_t count = 0;
221  // Collect opponent spaces in this direction.
222  while (neighbor_pos.IsValid() && GetPosOwner(neighbor_pos) == opponent) {
223  count++;
224  neighbor_pos = GetNeighbor(neighbor_pos, dir);
225  }
226  // If this line ended with current color (and has spots to flip) we found a good solution!
227  if (count && neighbor_pos.IsValid() && GetPosOwner(neighbor_pos) == player) { return true; }
228  }
229  return false;
230  }
231 
232 
235  emp_assert(IsValidPlayer(player));
236  emp::vector<Index> valid_moves;
237  for (size_t i = 0; i < NUM_CELLS; ++i) {
238  if (IsValidMove(player, i)) valid_moves.emplace_back(i);
239  }
240  return valid_moves;
241  }
242 
245 
247  bool HasMoveOptions(Player player) {
248  emp_assert(IsValidPlayer(player));
249  for (size_t i = 0; i < NUM_CELLS; ++i) {
250  if (IsValidMove(player, i)) return true;
251  }
252  return false;
253  }
254 
256  double GetScore(Player player) {
257  emp_assert(IsValidPlayer(player));
258  return std::count(game_board.begin(), game_board.end(), player);
259  }
260 
262  size_t CountFrontierPos(Player player) {
263  emp_assert(IsValidPlayer(player));
264  size_t frontier_size = 0;
265  for (size_t i = 0; i < NUM_CELLS; ++i) { // Search through all cells
266  if (game_board[i] == Player::NONE) { // Is the test cell empty?
267  if (IsAdjacentTo(i, player)) ++frontier_size; // If so, test if on player's frontier
268  }
269  }
270  return frontier_size;
271  }
272 
274  bool IsAdjacentTo(Index pos, Player owner) {
275  for (Facing dir : ALL_DIRECTIONS) {
276  Index nID = GetNeighbor(pos, dir);
277  if (!nID.IsValid()) continue;
278  if (GetPosOwner(nID) == owner) return true;
279  }
280  return false;
281  }
282 
284  void SetPos(Index pos, Player player) {
285  emp_assert(pos.IsValid());
286  game_board[pos] = player;
287  }
288 
291  for (auto x : ids) SetPos(x, player);
292  }
293 
296  void SetBoard(const board_t & other_board) { game_board = other_board; }
297 
299  void SetBoard(const this_t & other_othello) { SetBoard(other_othello.GetBoard()); }
300 
302  void SetCurPlayer(Player player) {
303  emp_assert(IsValidPlayer(player));
304  cur_player = player;
305  }
306 
309  bool DoNextMove(Index pos) { return DoMove(cur_player, pos); }
310 
315  bool DoMove(Player player, Index pos) {
316  emp_assert(IsValidPlayer(player) && pos.IsValid()); // Validate position and player.
317  emp_assert(GetPosOwner(pos) == Player::NONE); // Make sure position is empty.
318  SetPos(pos, player); // Take position for player.
319  DoFlips(player, pos); // Flip tiles on the board.
320  auto opp_moves = HasMoveOptions(GetOpponent(player)); // Test if opponent can go.
321  if (opp_moves) { cur_player = GetOpponent(player); return false; }
322 
323  auto player_moves = HasMoveOptions(player); // Opponent can't go; test cur player
324  if (player_moves) { return true; } // This player can go again!
325 
326  over = true; // No one can go; game over!
327  return false;
328  }
329 
331  void DoFlips(Player player, Index pos) {
332  emp_assert(IsValidPlayer(player));
333  auto flip_list = GetFlipList(player, pos);
334  for (Index flip : flip_list) { SetPos(flip, player); }
335  }
336 
338  void Print(std::ostream & os=std::cout, std::string dark_token = "D",
339  std::string light_token = "L", std::string open_space = "O") {
340  // Output column labels.
341  unsigned char letter = 'A';
342  os << "\n ";
343  for (size_t i = 0; i < BOARD_SIZE; ++i) os << char(letter + i) << " ";
344  os << "\n";
345  // Output row labels and board information.
346  for (size_t y = 0; y < BOARD_SIZE; ++y) {
347  os << y << " ";
348  for (size_t x = 0; x < BOARD_SIZE; ++x) {
349  Player space = GetPosOwner({x,y});
350  if (space == Player::DARK) { os << dark_token << " "; }
351  else if (space == Player::LIGHT) { os << light_token << " "; }
352  else { os << open_space << " "; }
353  }
354  os << "\n";
355  }
356  }
357  };
358 
360 }
361 
362 #endif
Player
Definition: Othello.h:35
size_t GetNumCells() const
Definition: Othello.h:122
const board_t & GetBoard() const
Definition: Othello.h:164
Player GetOpponent(Player player) const
Get opponent ID of give player ID.
Definition: Othello.h:126
Definition: Othello.h:35
constexpr const double E
e
Definition: const.h:18
bool IsValidMove(Player player, Index pos)
Is given move valid?
Definition: Othello.h:167
Index(size_t _pos)
Definition: Othello.h:52
Definition: Othello.h:36
size_t GetFlipCount(Player player, Index pos)
Count the number of positions that would flip if we placed a piece at a specific location.
Definition: Othello.h:198
bool IsOver() const
Definition: Othello.h:174
size_t x() const
Definition: Othello.h:57
std::array< Player, NUM_CELLS > board_t
Definition: Othello.h:46
bool HasValidFlips(Player player, Index pos)
Are there any valid flips from this position?
Definition: Othello.h:216
Definition: Othello.h:36
Base class for all sizes of Othello games.
Definition: Othello.h:34
emp::vector< Index > neighbors
Definition: Othello.h:80
void SetPos(Index pos, Player player)
Set board position (ID) to given space value.
Definition: Othello.h:284
Definition: Othello.h:36
Definition: Othello.h:36
Player cur_player
Who is the current player set to move next?
Definition: Othello.h:83
Class for othello games of a specific size.
Definition: Othello.h:42
bool IsValidPlayer(Player player) const
Is the given player ID a valid player?
Definition: Othello.h:132
void Set(size_t x, size_t y)
Definition: Othello.h:59
Definition: Othello.h:35
static size_t GetNeighborIndex(Index pos, Facing dir)
Internal function for accessing the neighbors vector.
Definition: Othello.h:87
static constexpr Index GetIndex(size_t x, size_t y)
Definition: Othello.h:100
bool DoNextMove(Index pos)
Definition: Othello.h:309
Othello_Game()
Definition: Othello.h:92
size_t size() const
Definition: vector.h:151
void emplace_back(ARGS &&...args)
Definition: vector.h:219
void SetBoard(const this_t &other_othello)
Set current board to be the same as board from other othello game.
Definition: Othello.h:299
Definition: Othello.h:35
bool IsAdjacentTo(Index pos, Player owner)
Is position given by ID adjacent to the given owner?
Definition: Othello.h:274
auto BuildNeighbors()
Definition: Othello.h:134
emp::vector< Index > GetFlipList(Player player, Index pos)
Definition: Othello.h:178
Facing
Definition: Othello.h:36
size_t y() const
Definition: Othello.h:58
Definition: Othello.h:36
std::array< Facing, NUM_DIRECTIONS > ALL_DIRECTIONS
Definition: Othello.h:79
Index GetNeighbor(Index id, Facing dir) const
Definition: Othello.h:152
static constexpr size_t NUM_DIRECTIONS
Number of neighbors each board space has.
Definition: Othello.h:37
size_t CountFrontierPos(Player player)
Count the number of empty squares adjacent to a player&#39;s pieces (frontier size)
Definition: Othello.h:262
void SetPositions(emp::vector< Index > ids, Player player)
Set positions given by ids to be owned by the given player.
Definition: Othello.h:290
constexpr size_t GetBoardWidth() const
Definition: Othello.h:121
Definition: Othello.h:48
emp::vector< Index > GetMoveOptions(Player player)
Get a list of valid move options for given player.
Definition: Othello.h:234
void resize(size_t new_size)
Definition: vector.h:161
bool IsValid() const
Definition: Othello.h:60
Definition: Othello.h:36
bool HasMoveOptions(Player player)
Determine if there are any move options for given player.
Definition: Othello.h:247
~Othello_Game()
Definition: Othello.h:98
If we are in emscripten, make sure to include the header.
Definition: array.h:37
Index()
Definition: Othello.h:51
size_t pos
Definition: Othello.h:49
Build a debug wrapper emp::vector around std::vector.
Definition: vector.h:42
Player GetCurPlayer() const
Definition: Othello.h:123
board_t game_board
Game board.
Definition: Othello.h:84
emp::vector< Index > GetMoveOptions()
GetMoveOptions() without a specified player used current player.
Definition: Othello.h:244
void DoFlips(Player player, Index pos)
NOTE: does not check for move validity.
Definition: Othello.h:331
#define emp_assert(...)
Definition: assert.h:199
Definition: Othello.h:36
board_t & GetBoard()
Definition: Othello.h:163
void SetCurPlayer(Player player)
Set the current player.
Definition: Othello.h:302
void Print(std::ostream &os=std::cout, std::string dark_token="D", std::string light_token="L", std::string open_space="O")
Print board state to given ostream.
Definition: Othello.h:338
void SetBoard(const board_t &other_board)
Definition: Othello.h:296
Definition: Othello.h:36
void Reset()
Reset the board to the starting condition.
Definition: Othello.h:103
double GetScore(Player player)
Get the current score for a given player.
Definition: Othello.h:256
bool DoMove(Player player, Index pos)
Definition: Othello.h:315
Index(size_t x, size_t y)
Definition: Othello.h:53
Player GetPosOwner(Index id) const
Get the value (light, dark, or open) at a position on the board.
Definition: Othello.h:158
Index CalcNeighbor(Facing dir)
Definition: Othello.h:62
Index(const Index &_in)
Definition: Othello.h:54