13 #ifndef EMP_GAME_OTHELLO8_H 14 #define EMP_GAME_OTHELLO8_H 19 #include <unordered_map> 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" 47 constexpr
Index() : pos(NUM_CELLS) { ; }
49 constexpr
Index(
size_t x,
size_t y) : pos() {
Set(x,y); }
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; }
61 case Facing::N: { faced_id.
Set(
x() ,
y() - 1);
break; }
62 case Facing::S: { faced_id.
Set(
x() ,
y() + 1);
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; }
78 void Clear() { occupied = 0; player = 0; }
79 void Clear(
Index pos) { uint64_t mask = ~(((uint64_t) 1) <<
pos); occupied &= mask; player &= mask; }
81 uint64_t
id = (((uint64_t) 1) <<
pos);
82 if (occupied &
id)
return (player &
id) ? Player::LIGHT : Player::DARK;
86 const uint64_t
id = ((uint64_t) 1) <<
pos;
88 if (owner == Player::DARK) player &= ~id;
94 if (owner == Player::DARK)
return count_bits(occupied & ~player);
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 };
110 return (((
size_t) pos) * NUM_DIRECTIONS) + (size_t) dir;
116 if (neighbors.
size() == 0) {
117 neighbors.
resize(NUM_CELLS * NUM_DIRECTIONS);
118 for (
size_t posID = 0; posID <
NUM_CELLS; ++posID) {
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);
158 cur_player = Player::DARK;
171 return (player == Player::DARK) ? Player::LIGHT : Player::DARK;
187 return game_board.
Owner(
id);
196 if (!pos.
IsValid())
return false;
197 if (game_board.
Occupied(pos))
return false;
215 emp::vector<Index> & flip_list = (player == Player::LIGHT) ? light_flips[pos] : dark_flips[pos];
216 if (cache_ok ==
false) {
230 else { prev_len = flip_list.
size(); }
239 return (player == Player::LIGHT) ? light_flips[
pos].size() : dark_flips[
pos].size();
241 size_t flip_count = 0;
245 size_t dir_count = 0;
252 if (neighbor_pos.
IsValid() &&
GetPosOwner(neighbor_pos) == player) { flip_count += dir_count; }
260 return (player == Player::LIGHT) ? light_flips[
pos].size() : dark_flips[
pos].size();
272 if (count && neighbor_pos.
IsValid() &&
GetPosOwner(neighbor_pos) == player) {
return true; }
303 return (
double) game_board.
Score(player);
309 size_t frontier_size = 0;
311 if (game_board.
Occupied(i) ==
false) {
315 return frontier_size;
336 game_board.
Clear(pos);
342 for (
auto x : ids)
SetPos(
x, player);
347 void SetBoard(
const Board & other_board) { game_board = other_board; cache_ok =
false; }
372 if (opp_moves) { cur_player =
GetOpponent(player);
return false; }
375 if (player_moves) {
return true; }
385 for (
Index flip : flip_list) {
SetPos(flip, player); }
389 void Print(std::ostream & os=std::cout, std::string dark_token =
"D",
390 std::string light_token =
"L", std::string open_space =
"O") {
392 unsigned char letter =
'A';
394 for (
size_t i = 0; i <
BOARD_SIZE; ++i) os <<
char(letter + i) <<
" ";
401 if (space == Player::DARK) { os << dark_token <<
" "; }
402 else if (space == Player::LIGHT) { os << light_token <<
" "; }
403 else { os << open_space <<
" "; }
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'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