API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jul 17th, 2018
187
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 27.91 KB | None | 0 0
raw download clone embed print report
  1. // Samsung Go Tournament Form C (g++-4.8.3)
  2.  
  3. /*
  4. [AI 코드 작성 방법]
  5. 1. char info[]의 배열 안에                    "TeamName:자신의 팀명,Department:자신의 소속"                    순서로 작성합니다.
  6. ( 주의 ) Teamname:과 Department:는 꼭 들어가야 합니다.
  7. "자신의 팀명", "자신의 소속"을 수정해야 합니다.
  8. 2. 아래의 myturn() 함수 안에 자신만의 AI 코드를 작성합니다.
  9. 3. AI 파일을 테스트 하실 때는 "육목 알고리즘대회 툴"을 사용합니다.
  10. 4. 육목 알고리즘 대회 툴의 연습하기에서 바둑돌을 누른 후, 자신의 "팀명" 이 들어간 알고리즘을 추가하여 테스트 합니다.
  11. [변수 및 함수]
  12. myturn(int cnt) : 자신의 AI 코드를 작성하는 메인 함수 입니다.
  13. int cnt (myturn()함수의 파라미터) : 돌을 몇 수 둬야하는지 정하는 변수, cnt가 1이면 육목 시작 시  한 번만  두는 상황(한 번), cnt가 2이면 그 이후 돌을 두는 상황(두 번)
  14. int  x[0], y[0] : 자신이 둘 첫 번 째 돌의 x좌표 , y좌표가 저장되어야 합니다.
  15. int  x[1], y[1] : 자신이 둘 두 번 째 돌의 x좌표 , y좌표가 저장되어야 합니다.
  16. void domymove(int x[], int y[], cnt) : 둘 돌들의 좌표를 저장해서 출력
  17. //int board[BOARD_SIZE][BOARD_SIZE]; 바둑판 현재상황 담고 있어 바로사용 가능함. 단, 원본데이터로 수정 절대금지
  18. // 놓을수 없는 위치에 바둑돌을 놓으면 실격패 처리.
  19. boolean ifFree(int x, int y) : 현재 [x,y]좌표에 바둑돌이 있는지 확인하는 함수 (없으면 true, 있으면 false)
  20. int showBoard(int x, int y) : [x, y] 좌표에 무슨 돌이 존재하는지 보여주는 함수 (1 = 자신의 돌, 2 = 상대의 돌, 3 = 블럭킹)
  21. <-------AI를 작성하실 때, 같은 이름의 함수 및 변수 사용을 권장하지 않습니다----->
  22. */
  23.  
  24. #include <stdio.h>
  25. #include <Windows.h>
  26. #include <time.h>
  27. #include <vector>
  28. #include <algorithm>
  29. #include <tuple>
  30. #include "Connect6Algo.h"
  31. using namespace std;
  32. typedef pair<int, int> POSITION;
  33. typedef pair<POSITION, POSITION> MOVES;
  34. #define X first
  35. #define Y second
  36. #define BOARD_ROW 19
  37. #define BOARD_COL 19
  38. #define EMPTY 0
  39. #define BLACK 1
  40. #define WHITE 2
  41. #define BLOCK 3
  42. #define MARK 4
  43.  
  44. // "샘플코드[C]"  -> 자신의 팀명 (수정)
  45. // "AI부서[C]"  -> 자신의 소속 (수정)
  46. // 제출시 실행파일은 반드시 팀명으로 제출!
  47. char info[] = { "TeamName:자본주의가낳은AI,Department:고려대학교" };
  48.  
  49. //(x, y)가 보드 내에 위치하는지 아닌지 확인하는 함수
  50. bool IsOutOfBounds(int x, int y) {
  51.     if (0 <= x && x < BOARD_ROW && 0 <= y && y < BOARD_COL)
  52.         return false;
  53.     return true;
  54. }
  55.  
  56. void print_POSITION(POSITION tmp) {
  57.     printf("(%d, %d)\n", tmp.X, tmp.Y);
  58. }
  59. void print_MOVES(MOVES tmp2) {
  60.     printf("(%d, %d), (%d, %d)\n", tmp2.first.X, tmp2.first.Y, tmp2.second.X, tmp2.second.Y);
  61. }
  62. void print_BOARD(int myBoard[][BOARD_COL]) {
  63.     for (int x = 0; x < BOARD_ROW; x++) {
  64.         for (int y = 0; y < BOARD_COL; y++)
  65.             printf("%d ", myBoard[x][y]);
  66.         printf("\n");
  67.     }
  68. }
  69. // player(=BLACK or WHITE)가 board에 myMove를 착수했을 때 6목이 있는지 없는지 판단하는 함수. board는 갱신된 상태로 넘어옴
  70. bool Is_Conn6(int myBoard[][BOARD_COL], MOVES myMove, int player) {
  71.     POSITION tmp[2] = { myMove.first, myMove.second };
  72.     for (int iter = 0; iter < 2; iter++) {
  73.         int x = tmp[iter].X;
  74.         int y = tmp[iter].Y; // 착수한 두 점에 대해 4방향으로 살펴보며 6목이 생성되었는지 확인. 확인하는 방법은 착수한 점을 기준으로 양 방향으로 player의 말이 몇개가 연속하는지 확인
  75.         int dx[4] = { 1, 1, 0, 1 };
  76.         int dy[4] = { 1, 0, 1, -1 };
  77.         for (int dir = 0; dir < 4; dir++) {
  78.             int cnt = 1;
  79.             int curx = x + dx[dir];
  80.             int cury = y + dy[dir];
  81.             while (!IsOutOfBounds(curx, cury) && myBoard[curx][cury] == player) {
  82.                 cnt++;
  83.                 curx += dx[dir];
  84.                 cury += dy[dir];
  85.             } // dx, dy 방향대로 진행
  86.             curx = x - dx[dir];
  87.             cury = y - dy[dir];
  88.             while (!IsOutOfBounds(curx, cury) && myBoard[curx][cury] == player) {
  89.                 cnt++;
  90.                 curx -= dx[dir];
  91.                 cury -= dy[dir];
  92.             } // dx, dy 반대 방향으로 진행
  93.             if (cnt == 6) // 정확히 6개의 돌이 연속했을 경우
  94.                 return true;
  95.         }
  96.     }
  97.     return false;
  98. }
  99.  
  100. // board_source를 board_dest에 deep copy함
  101. void DeepCopy_Board(int board_source[][BOARD_COL], int board_dest[][BOARD_COL]) {
  102.     for (int x = 0; x < BOARD_ROW; x++) {
  103.         for (int y = 0; y < BOARD_COL; y++) {
  104.             board_dest[x][y] = board_source[x][y];
  105.         }
  106.     }
  107. }
  108.  
  109. // player가 상대의 승리를 막기 위해 반드시 둬야 할 돌의 최소 갯수(=Threat의 갯수)를 구함. 적으면 적을수록 player에게 유리한 것임
  110. int Count_Threat(int myBoard[][BOARD_COL], int player) {
  111.     int opponent = 3 - player;
  112.     int threat_cnt = 0;
  113.     int board_copy[BOARD_ROW][BOARD_COL];
  114.     DeepCopy_Board(myBoard, board_copy); // board_copy에 myBoard를 copy
  115.     int dx[4] = { -1, 0, 1, 1 };
  116.     int dy[4] = { 1, 1, 1, 0 };
  117.     for (int x = 0; x < BOARD_ROW; x++) {
  118.         for (int y = 0; y < BOARD_COL; y++) { // 각 (x, y)에 대해 dir 방향으로 진행했을 때 threat window 안에 4개 이상의 opponent 돌이 존재하고, 인접한 돌이 opponent 돌이 아니고, player 돌이나 mark가 존재하지 않을 경우를 찾음
  119.             for (int dir = 0; dir < 4; dir++) {
  120.                 if (IsOutOfBounds(x + 5 * dx[dir], y + 5 * dy[dir]))
  121.                     continue;
  122.                 int opponentStone = 0;
  123.                 for (int i = 0; i < 6; i++) { // threat window 안의 6개 돌을 살펴보는 중
  124.                     if (board_copy[x + i*dx[dir]][y + i*dy[dir]] == EMPTY) // 빈 칸일 경우
  125.                         continue;
  126.                     else if (board_copy[x + i*dx[dir]][y + i*dy[dir]] == opponent) // opponent 돌이 놓여있을 경우
  127.                         opponentStone++;
  128.                     else { // player 돌이 놓여있거나 mark가 놓여있을 경우
  129.                         opponentStone = 0;
  130.                         break;
  131.                     }
  132.                 }
  133.                 if (opponentStone >= 4 && (IsOutOfBounds(x - dx[dir], y - dy[dir]) || board_copy[x - dx[dir]][y - dy[dir]] != opponent) && (IsOutOfBounds(x + 6 * dx[dir], y + 6 * dy[dir]) || board_copy[x + 6 * dx[dir]][y + 6 * dy[dir]] != opponent)) { // threat window 안에 4개 이상의 player 돌이 존재하고, 상대방 혹은 mark 돌이 없으며 threat window와 인접한 2개의 돌이 opponent의 돌이 아닐때(7목 8목 방지용)
  134.                     threat_cnt++;
  135.                     for (int i = 0; i < 6; i++) {
  136.                         if (board_copy[x + i*dx[dir]][y + i*dy[dir]] == EMPTY)
  137.                             board_copy[x + i*dx[dir]][y + i*dy[dir]] = MARK; // 빈 칸을 MARK로 변경
  138.                     }
  139.                 }
  140.             }
  141.         }
  142.     }
  143.     return threat_cnt;
  144. }
  145.  
  146. // 상대의 승리를 막기 위해 반드시 두어야하는 자리들의 목록을 반환.
  147. // (만약 Threat의 수가 1일 경우 {{x, y}, {-1, -1}}을 반환. threat_cnt에는 threat의 수를 기록할 것임
  148. // board에 opponent의 6목은 없다고 가정.(있을 경우 밑의 tmp 부분에서 오류 발생함)
  149. vector<MOVES> Get_ForcedMove(int myBoard[][BOARD_COL], int player, int* threat_cnt) {
  150.     int opponent = 3 - player;
  151.     *threat_cnt = 0;
  152.     int board_copy[BOARD_ROW][BOARD_COL];
  153.     DeepCopy_Board(myBoard, board_copy);
  154.     int dx[4] = { -1, 0, 1, 1 };
  155.     int dy[4] = { 1, 1, 1, 0 };
  156.     vector<MOVES> ForcedMove;
  157.     vector<MOVES> ThreatList;
  158.     for (int x = 0; x < BOARD_ROW; x++) {
  159.         for (int y = 0; y < BOARD_COL; y++) { // 각 (x, y)에 대해 dir 방향으로 진행했을 때 threat window 안에 4개 이상의 opponent 돌이 존재하고, 인접한 돌이 opponent 돌이 아니고, player 돌이나 mark가 존재하지 않을 경우를 찾음
  160.             for (int dir = 0; dir < 4; dir++) {
  161.                 if (IsOutOfBounds(x + 5 * dx[dir], y + 5 * dy[dir]))
  162.                     continue;
  163.                 int opponentStone = 0;
  164.                 for (int i = 0; i < 6; i++) { // threat window 안의 6개 돌을 살펴보는 중
  165.                     if (board_copy[x + i*dx[dir]][y + i*dy[dir]] == EMPTY) // 빈 칸일 경우
  166.                         continue;
  167.                     else if (board_copy[x + i*dx[dir]][y + i*dy[dir]] == opponent) // opponent 돌이 놓여있을 경우
  168.                         opponentStone++;
  169.                     else { // player 돌이 놓여있거나 mark가 놓여있을 경우
  170.                         opponentStone = 0;
  171.                         break;
  172.                     }
  173.                 }
  174.                 if (opponentStone >= 4 && (IsOutOfBounds(x - dx[dir], y - dy[dir]) || board_copy[x - dx[dir]][y - dy[dir]] != opponent) && (IsOutOfBounds(x + 6 * dx[dir], y + 6 * dy[dir]) || board_copy[x + 6 * dx[dir]][y + 6 * dy[dir]] != opponent)) { // threat window 안에 4개 이상의 player 돌이 존재하고, 상대방 혹은 mark 돌이 없으며 threat window와 인접한 2개의 돌이 opponent의 돌이 아닐때(7목 8목 방지용)
  175.                     (*threat_cnt)++;
  176.                     if ((*threat_cnt) > 2) // 내가 막아야할 자리가 3곳 이상인 상태니 어차피 졌음. 시간 아까우니 그냥 바로 return
  177.                         return ForcedMove;
  178.                     int tmp[4] = { -1, -1, -1, -1 }; // ThreatList에 파싱할 것임
  179.                     for (int i = 0; i < 6; i++) {
  180.                         if (board_copy[x + i*dx[dir]][y + i*dy[dir]] == EMPTY) {
  181.                             board_copy[x + i*dx[dir]][y + i*dy[dir]] = MARK; // 빈 칸을 MARK로 변경
  182.                             if (tmp[0] == -1) {
  183.                                 tmp[0] = x + i*dx[dir];
  184.                                 tmp[1] = y + i*dy[dir];
  185.                             }
  186.                             else {
  187.                                 tmp[2] = x + i*dx[dir];
  188.                                 tmp[3] = y + i*dy[dir];
  189.                             }
  190.                         } // tmp에 현재 threat window의 좌표를 기록해둠.(threat window 내 빈칸이 1칸일 경우 끝에는 -1, -1이 들어감)
  191.                     }
  192.                     ThreatList.push_back({ { tmp[0], tmp[1] },{ tmp[2], tmp[3] } }); // ThreatList에 현재 threat window에 대한 threat을 삽입
  193.                 }
  194.             }
  195.         }
  196.     }
  197.     if ((*threat_cnt) == 0) // threat이 없으면
  198.         return ForcedMove; // 아무것도 안채워넣은걸 그냥 반환
  199.     if ((*threat_cnt) == 1) { // threat이 1개이면
  200.         myBoard[ThreatList[0].first.X][ThreatList[0].first.Y] = player;
  201.         if (Count_Threat(myBoard, player) == 0) // threat 후보 중에서 하나를 메꾸니 Threat이 없어졌다면 이는 올바른 착수
  202.             ForcedMove.push_back({ ThreatList[0].first,{ -1, -1 } });
  203.         myBoard[ThreatList[0].first.X][ThreatList[0].first.Y] = EMPTY;
  204.         if (ThreatList[0].second.X == -1) // 해당 threat window에 threat이 1개 있었을 경우
  205.             return ForcedMove;
  206.         myBoard[ThreatList[0].second.X][ThreatList[0].second.Y] = player;
  207.         if (Count_Threat(myBoard, player) == 0) // threat 후보 중에서 하나를 메꾸니 Threat이 없어졌다면 이는 올바른 착수
  208.             ForcedMove.push_back({ ThreatList[0].second,{ -1, -1 } });
  209.         myBoard[ThreatList[0].second.X][ThreatList[0].second.Y] = EMPTY;
  210.         return ForcedMove;
  211.     }
  212.     if ((*threat_cnt) == 2) { // threat이 2개이면
  213.         POSITION tmp1[2] = { ThreatList[0].first, ThreatList[0].second };
  214.         POSITION tmp2[2] = { ThreatList[1].first, ThreatList[1].second };
  215.         for (int i = 0; i < 2; i++) {
  216.             if (tmp1[i].X == -1)
  217.                 continue;
  218.             for (int j = 0; j < 2; j++) {
  219.                 if (tmp2[j].X == -1)
  220.                     continue;
  221.                 myBoard[tmp1[i].X][tmp1[i].Y] = player;
  222.                 myBoard[tmp2[j].X][tmp2[j].Y] = player;
  223.                 if (Count_Threat(myBoard, player) == 0) // threat 후보 중에서 하나를 메꾸니 Threat이 없어졌다면 이는 올바른 착수
  224.                     ForcedMove.push_back({ tmp1[i], tmp2[j] });
  225.                 myBoard[tmp1[i].X][tmp1[i].Y] = EMPTY;
  226.                 myBoard[tmp2[j].X][tmp2[j].Y] = EMPTY; // 원상복귀
  227.             }
  228.         }
  229.         return ForcedMove;
  230.     }
  231.     return ForcedMove; // 사실 Unreachable 코드
  232. }
  233.  
  234. // 놓으면 6목을 만들 수 있는 수가 있는지 확인. 있으면 보드를 갱신하고 6목을 만드는 수를 반환, 없으면 {{-1,-1},{-1,-1}}을 반환
  235. MOVES Find_Conn6Move(int myBoard[][BOARD_COL], int player) {
  236.     int dx[4] = { -1, 0, 1, 1 };
  237.     int dy[4] = { 1, 1, 1, 0 };
  238.     for (int x = 0; x < BOARD_ROW; x++) {
  239.         for (int y = 0; y < BOARD_COL; y++) { // 각 (x, y)에 대해 dir 방향으로 진행했을 때 threat window 안에 4개 이상의 player 돌이 존재하고, 인접한 돌이 player 돌이 아니고, 상대 돌이나 mark가 존재하지 않을 경우를 찾음
  240.             for (int dir = 0; dir < 4; dir++) {
  241.                 if (IsOutOfBounds(x + 5 * dx[dir], y + 5 * dy[dir]))
  242.                     continue;
  243.                 int playerStone = 0;
  244.                 for (int i = 0; i < 6; i++) { // threat window 안의 6개 돌을 살펴보는 중
  245.                     if (myBoard[x + i*dx[dir]][y + i*dy[dir]] == EMPTY) // 빈 칸일 경우
  246.                         continue;
  247.                     else if (myBoard[x + i*dx[dir]][y + i*dy[dir]] == player) // player 돌이 놓여있을 경우
  248.                         playerStone++;
  249.                     else { // 상대방의 돌이 놓여있을 경우
  250.                         playerStone = 0;
  251.                         break;
  252.                     }
  253.                 }
  254.                 if (playerStone >= 4 && (IsOutOfBounds(x - dx[dir], y - dy[dir]) || myBoard[x - dx[dir]][y - dy[dir]] != player) && (IsOutOfBounds(x + 6 * dx[dir], y + 6 * dy[dir]) || myBoard[x + 6 * dx[dir]][y + 6 * dy[dir]] != player)) { // threat window 안에 4개 이상의 player 돌이 존재하고, 상대방 돌이 없으며 threat window와 인접한 2개의 돌이 player의 돌이 아닐때(7목 8목 방지용)
  255.                     POSITION tmp[2] = { { 0, 0 },{ 0, 0 } };
  256.                     int idx = 0;
  257.                     for (int i = 0; i < 6; i++) {
  258.                         if (myBoard[x + i*dx[dir]][y + i*dy[dir]] == EMPTY) {
  259.                             myBoard[x + i*dx[dir]][y + i*dy[dir]] = player;
  260.                             tmp[idx++] = { x + i*dx[dir], y + i*dy[dir] };
  261.                         }
  262.                     }
  263.                     if (idx == 1) { // 5개의 player 돌로 채워진 곳이라 한 개의 돌은 다른 곳에 착수해야하는 상황일 때
  264.                         for (int i = 0; i < BOARD_ROW; i++) {
  265.                             for (int j = 0; j < BOARD_COL; j++) {
  266.                                 if (myBoard[i][j] != EMPTY) // 빈칸이 아닐 경우
  267.                                     continue;
  268.                                 if (i == x - dx[dir] && j == y - dy[dir]) // 6목을 깨버릴 경우
  269.                                     continue;
  270.                                 if (i == x + 6 * dx[dir] && j == y + dx[dir]) // 6목을 꺠버릴 경우
  271.                                     continue;
  272.                                 tmp[1] = { i, j };
  273.                                 return { tmp[0], tmp[1] };
  274.                             }
  275.                         }
  276.                         // 여기에 도달했다는 것은 한 개의 돌을 어디에 두더라도 승리조건이 위배된다는 의미.
  277.                         return{ { -1,-1 },{ -1,-1 } };
  278.                     }
  279.                     return { tmp[0], tmp[1] }; // 빈칸을 반환. 여기에 착수하면 됨
  280.                 }
  281.             }
  282.         }
  283.     }
  284.     return{ { -1, -1 },{ -1, -1 } };
  285. }
  286.  
  287. // 지금 두는 수(두 수)의 Score를 반환
  288. double Get_ScoreOfSingleMove(int myBoard[][BOARD_COL], POSITION myMove, int player) {
  289.     double PlayerFactor[6] = { 0.0, 1.0, 2.0, 4.0, 6.0, 6.0 }; // PlayerFactor[i] : 나의 착수로 window 안에 나의 돌 i개를 만들었을 때 score
  290.     double OpponentFactor[6] = { 0.0, 1.5, 3.0, 6.0, 0.0, 0.0 }; // OpponentFacotr[i] : 나의 착수로 window 안에 상대 돌 i개를 저지했을 때 score. 하얀돌 4/5개를 막는건 어차피 Threat에서 걸러지므로 따로 score를 부여할 필요 없음
  291.     int opponent = 3 - player;
  292.     double score = 0.0;
  293.     int board_copy[BOARD_ROW][BOARD_COL];
  294.     DeepCopy_Board(myBoard, board_copy);
  295.     board_copy[myMove.X][myMove.Y] = player; // Threat의 수를 쉽게 구하기 위해 일단 착수시켜둠
  296.     int dx[4] = { 1, 0, 1, 1 };
  297.     int dy[4] = { 0, 1, 1, -1 };
  298.     for (int dir = 0; dir < 4; dir++) {
  299.         for (int x = myMove.X - 5 * dx[dir]; x <= myMove.X; x++) {
  300.             for (int y = myMove.Y - 5 * dy[dir]; y <= myMove.Y; y++) {
  301.                 if (IsOutOfBounds(x, y) || IsOutOfBounds(x + 5 * dx[dir], y + 5 * dy[dir]))
  302.                     continue; // 6칸이 다 보드 안에 있지 않는 threat window는 그냥 버림
  303.                 bool isThreat = true;
  304.                 int PlayerStoneCnt = 0; // 6칸 내에 player 돌의 갯수(최소 1이어야 함, 0일 경우 6칸 내에 상대 돌이나 Block이 있는 경우
  305.                 int OpponentStoneCnt = 0;
  306.                 for (int i = 0; i < 6; i++) {
  307.                     if (board_copy[x + i*dx[dir]][y + i*dy[dir]] == BLOCK) { // Block이 있는 경우
  308.                         PlayerStoneCnt = 0;
  309.                         OpponentStoneCnt = 0; // Player, Opponent 둘 다 가능성이 없음
  310.                         isThreat = false;
  311.                         break;
  312.                     }
  313.                     else if (board_copy[x + i*dx[dir]][y + i*dy[dir]] == opponent) { // 상대 돌인 경우
  314.                         OpponentStoneCnt++;
  315.                         isThreat = false;
  316.                     }
  317.                     else if (board_copy[x + i*dx[dir]][y + i*dy[dir]] == player) // 내 돌인 경우
  318.                         PlayerStoneCnt++;
  319.                     else // MARK가 놓여있거나 EMPTY가 놓여있는 경우(계속 진행은 하지만 Threat은 아님)
  320.                         isThreat = false;
  321.                 }
  322.                 if (isThreat && (IsOutOfBounds(x - dx[dir], y - dy[dir]) || myBoard[x - dx[dir]][y - dy[dir]] != player) && (IsOutOfBounds(x + 6 * dx[dir], y + 6 * dy[dir]) || myBoard[x + 6 * dx[dir]][y + 6 * dy[dir]] != player)) { // Threat이면서 window의 양 끝이 player의 돌이 아닌경우(7,8목 방지용)                    
  323.                     score += 10000.0;
  324.                     for (int i = 0; i < 6; i++) {
  325.                         if (board_copy[x + i*dx[dir]][y + i*dy[dir]] == EMPTY)
  326.                             board_copy[x + i*dx[dir]][y + i*dy[dir]] = MARK; // 비어있는 칸에 mark를 둠
  327.                     }
  328.                 }
  329.                 if (OpponentStoneCnt == 0 && (IsOutOfBounds(x - dx[dir], y - dy[dir]) || board_copy[x - dx[dir]][y - dy[dir]] != player) && (IsOutOfBounds(x + 6 * dx[dir], y + 6 * dy[dir]) || board_copy[x + 6 * dx[dir]][y + 6 * dy[dir]] != player)) // 상대돌이 없을 때
  330.                     score += PlayerFactor[PlayerStoneCnt];
  331.                 if (PlayerStoneCnt == 1 && (IsOutOfBounds(x - dx[dir], y - dy[dir]) || board_copy[x - dx[dir]][y - dy[dir]] != opponent) && (IsOutOfBounds(x + 6 * dx[dir], y + 6 * dy[dir]) || board_copy[x + 6 * dx[dir]][y + 6 * dy[dir]] != opponent)) // 내 돌이 없는(자기자신때문에 값은 1) window일 경우.(즉 상대의 6목을 저지했음)
  332.                     score += OpponentFactor[OpponentStoneCnt];
  333.             }
  334.         }
  335.     }
  336.     return score;
  337. }
  338.  
  339. double Get_ScoreOfDoubleMoves(int myBoard[][BOARD_COL], MOVES myMoves, int player) {
  340.     double score = 0.0;
  341.     score += Get_ScoreOfSingleMove(myBoard, myMoves.first, player);
  342.     myBoard[myMoves.first.X][myMoves.first.Y] = player; // 첫번째 착점하는 곳을 player로 채워넣고 두번째 착수에 대한 score를 합산
  343.     score += Get_ScoreOfSingleMove(myBoard, myMoves.second, player);
  344.     myBoard[myMoves.first.X][myMoves.first.Y] = EMPTY; // 다시 되돌림
  345.     return score;
  346. }
  347.  
  348. // 최선의 수를 반환(한개짜리)
  349. POSITION Find_BestSingleMove(int myBoard[][BOARD_COL], int player) {
  350.     double maxscore = -1.0;
  351.     POSITION bestmove = { -1, -1 };
  352.     for (int x = 0; x < BOARD_ROW; x++) {
  353.         for (int y = 0; y < BOARD_COL; y++) {
  354.             if (myBoard[x][y] != EMPTY)
  355.                 continue;
  356.             double tmpScore = Get_ScoreOfSingleMove(myBoard, { x, y }, player);
  357.             if (tmpScore >= maxscore && abs(BOARD_ROW/2 - x) + abs(BOARD_COL/2  - y) < abs(BOARD_ROW/2 - bestmove.X) + abs(BOARD_COL/2 - bestmove.Y)) {
  358.                 bestmove = { x, y };
  359.                 maxscore = tmpScore;
  360.             }
  361.         }
  362.     }
  363.     return bestmove;
  364. }
  365.  
  366. // 최선의 수를 반환(두개짜리)
  367. MOVES Find_BestDoubleMoves(int myBoard[][BOARD_COL], int player) {
  368.     int opponent = 3 - player;
  369.     double maxscore = -1.0;
  370.     MOVES bestmove = Find_Conn6Move(myBoard, player);
  371.     if (bestmove.first.X >= 0) // 6목을 만드는 적절한 착수가 존재할 경우
  372.         return bestmove; // 더 살펴볼 필요 없이 최선의 수를 바로 반환    
  373.     vector<MOVES> forcedmove;
  374.     int player_threat;
  375.     forcedmove = Get_ForcedMove(myBoard, player, &player_threat);
  376.     if (player_threat >= 3) { // 막아야할 곳이 세 곳 이상이면(나의 Threat이 3이상이면)
  377.         return{ { -1, -1 },{ -1, -1 } }; // 어차피 승산이 없으므로 아무값이나 반환함
  378.     }
  379.     if (player_threat == 2) { // 둘 곳이 굉장히 한정됨. 그 한정된 자리들을 대상으로 Score를 확인해 가장 점수가 높은 곳을 찾음
  380.         for (auto const& candidateMoves : forcedmove) {
  381.             double tmpScore = Get_ScoreOfDoubleMoves(myBoard, candidateMoves, player);
  382.             if (maxscore < tmpScore) {
  383.                 bestmove = candidateMoves;
  384.                 maxscore = tmpScore;
  385.             }
  386.         }
  387.         return bestmove;
  388.     }
  389.     if (player_threat == 1) { // 고정적으로 둬야할 자리가 1개 있고 그것의 종류가 1개 혹은 2개이므로 고정적으로 둬야할 자리를 고정해두고 나머지 빈칸을 전수조사 해서 찾을 것임
  390.         for (auto const& candidateMoves : forcedmove) {
  391.             for (int x = 0; x < BOARD_ROW; x++) {
  392.                 for (int y = 0; y < BOARD_COL; y++) {
  393.                     if (myBoard[x][y] != EMPTY || (x == candidateMoves.first.X && y == candidateMoves.first.Y)) // 비어있지 않은 칸이거나 x, y가 이미 1개 둔 자리에 겹친 경우
  394.                         continue;
  395.                     MOVES tmpMoves = { candidateMoves.first,{ x, y } };
  396.                     double tmpScore = Get_ScoreOfDoubleMoves(myBoard, tmpMoves, player);
  397.                    
  398.                     if (maxscore < tmpScore) {
  399.                         bestmove = tmpMoves;
  400.                         maxscore = tmpScore;
  401.                     }
  402.                 }
  403.             }
  404.         }
  405.     }
  406.     if (player_threat == 0) { // 모든 빈칸(대략 300개)에 대해, 300C2 가지를 전부 따져보면 가장 좋지만 너무 시간을 많이 잡아먹으므로 우선 한 개의 돌에 대해 착점해서 점수가 높은 상위 High_N개에 대해서 2개씩 매칭해 조사를 할 것임
  407.         int High_N = 5;
  408.         vector<POSITION> highScoredPosition(High_N, { -1, -1 });
  409.         vector<double> highScore(High_N);
  410.         for (int i = 0; i < High_N; i++)
  411.             highScore[i] = -i * 1.0;
  412.         for (int x = 0; x < BOARD_ROW; x++) {
  413.             for (int y = 0; y < BOARD_COL; y++) {
  414.                 if (myBoard[x][y] != EMPTY) // 빈칸이 아닐 경우 스킵
  415.                     continue;
  416.                 double currentScore = Get_ScoreOfSingleMove(myBoard, { x, y }, player);
  417.                 int idx = High_N - 1;
  418.                 while (idx >= 0 && currentScore > highScore[idx])
  419.                     idx--;
  420.                 if (idx == High_N - 1) // High_N번째보다 작을 경우
  421.                     continue;
  422.                 for (int i = High_N - 2; i >= idx+1; i--) {
  423.                     highScore[i + 1] = highScore[i];
  424.                     highScoredPosition[i + 1] = highScoredPosition[i]; // (idx+1)번째에 {x, y}를 삽입할 수 있도록 공간확보
  425.                 }
  426.                 highScore[idx + 1] = currentScore;
  427.                 highScoredPosition[idx + 1] = { x, y };
  428.             }
  429.         } // hightScore에 다 채워넣음
  430.  
  431.         for (int i = 0; i < High_N; i++) {
  432.             for (int j = i + 1; j < High_N; j++) {
  433.                 double tmpScore = Get_ScoreOfDoubleMoves(myBoard, { highScoredPosition[i], highScoredPosition[j] }, player);
  434.                 if (tmpScore > maxscore) {
  435.                     maxscore = tmpScore;
  436.                     bestmove = { highScoredPosition[i], highScoredPosition[j] };
  437.                 }
  438.             }
  439.         }
  440.     }
  441.     return bestmove;
  442. }
  443.  
  444. void myturn(int cnt) {
  445.  
  446.     int myBoard[BOARD_ROW][BOARD_COL];
  447.     for (int i = 0; i < BOARD_ROW; i++) {
  448.         for (int j = 0; j < BOARD_COL; j++) {
  449.             myBoard[i][j] = showBoard(i, j);
  450.         }
  451.     } // myBoard에 board 상태를 저장
  452.  
  453.     int x[2], y[2];
  454.  
  455.     // 이 부분에서 알고리즘 프로그램(AI)을 작성하십시오. 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하시면 됩니다.
  456.     // 현재 Sample code의 AI는 Random으로 돌을 놓는 Algorithm이 작성되어 있습니다.
  457.     if (cnt == 1) {
  458.         POSITION myMove = Find_BestSingleMove(myBoard, 1);
  459.         x[0] = myMove.X;
  460.         x[1] = 0;
  461.         y[0] = myMove.Y;
  462.         y[1] = 0;
  463.     }
  464.     else {
  465.         MOVES myMove = Find_BestDoubleMoves(myBoard, 1);
  466.         x[0] = myMove.first.X;
  467.         x[1] = myMove.second.X;
  468.         y[0] = myMove.first.Y;
  469.         y[1] = myMove.second.Y;
  470.     }
  471.  
  472.     // 이 부분에서 자신이 놓을 돌을 출력하십시오.
  473.     // 필수 함수 : domymove(x배열,y배열,배열크기)
  474.     // 여기서 배열크기(cnt)는 myturn()의 파라미터 cnt를 그대로 넣어야합니다.
  475.     domymove(x, y, cnt);
  476. }
  477.  
  478.  
  479. /*
  480. int main(void) {
  481. // COLUMN 00010203040506070809101112131415161718
  482.     int myBoard[BOARD_ROW][BOARD_COL] = {
  483.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 0
  484.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 1
  485.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 2
  486.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 3
  487.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 4
  488.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 5
  489.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 6
  490.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 7
  491.         { 0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0 }, // ROW 8
  492.         { 0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0 }, // ROW 9
  493.         { 0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0 }, // ROW 10
  494.         { 0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0 }, // ROW 11
  495.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 12
  496.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 13
  497.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 14
  498.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 15
  499.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 16
  500.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }, // ROW 17
  501.         { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }  // ROW 18
  502.     };
  503.     MOVES tmp2 = Find_BestDoubleMoves(myBoard, 1);
  504.     print_MOVES(tmp2);
  505. }*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!