Board.h

   1 #ifndef __IA_BOARD_H__
   2 #define __IA_BOARD_H__
   3
   4 #include "common.h"
   5
   6 #include <bitset>
   7 #include <map>
   8 #include <vector>
   9 #include <set>
  10
  11 #define DIAG0(i, j) ((i) + (j))
  12 #define DIAG1(i, j) ((i) - (j) + 7)
  13
  14 #define MoveOt(x, y)  (((x) << 6) + (y))
  15
  16 #define INDEX_X(i) ((i) >> 3)
  17 #define INDEX_Y(i) ((i) & 7)
  18
  19 #define INDEX_FROM(i) ((i) >> 6)
  20 #define INDEX_TO(i) ((i) & 63)
  21
  22 extern char horiz[8], vert[8], diag[2][15];
  23 extern std::bitset<64> adj, both;
  24 extern bool g_player;
  25 extern char dx[4], dy[4];
  26
  27 class Board
  28 {
  29 public:
  30         //representação das peças de um dos jogadores
  31   typedef std::bitset<64> Imp;
  32         //representação das peças de um dos jogadores para fins de comparação
  33         typedef unsigned long long ImpComp;
  34         //representação do board para comparação
  35         typedef std::pair<ImpComp, ImpComp> Comp;
  36         //conjunto de boards
  37         typedef std::set<Comp, bool (*)(const Comp&, const Comp&)> Set;
  38         //representação dos movimentos (origem, destino) em coordenadas absolutas [0,63]
  39   typedef std::pair<char, char> Move;
  40   typedef std::vector<Move> MoveList; //Lista de movimentos
  41         // representação otimizada (origem << 6 + destino) em coordenadas absolutas [0, 63]
  42         typedef unsigned int MoveOt;
  43         typedef MoveOt MoveListOt[8 * 12]; //Lista de movimentos otimizada
  44
  45   Board();
  46   ~Board() {}
  47   void initial_position();
  48
  49   inline void set(bool player, char i, char j, bool val = true) {
  50     //t[player].set(INDEX(i, j), val);
  51     t[player][INDEX(i, j)] = val;
  52   }
  53
  54   inline bool get(bool player, char i, char j) {
  55     return t[player]._Unchecked_test(INDEX(i, j)); //profiling
  56     //return t[player][INDEX(i, j)];
  57   }
  58
  59   /* efetua o movimento move pelo jogador player */
  60         inline void move(bool player, Move move) {
  61                 t[player][move.first] = t[!player][move.second] = 0;
  62                 t[player][move.second] = 1;
  63         }
  64
  65         /* efetua o movimento num tabuleiro novo */
  66         inline Board move_result(bool player, MoveOt move) {
  67                 Board res = *this;
  68                 res.t[player][INDEX_FROM(move)] = res.t[!player][INDEX_TO(move)] = 0;
  69                 res.t[player][INDEX_TO(move)] = 1;
  70                 return res;
  71         }
  72
  73         /* efetua o movimento num tabuleiro novo */
  74         inline Board move_result(bool player, Move move) {
  75                 Board res = *this;
  76                 /* por que não res.move(player, move); ? */
  77                 res.t[player][move.first] = res.t[!player][move.second] = 0;
  78                 res.t[player][move.second] = 1;
  79                 return res;
  80         }
  81
  82         /* gera uma lista com os movimentos partindo de fromX, fromY */
  83         void moves(bool player, int fromX, int fromY, MoveList &to);
  84
  85         /* gera uma lista com todos os movimentos possíveis do jogador player */
  86         /* copy paste da moves, necessária por uma questão de eficiência */
  87         int all_moves(bool player, MoveListOt &to) {
  88                 rep(i, 8)
  89                         horiz[i] = vert[i] = 0;
  90                 rep(i, 15)
  91                         diag[0][i] = diag[1][i] = 0;
  92
  93                 both = t[0] | t[1];
  94
  95                 char pos = both._Find_first();
  96                 do {
  97                         int i = INDEX_X(pos), j = INDEX_Y(pos);
  98                         horiz[i]++;
  99                         vert[j]++;
 100                         diag[0][DIAG0(i, j)]++;
 101                         diag[1][DIAG1(i, j)]++;
 102                 } while((pos = both._Find_next(pos)) != 64);
 103
 104                 int k, x, y, res = 0;
 105                 bool valid_move;
 106
 107                 pos = t[player]._Find_first();
 108                 do {
 109                         int i = INDEX_X(pos), j = INDEX_Y(pos);
 110                         rep(d, 4) {
 111                                 k = count(d, i, j);
 112                                 for(int m = -1; m <= 1; m += 2) {
 113                                         valid_move = true;
 114                                         /* Fiz uma otimização aqui, diga-me o que achas de-
 115                                                  pois. Principal melhora é no for. */
 116                                         int tmp1 = dx[d] * m;
 117                                         int tmp2 = dy[d] * m;
 118
 119                                         x = i + k * tmp1;
 120                                         y = j + k * tmp2;
 121                                         if(x > 7 || x < 0 ||
 122                                                  y > 7 || y < 0) { // fora do tabuleiro
 123                                                 continue;
 124                                         }
 125
 126                                         x = i;
 127                                         y = j;
 128                                         repb(z, 1, k) {
 129                                                 x += tmp1;
 130                                                 y += tmp2;
 131                                                 if(get(!player, x, y)) { // barrado por inimigo
 132                                                         valid_move = false;
 133                                                         break;
 134                                                 }
 135                                         }
 136
 137                                         if(valid_move) {
 138                                                 x += tmp1;
 139                                                 y += tmp2;
 140                                                 if(!get(player, x, y)) { // não é sobre um amigo
 141                                                         to[res++] = MoveOt(pos, INDEX(x, y));
 142                                                 }
 143                                         }
 144                                 }
 145                         }
 146                 } while((pos = t[player]._Find_next(pos)) != 64);
 147                 return res;
 148         }
 149
 150         /* retorna a quantidade de peças vivas */
 151         inline char count() {
 152                 return t[0].count() + t[1].count();
 153         }
 154
 155   /* retorna a quantidade de casas que a peça na posição (i, j) pode andar na direção d */
 156   inline char count(int d, char i, char j) {
 157     switch(d) {
 158       case 1: return vert[(int) j];
 159       case 0: return horiz[(int) i];
 160       case 2: return diag[1][DIAG1(i, j)];
 161       case 3: return diag[0][DIAG0(i, j)];
 162     }
 163     return 0;
 164   }
 165
 166         /* retorna uma cópia do tabuleiro */
 167         Board *copy() {
 168                 Board *res = new Board();
 169                 res->t[0] = t[0];
 170                 res->t[1] = t[1];
 171                 return res;
 172         }
 173
 174         /* testa se o jogo terminou */
 175         bool is_end() {
 176                 return t[0].count() < 2 || t[1].count() < 2 || win(0) || win(1);
 177         }
 178
 179         /* função para determinar se as peças do jogador g_player estão adjacentes, partindo da peça na posição (i, j) */
 180         unsigned char adjacent(char i, char j) {
 181                 static char adjdx[] = {-1, -1, -1,  0, 0,  1, 1, 1},
 182                                    adjdy[] = {-1,  0,  1, -1, 1, -1, 0, 1};
 183                 char x, y, z;
 184                 unsigned char res = 1;
 185                 adj._Unchecked_set(INDEX(i, j));
 186                 rep(d, 8) {
 187                         x = i + adjdx[d];
 188                         y = j + adjdy[d];
 189                         if(x > 7 || x < 0 || y > 7 || y < 0) continue;
 190                         z = INDEX(x, y);
 191                         if(adj._Unchecked_test(z) || !t[g_player]._Unchecked_test(z)) continue;
 192                         res += adjacent(x, y);
 193                 }
 194                 return res;
 195         }
 196
 197         /* testa se o jogador player venceu o jogo */
 198         inline bool win(bool player) {
 199                 adj.reset();
 200                 g_player = player;
 201                 char pos = t[player]._Find_first();
 202                 return pos == 64 || adjacent(INDEX_X(pos), INDEX_Y(pos)) == t[player].count();
 203         }
 204
 205         /* converte um bitset para facilitar comparação entre tabuleiros */
 206         inline Board::ImpComp to_imp_comp(const Imp &t) {
 207                 Board::ImpComp res = 0;
 208                 char pos = t._Find_first();
 209                 do {
 210                         res |= ((Board::ImpComp) 1) << pos;
 211                 } while((pos = t._Find_next(pos)) != 64);
 212                 return res;
 213         }
 214
 215         /* converte um board para comparação */
 216         inline Board::Comp to_comp() {
 217                 return Board::Comp(to_imp_comp(t[0]), to_imp_comp(t[1]));
 218         }
 219         friend class MinimaxEnemy;
 220
 221 private:
 222   Imp t[2]; //t[i] representa o tabuleiro somente com as peças do jogador i
 223 };
 224
 225 /* compara boards */
 226 bool board_compare(const Board::Comp& l, const Board::Comp& r);
 227
 228 #endif