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