MinimaxEnemy.cpp

   1 #include "MinimaxEnemy.h"
   2 #include "Board.h"
   3
   4 #include <cstdio>
   5 #include <climits>
   6 //#include <iostream>
   7 //using namespace std;
   8 typedef MinimaxEnemy::HeuType HeuType;
   9
  10 HeuType maxhNull = -1
  11                                 , maxhCentro = -1
  12                                 , maxhConcentration = -1
  13                                 , maxhCentralisation = -1
  14                                 , maxhMasscenter = -1
  15                                 , maxhQuads = -1
  16                                 , maxhConnectedness = -1
  17                                 , maxhUniformity = -1
  18                                 ;
  19 typedef struct sHeu {
  20         int i;
  21         HeuType h;
  22 } Heu;
  23
  24 static Board::MoveListOt g_MoveList[10];
  25 //static Board::Set _think_boards[2] = {Board::Set(board_compare), Board::Set(board_compare)};
  26 //#include <map>
  27 //static std::map<Board::Comp, int> _board_value[2];
  28 static Heu g_Heu[10][8 * 12];
  29 static Board g_Boards[10][8 * 12];
  30
  31 int lessHeu(const void *l, const void *r) {
  32         return ((Heu *)l)->h - ((Heu *)r)->h;
  33 }
  34
  35 int moreHeu(const void *l, const void *r) {
  36         return ((Heu *)r)->h - ((Heu *)l)->h;
  37 }
  38
  39 void MinimaxEnemy::move(Board *board, int& fromX, int& fromY, int& toX, int& toY)
  40 {
  41         //_game_boards.insert(board->to_comp());
  42         //_think_boards[0].clear();
  43         //_think_boards[1].clear();
  44         //_board_value[0].clear();
  45         //_board_value[1].clear();
  46
  47         /*
  48         for(Board::Set::iterator i = _game_boards.begin(); i != _game_boards.end(); ++i) {
  49                 cout << i->first << ' ' << i->second << endl;
  50         }
  51         cout << endl;//*/
  52
  53   Board::MoveListOt moveList;
  54         board->all_moves(_player, moveList);
  55
  56         alphabeta(*board, _minimax_depth, -HeuTypeMax, HeuTypeMax, _player);
  57         //_game_boards.insert(board->move_result(_player, moveList[_choice]).to_comp());
  58
  59         //printf("_choice: %i\n", _choice); fflush(stdout);
  60         /*
  61   reps(i, moveList) {
  62                 printf("%i: (%i, %i) -> (%i, %i)\n", i, INDEX_X(moveList[i].first), INDEX_Y(moveList[i].first)
  63                                                            , INDEX_X(moveList[i].second), INDEX_Y(moveList[i].second));
  64                 fflush(stdout);
  65   } //*/
  66
  67         fromX = INDEX_X(INDEX_FROM(moveList[g_Heu[_minimax_depth][_choice].i]));
  68         fromY = INDEX_Y(INDEX_FROM(moveList[g_Heu[_minimax_depth][_choice].i]));
  69         toX = INDEX_X(INDEX_TO(moveList[g_Heu[_minimax_depth][_choice].i]));
  70         toY = INDEX_Y(INDEX_TO(moveList[g_Heu[_minimax_depth][_choice].i]));
  71
  72         *board = g_Boards[_minimax_depth][g_Heu[_minimax_depth][_choice].i];
  73         //Board b;
  74         //b.initial_position();
  75         //*board = b;
  76
  77 #define PRINTHEU(x) \
  78         if(1) { \
  79                 printf(#x ": %.5f %.5f\n", board->x[0], board->x[1]); \
  80         }
  81         //PRINTHEU(centro);
  82         //PRINTHEU(concentration);
  83         //PRINTHEU(centralisation);
  84         //PRINTHEU(masscenter);
  85         //PRINTHEU(quads);
  86         //PRINTHEU(connectedness);
  87         //PRINTHEU(uniformity);
  88 }
  89
  90 #define SQU(x) ((x) * (x))
  91 #define ABS(x) ((x) > 0 ? (x) : (-(x)))
  92 #define MAX(x, y) ((x) > (y) ? (x) : (y))
  93 #define MAX_ALPHABETA HeuTypeMax / 10000
  94
  95
  96 // negamax com poda alphabeta
  97 HeuType MinimaxEnemy::alphabeta(const Board &board, int depth, HeuType alpha, HeuType beta, int player)
  98 {
  99         //printf("alphabeta(%i, %i, %i, %i)\n", depth, alpha, beta, player);
 100
 101         if(board.is_end()) {
 102                 //printf("board is end %i %i\n", board.win(0), board.win(1));
 103                 int mul = 2 * player - 1; //1 -> 1; 0 -> -1
 104                 mul *= 2 * _player - 1;
 105                 if(board.win(_player)) return mul * MAX_ALPHABETA * (1 - 2 * board.win(!_player)) * (depth + 1); /* considerando vitoria simultanea */
 106                 return -mul * MAX_ALPHABETA * (depth + 1); /* dando prioridade para o caminho mais curto */
 107         }
 108         if(depth == 0) {
 109                 int mul = 2 * player - 1; //1 -> 1; 0 -> -1
 110                 mul *= 2 * _player - 1;
 111                 Board b = board;
 112                 return mul * heuristica(b, _player, player);
 113         }
 114
 115         /*
 116         if(_game_boards.count(board.to_comp())) { // empate
 117                 return 0; // nao funciona, acaba sendo sempre a melhor escolha para ambos
 118         }*/
 119
 120         //Board::MoveOt *moveList = g_MoveList[depth];
 121         int size = board.all_moves(player, g_MoveList[depth]);
 122
 123 /* sort */
 124         rep(i, size) {
 125                 g_Heu[depth][i].h = heuristica(g_Boards[depth][i] = board.move_result(player, g_MoveList[depth][i]), _player, player);
 126                 g_Heu[depth][i].i = i;
 127         }
 128
 129         if(player != _player) {
 130                 qsort(&g_Heu[depth], size, sizeof(Heu), lessHeu);
 131         } else {
 132                 qsort(&g_Heu[depth], size, sizeof(Heu), moreHeu);
 133         }
 134         //Heu *perm = g_Heu[depth];
 135         //Board *boards = g_Boards[depth];
 136
 137         /*
 138         if(depth == _minimax_depth) {
 139                 rep(i, size)
 140                         printf("%i(%i) ", g_Heu[depth][i].i, g_Heu[depth][i].h);
 141                 printf("\n");
 142         }//*/
 143 /* end sort */
 144
 145         rep(i, size) {
 146                 /*
 147                 if(i / (float) size > 0.75) { // ignora os piores
 148                         break;
 149                 }//*/
 150                 //Board b = board.move_result(player, moveList[perm[i].i]);
 151                 //if(_game_boards.count(b.to_comp())) { /* empate */
 152                         //continue; // ignora posições que já foram atingidas antes
 153                 //}
 154                 //HeuType rec;
 155                 //if(_think_boards[!player].count(b.to_comp())) { /* transposição */
 156                 //      rec = -_board_value[!player][b.to_comp()];
 157                 //} else {
 158                 HeuType rec = -alphabeta(g_Boards[depth][g_Heu[depth][i].i], depth - 1, -beta, -alpha, !player);
 159                 //}
 160                 if(alpha < rec) {
 161                         alpha = rec;
 162                         if(depth == _minimax_depth) {
 163                                 //_choice = g_Heu[depth][i].i;
 164                                 _choice = i;
 165                         }
 166                 }
 167                 if(alpha >= beta) {
 168                         //_board_value[player][board.to_comp()] = alpha; _think_boards[player].insert(board.to_comp());
 169                         return alpha;
 170                 }
 171         }
 172         //_board_value[player][board.to_comp()] = alpha; _think_boards[player].insert(board.to_comp());
 173         return alpha;
 174 }
 175
 176 #define FINDMAX(x) \
 177         if(x > MAX(1, max##x)) { \
 178                 max##x = x; \
 179                 printf(#x ": %f\n", x); \
 180         }
 181
 182 HeuType MinimaxEnemy::heuristica(Board &board, bool player, bool plastmove)
 183 {
 184         HeuType hNull = rand() / (double) RAND_MAX
 185                                         , hCentro = centro(board, player, plastmove)
 186                                         , hConcentration = concentration(board, player, plastmove)
 187                                         , hCentralisation = centralisation(board, player, plastmove)
 188                                         , hMasscenter = masscenter(board, player, plastmove)
 189                                         , hQuads = quads(board, player, plastmove)
 190                                         , hConnectedness = connectedness(board, player, plastmove)
 191                                         , hUniformity = uniformity(board, player, plastmove)
 192                                         ;
 193         FINDMAX(hCentro);
 194         FINDMAX(hConcentration);
 195         FINDMAX(hCentralisation);
 196         FINDMAX(hMasscenter);
 197         FINDMAX(hQuads);
 198         FINDMAX(hConnectedness);
 199         FINDMAX(hUniformity);
 200         return (hNull * _heu[0]
 201                 + hCentro * _heu[1]
 202                 + hConcentration * _heu[2]
 203                 + hCentralisation * _heu[3]
 204                 + hMasscenter * _heu[4]
 205                 + hQuads * _heu[5]
 206                 + hConnectedness * _heu[6]
 207                 + hUniformity * _heu[7]) / _heu_total
 208                 //+ centro(board, player)
 209                 //+ concentration(board, player)
 210                 //+ centralisation(board, player)
 211                 //+ masscenter(board, player)
 212                 //+ quads(board, player)
 213                 //+ connectedness(board, player)
 214                 //+ uniformity(board, player)
 215                 ;
 216 }
 217
 218 // centro: diferença entra as médias das distâncias para o centro
 219 HeuType MinimaxEnemy::centro(Board &board, bool player, bool plastmove)
 220 {
 221         HeuType res = 0;
 222         HeuType resb = 0;
 223         if(player == plastmove) {
 224                 rep(i, 8)
 225                         rep(j, 8)
 226                                 if(board.get(player, i, j))
 227                                         res += SQU(i - 3.5) + SQU(j - 3.5); // distância para o centro
 228                 res /= (double) board.t[player].count();
 229                 board.centro[player] = res;
 230                 resb = board.centro[!player];
 231         } else {
 232                 rep(i, 8)
 233                         rep(j, 8)
 234                                 if(board.get(!player, i, j))
 235                                         resb += SQU(i - 3.5) + SQU(j - 3.5); // distância para o centro
 236                 resb /= (double) board.t[!player].count();
 237                 board.centro[!player] = resb;
 238                 res = board.centro[player];
 239         }
 240         //return MAX_ALPHABETA - res;
 241         //printf("centro: %i %f %f\n", player, res, resb);
 242         return (resb - res) / 14.8;
 243 }
 244
 245 HeuType MinimaxEnemy::concentration(Board &board, bool player, bool plastmove)
 246 {
 247         static HeuType minsum[] = {0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 18, 20, 22};
 248         HeuType cmx = 0, cmy = 0;
 249         HeuType res = 0, resb = 0;
 250         int n = board.t[player].count();
 251         if(player == plastmove) {
 252                 rep(i, 8)
 253                         rep(j, 8)
 254                                 if(board.get(player, i, j)) {
 255                                         cmx += i;
 256                                         cmy += j;
 257                                 }
 258                 cmx /= (double) n;
 259                 cmy /= (double) n;
 260                 board.cmx[player] = cmx;
 261                 board.cmy[player] = cmy;
 262                 //printf("cm: %f %f\n", cmx, cmy);
 263
 264                 HeuType sum = -minsum[n];
 265                 rep(i, 8)
 266                         rep(j, 8)
 267                                 if(board.get(player, i, j)) {
 268                                         HeuType dx = ABS(cmx - i);
 269                                         HeuType dy = ABS(cmy - j);
 270                                         sum += MAX(dx, dy);
 271                                 }
 272                 res = sum;
 273                 board.concentration[player] = res;
 274                 resb = board.concentration[!player];
 275         } else {
 276                 cmx = 0, cmy = 0;
 277                 n = board.t[!player].count();
 278                 rep(i, 8)
 279                         rep(j, 8)
 280                                 if(board.get(!player, i, j)) {
 281                                         cmx += i;
 282                                         cmy += j;
 283                                 }
 284                 cmx /= (double) n;
 285                 cmy /= (double) n;
 286                 board.cmx[!player] = cmx;
 287                 board.cmy[!player] = cmy;
 288
 289                 HeuType sum = -minsum[n];
 290                 rep(i, 8)
 291                         rep(j, 8)
 292                                 if(board.get(!player, i, j)) {
 293                                         HeuType dx = ABS(cmx - i);
 294                                         HeuType dy = ABS(cmy - j);
 295                                         sum += MAX(dx, dy);
 296                                 }
 297                 resb = sum;
 298                 board.concentration[!player] = resb;
 299                 res = board.concentration[player];
 300         }
 301         //printf(": %f %f\n", res, resb);
 302         return (resb - res) / 24;
 303 }
 304
 305 HeuType MinimaxEnemy::centralisation(Board &board, bool player, bool plastmove)
 306 {
 307         static
 308         int squval[8][8] = {{-80, -25, -20, -20, -20, -20, -25, -80},
 309                                         {-25,  10,  10,  10,  10,  10,  10, -25},
 310                                                                                         {-20,  10,  25,  25,  25,  25,  10, -20},
 311                                                                                         {-20,  10,  25,  50,  50,  25,  10, -20},
 312                                                                                         {-20,  10,  25,  50,  50,  25,  10, -20},
 313                                                                                         {-20,  10,  25,  25,  25,  25,  10, -20},
 314                                         {-25,  10,  10,  10,  10,  10,  10, -25},
 315                                                                                         {-80, -25, -20, -20, -20, -20, -25, -80}};
 316         HeuType res = 0.0;
 317         HeuType resb = 0.0;
 318
 319         if(player == plastmove) {
 320                 rep(i, 8)
 321                         rep(j, 8)
 322                                 if(board.get(player, i, j)) {
 323                                         res += squval[i][j];
 324                                 }
 325                 res /= board.t[player].count();
 326                 board.centralisation[player] = res;
 327                 resb = board.centralisation[!player];
 328         } else {
 329                 rep(i, 8)
 330                         rep(j, 8)
 331                                 if(board.get(!player, i, j)) {
 332                                         resb += squval[i][j];
 333                                 }
 334                 resb /= board.t[!player].count();
 335                 board.centralisation[!player] = resb;
 336                 res = board.centralisation[player];
 337         }
 338         //printf(": %f %f\n", res, resb);
 339         return (res - resb) / 63.1;
 340 }
 341
 342 HeuType MinimaxEnemy::masscenter(Board &board, bool player, bool plastmove)
 343 {
 344         HeuType cmx = 0, cmy = 0;
 345         HeuType res = 0.0, resb = 0.0;
 346         //int n = board.t[player].count();
 347         //rep(i, 8)
 348                 //rep(j, 8)
 349                         //if(board.get(player, i, j)) {
 350                                 //cmx += i;
 351                                 //cmy += j;
 352                         //}
 353         //cmx /= (double) n;
 354         //cmy /= (double) n;
 355         if(player == plastmove) {
 356                 cmx = board.cmx[player];
 357                 cmy = board.cmy[player];
 358                 res = SQU(cmx) + SQU(cmy);
 359                 board.masscenter[player] = res;
 360                 resb = board.masscenter[!player];
 361         } else {
 362                 cmx = board.cmx[!player];
 363                 cmy = board.cmy[!player];
 364                 resb = SQU(cmx) + SQU(cmy);
 365                 board.masscenter[!player] = resb;
 366                 res = board.masscenter[player];
 367         }
 368
 369         //cmx = 0, cmy = 0;
 370         //n = board.t[!player].count();
 371         //rep(i, 8)
 372                 //rep(j, 8)
 373                         //if(board.get(!player, i, j)) {
 374                                 //cmx += i;
 375                                 //cmy += j;
 376                         //}
 377         //cmx /= (double) n;
 378         //cmy /= (double) n;
 379         //HeuType resb = SQU(cmx) + SQU(cmy);
 380
 381         //printf(": %f %f\n", res, resb);
 382         return (res - resb) / 52.5;
 383 }
 384
 385 HeuType MinimaxEnemy::quads(Board &board, bool player, bool plastmove)
 386 {
 387         HeuType cmx = 0, cmy = 0;
 388         //int n = board.t[player].count();
 389         //rep(i, 8)
 390                 //rep(j, 8)
 391                         //if(board.get(player, i, j)) {
 392                                 //cmx += i;
 393                                 //cmy += j;
 394                         //}
 395         //cmx /= (double) n;
 396         //cmy /= (double) n;
 397         HeuType res = 0;
 398         HeuType resb = 0;
 399
 400         if(player == plastmove) {
 401                 cmx = board.cmx[player];
 402                 cmy = board.cmy[player];
 403                 repbe(i, MAX(0, cmx - 2), MIN(6, cmx + 3)) {
 404                         repbe(j, MAX(0, cmy - 2), MIN(6, cmy + 3)) {
 405                                 if(board.get(player, i, j) +
 406                                          board.get(player, i + 1, j) +
 407                                          board.get(player, i, j + 1) +
 408                                          board.get(player, i + 1, j + 1) >= 3) {
 409                                         res++;
 410                                 }
 411                         }
 412                 }
 413                 board.quads[player] = res;
 414                 resb = board.quads[!player];
 415         } else {
 416                 cmx = board.cmx[!player];
 417                 cmy = board.cmy[!player];
 418                 repbe(i, MAX(0, cmx - 2), MIN(6, cmx + 3)) {
 419                         repbe(j, MAX(0, cmy - 2), MIN(6, cmy + 3)) {
 420                                 if(board.get(!player, i, j) +
 421                                          board.get(!player, i + 1, j) +
 422                                          board.get(!player, i, j + 1) +
 423                                          board.get(!player, i + 1, j + 1) >= 3) {
 424                                         resb++;
 425                                 }
 426                         }
 427                 }
 428                 board.quads[!player] = resb;
 429                 res = board.quads[player];
 430         }
 431         //cmx = 0, cmy = 0;
 432         //n = board.t[!player].count();
 433         //rep(i, 8)
 434                 //rep(j, 8)
 435                         //if(board.get(!player, i, j)) {
 436                                 //cmx += i;
 437                                 //cmy += j;
 438                         //}
 439         //cmx /= (double) n;
 440         //cmy /= (double) n;
 441
 442         //printf(": %f %f\n", res, resb);
 443         return (res - resb) / 8.0;
 444 }
 445
 446 HeuType MinimaxEnemy::connectedness(Board &board, bool player, bool plastmove)
 447 {
 448         static int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1},
 449                                                  dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
 450
 451         HeuType res = 0;
 452         HeuType resb = 0;
 453
 454         if(player == plastmove) {
 455                 rep(i, 8)
 456                         rep(j, 8)
 457                                 if(board.get(player, i, j)) {
 458                                         rep(d, 8) {
 459                                                 int x = i + dx[d],
 460                                                                 y = j + dy[d];
 461                                                 if(x < 0 || x > 7 ||
 462                                                          y < 0 || y > 7) {
 463                                                         continue;
 464                                                 }
 465                                                 if(board.get(player, x, y)) {
 466                                                         res++;
 467                                                 }
 468                                         }
 469                                 }
 470                 res /= (double) board.t[player].count();
 471                 board.connectedness[player] = res;
 472                 resb = board.connectedness[!player];
 473         } else {
 474                 rep(i, 8)
 475                         rep(j, 8)
 476                                 if(board.get(!player, i, j)) {
 477                                         rep(d, 8) {
 478                                                 int x = i + dx[d],
 479                                                                 y = j + dy[d];
 480                                                 if(x < 0 || x > 7 ||
 481                                                          y < 0 || y > 7) {
 482                                                         continue;
 483                                                 }
 484                                                 if(board.get(!player, x, y)) {
 485                                                         resb++;
 486                                                 }
 487                                         }
 488                                 }
 489                 resb /= (double) board.t[!player].count();
 490                 board.connectedness[!player] = resb;
 491                 res = board.connectedness[player];
 492         }
 493         //printf(": %f %f\n", res, resb);
 494         return (res - resb) / 4.0;
 495 }
 496
 497 HeuType MinimaxEnemy::uniformity(Board &board, bool player, bool plastmove)
 498 {
 499         HeuType res;
 500         HeuType resb;
 501         int minx, miny, maxx, maxy;
 502
 503         if(player == plastmove) {
 504                 minx = miny = 8;
 505                 maxx = maxy = -1;
 506                 rep(i, 8)
 507                         rep(j, 8)
 508                                 if(board.get(player, i, j)) {
 509                                         if(i < minx) minx = i;
 510                                         if(i > maxx) maxx = i;
 511                                         if(j < miny) miny = j;
 512                                         if(j > maxy) maxy = j;
 513                                 }
 514                 res = (maxx - minx + 1) * (maxy - miny + 1);
 515                 board.uniformity[player] = res;
 516                 resb = board.uniformity[!player];
 517         } else {
 518                 minx = miny = 8;
 519                 maxx = maxy = -1;
 520                 rep(i, 8)
 521                         rep(j, 8)
 522                                 if(board.get(!player, i, j)) {
 523                                         if(i < minx) minx = i;
 524                                         if(i > maxx) maxx = i;
 525                                         if(j < miny) miny = j;
 526                                         if(j > maxy) maxy = j;
 527                                 }
 528                 resb = (maxx - minx + 1) * (maxy - miny + 1);
 529                 board.uniformity[!player] = resb;
 530                 res = board.uniformity[player];
 531         }
 532         //printf(": %f %f\n", res, resb);
 533         return (resb - res) / 52;
 534 }
 535
 536 void MinimaxEnemy::set_weights(HeuType heu[NUM_HEU])
 537 {
 538         _heu_total = 0;
 539         rep(i, NUM_HEU)
 540                 _heu_total += _heu[i] = heu[i];
 541 }
 542