tetrisolve

make a line in adversarial tetris
git clone https://a3nm.net/git/tetrisolve/
Log | Files | Refs | README | LICENSE

bruteforce.cpp (11819B)


      1 /* Compute winning strategy for tetris
      2  * Running this code requires around 30GB RAM and a few hours
      3  * It writes to file "solution" a strategy to always make a line in the first
      4  * MAXHEIGHT rows of a tetris playing field of COLS by LINES */
      5 
      6 #include<cstdio>
      7 #include<iostream>
      8 #include<unordered_set>
      9 #include<algorithm>
     10 #include<cassert>
     11 #include<queue>
     12 #include<unordered_map>
     13 #include "common_tetris.cpp"
     14 
     15 // bit sizes when coding configurations
     16 // a configuration consists of COLS integers over HEIGHTSIZE bits
     17 // representing the height of the playing field in that column
     18 // and on the most significant bits a bit vector of SACSIZE bits
     19 // describing which rows contains holes
     20 // configurations are 64-bits words so you must have
     21 // HEIGHTSIZE*COLS+SACSIZE <= 64
     22 #define HEIGHTSIZE 4
     23 #define SACSIZE 16
     24 
     25 // height of playing field in which to complete lines
     26 // (you must have SACSIZE >= MAXHEIGHT and 2^HEIGHTSIZE >= MAXHEIGHT+1
     27 #define MAXHEIGHT 6
     28 #define TOTALMAXMOVES (MAXHEIGHT*COLS+1)
     29 
     30 // search options
     31 // if JUSTONE is true, the program will run faster to find some winning stategy
     32 // (without trying to find the shortest paths to a win)
     33 #define JUSTONE 0
     34 // if ALPHABETA is true, the program will prune branches using alpha-beta, it
     35 // should give a strategy with the same performance as when it is not set
     36 #define ALPHABETA 1
     37 
     38 // last played pieces
     39 int lastpiece[TOTALMAXMOVES];
     40 
     41 // file in which to write solution
     42 FILE *fsol;
     43 
     44 using namespace std;
     45 
     46 typedef unsigned long long ull;
     47 typedef pair<int, int> pii;
     48 typedef pair<int, pii> piii;
     49 typedef pair<int, ull> piull;
     50 typedef pair<ull, pii> pullii;
     51 typedef pair<piull, pii> piullii;
     52 typedef pair<pii, pii> piiii;
     53 
     54 // cache of losing configurations (this takes the most RAM)
     55 // mapping configurations that were explored and not found to be winning
     56 // to the maximal maxmoves to which they were explored
     57 // (-2 for unlimited => always failing)
     58 // (if ALPHABETA=0, we only care about the set of keys, not the associated
     59 // values)
     60 unordered_map<ull, int> mycache0;
     61 // cache of winning configurations and number of moves to win
     62 unordered_map<ull, int> mycache1;
     63 
     64 bool fits_maxheight(int p, int r, int c, int l) {
     65   if (!fits(p, r, c, l))
     66     return false;
     67   for (int i = 0; i < 4; i++)
     68     for (int j = 0; j < 4; j++)
     69       if (piecesr[p][r][i][j]) {
     70         // do not put a piece above a column that's already full
     71         // the reason is that we do not know how high the column is and so the
     72         // effect of lower components of the piece in adjacent columns may be
     73         // inaccurate
     74         if (field[LINES-MAXHEIGHT][c+j])
     75           return false;
     76       }
     77   return true;
     78 }
     79 
     80 int line_config(ull config) {
     81   // test if field contains a line
     82   // the argument config is used only for the "SACSIZE" component describing
     83   // which rows contain holes
     84   ull sac = config >> HEIGHTSIZE*COLS;
     85   for (int i = 0; i < LINES; i++) {
     86     if (sac & (((ull) 1) << i))
     87       continue; // line contains a hole so we shouldn't consider it
     88     bool ok = true;
     89     for (int j = 0; j < COLS; j++)
     90       if (!field[i][j]) {
     91         ok = false;
     92         break;
     93       }
     94     if (ok)
     95       return true;
     96   }
     97   return false;
     98 }
     99 
    100 void printfield(int depth, ull config) {
    101   // print current status of playing field
    102   ull sac = config >> HEIGHTSIZE*COLS;
    103   printf("========== MH:%d depth:%d cache0:%ld cache1:%ld\n", MAXHEIGHT, depth, mycache0.size(), mycache1.size());
    104   printf("branch %d %d %d %d %d %d\n",
    105       lastpiece[0], lastpiece[1], lastpiece[2], lastpiece[3], lastpiece[4], lastpiece[5]);
    106   for(int i = 0; i < LINES; i++) {
    107     printf("%c", sac & (((ull) 1) << i) ? '!' : ' ');
    108     for (int j = 0; j < COLS; j++) {
    109       printf("%c", field[i][j] ? '#' : '.');
    110     }
    111     printf("\n");
    112   }
    113   printf("==========\n");
    114 }
    115 
    116 void printconfig(ull sig) {
    117   // print a configuration
    118 
    119   cout << "sig: " << sig;
    120   for (int c = 0; c < 10; c++) {
    121     int h = sig & ((((ull) 1) << HEIGHTSIZE)-1);
    122     sig >>= HEIGHTSIZE;
    123     printf(" %d", h); // height of column c
    124   }
    125   printf(" ");
    126   for (int r = 0; r < LINES; r++)
    127     printf("%c", (((ull) 1) << r) & sig ? '!':'.'); // incomplete rows
    128   printf("\n");
    129 }
    130 
    131 ull get_config(ull configold) {
    132   // compute configuration from field
    133   // the argument configold is used only for the "SACSIZE" component describing
    134   // which rows contain holes, to account for the fact that they still contain
    135   // holes
    136   ull sac = configold >> HEIGHTSIZE*COLS;
    137   int height[COLS] = {};
    138 
    139   // compute which rows now contain holes, and the maximal height of each line
    140   for (int c = 0; c < COLS; c++) {
    141     bool seenone = false;
    142     for (int r = 0; r < LINES; r++) {
    143       if (field[r][c] && !seenone) {
    144         seenone = true;
    145         height[c] = min(LINES-r, MAXHEIGHT);
    146         continue;
    147       }
    148       if (seenone && !field[r][c]) {
    149         if (r >= LINES-MAXHEIGHT)
    150           sac |= (((ull) 1) << r); // incomplete row
    151       }
    152     } 
    153     if (!seenone)
    154       height[c] = 0;
    155   }
    156 
    157   // prepare the config
    158   ull conf2 = sac;
    159   for (int c = COLS-1; c >= 0; c--) {
    160     conf2 <<= HEIGHTSIZE;
    161     conf2 |= height[c];
    162   }
    163   return conf2;
    164 }
    165 
    166 
    167 ull load_config(ull config) {
    168   // load configuration into field
    169   // return the SACSIZE component with the incomplete lines
    170   for (int r = 0; r < LINES; r++)
    171     for (int c = 0; c < COLS; c++)
    172       field[r][c] = 0;
    173   for (int c = 0; c < COLS; c++) {
    174     int h = config & ((((ull) 1) << HEIGHTSIZE)-1);
    175     config >>= HEIGHTSIZE;
    176     for (int r = LINES-1; r > LINES-1-h; r--)
    177       field[r][c] = 1;
    178   }
    179   return config; // remaining sac
    180 }
    181 
    182 int wins(ull sig, int depth, int maxmoves);
    183 
    184 piullii winsp(ull config, int depth, int p, int maxmoves) {
    185   // do we win at config when playing piece p?
    186   // depth is the current depth in the tree
    187   // last arg is how many moves are allowed
    188   // if ALPHABETA=0, last arg is not used
    189   // the return value describes the number of moves to win (-1 if losing)
    190   // the column and rotation where to put piece p
    191   // and the config to which this leads
    192  
    193   // if the configuration is already known to be losing, return
    194   if (mycache0.find(config) != mycache0.end()) {
    195     int damaxmoves = mycache0[config];
    196     if (!ALPHABETA || damaxmoves == -2 || damaxmoves >= maxmoves)
    197       return make_pair(make_pair(-1, 0), make_pair(-1, -1));
    198   }
    199 
    200   lastpiece[depth] = p;
    201   assert(depth < TOTALMAXMOVES);
    202 
    203   load_config(config);
    204 
    205   if (depth < 7) {
    206     // show progress info
    207     printf("winsp %lld %d %d\n", config, depth, p);
    208     cout << "config " << config << endl;
    209     printfield(depth, config);
    210   }
    211 
    212   // best number of moves to win, and corresponding rotation, column, config
    213   int initvbest = (maxmoves == -2 || !ALPHABETA) ? TOTALMAXMOVES : maxmoves;
    214   int vbest = initvbest;
    215   int rbest = -1, cbest = -1;
    216   ull sbest = -1;
    217 
    218   // store options before recursing on them
    219   // that way, if there is a win in one move, we won't recurse
    220   vector<pullii> opts;
    221 
    222   for (int r = 0; r < 4; r++) {
    223     for (int c = -2; c < COLS; c++) {
    224       if (fits_maxheight(p, r, c, 0)) {
    225         // try to put piece p with rotation r at column c
    226         // see where it falls
    227         int l = 0;
    228         while(fits_maxheight(p, r, c, l))
    229           l++;
    230         l--;
    231         // blit piece at row l
    232         blit(p, r, c, l, 0);
    233         // check if we won and what is the resulting config
    234         bool won = line_config(config);
    235         ull config2 = get_config(config);
    236         // and reset the field
    237         load_config(config);
    238 
    239         if (config2 == config)
    240           continue; // no progress when dropping this piece
    241         if (won)
    242           return make_pair(make_pair(1, config2), make_pair(r, c));
    243         if (mycache0.find(config2) != mycache0.end()) {
    244           if (!ALPHABETA)
    245             continue; // known to be losing
    246           // with ALPHABETA, we check how far we explored it
    247           int damaxmoves = mycache0[config2];
    248           if (damaxmoves == -2 || damaxmoves >= vbest)
    249             continue; // known to be losing
    250         }
    251         ull sac2 = config2 >> HEIGHTSIZE*COLS;
    252         if (sac2 == (((ull) 1) << MAXHEIGHT)-1)
    253           continue; // no feasible rows remain
    254         if (mycache1.find(config2) != mycache1.end()) {
    255           // config was already studied and is winning, does it make us win
    256           // faster?
    257           int vposs = mycache1[config2];
    258           if (vposs < vbest) {
    259             // it makes us win faster
    260             vbest = vposs;
    261             rbest = r;
    262             cbest = c;
    263             sbest = config2;
    264           }
    265           if (JUSTONE)
    266 	    return make_pair(make_pair(1+vbest, sbest), make_pair(rbest, cbest));
    267           continue;
    268         }
    269         opts.push_back(make_pair(config2, make_pair(r, c)));
    270       }
    271     }
    272   }
    273   for (auto opt : opts) {
    274     // study the resulting configuration recursively
    275     int vposs = wins(opt.first, depth+1, vbest-1);
    276     load_config(config); // reset state after recursive call
    277     if (vposs >= 0) {
    278       if (vposs < vbest) {
    279         // resulting configuration makes us win faster
    280         vbest = vposs;
    281         rbest = opt.second.first;
    282         cbest = opt.second.second;
    283         sbest = opt.first;
    284       }
    285       if (JUSTONE)
    286         return make_pair(make_pair(1+vbest, sbest), make_pair(rbest, cbest));
    287     }
    288   }
    289   if (vbest < initvbest) {
    290     // we found a way to win!
    291     return make_pair(make_pair(1+vbest, sbest), make_pair(rbest, cbest));
    292   } else {
    293     // all moves are losing
    294     return make_pair(make_pair(-1, 0), make_pair(-1, -1));
    295   }
    296 }
    297 
    298 int wins(ull sig, int depth, int maxmoves) {
    299   // what is the minimal number of moves to win from config sig?
    300   // maxmoves is the maximal number of allowed moves (-2 for unlimited)
    301   // if ALPHABETA=0, last arg is not used
    302   if (ALPHABETA && maxmoves != -2 && maxmoves < 0)
    303     return -1; // not enough moves remain
    304   
    305   // return values of winsp
    306   int mr[7], mc[7], mv[7];
    307   ull ms[7];
    308 
    309   if (mycache0.find(sig) != mycache0.end()) {
    310     if (!ALPHABETA)
    311       return -1; // known to be losing
    312     // with ALPHABETA, we check how far we explored it
    313     int damaxmoves = mycache0[sig];
    314     if (damaxmoves == -2)
    315       return -1; // we know it is always losing
    316     if (damaxmoves >= maxmoves)
    317       return -1; // already explored to this depth and failed
    318   }
    319   if (mycache1.find(sig) != mycache1.end())
    320     return mycache1[sig]; // we know it is winning
    321   int longest=-1; // maximal number of moves to win (worse case among all pieces)
    322   for (int p = 0; p < 7; p++) {
    323     // try each piece
    324     piullii nmovespp = winsp(sig, depth, p, maxmoves);
    325     mv[p] = nmovespp.first.first;
    326     ms[p] = nmovespp.first.second;
    327     if (mv[p] == -1) {
    328       // piece p is losing, so position is losing
    329       if (mycache0.find(sig) == mycache0.end()) {
    330         mycache0[sig] = maxmoves; // not known to be losing, store it
    331       } else {
    332         if (mycache0[sig] >= 0) {
    333           if (maxmoves == -2) {
    334             mycache0[sig] = -2;
    335           } else {
    336             mycache0[sig] = max(mycache0[sig], maxmoves); // update depth at which it loses
    337           }
    338         }
    339       }
    340       return -1; // losing
    341     }
    342     mr[p] = nmovespp.second.first;
    343     mc[p] = nmovespp.second.second;
    344 
    345     if (mv[p] >= 0) {
    346       longest = max(longest, mv[p]);
    347     }
    348   }
    349 
    350   // if we went so far, this is a winning position
    351   mycache1[sig] = longest;
    352   // store its details in solution file
    353   for (int p = 0; p < 7; p++) {
    354     // field 1: the config in question
    355     // field 2: the piece to play
    356     // field 3: the number of moves to win
    357     // fields 4 and 5: the rotation and column where to play it
    358     // field 6: the resulting config
    359     fprintf(fsol, "%lld %d %d %d %d %lld\n", sig, p, mv[p], mr[p], mc[p], ms[p]);
    360   }
    361 
    362   return longest;
    363 }
    364 
    365 int main(int argc, char **argv) {
    366   init_pieces();
    367   fsol = fopen("solution", "w");
    368   int ww = wins(0, 0, -2);
    369   assert(ww > 0);
    370   fclose(fsol);
    371   return 0;
    372 }
    373