sr.c

   1 /*
   2  * sr -- A sample robot for Netris
   3  * Copyright (C) 1994,1995,1996  Mark H. Weaver <mhw@netris.org>
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  *
  19  * $Id: sr.c,v 1.10 1996/02/09 08:22:20 mhw Exp $
  20  */
  21
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <stdarg.h>
  26 #include <math.h>
  27 #include <limits.h>
  28
  29 /* Both of these should be at least twice the actual max */
  30 #define MAX_BOARD_WIDTH         32
  31 #define MAX_BOARD_HEIGHT        64
  32
  33 char b[1024];
  34 FILE *logFile;
  35
  36 int twoPlayer;
  37 int boardHeight, boardWidth;
  38 int board[MAX_BOARD_HEIGHT][MAX_BOARD_WIDTH];
  39 int piece[4][4];
  40 int pieceLast[4][4];
  41
  42 int board1[MAX_BOARD_HEIGHT][MAX_BOARD_WIDTH];
  43 int piece1[4][4];
  44 int piece2[4][4];
  45
  46 int pieceCount;         /* Serial number of current piece, for sending commands */
  47 int pieceVisible;       /* How many blocks of the current piece are visible */
  48 int pieceBottom, pieceLeft;     /* Position of bottom-left square */
  49 int pieceBottomLast, pieceLeftLast;
  50
  51 /*
  52  * 0 = Not decided yet
  53  * 1 = decided
  54  * 2 = move in progress
  55  * 3 = drop in progress
  56  */
  57 int pieceState;
  58
  59 int leftDest;
  60 int pieceDest[4][4];
  61
  62 int masterEnable = 1, dropEnable = 1;
  63
  64 float curTime, moveTimeout;
  65
  66 int min(int a, int b)
  67 {
  68         return a < b ? a : b;
  69 }
  70
  71 char *ReadLine(char *buf, int size)
  72 {
  73         int len;
  74
  75         if (!fgets(buf, size, stdin))
  76                 return NULL;
  77         len = strlen(buf);
  78         if (len > 0 && buf[len-1] == '\n')
  79                 buf[len-1] = 0;
  80         if (logFile)
  81                 fprintf(logFile, "  %s\n", buf);
  82         return buf;
  83 }
  84
  85 int WriteLine(char *fmt, ...)
  86 {
  87         int result;
  88         va_list args;
  89
  90         va_start(args, fmt);
  91         result = vfprintf(stdout, fmt, args);
  92         if (logFile) {
  93                 fprintf(logFile, "> ");
  94                 vfprintf(logFile, fmt, args);
  95         }
  96         va_end(args);
  97         return result;
  98 }
  99
 100 void FindPiece(void)
 101 {
 102         int row, col;
 103
 104         pieceVisible = 0;
 105         pieceBottom = MAX_BOARD_HEIGHT;
 106         pieceLeft = MAX_BOARD_WIDTH;
 107         for (row = boardHeight - 1; row >= 0; --row)
 108                 for (col = boardWidth - 1; col >= 0; --col)
 109                         if (board[row][col] < 0) {
 110                                 pieceBottom = row;
 111                                 if (pieceLeft > col)
 112                                         pieceLeft = col;
 113                                 pieceVisible++;
 114                         }
 115         for (row = 0; row < 4; ++row)
 116                 for (col = 0; col < 4; ++col)
 117                         piece[row][col] = board[pieceBottom + row][pieceLeft + col] < 0;
 118 }
 119
 120 void RotatePiece1(void)
 121 {
 122         int row, col, height = 0;
 123
 124         for (row = 0; row < 4; ++row)
 125                 for (col = 0; col < 4; ++col)
 126                 {
 127                         piece2[row][col] = piece1[row][col];
 128                         piece1[row][col] = 0;
 129                         if (piece2[row][col])
 130                                 height = row + 1;
 131                 }
 132         for (row = 0; row < 4; ++row)
 133                 for (col = 0; col < height; ++col)
 134                         piece1[row][col] = piece2[height - col - 1][row];
 135 }
 136
 137 int PieceFits(int row, int col)
 138 {
 139         int i, j;
 140
 141         if (row < 0)
 142                 return 0;
 143         for (i = 0; i < 4; ++i)
 144                 for (j = 0; j < 4; ++j)
 145                         if (piece1[i][j])
 146                                 if (col+j >= boardWidth || board[row+i][col+j] > 0)
 147                                         return 0;
 148         return 1;
 149 }
 150
 151 int SimPlacement(int row, int col)
 152 {
 153         int i, j;
 154         int from, to, count;
 155
 156         for (i = 0; i < boardHeight; ++i)
 157                 for (j = 0; j < boardWidth; ++j) {
 158                         board1[i][j] = board[i][j] > 0;
 159                         if (i >= row && i < row+4 && j >= col && j < col+4)
 160                                 if (piece1[i - row][j - col])
 161                                         board1[i][j] = 1;
 162                 }
 163         for (from = to = 0; to < boardHeight; ++from) {
 164                 count = boardWidth;
 165                 for (j = 0; j < boardWidth; ++j)
 166                         count -= board1[to][j] = board1[from][j];
 167                 to += (count > 0);
 168         }
 169         return from - to;
 170 }
 171
 172 double BoardScore(int linesCleared, int pRow, int verbose)
 173 {
 174         double score = 0;
 175         double avgHeight2 = 0, avgHolesTimesDepth = 0;
 176         int maxMidHeight = 0, maxHeight = 0;
 177         int height[MAX_BOARD_WIDTH];
 178         int holesTimesDepth[MAX_BOARD_WIDTH];
 179         int holes[MAX_BOARD_WIDTH];
 180         double hardFit[MAX_BOARD_HEIGHT];
 181         int depend[MAX_BOARD_HEIGHT];
 182         int cover[MAX_BOARD_WIDTH];
 183         int row, col, count, i;
 184         int deltaLeft, deltaRight;
 185         double closeToTop, topShape = 0, fitProbs = 0, space = 0;
 186         double maxHard;
 187
 188         for (col = 0; col < boardWidth; ++col) {
 189                 cover[col] = 0;
 190                 height[col] = 0;
 191                 for (row = 0; row < boardHeight; ++row)
 192                         if (board1[row][col])
 193                                 height[col] = row + 1;
 194                 avgHeight2 += height[col] * height[col];
 195                 if (maxHeight < height[col])
 196                         maxHeight = height[col];
 197                 if (col >= 2 && col < boardWidth - 2 && maxMidHeight < height[col])
 198                         maxMidHeight = height[col];
 199                 holes[col] = 0;
 200                 holesTimesDepth[col] = 0;
 201                 for (row = 0; row < height[col]; ++row) {
 202                         if (board1[row][col])
 203                                 holesTimesDepth[col] += holes[col];
 204                         else
 205                                 holes[col]++;
 206                 }
 207                 avgHolesTimesDepth += holesTimesDepth[col];
 208         }
 209         avgHeight2 /= boardWidth;
 210         avgHolesTimesDepth /= boardWidth;
 211
 212         /* Calculate dependencies */
 213         for (row = maxHeight - 1; row >= 0; --row) {
 214                 depend[row] = 0;
 215                 for (col = 0; col < boardWidth; ++col) {
 216                         if (board1[row][col])
 217                                 cover[col] |= 1 << row;
 218                         else
 219                                 depend[row] |= cover[col];
 220                 }
 221                 for (i = row + 1; i < maxHeight; ++i)
 222                         if (depend[row] & (1 << i))
 223                                 depend[row] |= depend[i];
 224         }
 225
 226         /* Calculate hardness of fit */
 227         for (row = maxHeight - 1; row >= 0; --row) {
 228                 hardFit[row] = 5;
 229                 count = 0;
 230                 for (col = 0; col < boardWidth; ++col) {
 231                         if (board1[row][col]) {
 232                                 space += 0.5;
 233                         }
 234                         else if (!board1[row][col]) {
 235                                 count++;
 236                                 space += 1;
 237                                 hardFit[row]++;
 238                                 if (height[col] < row)
 239                                         hardFit[row] += row - height[col];
 240                                 if (col > 0)
 241                                         deltaLeft = height[col - 1] - row;
 242                                 else
 243                                         deltaLeft = MAX_BOARD_HEIGHT;
 244                                 if (col < boardWidth - 1)
 245                                         deltaRight = height[col + 1] - row;
 246                                 else
 247                                         deltaRight = MAX_BOARD_HEIGHT;
 248                                 if (deltaLeft > 2 && deltaRight > 2)
 249                                         hardFit[row] += 7;
 250                                 else if (deltaLeft > 2 || deltaRight > 2)
 251                                         hardFit[row] += 2;
 252                                 else if (abs(deltaLeft) == 2 && abs(deltaRight) == 2)
 253                                         hardFit[row] += 2;
 254                                 else if (abs(deltaLeft) == 2 || abs(deltaRight) == 2)
 255                                         hardFit[row] += 3;
 256                         }
 257                 }
 258                 maxHard = 0;
 259                 for (i = row + 1; i < row + 5 && i < maxHeight; ++i)
 260                         if (depend[row] & (1 << i))
 261                                 if (maxHard < hardFit[i])
 262                                         maxHard = hardFit[i];
 263                 fitProbs += maxHard * count;
 264         }
 265
 266         /* Calculate score based on top shape */
 267         for (col = 0; col < boardWidth; ++col) {
 268                 if (col > 0)
 269                         deltaLeft = height[col - 1] - height[col];
 270                 else
 271                         deltaLeft = MAX_BOARD_HEIGHT;
 272                 if (col < boardWidth - 1)
 273                         deltaRight = height[col + 1] - height[col];
 274                 else
 275                         deltaRight = MAX_BOARD_HEIGHT;
 276                 if (deltaLeft > 2 && deltaRight > 2)
 277                         topShape += 15 + 15 * (min(deltaLeft, deltaRight) / 4);
 278                 else if (deltaLeft > 2 || deltaRight > 2)
 279                         topShape += 2;
 280                 else if (abs(deltaLeft) == 2 && abs(deltaRight) == 2)
 281                         topShape += 2;
 282                 else if (abs(deltaLeft) == 2 || abs(deltaRight) == 2)
 283                         topShape += 3;
 284         }
 285
 286         closeToTop = (pRow / (double)boardHeight);
 287         closeToTop *= closeToTop;
 288
 289         closeToTop *= 200;
 290         space /= 2;
 291         score = space + closeToTop + topShape + fitProbs - linesCleared * 10;
 292
 293         if (verbose) {
 294                 WriteLine("Message space=%g, close=%g, shape=%g\n",
 295                         space, closeToTop, topShape);
 296                 WriteLine("Message fitProbs=%g, cleared=%d\n",
 297                         fitProbs, -linesCleared * 10);
 298         }
 299
 300         return score;
 301 }
 302
 303 void PrintGoal(void)
 304 {
 305         char b[32];
 306         int i, j, c;
 307
 308         c = 0;
 309         for (i = 0; i < 4; ++i) {
 310                 b[c++] = ':';
 311                 for (j = 0; j < 4; ++j)
 312                         b[c++] = pieceDest[i][j] ? '*' : ' ';
 313         }
 314         b[c++]=':';
 315         b[c++]=0;
 316         WriteLine("Message Goal %d %s\n", leftDest, b);
 317 }
 318
 319 double MakeDecision(void)
 320 {
 321         int row, col, rot;
 322         int linesCleared;
 323         int first = 1;
 324         double minScore = 0, score;
 325
 326         memcpy(piece1, piece, sizeof(piece));
 327         for (rot = 0; rot < 4; ++rot) {
 328                 RotatePiece1();
 329                 for (col = 0; col < boardWidth; ++col) {
 330                         if (!PieceFits(pieceBottom, col))
 331                                 continue;
 332                         for (row = pieceBottom; PieceFits(row-1, col); --row)
 333                                 ;
 334                         linesCleared = SimPlacement(row, col);
 335                         score = BoardScore(linesCleared, row, 0);
 336                         if (first || minScore > score) {
 337                                 first = 0;
 338                                 minScore = score;
 339                                 memcpy(pieceDest, piece1, sizeof(piece));
 340                                 leftDest = col;
 341                         }
 342                 }
 343         }
 344         PrintGoal();
 345         return minScore;
 346 }
 347
 348 double PeekScore(int verbose)
 349 {
 350         int row, col, linesCleared;
 351
 352         memcpy(piece1, piece, sizeof(piece));
 353         col = pieceLeft;
 354         for (row = pieceBottom; PieceFits(row-1, col); --row)
 355                 ;
 356         linesCleared = SimPlacement(row, col);
 357         return BoardScore(linesCleared, row, verbose);
 358 }
 359
 360 int main(int argc, char **argv)
 361 {
 362         int ac;
 363         char *av[32];
 364
 365         if (argc == 2 && !strcmp(argv[1], "-l")) {
 366                 logFile = fopen("log", "w");
 367                 if (!logFile) {
 368                         perror("fopen log");
 369                         exit(1);
 370                 }
 371         }
 372         setvbuf(stdout, NULL, _IOLBF, 0);
 373         WriteLine("Version 1\n");
 374         while(ReadLine(b, sizeof b)) {
 375                 av[0] = strtok(b, " ");
 376                 if (!av[0])
 377                         continue;
 378                 ac = 1;
 379                 while ((av[ac] = strtok(NULL, " ")))
 380                         ac++;
 381                 if (!strcmp(av[0], "Exit"))
 382                         return 0;
 383                 else if (!strcmp(av[0], "NewPiece") && ac >= 2) {
 384                         pieceCount = atoi(av[1]);
 385                         pieceState = 0;
 386                 }
 387                 else if (!strcmp(av[0], "BoardSize") && ac >= 4) {
 388                         if (atoi(av[1]) != 0)
 389                                 continue;
 390                         boardHeight = atoi(av[2]);
 391                         boardWidth = atoi(av[3]);
 392                 }
 393                 else if (!strcmp(av[0], "RowUpdate") && ac >= 3 + boardWidth) {
 394                         int scr, row, col;
 395
 396                         scr = atoi(av[1]);
 397                         if (scr != 0)
 398                                 continue;
 399                         row = atoi(av[2]);
 400                         for (col = 0; col < boardWidth; col++)
 401                                 board[row][col] = atoi(av[3 + col]);
 402                 }
 403                 else if (!strcmp(av[0], "UserKey") && ac >= 3) {
 404                         char key;
 405
 406                         key = atoi(av[1]);
 407                         switch (key) {
 408                                 case 'v':
 409                                 case 's':
 410                                         FindPiece();
 411                                         WriteLine("Message Score = %g\n", PeekScore(key == 'v'));
 412                                         break;
 413                                 case 'e':
 414                                         masterEnable = !masterEnable;
 415                                         WriteLine("Message Enable = %d\n", masterEnable);
 416                                         break;
 417                                 case 'd':
 418                                         dropEnable = !dropEnable;
 419                                         WriteLine("Message Drop Enable = %d\n", dropEnable);
 420                                         break;
 421                                 default:
 422                                         if (strcmp(av[2], "?"))
 423                                                 WriteLine("%s %d\n", av[2], pieceCount);
 424                                         break;
 425                         }
 426                 }
 427                 else if (!strcmp(av[0], "TimeStamp") && ac >= 2 && masterEnable) {
 428                         curTime = atof(av[1]);
 429                         FindPiece();
 430                         if (pieceVisible < 4)
 431                                 continue;
 432                         if (memcmp(piece, pieceLast, sizeof(piece)) ||
 433                                         pieceLeft != pieceLeftLast) {
 434                                 if (pieceState == 2)
 435                                         pieceState = 1;
 436                                 memcpy(pieceLast, piece, sizeof(piece));
 437                                 pieceLeftLast = pieceLeft;
 438                         }
 439                         if (pieceState == 0) {          /* Undecided */
 440                                 MakeDecision();
 441                                 pieceState = 1;
 442                         }
 443                         if (pieceState >= 2) {          /* Move or drop in progress */
 444                                 if (curTime >= moveTimeout)
 445                                         pieceState = 1;
 446                         }
 447                         if (pieceState == 1) {          /* Decided */
 448                                 if (memcmp(piece, pieceDest, sizeof(piece))) {
 449                                         WriteLine("Rotate %d\n", pieceCount);
 450                                         pieceState = 2;
 451                                 }
 452                                 else if (pieceLeft != leftDest) {
 453                                         if (pieceLeft < leftDest)
 454                                                 WriteLine("Right %d\n", pieceCount);
 455                                         else
 456                                                 WriteLine("Left %d\n", pieceCount);
 457                                         pieceState = 2;
 458                                 }
 459                                 else if (dropEnable) {
 460                                         WriteLine("Drop %d\n", pieceCount);
 461                                         pieceState = 3;
 462                                 }
 463                                 if (pieceState == 2)
 464                                         moveTimeout = curTime + 0.5;
 465                         }
 466                 }
 467         }
 468         return 0;
 469 }
 470
 471 /*
 472  * vi: ts=4 ai
 473  * vim: noai si
 474  */