Board.h

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