Comment out the homepage URL
[pkg/netris.git] / 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  */