1 /*
2 File: BotPlayer.cpp
3 Description: AI player (Evaluation function)
4 Program: BlockOut
5 Author: Jean-Luc PONS, Lieven
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16 */
17 #include "BotPlayer.h"
18 #include <stdlib.h>
19 #include <string.h>
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <math.h>
23
24 #define GET_DISTANCE(x,y,z) sqrtf((float)(((x)-W)*((x)-W)+(y)*(y)+(z)*(z)));
25 #define EDGE_MATRIX(x,y,z) edgeMatrix[(x) + (y)*width + (z)*area]
26
27 // --------------------------------------------------
28
GetDepthAt(int x,int y)29 inline int BotPlayer::GetDepthAt(int x,int y) {
30
31 int *lMatrix = matrix + (y*width + x);
32 int k;
33
34 for(k=0;k<depth && (*lMatrix == 0);k++)
35 lMatrix += area;
36
37 return k;
38
39 }
40
41 // ------------------------------------------------------------------------
42
CheckDeathZone()43 float BotPlayer::CheckDeathZone() {
44
45 float note = 0.0f;
46 int W = width-1;
47 int H = height-1;
48
49 // First line
50 for(int j=0;j<height;j++) {
51 for(int i=0;i<width;i++) {
52 if(GET_VALUE(i,j,0)) note -= 2.5f;
53 }
54 }
55
56 // Death zone (L0)
57 if(GET_VALUE(W,0,0)) note -= 25.0f;
58 if(GET_VALUE(W,1,0)) note -= 25.0f;
59 if(GET_VALUE(W-1,0,0)) note -= 25.0f;
60 if(GET_VALUE(W-1,1,0)) note -= 25.0f;
61 if(GET_VALUE(W-2,0,0)) note -= 25.0f;
62
63 // Death zone (L1)
64 if(GET_VALUE(W,0,1)) note -= 5.0f;
65 if(GET_VALUE(W,1,1)) note -= 5.0f;
66 if(GET_VALUE(W-1,0,1)) note -= 5.0f;
67 if(GET_VALUE(W-1,1,1)) note -= 5.0f;
68
69 return note;
70
71 }
72
73 // ------------------------------------------------------------------------
74
GetPitNote()75 float BotPlayer::GetPitNote() {
76
77 // Compute pit note for the played block
78 float note = 0.0f;
79 for(int i=0;i<nbCube;i++) {
80 int x = transCube[i].x;
81 int y = transCube[i].y;
82 int z = transCube[i].z;
83 note+=EDGE_MATRIX(x,y,z);
84 }
85 return note/(float)nbCube;
86
87 }
88
89 // ------------------------------------------------------------------------
90
CountEdge(int x,int y,int z,int * common,int * edge)91 void BotPlayer::CountEdge(int x,int y,int z,int *common,int *edge) {
92
93 //v=0 => Free cell
94 //v=1 => Occupied cell
95 //v=2 => Cell occupied by a cube of the currently played block
96 int v = GetValue(x,y,z);
97
98 if( v==0 ) {
99 *edge = *edge + 1;
100 } else if( v==1 ) {
101 *edge = *edge + 1;
102 *common = *common + 1;
103 }
104
105 }
106
GetCommonEdge()107 float BotPlayer::GetCommonEdge() {
108
109 // Puzzle solver
110 // Count number of common edges (facets) between the played block, the pit surface and
111 // pit sides. This greatly increase the building efficiency (especialy in OOC)
112 int nbCommon = 0;
113 int nbEdge = 0;
114
115 for(int i=0;i<nbCube;i++) {
116
117 int x = transCube[i].x;
118 int y = transCube[i].y;
119 int z = transCube[i].z;
120 CountEdge(x-1,y,z,&nbCommon,&nbEdge);
121 CountEdge(x+1,y,z,&nbCommon,&nbEdge);
122 CountEdge(x,y-1,z,&nbCommon,&nbEdge);
123 CountEdge(x,y+1,z,&nbCommon,&nbEdge);
124 CountEdge(x,y,z-1,&nbCommon,&nbEdge);
125 CountEdge(x,y,z+1,&nbCommon,&nbEdge);
126
127 }
128
129 return (float)nbCommon/(float)nbEdge;
130
131 }
132
133 // --------------------------------------------------
134
Smoothness()135 inline float BotPlayer::Smoothness() {
136
137 int total=0;
138 int d;
139
140 for(int i=0;i<width;i++) {
141 for(int j=0;j<height;j++) {
142 dd[i][j]=GetDepthAt(i,j);
143 }
144 }
145
146 for(int i=0;i<width;i++) {
147 for(int j=0;j<height;j++) {
148 if (i-1>=0) {d=dd[i][j]-dd[i-1][j];total+=d*d;};
149 if (j-1>=0) {d=dd[i][j]-dd[i][j-1];total+=d*d;};
150 if (j+1<height){d=dd[i][j]-dd[i][j+1];total+=d*d;};
151 if (i+1<width) {d=dd[i][j]-dd[i+1][j];total+=d*d;};
152 }
153 }
154
155 // Bonus on flat pit
156 if(total==0) total = -10;
157
158 return (float)total/(float)area;
159
160 }
161
162 // --------------------------------------------------
163
Peakness(int bias)164 inline float BotPlayer::Peakness(int bias) {
165
166 float note=0.0f;
167 int W = width-1;
168 int H = height-1;
169 int ddij;
170
171 // Detect "1 cube size pit"
172 // Note: Smothness() must be called before
173
174 for(int i=0;i<width;i++) {
175 for(int j=0;j<height;j++) {
176 ddij = dd[i][j];
177 if( i==0 && j==0 ) {
178 if( (dd[i+1][j] - ddij)<=bias &&
179 (dd[i][j+1] - ddij)<=bias ) note +=1.0f;
180 } else if (i==0 && j==H) {
181 if( (dd[i+1][j] - ddij)<=bias &&
182 (dd[i][j-1] - ddij)<=bias ) note +=1.0f;
183 } else if (i==W && j==0) {
184 if( (dd[i-1][j] - ddij)<=bias &&
185 (dd[i][j+1] - ddij)<=bias ) note +=1.0f;
186 } else if (i==W && j==H) {
187 if( (dd[i-1][j] - ddij)<=bias &&
188 (dd[i][j-1] - ddij)<=bias ) note +=1.0f;
189 } else {
190 if( (dd[i-1][j] - ddij)<=bias &&
191 (dd[i+1][j] - ddij)<=bias &&
192 (dd[i][j-1] - ddij)<=bias &&
193 (dd[i][j+1] - ddij)<=bias ) note +=1.0f;
194 }
195 }
196 }
197
198 return note;
199
200 }
201
202 // ------------------------------------------------------------------------
203 // Pit edges bonus
204 // ------------------------------------------------------------------------
InitPitCoef()205 void BotPlayer::InitPitCoef() {
206
207 // 1 bonus coeficiens per pit cell
208
209 // Reset all coeficients to zero
210 memset(edgeMatrix,0,mSize*sizeof(float));
211 int W = width-1;
212 int H = height-1;
213
214 // Fill up edge/corner bonus
215 for(int k=0;k<depth;k++) {
216
217 for(int i=0;i<width;i++) {
218 EDGE_MATRIX(i,0,k) = edgeCoef;
219 EDGE_MATRIX(i,H,k) = edgeCoef;
220 }
221 for(int j=1;j<H;j++) {
222 EDGE_MATRIX(0,j,k) = edgeCoef;
223 EDGE_MATRIX(W,j,k) = edgeCoef;
224 }
225 // Corner
226 EDGE_MATRIX(0,0,k) = cornerCoef;
227 EDGE_MATRIX(0,H,k) = cornerCoef;
228 EDGE_MATRIX(W,0,k) = cornerCoef;
229 EDGE_MATRIX(W,H,k) = cornerCoef;
230
231 }
232
233 // Fill up origin to edge distance (for asymetric edges)
234 // Prefere to place the block at the opposite corner
235 // in case of equlity. That's the reason of the low
236 // value of edgeDistCoef.
237 // However, it seems that in OOC, it is preferable to
238 // go to the opposite side (not corner).
239
240 switch(blockSet) {
241
242 case BLOCKSET_EXTENDED:
243 for(int k=0;k<depth;k++) {
244 for(int j=0;j<height;j++) {
245 for(int i=0;i<width;i++) {
246 EDGE_MATRIX(i,j,k) += distCoef * GET_DISTANCE(i,0,0);
247 }
248 }
249 }
250 break;
251
252 case BLOCKSET_BASIC:
253 case BLOCKSET_FLAT:
254 for(int k=0;k<depth;k++) {
255 for(int j=0;j<height;j++) {
256 for(int i=0;i<width;i++) {
257 EDGE_MATRIX(i,j,k) += distCoef * GET_DISTANCE(i,j,k);
258 }
259 }
260 }
261 break;
262
263 }
264
265 }
266
InitCoef()267 void BotPlayer::InitCoef() {
268
269
270 // Blockset independent coefficients
271
272 // Per block
273 puzzleCoef = 11.7f; // Puzzle solver (per block)
274 distCoef = 0.001f; // Distance to origin
275
276 // Per pit
277 linesCoef = 0.7f; // Line (layer)
278 smoothCoef = -0.28f; // Pit surface smoothness (sqr)
279
280 // Blockset dependent coefficients
281 // Ref are given in number of cubes.
282 switch(blockSet) {
283
284 case BLOCKSET_FLAT:
285
286 //Ref:3x3x6 FLAT Avg=29228.7 Min=109(410276037) Max=237501 nbGame=1000
287
288 cornerCoef = 0.0f; // Pit corner occupation (per block)
289 edgeCoef = 0.0f; // Pit side occupation (per block)
290 holeCoef = -1.9f; // Hole
291 peakCoef = -0.0f; // Pit surface "peakness" (peak detection)
292 break;
293
294 case BLOCKSET_EXTENDED:
295
296 //Ref:5x5x10 EXTENDED Avg=243031 Min=272(1896058267) Max=1924054 nbGame=1000
297 //Ref:3x3x18 EXTENDED Avg=488.657 Min=165(362445833) Max=1458 nbGame=1000
298
299 // Special peak/corner/edge handling for 3x3
300 if( width==3 && height==3 ) {
301 // Per block
302 cornerCoef = 2.8f; // Pit corner occupation
303 edgeCoef = 0.8f; // Pit side occupation
304 // Per pit
305 peakCoef = -0.8f; // Pit surface "peakness" (peak detection)
306 } else {
307 // Per block
308 cornerCoef = 0.0f; // Pit corner occupation
309 edgeCoef = 0.0f; // Pit side occupation
310 // Per pit
311 peakCoef = -0.0f; // Pit surface "peakness" (peak detection)
312 }
313
314 // Per pit
315 holeCoef = -1.9f; // Hole
316 break;
317
318 case BLOCKSET_BASIC:
319
320 //Ref:3x3x6 BASIC Avg=1834.73 Min=32(1592640469) Max=15939 nbGame=10000
321
322 // Per block
323 cornerCoef = 2.8f; // Pit corner occupation
324 edgeCoef = 0.8f; // Pit side occupation
325
326 // Per pit
327 holeCoef = -1.1f; // Hole
328 peakCoef = -0.81f; // Pit surface "peakness" (peak detection)
329 break;
330
331 }
332
333 InitPitCoef();
334
335 }
336
337 // --------------------------------------------------
338 // JL and Lieven's Evaluation function ;)
339 // --------------------------------------------------
340 #if 1
Evaluate()341 float BotPlayer::Evaluate() {
342
343 DropBlock(); // Drop the block
344 AddBlock(); // Add the block to the pit
345 float commonEdge = GetCommonEdge(); // Puzzle solver
346 float pitBonus = GetPitNote(); // Pit note
347 float nbLines = RemoveLines(); // Remove lines
348 float dNote = CheckDeathZone(); // Death zone
349 pitBonus += dNote;
350
351 float linesNote = linesCoef * nbLines; // Line (layer)
352 float pitNote = pitBonus; // Edge,corner,distance,death zone
353 float smooth2Note = smoothCoef * Smoothness(); // Pit surface smoothness
354 float commonNote = puzzleCoef * commonEdge; // Puzzle solver
355 float nbHoleNote = holeCoef * GetNbHole(); // Hole
356 float peakNote = peakCoef * Peakness(-2); // Pit surface "peakness" (peak detection)
357
358 float coveredNote = 0.0f; //-0.02f * GetNbCoveredHole(); // Covered hole
359
360 float totalNote=pitNote+smooth2Note+peakNote+commonNote+linesNote+nbHoleNote+coveredNote;
361
362 #ifdef _DEBUG
363 // sprintf(infoStr,
364 // "Pt=%.3f Cm=%.2f Pk=%.2f Hl=%.2f Ln=%.2f Cv=%.2f Sh=%.2f N=%.3f",
365 // pitNote,commonNote,peakNote,nbHoleNote,linesNote,coveredNote,smooth2Note,totalNote);
366 sprintf(infoStr,
367 "Pt=%.3f Cm=%.2f Pk=%.2f Hl=%.2f Ln=%.2f Sh=%.2f N=%.3f",
368 pitNote,commonNote,peakNote,nbHoleNote,linesNote,smooth2Note,totalNote);
369 #endif
370
371 return totalNote;
372 }
373 #endif
374
375 // ----------------------------------------------------------------------
376 // Lieven's original evaluation function (already quite good in 3DMania)
377 // ----------------------------------------------------------------------
378 #if 0
379 float BotPlayer::Evaluate() {
380
381 DropBlock(); // Drop the block
382 AddBlock(); // Add the block to the pit
383 float nbLines = RemoveLines(); // Remove lines
384
385 float thick=(float)nbCubeInPit-nbLines*(float)area; //Number of blocks
386 float nbHole1 = GetNbHole(); // Number of holes
387 float smooth2 = Smoothness2(); // How smooth is the pitch (sqr)
388 //float smooth = Smoothness1(); // How smooth is the pitch (abs)
389 float edgel = Edges(); //if you have to go high, go high on the edge
390
391 //float note = -27*thick-75.0f*nbHole1-3.0f*smooth2+2*edgel; //FLAT FUN
392 float note = -27.0f*thick-75.0f*nbHole1-3.0f*smooth2+17.0f*edgel; //3DMANIA
393 //return -17.0f*thick-500.0f*nbHole1-40.0f*smooth+11.0f*edgel; //OUT OF CONTROL
394
395 #ifdef _DEBUG
396 sprintf(infoStr,
397 "thick=%.3f, edge1=%.3f, smooth=%.3f, hole=%.0f\nnote=%f",
398 thick,edgel,smooth2,nbHole1,note);
399 #endif
400
401 return note;
402
403 }
404
405 // --------------------------------------------------
406
407 inline float BotPlayer::Smoothness2() {
408
409 int hh[7][7];
410 int total=0,d;
411
412 for(int i=0;i<width;i++) {
413 for(int j=0;j<height;j++) {
414 hh[i][j]=GetDepthAt(i,j);
415 }
416 }
417
418 for(int i=0;i<width;i++) {
419 for(int j=0;j<height;j++) {
420 if (i-1>=0) {d=hh[i][j]-hh[i-1][j];total+=d*d;}
421 if (j-1>=0) {d=hh[i][j]-hh[i][j-1];total+=d*d;}
422 if (j+1<height){d=hh[i][j]-hh[i][j+1];total+=d*d;}
423 if (i+1<width) {d=hh[i][j]-hh[i+1][j];total+=d*d;}
424 }
425 }
426
427 // Bonus if empty pit (flush)
428 int good=50;
429 for(int i=0;i<width;i++)
430 for(int j=0;j<height;j++)
431 if (hh[i][j]) good=0;
432
433 return (float)(total-good);
434
435 }
436
437 // --------------------------------------------------
438
439 inline float BotPlayer::Edges() {
440
441 // Count cubes near the edges
442 // Count 2 times cubes in corner
443 int *lMatrix = matrix;
444 int total = 0;
445 int W = width-1;
446 int H = height-1;
447 for(int k=0;k<depth;k++) {
448
449 for(int i=0;i<width;i++) {
450 if( lMatrix[i+0*width] ) total++;
451 if( lMatrix[i+H*width] ) total++;
452 }
453 for(int j=0;j<height;j++) {
454 if( lMatrix[0+j*width] ) total++;
455 if( lMatrix[W+j*width] ) total++;
456 }
457
458 lMatrix += area;
459
460 }
461
462 return (float)total;
463
464 }
465
466 // --------------------------------------------------
467
468 inline float BotPlayer::Smoothness1() {
469
470 int total=0,d;
471
472 for(int i=0;i<width;i++) {
473 for(int j=0;j<height;j++) {
474 dd[i][j]=GetDepthAt(i,j);
475 }
476 }
477
478 for(int i=0;i<width;i++) {
479 for(int j=0;j<height;j++) {
480 if (i-1>=0) {d=dd[i][j]-dd[i-1][j];total+=abs(d);}
481 if (j-1>=0) {d=dd[i][j]-dd[i][j-1];total+=abs(d);}
482 if (j+1<height){d=dd[i][j]-dd[i][j+1];total+=abs(d);}
483 if (i+1<width) {d=dd[i][j]-dd[i+1][j];total+=abs(d);}
484 }
485 }
486
487 // Bonus if empty pit (flush)
488 int good=50;
489 for(int i=0;i<width;i++)
490 for(int j=0;j<height;j++)
491 if (dd[i][j]) good=0;
492
493 return (float)(total-good);
494
495 }
496
497 #endif
498