You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 

392 lines
7.8 KiB

  1. #pragma once
  2. #include <cassert>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <sys/types.h>
  6. #include <sys/stat.h>
  7. #include <fcntl.h>
  8. #include <unistd.h>
  9. typedef unsigned int idx_t;
  10. /*
  11. * Potential values for the pieces on the board.
  12. */
  13. enum FieldType
  14. {
  15. EMPTY,
  16. PLAYER_1,
  17. PLAYER_2,
  18. OUT_OF_BOUNDS
  19. };
  20. /*
  21. * direction flags are used by the algorithms below to validate
  22. * and perform moves.
  23. */
  24. enum direction {
  25. LEFT,
  26. RIGHT,
  27. UP,
  28. DOWN,
  29. UP_LEFT,
  30. UP_RIGHT,
  31. DOWN_LEFT,
  32. DOWN_RIGHT
  33. };
  34. class OthelloBoard
  35. {
  36. protected:
  37. idx_t _rows; // no. of rows
  38. idx_t _cols; // no. of columns
  39. bool _last_player_skipped; // remember if last player skipped
  40. bool _both_skipped; // termination condition
  41. FieldType *_field; // array storing the types of stones set on the board
  42. FieldType _player; // whose turn is it?
  43. /* make object non-assignable */
  44. OthelloBoard& operator=(OthelloBoard&)
  45. { return *this; }
  46. private:
  47. /*
  48. * Depending on a given direction, we need to setup up to four
  49. * variables in different types of algorithms. This convenience
  50. * function does so.
  51. */
  52. void setup_directions(unsigned &row_idx, unsigned &col_idx,
  53. int &inc_row, int &inc_col, direction const dir) const;
  54. /*
  55. * Check if a position is reachable from a given direction.
  56. *
  57. * Reachability means, that from the target position given by
  58. * (row, col) there are only non-empty stones of type != _player until
  59. * we find a stone of type _player.
  60. */
  61. bool position_reachable(unsigned row, unsigned col,
  62. direction const dir) const;
  63. /*
  64. * Really make a move
  65. */
  66. void make_move(unsigned row, unsigned col,
  67. direction dir);
  68. /*
  69. * Validate correctness of a move.
  70. *
  71. * \param row, col coordinates to move to
  72. *
  73. * \return true if move is valid
  74. */
  75. bool validate(unsigned row, unsigned col, bool silent=false) const;
  76. public:
  77. /*
  78. * Get the number of rows.
  79. */
  80. unsigned rows() const { return _rows; }
  81. /*
  82. * Get the number of columns
  83. */
  84. unsigned columns() const { return _cols; }
  85. /*
  86. * Construct a default OthelloBoard
  87. */
  88. OthelloBoard(unsigned r = 8,
  89. unsigned c = 8)
  90. : _rows(r),
  91. _cols(c),
  92. _last_player_skipped(false),
  93. _both_skipped(false),
  94. _field(0),
  95. _player(PLAYER_1)
  96. {
  97. _field = new FieldType[rows()*columns()];
  98. for (unsigned idx = 0; idx < rows() * columns(); ++idx)
  99. _field[idx] = EMPTY;
  100. set(rows()/2, columns()/2, PLAYER_1);
  101. set(rows()/2+1, columns()/2+1, PLAYER_1);
  102. set(rows()/2, columns()/2 + 1, PLAYER_2);
  103. set(rows()/2+1, columns()/2, PLAYER_2);
  104. }
  105. /*
  106. * Copy constructor.
  107. *
  108. * XXX: If you plan to use it, go and implement it!
  109. */
  110. OthelloBoard(const OthelloBoard& copy);
  111. /* Destructor */
  112. virtual ~OthelloBoard() { delete [] _field; }
  113. /* Get current player type */
  114. FieldType player() const { return _player; }
  115. /* Set current player */
  116. void player(int no) {
  117. switch(no) {
  118. case 0: _player = PLAYER_1; break;
  119. case 1: _player = PLAYER_2; break;
  120. default: assert(false); break;
  121. }
  122. }
  123. /*
  124. * Dump the current board state to a file
  125. */
  126. bool dump_to_fd(int fd, bool fancy = false) const
  127. {
  128. FILE *file = fdopen(dup(fd), "w");
  129. if (!file) return false;
  130. // print head line
  131. if (fancy)
  132. ::fprintf(file, " %c ", type_to_str(_player));
  133. else
  134. ::fprintf(file, "%c", type_to_str(_player));
  135. if (fancy) {
  136. for (unsigned c = 0; c < columns(); ++c)
  137. ::fprintf(file, "%d ", c+1);
  138. ::fprintf(file,"\n");
  139. }
  140. for (unsigned r = 0; r < rows(); ++r) {
  141. if (fancy) ::fprintf(file, "%2d ", r+1);
  142. for (unsigned c = 0; c < columns(); ++c) {
  143. if (fancy)
  144. ::fprintf(file, "%s ", type_to_str_fancy(get(r+1, c+1)));
  145. else {
  146. ::fprintf(file, "%c", type_to_str(get(r+1,c+1)));
  147. }
  148. }
  149. if (fancy) ::fprintf(file,"\n");
  150. }
  151. fclose(file);
  152. return true;
  153. }
  154. /* Special case: dump to stdout */
  155. bool dump_to_stdio() const { return dump_to_fd(STDOUT_FILENO, true); }
  156. /*
  157. * Get element at location.
  158. *
  159. * Location coordinates are
  160. * row with 0 < row <= rows()
  161. * col with 0 < col <= columns()
  162. *
  163. * Otherwise, returns OUT_OF_BOUNDS field type.
  164. */
  165. FieldType get(unsigned row, unsigned col) const
  166. {
  167. if ((row <= 0) ||
  168. (col <= 0) ||
  169. (row > rows()) ||
  170. (col > columns()))
  171. return OUT_OF_BOUNDS;
  172. return _field[(row-1)*columns() + col - 1];
  173. }
  174. /*
  175. * Set element at certain location.
  176. *
  177. * Location coordinates are
  178. * row with 0 < row <= rows()
  179. * col with 0 < col <= columns()
  180. */
  181. void set(unsigned row, unsigned col, FieldType type)
  182. {
  183. assert(row > 0);
  184. assert(row <= rows());
  185. assert(col > 0);
  186. assert(col <= columns());
  187. _field[(row-1)*columns() + col - 1] = type;
  188. }
  189. /*
  190. * Perform a move.
  191. *
  192. * First, validates the move. Then performs all necessary
  193. * field type conversions.
  194. */
  195. bool move(unsigned row, unsigned col);
  196. /*
  197. * Count the number of fields that contain a stone
  198. * of the given type.
  199. */
  200. unsigned count_of_type(FieldType t) const
  201. {
  202. unsigned res = 0;
  203. for (unsigned i = 0; i < rows() * columns(); ++i)
  204. if (_field[i] == t) res += 1;
  205. return res;
  206. }
  207. void skipped()
  208. {
  209. if (_last_player_skipped)
  210. _both_skipped = true;
  211. else
  212. _last_player_skipped = true;
  213. }
  214. /*
  215. * Determine whether the game is done.
  216. */
  217. bool finished() const
  218. {
  219. unsigned c1 = count_of_type(PLAYER_1);
  220. unsigned c2 = count_of_type(PLAYER_2);
  221. return ( _both_skipped ||
  222. (c1 == 0) ||
  223. (c2 == 0) ||
  224. (c1 + c2 >= 64)
  225. );
  226. }
  227. /*
  228. * Transform field type into fancy print version (for stdio).
  229. */
  230. char const *type_to_str_fancy(FieldType t) const
  231. {
  232. switch (t) {
  233. case EMPTY: return "\033[34;1m.\033[0m";
  234. case PLAYER_1: return "\033[31mO\033[0m";
  235. case PLAYER_2: return "\033[33mX\033[0m";
  236. case OUT_OF_BOUNDS: return "/";
  237. default: __builtin_unreachable();
  238. }
  239. }
  240. /*
  241. * Transform field type into print version.
  242. */
  243. char type_to_str(FieldType t) const
  244. {
  245. switch (t) {
  246. case EMPTY: return '.';
  247. case PLAYER_1: return 'O';
  248. case PLAYER_2: return 'X';
  249. case OUT_OF_BOUNDS: return '/';
  250. default: __builtin_unreachable();
  251. }
  252. }
  253. /*
  254. * Check, whether the given player can make any move at the moment.
  255. */
  256. bool can_move() const
  257. {
  258. for (unsigned r = 1; r <= rows(); ++r)
  259. for (unsigned c = 1; c <= columns(); ++c)
  260. if (validate(r, c, true))
  261. return true;
  262. return false;
  263. }
  264. /*
  265. * Invalidate all stones belonging to a player.
  266. *
  267. * The engine uses this as a penalty for making more than 3
  268. * illegal moves in a row.
  269. */
  270. void invalidate_stones(FieldType t)
  271. {
  272. for (unsigned idx = 0; idx < rows() * columns(); ++idx)
  273. if (_field[idx] == t)
  274. _field[idx] = EMPTY;
  275. }
  276. };
  277. struct OthelloMove
  278. {
  279. idx_t row;
  280. idx_t col;
  281. OthelloMove(idx_t r=0, idx_t c=0)
  282. : row(r), col(c)
  283. { }
  284. };
  285. /***************************************
  286. * MCP adaptor definitions & functions *
  287. ***************************************/
  288. typedef OthelloBoard game_state;
  289. typedef OthelloMove game_move;
  290. /**
  291. * Game state is serialized into a human-readable string.
  292. */
  293. bool serialize_state(int fd, const game_state *state);
  294. /**
  295. * Game state is parsed from a string written by serialize_state.
  296. */
  297. bool deserialize_state(int fd, game_state *state);
  298. bool serialize_move (int fd, const game_move *move);
  299. bool deserialize_move(int fd, game_move *move);
  300. /**
  301. * Generate the initial board.
  302. */
  303. void initialize_state(game_state *state, char const *init);
  304. /**
  305. * Returns true, if this is a final game state.
  306. */
  307. bool is_final_state(game_state const *state);
  308. /**
  309. * Tries to apply a move to the given state. Returns false, if the
  310. * move was invalid.
  311. */
  312. bool apply_move(game_state *state,
  313. const game_move *move);