00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #ifndef AIOPPONENT_H
00013 #define AIOPPONENT_H
00014
00015 #include "Iw2D.h"
00016 #include "limits.h"
00017
00024 class AIOpponent
00025 {
00026 public:
00031 AIOpponent(int difficulty);
00032
00036 ~AIOpponent();
00037
00042 CIwFVec2 CalculateShot(char arr[6][7]);
00043
00044 protected:
00046 enum State { EASY = 1, MEDIUM = 2, HARD = 3 };
00047
00049 CIwFVec2 m_validShots[7];
00050
00052 bool m_turn;
00053
00055 int m_difficulty;
00056
00058 static const int fourWeight = 10000;
00059
00061 static const int threeWeight = 300;
00062
00064 static const int twoWeight = 40;
00065
00067 static const int fourBlockWeight = 7500;
00068
00070 static const int threeBlockWeight = 75;
00071
00073 static const int twoBlockWeight = 10;
00074
00081 inline bool CanMakeMove(char g[6][7],
00082 int col)
00083 {
00084 return g[0][col] == 'E' ? true : false;
00085 }
00086
00093 inline int GetNextEmptyInCol(char g[6][7],
00094 int col)
00095 {
00096 for (int i = 5; i >= 0; --i)
00097 {
00098 if (g[i][col] == 'E')
00099 {
00100 return i;
00101 }
00102 }
00103 return -1;
00104 }
00105
00111 inline char CheckHorizontal(char g[6][7])
00112 {
00113 for (int i = 0; i < 6; ++i)
00114 {
00115 for (int j = 0; j < 4; ++j)
00116 {
00117 if (g[i][j] != 'E')
00118 {
00119 if ((('R' == g[i][j]) && ('R' == g[i][j + 1]) && ('R' == g[i][j + 2]) && ('R' == g[i][j + 3]))
00120 || (('Y' == g[i][j]) && ('Y' == g[i][j + 1]) && ('Y' == g[i][j + 2]) && ('Y' == g[i][j + 3])))
00121 {
00122 return g[i][j];
00123 }
00124 }
00125 }
00126 }
00127 return 'E';
00128 }
00129
00135 inline char CheckVertical(char g[6][7])
00136 {
00137 for (int i = 0; i < 3; ++i)
00138 {
00139 for (int j = 0; j < 7; ++j)
00140 {
00141 if (g[i][j] != 'E')
00142 {
00143 if ((('R' == g[i][j]) && ('R' == g[i + 1][j]) && ('R' == g[i + 2][j]) && ('R' == g[i + 3][j]))
00144 || (('Y' == g[i][j]) && ('Y' == g[i + 1][j]) && ('Y' == g[i + 2][j]) && ('Y' == g[i + 3][j])))
00145 {
00146 return g[i][j];
00147 }
00148 }
00149 }
00150 }
00151 return 'E';
00152 }
00153
00159 inline char CheckDiagonalOne(char g[6][7])
00160 {
00161 for (int i = 0; i < 3; ++i)
00162 {
00163 for (int j = 0; j < 4; ++j)
00164 {
00165 if (g[i][j] != 'E')
00166 {
00167 if ((('R' == g[i][j]) && ('R' == g[i + 1][j + 1]) && ('R' == g[i + 2][j + 2]) && ('R' == g[i + 3][j + 3]))
00168 || (('Y' == g[i][j]) && ('Y' == g[i + 1][j + 1]) && ('Y' == g[i + 2][j + 2]) && ('Y' == g[i + 3][j + 3])))
00169 {
00170 return g[i][j];
00171 }
00172 }
00173 }
00174 }
00175 return 'E';
00176 }
00177
00183 inline char CheckDiagonalTwo(char g[6][7])
00184 {
00185 for (int i = 5; i > 2; --i)
00186 {
00187 for (int j = 0; j < 4; ++j)
00188 {
00189 if (g[i][j] != 'E')
00190 {
00191 if ((('R' == g[i][j]) && ('R' == g[i - 1][j + 1]) && ('R' == g[i - 2][j + 2]) && ('R' == g[i - 3][j + 3]))
00192 || (('Y' == g[i][j]) && ('Y' == g[i - 1][j + 1]) && ('Y' == g[i - 2][j + 2]) && ('Y' == g[i - 3][j + 3])))
00193 {
00194 return g[i][j];
00195 }
00196 }
00197 }
00198 }
00199 return 'E';
00200 }
00201
00207 inline bool CheckDraw(char g[6][7])
00208 {
00209 for (int i = 0; i < 7; ++i)
00210 {
00211 if (g[0][i] == 'E')
00212 {
00213 return false;
00214 }
00215 }
00216 return true;
00217 }
00218
00224 inline char CheckForWinner(char g[6][7])
00225 {
00226 char result = CheckHorizontal(g);
00227 if (result != 'E')
00228 {
00229 return result;
00230 }
00231
00232 result = CheckVertical(g);
00233 if (result != 'E')
00234 {
00235 return result;
00236 }
00237 result = CheckDiagonalOne(g);
00238 if (result != 'E')
00239 {
00240 return result;
00241 }
00242 result = CheckDiagonalTwo(g);
00243 if (result != 'E')
00244 {
00245 return result;
00246 }
00247 if (CheckDraw(g))
00248 {
00249 return 'D';
00250 }
00251 return 'E';
00252 }
00253
00267 inline void EvaluateSegment(char s[5],
00268 int &redFour,
00269 int &redThree,
00270 int &redTwo,
00271 int &yellowFour,
00272 int &yellowThree,
00273 int &yellowTwo,
00274 int &fourBlock,
00275 int &threeBlock,
00276 int &twoBlock)
00277 {
00278 int rC = 0;
00279 int yC = 0;
00280 for (int i = 0; i < 4; i++)
00281 {
00282 'R' == s[i] ? ++rC : ++yC;
00283 }
00284 if (0 == rC && yC != 0)
00285 {
00286 if (4 == yC)
00287 {
00288 ++yellowFour;
00289 }
00290 else if (3 == yC)
00291 {
00292 ++yellowThree;
00293 }
00294 else if (2 == yC)
00295 {
00296 ++yellowTwo;
00297 }
00298 }
00299 else if (0 == yC && rC != 0)
00300 {
00301 if (4 == rC)
00302 {
00303 ++redFour;
00304 }
00305 else if (3 == rC)
00306 {
00307 ++redThree;
00308 }
00309 else if (2 == rC)
00310 {
00311 ++redTwo;
00312 }
00313 }
00314 else if (3 == rC && 1 == yC)
00315 {
00316 ++fourBlock;
00317 }
00318 else if (2 == rC && 1 == yC)
00319 {
00320 ++threeBlock;
00321 }
00322 else if (1 == rC && yC >= 1)
00323 {
00324 ++twoBlock;
00325 }
00326 }
00327
00341 inline void EvaluateHorizontals(char g[6][7],
00342 int &redFour,
00343 int &redThree,
00344 int &redTwo,
00345 int &yellowFour,
00346 int &yellowThree,
00347 int &yellowTwo,
00348 int &fourBlock,
00349 int &threeBlock,
00350 int &twoBlock)
00351 {
00352 for (int i = 0; i < 6; ++i)
00353 {
00354 for (int j = 0; j < 4; ++j)
00355 {
00356 char seg[5];
00357 seg[0] = g[i][j];
00358 seg[1] = g[i][j + 1];
00359 seg[2] = g[i][j + 2];
00360 seg[3] = g[i][j + 3];
00361 seg[4] = '\0';
00362 EvaluateSegment(seg, redFour, redThree, redTwo, yellowFour, yellowThree, yellowTwo, fourBlock, threeBlock, twoBlock);
00363 }
00364 }
00365 }
00366
00380 inline void EvaluateVerticals(char g[6][7],
00381 int &redFour,
00382 int &redThree,
00383 int &redTwo,
00384 int &yellowFour,
00385 int &yellowThree,
00386 int &yellowTwo,
00387 int &fourBlock,
00388 int &threeBlock,
00389 int &twoBlock)
00390 {
00391 for (int i = 0; i < 3; ++i)
00392 {
00393 for (int j = 0; j < 7; ++j)
00394 {
00395 char seg[5];
00396 seg[0] = g[i][j];
00397 seg[1] = g[i + 1][j];
00398 seg[2] = g[i + 2][j];
00399 seg[3] = g[i + 3][j];
00400 seg[4] = '\0';
00401 EvaluateSegment(seg, redFour, redThree, redTwo, yellowFour, yellowThree, yellowTwo, fourBlock, threeBlock, twoBlock);
00402 }
00403 }
00404 }
00405
00419 inline void EvaluateDiagonalOne(char g[6][7],
00420 int &redFour,
00421 int &redThree,
00422 int &redTwo,
00423 int &yellowFour,
00424 int &yellowThree,
00425 int &yellowTwo,
00426 int &fourBlock,
00427 int &threeBlock,
00428 int &twoBlock)
00429 {
00430 for (int i = 0; i < 3; ++i)
00431 {
00432 for (int j = 0; j < 4; ++j)
00433 {
00434 char seg[5];
00435 seg[0] = g[i][j];
00436 seg[1] = g[i + 1][j + 1];
00437 seg[2] = g[i + 2][j + 2];
00438 seg[3] = g[i + 3][j + 3];
00439 seg[4] = '\0';
00440 EvaluateSegment(seg, redFour, redThree, redTwo, yellowFour, yellowThree, yellowTwo, fourBlock, threeBlock, twoBlock);
00441 }
00442 }
00443 }
00444
00458 inline void EvaluateDiagonalTwo(char g[6][7],
00459 int &redFour,
00460 int &redThree,
00461 int &redTwo,
00462 int &yellowFour,
00463 int &yellowThree,
00464 int &yellowTwo,
00465 int &fourBlock,
00466 int &threeBlock,
00467 int &twoBlock)
00468 {
00469 for (int i = 5; i > 2; --i)
00470 {
00471 for (int j = 0; j < 4; ++j)
00472 {
00473 char seg[5];
00474 seg[0] = g[i][j];
00475 seg[1] = g[i - 1][j + 1];
00476 seg[2] = g[i - 2][j + 2];
00477 seg[3] = g[i - 3][j + 3];
00478 seg[4] = '\0';
00479 EvaluateSegment(seg, redFour, redThree, redTwo, yellowFour, yellowThree, yellowTwo, fourBlock, threeBlock, twoBlock);
00480 }
00481 }
00482 }
00483
00484
00491 inline int EvaluatePosition(char g[6][7],
00492 bool turn)
00493 {
00494 int redFour = 0;
00495 int redThree = 0;
00496 int redTwo = 0;
00497 int yellowFour = 0;
00498 int yellowThree = 0;
00499 int yellowTwo = 0;
00500 int fourBlock = 0;
00501 int threeBlock = 0;
00502 int twoBlock = 0;
00503
00504 EvaluateHorizontals(g, redFour, redThree, redTwo, yellowFour, yellowThree, yellowTwo, fourBlock, threeBlock, twoBlock);
00505 EvaluateVerticals(g, redFour, redThree, redTwo, yellowFour, yellowThree, yellowTwo, fourBlock, threeBlock, twoBlock);
00506 EvaluateDiagonalOne(g, redFour, redThree, redTwo, yellowFour, yellowThree, yellowTwo, fourBlock, threeBlock, twoBlock);
00507 EvaluateDiagonalTwo(g, redFour, redThree, redTwo, yellowFour, yellowThree, yellowTwo, fourBlock, threeBlock, twoBlock);
00508 int redScore = 0;
00509 if (redFour != 0)
00510 {
00511 redScore = INT_MAX;
00512 }
00513 else
00514 {
00515 redScore = (redThree * threeWeight) + (redTwo * twoWeight) + (fourBlock * fourBlockWeight) + (threeBlock * threeBlockWeight) + (twoBlock * twoBlockWeight);
00516 }
00517 int yellowScore = 0;
00518 if (yellowFour != 0)
00519 {
00520 yellowScore = INT_MAX;
00521 }
00522 else
00523 {
00524 yellowScore = (yellowThree * threeWeight) + (yellowTwo * twoWeight) + (fourBlock * fourBlockWeight) + (threeBlock * threeBlockWeight) + (twoBlock * twoBlockWeight);
00525 }
00526 int finalScore = yellowScore - redScore;
00527
00528 return turn ? finalScore : -finalScore;
00529 }
00530
00538 inline int UpdateGrid(char g[6][7],
00539 int col,
00540 char colour)
00541 {
00542 int row = 0;
00543 for (int i = 5; i >= 0; --i)
00544 {
00545 if ('E' == g[i][col])
00546 {
00547 g[i][col] = colour;
00548 row = i;
00549 break;
00550 }
00551 }
00552 return row;
00553 }
00554
00560 inline void MakeMove(char g[6][7],
00561 int col)
00562 {
00563 m_turn ? UpdateGrid(g, col, 'Y') : UpdateGrid(g, col, 'R');
00564 }
00565
00576 inline int NegaMax(char g[6][7],
00577 int depth,
00578 int &bM,
00579 int row,
00580 int col,
00581 bool aiTurn)
00582 {
00583 {
00584 char c = CheckForWinner(g);
00585 if ('E' != c || 0 == depth)
00586 {
00587 return EvaluatePosition(g, aiTurn);
00588 }
00589 }
00590 int bestScore = INT_MIN;
00591
00592 for (int i = 0; i < 7; ++i)
00593 {
00594 if (CanMakeMove(g, i))
00595 {
00596 {
00597 char newPos[6][7];
00598 memcpy(newPos, g, sizeof(char) * 6 * 7);
00599 int newRow = GetNextEmptyInCol(g, i);
00600 if (aiTurn)
00601 {
00602 UpdateGrid(newPos, i, 'Y');
00603 }
00604 else
00605 {
00606 UpdateGrid(newPos, i, 'R');
00607 }
00608 int newScore = 0; int newMove = 0;
00609 newScore = NegaMax(newPos, depth - 1, newMove, newRow, i, !aiTurn);
00610 newScore = -newScore;
00611 if (newScore > bestScore)
00612 {
00613 bM = i;
00614 bestScore = newScore;
00615 }
00616 }
00617 }
00618 }
00619 return bestScore;
00620 }
00621
00628 inline int GetMove(char g[6][7],
00629 int &score)
00630 {
00631 int bestMove = 0;
00632 int bestScore = 0;
00633 if (MEDIUM == m_difficulty)
00634 {
00635 bestScore = NegaMax(g, 2, bestMove, 0, 0, true);
00636 }
00637 else
00638 {
00639 bestScore = NegaMax(g, 6, bestMove, 0, 0, true);
00640 }
00641 return bestMove;
00642 }
00643 };
00644
00645 #endif
