main.cpp

   1 #include <cstdlib>
   2 #include <cstdio>
   3 #include <cstring>
   4 #include <ctime>
   5
   6 #include <vector>
   7 #include <string>
   8 #include <bitset>
   9 #include <iostream>
  10 #include <map>
  11 #include <set>
  12
  13 using namespace std;
  14
  15 #define rep(i, n) repb(i, 0, n)
  16 #define repb(i, b, n) repbc(i, b, n, <)
  17 #define repbc(i, b, n, c) for(int i = b; i c n; i++)
  18 #define repe(i, n) repbe(i, 0, n)
  19 #define repbe(i, b, n) repbc(i, b, n, <=)
  20 #define reps(i, n) for(unsigned int i = 0; i < n.size(); i++)
  21
  22 #define getch do{ if(0)scanf("%*c"); }while(0)
  23
  24 #define INDEX(i, j) (((i) << 3) + (j))
  25 #define DIAG0(i, j) ((i) + (j))
  26 #define DIAG1(i, j) ((i) - (j) + 7)
  27
  28 #define MAX_DEPTH 6
  29
  30 char dx[] = {0, 1, 1, 1}, dy[] = {1, 0, 1, -1}; //direções de movimento: vertical, horizontal e duas diagonais
  31
  32 typedef bitset<64> Imp; //representação das peças de um dos jogadores
  33
  34 Imp both, adj; // both armazena o tabuleiro com a peças de um ou de outro jogador
  35                // adj é utiliada para detectar quando algum jogador está em situação de vitória
  36                // podem (vão) se tornar membros estáticos da classe Tab em vez de globais
  37
  38 char horiz[8], vert[8], diag[2][15]; //quantidade de peças na horizontal, vertical e nas duas diagonais
  39
  40 /* converte um bitset correspondente a um tabuleiro para long long,
  41    para facilitar comparação entre tabuleiros */
  42 inline unsigned __int64 to_longlong(const Imp &t)
  43 {
  44   unsigned __int64 res = 0;
  45   rep(i, 64) {
  46     if(t.test(i))
  47       res |= ((unsigned __int64) 1) << i;
  48   }
  49   return res;
  50 }
  51
  52 typedef pair<unsigned __int64, unsigned __int64> TabComp;
  53
  54 /* comparação para o set */
  55 inline bool compareTabComp(const TabComp& l, const TabComp& r)
  56 {
  57   return l.first < r.first || (l.first == r.first && l.second < r.second);
  58 }
  59
  60 /* Classe que representa um tabuleiro do jogo */
  61 class Tab {
  62 public:
  63   typedef bitset<64> Imp; //representação das peças de um dos jogadores
  64   typedef pair<char, char> Move; //representação dos movimentos (origem, destino) em coordenadas absolutas [0,63]
  65
  66   typedef vector<Move> MoveList; //Lista de movimentos
  67                                  //OTI: Move[4 * 12] em vez de vector<Move> -- talvez não seja bom quando há poucas peças
  68                                  //OTI: v.reserve()
  69   inline Tab(){}
  70   inline ~Tab(){}
  71   inline Tab(const Tab& tab) { t[0] = tab.t[0]; t[1] = tab.t[1]; }
  72   inline const Tab& operator=(const Tab& tab) { t[0] = tab.t[0]; t[1] = tab.t[1]; return *this; }
  73
  74   /* há duas formas possíveis para os metodos set, reset e get:
  75      uma que utiliza [] e outra que utiliza a função correspondente
  76      estão aqui para testarmos qual é mais eficiente
  77      [] não testa se o índice é válido, mas retorna uma referência para o valor
  78      () teste se o índice é válido, mas retorna apenas um bool
  79   */
  80
  81   inline void set(bool player, char i, char j, bool val = true) {
  82     //t[player].set(INDEX(i, j), val);
  83     t[player][INDEX(i, j)] = val;
  84   }
  85
  86   inline void reset(bool player, char i, char j) {
  87     //t[player].reset(INDEX(i, j));
  88     t[player][INDEX(i, j)] = false;
  89   }
  90
  91   inline bool get(bool player, char i, char j) {
  92     return t[player].test(INDEX(i, j)); //profiling
  93     //return t[player][INDEX(i, j)];
  94   }
  95
  96   inline void clear() {
  97     t[0].reset();
  98     t[1].reset();
  99   }
 100
 101   /* print bonito do tabuleiro
 102      pode receber o próximo movimento a ser feito
 103   */
 104   inline void print(Move move = Move(-1, -1)) {
 105     system("cls");
 106     /*
 107     rep(p, 2) {
 108       printf("p: %i\n", p);
 109       rep(i, 8) {
 110         rep(j, 8)
 111           printf("%i ", get(p, i, j));
 112         printf("\n");
 113       }
 114       printf("\n");
 115     }//*/
 116     /*
 117     printf("both:\n");
 118     Imp temp = t[0] | t[1];
 119     rep(i, 8) {
 120       rep(j, 8)
 121         printf("%i ", (bool) temp[INDEX(i, j)]);
 122       printf("\n");
 123     }
 124     printf("\n");//*/
 125
 126     //*
 127     char rep[] = ".pb?PBxXX";
 128     rep(i, 8) {
 129       rep(j, 8)
 130         printf("%c", rep[(get(0, i, j) ? 1 : get(1, i, j) ? 2 : 0) + 3 * (move.first == INDEX(i, j)) + 6 * (move.second == INDEX(i, j))]);
 131       printf("\n");
 132     }
 133     printf("\n");//*/
 134
 135     //*
 136     cout << "[0]: " << to_longlong(t[0]) << "\n[1]: " << to_longlong(t[1]) << endl;
 137     //*/
 138
 139     //*
 140     printf("horiz: ");
 141     rep(i, 8)
 142       printf("%i ", horiz[i]);
 143     printf("\n");
 144
 145     printf("vert: ");
 146     rep(i, 8)
 147       printf("%i ", vert[i]);
 148     printf("\n");
 149
 150     printf("diag0: ");
 151     rep(i, 15)
 152         printf("%i ", diag[0][i]);
 153     printf("\n");
 154
 155     printf("diag1: ");
 156     rep(i, 15)
 157         printf("%i ", diag[1][i]);
 158     printf("\n");
 159
 160     getch;
 161   }
 162
 163   /* coloca o tabuleiro na posição inicial */
 164   void initial_position() {
 165     rep(i, 2)
 166       repbe(j, 1, 6) {
 167         set(0, i * 7, j);
 168         set(1, j, i * 7);
 169       }
 170   }
 171
 172   /* retorna a quantidade de casas que a peça na posição (i, j) pode andar na direção d */
 173   inline char count(int d, char i, char j) {
 174     //OTI: contar uma vez para cada linha, coluna e diagonal (8 + 8 + 15 + 15) em vez de 4 * 8 * 8
 175
 176     switch(d) {
 177       case 1:
 178         return vert[(int) j];
 179       case 0:
 180         return horiz[(int) i];
 181       case 2:
 182         return diag[1][DIAG1(i, j)];
 183       case 3:
 184         return diag[0][DIAG0(i, j)];
 185     }
 186     return 0;
 187
 188     /*
 189     int res = 0, x, y;
 190     rep(z, 9) {
 191       x = i + z * dx[d];
 192       y = j + z * dy[d];
 193       if(x > 7 || x < 0 ||
 194          y > 7 || y < 0)
 195         break;
 196       //res += both[INDEX(x, y)];
 197       res += both.test(INDEX(x, y)); //profiling
 198     }
 199     rep(z, 9) {
 200       x = i - z * dx[d];
 201       y = j - z * dy[d];
 202       if(x > 7 || x < 0 ||
 203          y > 7 || y < 0)
 204         break;
 205       //res += both[INDEX(x, y)];
 206       res += both.test(INDEX(x, y)); //profiling
 207     }
 208     //return res - both[INDEX(i, j)];
 209     return res - both.test(INDEX(i, j));//*/
 210   }
 211
 212   /* coloca em moves as jogadas possíveis na posição atual pelo jogador player */
 213   void valid_moves(bool player, MoveList &moves) {
 214
 215     rep(i, 8)
 216       horiz[i] = vert[i] = 0;
 217     rep(i, 15)
 218       diag[0][i] = diag[1][i] = 0;
 219
 220     both = t[0] | t[1];
 221     rep(i, 8)
 222       rep(j, 8)
 223         if(both.test(INDEX(i, j))) {
 224           horiz[i]++;
 225           vert[j]++;
 226           diag[0][DIAG0(i, j)]++;
 227           diag[1][DIAG1(i, j)]++;
 228         }
 229
 230     //print();
 231
 232     int k, x, y;
 233     bool valid_move;
 234
 235     rep(i, 8)
 236       rep(j, 8)
 237         if(get(player, i, j)) {
 238           rep(d, 4) {
 239             k = count(d, i, j);
 240             //printf("\n(k, d, i, j) = (%i, %i, %i, %i)\n", k, d, i, j);
 241
 242             valid_move = true;
 243             repb(z, 1, k) {
 244               x = i + z * dx[d];
 245               y = j + z * dy[d];
 246               if(x > 7 || x < 0 ||
 247                  y > 7 || y < 0) {
 248                 //printf("(x, y) = (%i, %i) out of tab!\n", x, y);
 249                 valid_move = false;
 250                 break;
 251               }
 252               if(get(!player, x, y)) {
 253                 //printf("(x, y) = (%i, %i) enemy!\n", x, y);
 254                 valid_move = false;
 255                 break;
 256               }
 257             }
 258             if(valid_move) {
 259               x = i + k * dx[d];
 260               y = j + k * dy[d];
 261               if(x > 7 || x < 0 ||
 262                  y > 7 || y < 0) {
 263                 //printf("(x, y) = (%i, %i) out of tab!\n", x, y);
 264               } else if(get(player, x, y)) {
 265                 //printf("(x, y) = (%i, %i) over own piece!\n", x, y);
 266               } else {
 267                 //printf("(x, y) = (%i, %i) valid move!\n", x, y);
 268                 moves.push_back(Move(INDEX(i, j), INDEX(x, y)));
 269               }
 270             }
 271
 272             valid_move = true;
 273             repb(z, 1, k) {
 274               x = i - z * dx[d];
 275               y = j - z * dy[d];
 276               if(x > 7 || x < 0 ||
 277                  y > 7 || y < 0) {
 278                 //printf("(x, y) = (%i, %i) out of tab!\n", x, y);
 279                 valid_move = false;
 280                 break;
 281               }
 282               if(get(!player, x, y)) {
 283                 //printf("(x, y) = (%i, %i) enemy!\n", x, y);
 284                 valid_move = false;
 285                 break;
 286               }
 287             }
 288             if(valid_move) {
 289               x = i - k * dx[d];
 290               y = j - k * dy[d];
 291               if(x > 7 || x < 0 ||
 292                  y > 7 || y < 0) {
 293                 //printf("(x, y) = (%i, %i) out of tab!\n", x, y);
 294               } else if(get(player, x, y)) {
 295                 //printf("(x, y) = (%i, %i) over own piece!\n", x, y);
 296               } else {
 297                 //printf("(x, y) = (%i, %i) valid move!\n", x, y);
 298                 moves.push_back(Move(INDEX(i, j), INDEX(x, y)));
 299               }
 300             }
 301           }
 302         }
 303   }
 304
 305   /* efetua o movimento move pelo jogador player */
 306   inline void move(bool player, Move move) {
 307     t[player][move.first] = t[!player][move.second] = 0;
 308     t[player][move.second] = 1;
 309   }
 310
 311   /* testa se o jogo terminou */
 312   inline bool end()
 313   {
 314     return t[0].count() < 2 || t[1].count() < 2 ||
 315            win(0) || win(1);
 316   }
 317
 318   /* test se o jogador player está com todas as suas peças adjacentes */
 319   inline bool win(bool player) {
 320     adj.reset();
 321     rep(i, 8)
 322       rep(j, 8)
 323         if(get(player, i, j)) {
 324           /*
 325           bool res = adjacent(player, i, j) == t[player].count();
 326           if(res) {
 327             //printf("win(%i)!!\n", player);
 328             //print();
 329             //printf("win(%i)!!\n", player);
 330             //while(1);
 331             //getch;
 332           }
 333           return res;//*/
 334           return adjacent(player, i, j) == t[player].count();
 335         }
 336
 337     return true;
 338   }
 339
 340   /* função para determinar se as peças do jogador player estão adjacentes, partindo
 341      da peça na posição (i, j) */
 342   inline unsigned char adjacent(bool player, char i, char j) {
 343     static int adjdx[] = {-1, -1, -1,  0, 0,  1, 1, 1},
 344                adjdy[] = {-1,  0,  1, -1, 1, -1, 0, 1};
 345     int x, y;
 346     int res = 1;
 347     adj.set(INDEX(i, j));
 348
 349     rep(d, 8) {
 350       x = i + adjdx[d];
 351       y = j + adjdy[d];
 352       if(x > 7 || x < 0 || y > 7 || y < 0) continue;
 353       if(adj.test(INDEX(x, y)) || !get(player, x, y)) continue;
 354       res += adjacent(player, x, y);
 355     }
 356
 357     return res;
 358   }
 359
 360 //private:
 361   Imp t[2]; //t[i] representa o tabuleiro somente com as peças do jogador i
 362 };
 363
 364 /* conjunto dos tabuleiros que já foram visitados
 365    utilizado para determinar quando estamos no mesmo tabuleiro pela segunda vez
 366    colocar os unsigned _int64 correspondentes aos tabuleiros facilita a comparação
 367 */
 368 set<TabComp, bool(*)(const TabComp&, const TabComp&)> tabSet[13][13];
 369
 370 /* número de tabuleiros pesquisados */
 371 int nSearch;
 372
 373 /* efetua todos as jogadas possíveis pelo jogador player no tabuleiro tab,
 374    chamando-se recursivamente, até uma certa profundidade */
 375 void search(bool player, Tab tab, int depth = 0) {
 376   nSearch++;
 377
 378   if(tab.end()) {
 379     //system("pause");
 380     return;
 381   }
 382
 383   if(depth > MAX_DEPTH) return;
 384
 385   Tab temp;
 386
 387   Tab::MoveList moves;
 388   moves.reserve((tab.t[0].count() + tab.t[1].count()) * 2); //reserva o dobro do numero de peças vivas
 389   tab.valid_moves(player, moves);
 390
 391   /*
 392   printf("\nmoves: ");
 393   for(unsigned int i = 0; i < moves.size(); i++)
 394     printf("(%i, %i) ", moves[i].first, moves[i].second);
 395   printf("\n");*/
 396
 397   unsigned char end = moves.size();
 398   for(unsigned char i = 0; i < end; i++) {
 399     //*
 400     if(depth < 2) {
 401       rep(j, depth) printf(".");
 402       printf("%2i / %2i\n", i, end);
 403       //if(!depth) system("pause");
 404     }//*/
 405     //printf("%4i:%4i\n", depth, i);
 406
 407     temp = tab;
 408
 409     //temp.print(moves[i]);
 410
 411     temp.move(player, moves[i]);
 412     pair<set<TabComp>::iterator, bool> res = tabSet[temp.t[0].count()][temp.t[1].count()].insert(
 413       TabComp(to_longlong(temp.t[0]),
 414               to_longlong(temp.t[1])));
 415     if(!res.second) {
 416       //printf("!!!!!!!!!!!!!!!!!!!!!!!!!!");
 417       //system("pause");
 418       continue;
 419     }
 420
 421     search(!player, temp, depth + 1);
 422   }
 423 }
 424
 425 int main()
 426 {
 427   Tab tab;
 428   printf("size tab: %i\n", sizeof(tab));
 429
 430   rep(i, 13)
 431     rep(j, 13)
 432       tabSet[i][j] = set<TabComp, bool(*)(const TabComp&, const TabComp&)>(compareTabComp);
 433
 434   tab.initial_position();
 435   /*
 436   tab.clear();
 437   tab.set(0, 0, 0);
 438   tab.set(0, 7, 7);
 439   tab.set(1, 0, 7);
 440   tab.set(1, 0, 0);//*/
 441   tabSet[tab.t[0].count()][tab.t[1].count()].insert(
 442       TabComp(to_longlong(tab.t[0]), //.to_string<char, char_traits<char>, allocator<char> >()
 443               to_longlong(tab.t[1])));
 444
 445   nSearch = 0;
 446   search(0, tab);
 447
 448   printf("nSearch: %i; tabSet.size(): %i\n", nSearch, tabSet[12][12].size());
 449   printf("clock(): %li", clock());
 450   printf("rand: %i\n", RAND_MAX);
 451
 452   system("pause");
 453   return 0;
 454 }
 455
 456 /**
 457
 458 http://en.wikipedia.org/wiki/Killer_heuristic
 459 http://en.wikipedia.org/wiki/Negascout
 460 http://en.wikipedia.org/wiki/MTD-f
 461 http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search
 462 http://en.wikipedia.org/wiki/Best_first_search
 463 http://en.wikipedia.org/wiki/Branch_and_bound
 464 http://en.wikipedia.org/wiki/Transposition_table
 465 http://en.wikipedia.org/wiki/Zobrist_hashing
 466 https://www.cs.wisc.edu/techreports/1970/TR88.pdf
 467 http://www.personeel.unimaas.nl/m-winands/loa/
 468  */
 469
 470 /* To Do:
 471  * funcao de avaliação
 472    * mobilidade
 473    * n peças adjacentes -> n!
 474    * distância para o centro do tabuleiro
 475  * ordenação (best first)
 476  * tabela de transposicao
 477  * forward prunning
 478  * aberturas
 479  * finais
 480  * pensar na vez do adversário
 481  */