Empirical
Othello8.h
Go to the documentation of this file.
1 
13 #ifndef EMP_GAME_OTHELLO8_H
14 #define EMP_GAME_OTHELLO8_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 #include "../tools/bitset_utils.h"
26 
27 namespace emp {
33 
35  class Othello8 {
36  public:
37  enum Player { DARK=0, LIGHT=1, NONE };
38  enum Facing { N, NE, E, SE, S, SW, W, NW };
39  static constexpr size_t NUM_DIRECTIONS = 8;
40  static constexpr size_t BOARD_SIZE = 8;
41  static constexpr size_t NUM_CELLS = 64;
42  using this_t = Othello8;
43 
44  struct Index {
45  size_t pos;
46 
47  constexpr Index() : pos(NUM_CELLS) { ; } // Default constructor is invalid position.
48  constexpr Index(size_t _pos) : pos(_pos) { emp_assert(pos <= NUM_CELLS); }
49  constexpr Index(size_t x, size_t y) : pos() { Set(x,y); }
50  constexpr Index(const Index & _in) : pos(_in.pos) { emp_assert(pos <= NUM_CELLS); }
51 
52  operator size_t() const { return pos; }
53  size_t x() const { return pos & 7; }
54  size_t y() const { return pos >> 3; }
55  void Set(size_t x, size_t y) { pos = (x<BOARD_SIZE && y<BOARD_SIZE) ? (x+(y<<3)) : NUM_CELLS; }
56  bool IsValid() const { return pos < NUM_CELLS; }
57 
59  Index faced_id;
60  switch(dir) {
61  case Facing::N: { faced_id.Set(x() , y() - 1); break; }
62  case Facing::S: { faced_id.Set(x() , y() + 1); break; }
63  case Facing::E: { faced_id.Set(x() + 1, y() ); break; }
64  case Facing::W: { faced_id.Set(x() - 1, y() ); break; }
65  case Facing::NE: { faced_id.Set(x() + 1, y() - 1); break; }
66  case Facing::NW: { faced_id.Set(x() - 1, y() - 1); break; }
67  case Facing::SE: { faced_id.Set(x() + 1, y() + 1); break; }
68  case Facing::SW: { faced_id.Set(x() - 1, y() + 1); break; }
69  }
70  return faced_id;
71  }
72  };
73 
74  struct Board {
75  uint64_t occupied;
76  uint64_t player;
77 
78  void Clear() { occupied = 0; player = 0; }
79  void Clear(Index pos) { uint64_t mask = ~(((uint64_t) 1) << pos); occupied &= mask; player &= mask; }
80  Player Owner(Index pos) const {
81  uint64_t id = (((uint64_t) 1) << pos);
82  if (occupied & id) return (player & id) ? Player::LIGHT : Player::DARK;
83  else return Player::NONE;
84  }
85  void SetOwner(Index pos, Player owner) {
86  const uint64_t id = ((uint64_t) 1) << pos;
87  occupied |= id;
88  if (owner == Player::DARK) player &= ~id;
89  else player |= id;
90  }
91  bool Occupied(Index pos) { return (occupied >> pos) & (size_t) 1; }
92 
93  size_t Score(Player owner) {
94  if (owner == Player::DARK) return count_bits(occupied & ~player);
95  return count_bits(player);
96  }
97  };
98 
99  protected:
101  static const auto & ALL_DIRECTIONS() {
102  static std::array<Facing, NUM_DIRECTIONS> dirs =
103  { Facing::N, Facing::NE, Facing::E, Facing::SE,
104  Facing::S, Facing::SW, Facing::W, Facing::NW };
105  return dirs;
106  }
107 
109  static size_t GetNeighborIndex(Index pos, Facing dir) {
110  return (((size_t) pos) * NUM_DIRECTIONS) + (size_t) dir;
111  }
112 
114  static const auto & NEIGHBORS() {
115  static emp::vector<Index> neighbors;
116  if (neighbors.size() == 0) {
117  neighbors.resize(NUM_CELLS * NUM_DIRECTIONS);
118  for (size_t posID = 0; posID < NUM_CELLS; ++posID) {
119  Index pos(posID);
120  for (Facing dir : ALL_DIRECTIONS()) {
121  neighbors[GetNeighborIndex(posID, dir)] = pos.CalcNeighbor(dir);
122  }
123  }
124  }
125  return neighbors;
126  }
127 
128  bool over = false;
131 
133  std::array<flip_list_t, NUM_CELLS> light_flips;
134  std::array<flip_list_t, NUM_CELLS> dark_flips;
135  bool cache_ok;
136 
137  public:
138  Othello8() : cur_player(Player::DARK), game_board(), light_flips(), dark_flips(), cache_ok(false) { Reset(); }
139 
140  ~Othello8() { ; }
141 
143  void Reset() {
144  // Reset the board.
145  game_board.Clear();
146 
147  // Setup Initial board
148  // ........
149  // ...LD...
150  // ...DL...
151  // ........
152  SetPos({BOARD_SIZE/2 - 1, BOARD_SIZE/2 - 1}, Player::LIGHT);
153  SetPos({BOARD_SIZE/2 - 1, BOARD_SIZE/2 }, Player::DARK);
154  SetPos({BOARD_SIZE/2, BOARD_SIZE/2 - 1}, Player::DARK);
155  SetPos({BOARD_SIZE/2, BOARD_SIZE/2 }, Player::LIGHT);
156 
157  over = false;
158  cur_player = Player::DARK;
159 
160  cache_ok = false;
161  }
162 
163  static constexpr Index GetIndex(size_t x, size_t y) { return Index(x, y); }
164  static constexpr size_t GetBoardWidth() { return BOARD_SIZE; }
165  size_t GetNumCells() const { return NUM_CELLS; }
166  Player GetCurPlayer() const { return cur_player; }
167  size_t GetHash() const { return game_board.occupied; }
168 
170  Player GetOpponent(Player player) const {
171  return (player == Player::DARK) ? Player::LIGHT : Player::DARK;
172  }
173 
175  bool IsValidPlayer(Player player) const { return (player == Player::DARK) || (player == Player::LIGHT); }
176 
180  if (!id.IsValid()) return Index();
181  return NEIGHBORS()[GetNeighborIndex(id, dir)];
182  }
183 
186  emp_assert(id.IsValid());
187  return game_board.Owner(id);
188  }
189 
190  Board & GetBoard() { return game_board; }
191  const Board & GetBoard() const { return game_board; }
192 
194  bool IsValidMove(Player player, Index pos) {
195  emp_assert(IsValidPlayer(player));
196  if (!pos.IsValid()) return false; // Is pos even on the board?
197  if (game_board.Occupied(pos)) return false; // Is pos empty?
198  return HasValidFlips(player, pos); // Will any tiles flip?
199  }
200 
201  bool IsOver() const { return over; }
202 
203  void SetupCache() {
204  for (size_t pos = 0; pos < NUM_CELLS; pos++) {
205  GetFlipList(Player::LIGHT, pos);
206  GetFlipList(Player::DARK, pos);
207  }
208  cache_ok = true;
209  }
210 
214  emp_assert(player != Player::NONE);
215  emp::vector<Index> & flip_list = (player == Player::LIGHT) ? light_flips[pos] : dark_flips[pos];
216  if (cache_ok == false) {
217  flip_list.resize(0);
218  size_t prev_len = 0;
219  const Player opponent = GetOpponent(player);
220  for (Facing dir : ALL_DIRECTIONS()) {
221  Index neighbor_pos = GetNeighbor(pos, dir);
222  // Collect opponent spaces in this direction.
223  while (neighbor_pos.IsValid() && GetPosOwner(neighbor_pos) == opponent) {
224  flip_list.emplace_back(neighbor_pos);
225  neighbor_pos = GetNeighbor(neighbor_pos, dir);
226  }
227  // If this line didn't end in current color, throw out everything we found.
228  if (!neighbor_pos.IsValid() || !game_board.Occupied(neighbor_pos)) { flip_list.resize(prev_len); }
229  // Otherwise keep it and update the locked in flips.
230  else { prev_len = flip_list.size(); }
231  }
232  }
233  return flip_list;
234  }
235 
237  size_t GetFlipCount(Player player, Index pos) {
238  if (cache_ok) {
239  return (player == Player::LIGHT) ? light_flips[pos].size() : dark_flips[pos].size();
240  }
241  size_t flip_count = 0;
242  const Player opponent = GetOpponent(player);
243  for (Facing dir : ALL_DIRECTIONS()) {
244  // Collect opponent spaces in this direction.
245  size_t dir_count = 0;
246  Index neighbor_pos = GetNeighbor(pos, dir);
247  while (neighbor_pos.IsValid() && GetPosOwner(neighbor_pos) == opponent) {
248  dir_count++;
249  neighbor_pos = GetNeighbor(neighbor_pos, dir);
250  }
251  // If this line ended in the correct color, add this direction to the total_count.
252  if (neighbor_pos.IsValid() && GetPosOwner(neighbor_pos) == player) { flip_count += dir_count; }
253  }
254  return flip_count;
255  }
256 
258  bool HasValidFlips(Player player, Index pos) {
259  if (cache_ok) {
260  return (player == Player::LIGHT) ? light_flips[pos].size() : dark_flips[pos].size();
261  }
262  const Player opponent = GetOpponent(player);
263  for (Facing dir : ALL_DIRECTIONS()) { // Loop through directions to explore
264  Index neighbor_pos = GetNeighbor(pos, dir); // Start at first neighbor.
265  size_t count = 0;
266  // Collect opponent spaces in this direction.
267  while (neighbor_pos.IsValid() && GetPosOwner(neighbor_pos) == opponent) {
268  count++;
269  neighbor_pos = GetNeighbor(neighbor_pos, dir);
270  }
271  // If this line ended with current color (and has spots to flip) we found a good solution!
272  if (count && neighbor_pos.IsValid() && GetPosOwner(neighbor_pos) == player) { return true; }
273  }
274  return false;
275  }
276 
277 
280  emp_assert(IsValidPlayer(player));
281  emp::vector<Index> valid_moves;
282  for (size_t i = 0; i < NUM_CELLS; ++i) {
283  if (IsValidMove(player, i)) valid_moves.emplace_back(i);
284  }
285  return valid_moves;
286  }
287 
290 
292  bool HasMoveOptions(Player player) {
293  emp_assert(IsValidPlayer(player));
294  for (size_t i = 0; i < NUM_CELLS; ++i) {
295  if (IsValidMove(player, i)) return true;
296  }
297  return false;
298  }
299 
301  double GetScore(Player player) {
302  emp_assert(IsValidPlayer(player));
303  return (double) game_board.Score(player);
304  }
305 
307  size_t CountFrontierPos(Player player) {
308  emp_assert(IsValidPlayer(player));
309  size_t frontier_size = 0;
310  for (size_t i = 0; i < NUM_CELLS; ++i) { // Search through all cells
311  if (game_board.Occupied(i) == false) { // Is the test cell empty?
312  if (IsAdjacentTo(i, player)) ++frontier_size; // If so, test if on player's frontier
313  }
314  }
315  return frontier_size;
316  }
317 
319  bool IsAdjacentTo(Index pos, Player owner) {
320  for (Facing dir : ALL_DIRECTIONS()) {
321  Index nID = GetNeighbor(pos, dir);
322  if (!nID.IsValid()) continue;
323  if (GetPosOwner(nID) == owner) return true;
324  }
325  return false;
326  }
327 
329  void SetPos(Index pos, Player player) {
330  emp_assert(pos.IsValid());
331  game_board.SetOwner(pos, player);
332  cache_ok = false;
333  }
334 
336  game_board.Clear(pos);
337  cache_ok = false;
338  }
339 
342  for (auto x : ids) SetPos(x, player);
343  }
344 
347  void SetBoard(const Board & other_board) { game_board = other_board; cache_ok = false; }
348 
350  void SetBoard(const this_t & other_othello) { SetBoard(other_othello.GetBoard()); }
351 
353  void SetCurPlayer(Player player) {
354  emp_assert(IsValidPlayer(player));
355  cur_player = player;
356  }
357 
360  bool DoNextMove(Index pos) { return DoMove(cur_player, pos); }
361 
366  bool DoMove(Player player, Index pos) {
367  emp_assert(IsValidPlayer(player) && pos.IsValid()); // Validate position and player.
368  emp_assert(GetPosOwner(pos) == Player::NONE); // Make sure position is empty.
369  SetPos(pos, player); // Take position for player.
370  DoFlips(player, pos); // Flip tiles on the board.
371  auto opp_moves = HasMoveOptions(GetOpponent(player)); // Test if opponent can go.
372  if (opp_moves) { cur_player = GetOpponent(player); return false; }
373 
374  auto player_moves = HasMoveOptions(player); // Opponent can't go; test cur player
375  if (player_moves) { return true; } // This player can go again!
376 
377  over = true; // No one can go; game over!
378  return false;
379  }
380 
382  void DoFlips(Player player, Index pos) {
383  emp_assert(IsValidPlayer(player));
384  auto flip_list = GetFlipList(player, pos);
385  for (Index flip : flip_list) { SetPos(flip, player); }
386  }
387 
389  void Print(std::ostream & os=std::cout, std::string dark_token = "D",
390  std::string light_token = "L", std::string open_space = "O") {
391  // Output column labels.
392  unsigned char letter = 'A';
393  os << "\n ";
394  for (size_t i = 0; i < BOARD_SIZE; ++i) os << char(letter + i) << " ";
395  os << "\n";
396  // Output row labels and board information.
397  for (size_t y = 0; y < BOARD_SIZE; ++y) {
398  os << y << " ";
399  for (size_t x = 0; x < BOARD_SIZE; ++x) {
400  Player space = GetPosOwner({x,y});
401  if (space == Player::DARK) { os << dark_token << " "; }
402  else if (space == Player::LIGHT) { os << light_token << " "; }
403  else { os << open_space << " "; }
404  }
405  os << "\n";
406  }
407  }
408  };
409 
410 }
411 
412 #endif
bool cache_ok
Definition: Othello8.h:135
static constexpr Index GetIndex(size_t x, size_t y)
Definition: Othello8.h:163
void SetBoard(const Board &other_board)
Definition: Othello8.h:347
Definition: Othello8.h:38
static size_t GetNeighborIndex(Index pos, Facing dir)
Internal function for accessing the neighbors vector.
Definition: Othello8.h:109
std::array< flip_list_t, NUM_CELLS > dark_flips
Definition: Othello8.h:134
bool IsValid() const
Definition: Othello8.h:56
void Reset()
Reset the board to the starting condition.
Definition: Othello8.h:143
void SetPositions(emp::vector< Index > ids, Player player)
Set positions given by ids to be owned by the given player.
Definition: Othello8.h:341
size_t GetHash() const
Definition: Othello8.h:167
bool HasValidFlips(Player player, Index pos)
Are there any valid flips from this position?
Definition: Othello8.h:258
constexpr const double E
e
Definition: const.h:18
constexpr Index(size_t _pos)
Definition: Othello8.h:48
constexpr size_t count_bits(uint64_t val)
Count the number of bits in a 64-bit unsigned integer.
Definition: bitset_utils.h:39
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: Othello8.h:237
size_t x() const
Definition: Othello8.h:53
bool IsAdjacentTo(Index pos, Player owner)
Is position given by ID adjacent to the given owner?
Definition: Othello8.h:319
bool IsValidPlayer(Player player) const
Is the given player ID a valid player?
Definition: Othello8.h:175
bool IsOver() const
Definition: Othello8.h:201
void SetupCache()
Definition: Othello8.h:203
Facing
Definition: Othello8.h:38
Player GetCurPlayer() const
Definition: Othello8.h:166
uint64_t occupied
Definition: Othello8.h:75
static constexpr size_t GetBoardWidth()
Definition: Othello8.h:164
Othello8()
Definition: Othello8.h:138
bool IsValidMove(Player player, Index pos)
Is given move valid?
Definition: Othello8.h:194
static const auto & NEIGHBORS()
Precalculated neighbors.
Definition: Othello8.h:114
Definition: Othello8.h:37
Definition: Othello8.h:38
size_t CountFrontierPos(Player player)
Count the number of empty squares adjacent to a player&#39;s pieces (frontier size)
Definition: Othello8.h:307
double GetScore(Player player)
Get the current score for a given player.
Definition: Othello8.h:301
Player Owner(Index pos) const
Definition: Othello8.h:80
size_t size() const
Definition: vector.h:151
void emplace_back(ARGS &&...args)
Definition: vector.h:219
void ClearPos(Index pos)
Definition: Othello8.h:335
bool over
Is the game over?
Definition: Othello8.h:128
std::array< flip_list_t, NUM_CELLS > light_flips
Definition: Othello8.h:133
constexpr Index()
Definition: Othello8.h:47
constexpr Index(size_t x, size_t y)
Definition: Othello8.h:49
emp::vector< Index > GetMoveOptions()
GetMoveOptions() without a specified player used current player.
Definition: Othello8.h:289
void Clear(Index pos)
Definition: Othello8.h:79
void SetPos(Index pos, Player player)
Set board position (ID) to given space value.
Definition: Othello8.h:329
void DoFlips(Player player, Index pos)
NOTE: does not check for move validity.
Definition: Othello8.h:382
Definition: Othello8.h:44
bool DoMove(Player player, Index pos)
Definition: Othello8.h:366
Definition: Othello8.h:38
constexpr Index(const Index &_in)
Definition: Othello8.h:50
const Board & GetBoard() const
Definition: Othello8.h:191
size_t pos
Definition: Othello8.h:45
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: Othello8.h:389
void resize(size_t new_size)
Definition: vector.h:161
bool HasMoveOptions(Player player)
Determine if there are any move options for given player.
Definition: Othello8.h:292
size_t GetNumCells() const
Definition: Othello8.h:165
Player GetPosOwner(Index id) const
Get the value (light, dark, or open) at a position on the board.
Definition: Othello8.h:185
size_t Score(Player owner)
Definition: Othello8.h:93
Definition: Othello8.h:37
void SetOwner(Index pos, Player owner)
Definition: Othello8.h:85
Definition: Othello8.h:38
If we are in emscripten, make sure to include the header.
Definition: array.h:37
bool Occupied(Index pos)
Definition: Othello8.h:91
void SetCurPlayer(Player player)
Set the current player.
Definition: Othello8.h:353
bool DoNextMove(Index pos)
Definition: Othello8.h:360
Definition: Othello8.h:38
Build a debug wrapper emp::vector around std::vector.
Definition: vector.h:42
emp::vector< Index > GetMoveOptions(Player player)
Get a list of valid move options for given player.
Definition: Othello8.h:279
Index CalcNeighbor(Facing dir)
Definition: Othello8.h:58
#define emp_assert(...)
Definition: assert.h:199
Index GetNeighbor(Index id, Facing dir)
Definition: Othello8.h:179
void Set(size_t x, size_t y)
Definition: Othello8.h:55
Board game_board
Game board.
Definition: Othello8.h:130
static constexpr size_t NUM_CELLS
Number of cells on total board.
Definition: Othello8.h:41
static constexpr size_t NUM_DIRECTIONS
Number of neighbors each board space has.
Definition: Othello8.h:39
static constexpr size_t BOARD_SIZE
Size of a side of the board.
Definition: Othello8.h:40
~Othello8()
Definition: Othello8.h:140
size_t y() const
Definition: Othello8.h:54
Definition: Othello8.h:38
Player
Definition: Othello8.h:37
Definition: Othello8.h:74
uint64_t player
Definition: Othello8.h:76
Class for size-8 othello games.
Definition: Othello8.h:35
Player GetOpponent(Player player) const
Get opponent ID of give player ID.
Definition: Othello8.h:170
void SetBoard(const this_t &other_othello)
Set current board to be the same as board from other othello game.
Definition: Othello8.h:350
Definition: Othello8.h:38
void Clear()
Definition: Othello8.h:78
Board & GetBoard()
Definition: Othello8.h:190
Player cur_player
Who is the current player set to move next?
Definition: Othello8.h:129
const emp::vector< Index > & GetFlipList(Player player, Index pos)
Definition: Othello8.h:213
Definition: Othello8.h:37
Definition: Othello8.h:38
static const auto & ALL_DIRECTIONS()
All eight cardinal directions.
Definition: Othello8.h:101