탐색을 적용시킨 오목 AI를 구현해보고 싶어서 3일동안 AI 제작을 진행하게 됐습니다.
먼저 19*19 바둑판 맵을 다 탐색을 하여 돌의 연결상태를 확인한 후 각 돌의 연결 상황마다 가중치를 부여했습니다.
그 후 Search 함수를 통해 탐색 과정에서 AI끼리 각자 가지치기 방식으로 최적의 수를 두어나갑니다.
탐색 중 상대방이 이기는 경우가 발생 하면 return 하여 가지가 갈라지는 분기점으로 돌아가 재 탐색을 시작합니다.
그렇게 탐색하는 도중 자신의 AI가 이기는 상황이 발생하면 맨 처음 좌표값을 저장한 후 그 이후부터는 모든 상황에 대해 return하여 탐색을 종료시켜 제작하였습니다.
최대 깊이 탐색은 현재 시점으로부터 30수까지 설정해 놓았습니다. 그 이유는 웬만하면 승부가 나는 시점까지 도달하고 탐색시간이 오래 걸리지 않았기 때문입니다.
그리고 탐색을 하는 도중에 각각의 AI의 입장에서 가장 최선의 수를 두어나가는 방식이므로 MIN_MAX 전략이라고 할 수 있겠습니다. 아군 AI입장에서는 적군 AI가 이기는 상황은 피하면서(MIN) 현재 자신에게 필요한 최적 수(MAX)를 두어 나가기 때문입니다.
다음은 탐색과정과 필승 수를 찾아가는 과정입니다.
위의 영상대로 가장 높은 가중치를 따라서 쭉쭉 진행하다가
이와 같이 빨간색으로 표시한 가중치값이 동일한 분기점에 도달하게 됩니다 (가지치기의 시작)
가장 왼쪽에 있는 곳부터 가장 최선의 수를 두어가며 다시 탐색을 시작합니다.
그러다가 상대방이 이기는 상황이 찾아오게 됩니다.
AI는 이 길은 잘 못된 경로라는 것을 인지하고 다시 분기점으로 되돌아 가고 두번째 경로를 선택하여 동일한 방식으로 탐색을 진행합니다.
해당 경로에서는 상대 AI(2) 가 계속해서 막기만하다가 자신의 AI(1)가 이기는 상황이 찾아옵니다.
AI는 이 경로가 필승 수가 되는 경로임을 파악하고
맨 처음 이 경로의 시작점인 (8,9)의 값으로 착수를 결정하게됩니다.
이와 같은 방식으로 진행한 전체 플레이 영상입니다.
/*
main 에서 구상
아군 AI, 적군 AI 실행
아군은 내가 두고
적군은 이제 판의 가중치를 고려하여 자유롭게 두는 방식
*패치사항*
1. 3을 막는것과 3에서 4로 연장시키는거 무작정 4로 연결시키면 좋지 않음
2. 120221 인식 못함
*/
#include <Windows.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#define endl '\n'
using namespace std;
int map[19][19];//바둑 판
int w_board[19][19];//가중치 판
int dir[8][2] = { { 1,0 },{ 0,1 },{ 1,1 },{ 1,-1 },{ -1,0 },{ 0,-1 },{ -1,-1 },{ -1,1 } };
int n = 19;
int w[2][6] = { { 0,1,50,9999,500000,10000000 },{ 0,1,12,250,400000,10000000 } };//막 3보다는 뚫2 //막 4보다는 뚫3// 상대편 막 4는 더 큼
int w2[2][6][3][2];
int stx, sty;//ai입장에서 탐색 맨 처음 좌표
int ansx, ansy;// 최종적으로 search를 통해 찾은 좌표
int real_high[6];//가장 높은 가중치
typedef struct xy {
int x, y;
}xy;
typedef struct info {
int num = 0, enemy = 0, emptyspace = 0;
}info;
typedef struct info2 {//x,y 좌표와 가중치값
int x, y, weight;
};
bool cmp(info2 a, info2 b) {
return a.weight > b.weight;
}
void Print();
void add_weight(int color[2]);
void search(int cnt, int color);
void AI(int user_color, int ai_color);
void Print();
void input(int type);
void game_type(int type);
bool check(int color);
void init() {
//0,2,25,421,1200000,10000000 },{ 0,1,22,105,17000,10000000
// my or your / num / enemy / space
//num=1 일때 빈공간 0인것만 1 나머지는 0
//map[5][9] = 1; map[5][10] = 2; map[5][11] = 2; map[5][13] = 2; map[5][14] = 1;
w2[0][1][0][0] = 2; w2[1][1][0][0] = 1;
w2[0][1][0][1] = 2; w2[1][1][0][1] = 0;
//num=2 일때
w2[0][2][0][0] = 25, w2[1][2][0][0] = 4;
w2[0][2][0][1] = 25, w2[1][2][0][1] = 1;
w2[0][2][1][1] = 2; w2[1][2][1][1] = 1;
w2[0][2][1][0] = 2; w2[1][2][1][0] = 1;
//num=3
w2[0][3][0][0] = 521, w2[1][3][0][0] = 105;
w2[0][3][0][1] = 301; w2[1][3][0][1] = 13;
w2[0][3][1][0] = 301, w2[1][3][1][0] = 13;
w2[0][3][1][1] = 301, w2[1][3][1][1] = 13;
//num=4
w2[0][4][0][0] = 21000; w2[0][4][1][0] = 20010; w2[0][4][2][0] = 20010;
w2[1][4][0][0] = 4001; w2[1][4][1][0] = 4001; w2[1][4][2][0] = 4001;
}
void add_weight(int color[2]) {//착수 후 근처에 가중치 부여
memset(w_board, 0, sizeof(w_board));
//착수하고 나면 그곳의 가중치는 0으로 만들고 착수된 곳엔 가중치 부여를 하지 않는다.
//만약 그곳에 착수 했을 경우 해당 자리 근처로
//2,막2 막막2 이런게 몇개인지 확인해야함
//1,2,3,4,막1,막2,막3,막4
for (int type = 0; type < 2; type++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int sum = 0;
info Count[5];//세로, 가로, 우하, 우상 돌 갯수
if (map[i][j])continue;
for (int d = 0; d < 4; d++) {
int nx, ny;
int cnt = 1;
int zerocnt = 0;//총 빈칸 0~ 2 개까지만 존재하도록 만들꺼
int zerocnt1 = 0;
int remember = 0;
int zerocnt2 = 0;
int num = 0;
int enemy_cnt = 0;
int before;
//cout << "정방향 " << endl;
while (true) {
nx = i + (cnt * dir[d][0]), ny = j + (cnt * dir[d][1]);
before = map[nx - dir[d][0]][ny - dir[d][1]];
//cout << "nx " << ny << " ny " << ny << " num " << num << " zerocnt " << zerocnt1 << " remember " << remember << " enemy " << enemy_cnt << endl;
if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
if (remember || zerocnt1 == 0) {
enemy_cnt++;
}
if (before != 0)remember = zerocnt1;
break;
}
if (map[nx][ny] == color[(type + 1) % 2]) {
if (remember || zerocnt1 == 0) {
enemy_cnt++;
}
if (before != 0)
remember = zerocnt1;
break;
}
if (map[nx][ny] == color[type]) {
remember = zerocnt1;
num++;
}
if (map[nx][ny] == 0)zerocnt1++;
if (zerocnt1 >= 2)break;
cnt++;
}
//cout <<"d: "<<d<< "remember " << remember <<" length "<<length<< endl;
zerocnt1 = remember;
cnt = 1;
remember = 0;
//반대편라인
//cout << "반대방향 " << endl;
while (true) {
nx = i + (cnt * dir[d + 4][0]), ny = j + (cnt * dir[d + 4][1]);
//cout << "nx " << ny << " ny " << ny << " num " << num << " zerocnt " << zerocnt1 << " remember " << remember << " enemy " << enemy_cnt << endl;
if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
if (remember || zerocnt2 == 0) {
enemy_cnt++;
}
if (before != 0)remember = zerocnt2;
break;
}
if (map[nx][ny] == color[(type + 1) % 2]) {
if (remember || zerocnt2 == 0) {
enemy_cnt++;
}
if (before != 0)remember = zerocnt2;
break;
}
if (map[nx][ny] == color[type]) {
remember = zerocnt2;
num++;
}
if (map[nx][ny] == 0)zerocnt2++;
if (zerocnt2 >= 2)break;
cnt++;
}
zerocnt2 = remember;
zerocnt = zerocnt1 + zerocnt2;
Count[d] = { num,enemy_cnt,zerocnt };
}
//
/*cout << "x " << i << " y " << j << " 연결된 나의돌 갯수와 막고있는 상대 돌 갯수 " << endl;
for (int d = 0; d < 4; d++) {
cout << d << ": " << Count[d].num << " " << Count[d].enemy<<" "<<Count[d].emptyspace << endl;
}
cout << endl;*/
//나의 돌을 상대가 막고 있음 가중치 많이 낮춰 드리자
for (int d = 0; d < 4; d++) {
int num = Count[d].num, enemy = Count[d].enemy, emptyspace = Count[d].emptyspace;
int temp_w = w2[(type + 1) % 2][num][enemy][emptyspace];
//빈 공간은 하나만 감당, num+emptyspace>=5,enemy 2개 가중치 부여하지 않는다.
if (emptyspace >= 2 || num + emptyspace >= 5)continue;
if (num != 4 && enemy >= 2)continue;
sum += temp_w;
}
w_board[i][j] += sum;
if (map[i][j])w_board[i][j] = 0;
}
}
}
/*xy ret;
int high = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (high < w_board[i][j]) {
ret = { i,j };
high = w_board[i][j];
}
else if (high == w_board[i][j]) {
for (int d = 0; d < 8; d++) {
int nx = i + dir[d][0], ny = j + dir[d][1];
if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
if (map[nx][ny]) {
ret = { i,j };
}
nx = i + dir[d][0], ny = j + dir[d][1];
if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
if (map[nx][ny]) {
ret = { i,j };
}
}
}
}
}*/
//가중치보드
/*
cout << "weight board" << endl;
cout << " x/y ";
for (int j = 0; j < n; j++) {
cout.width(5);
cout << j;
}
cout << endl;
for (int i = 0; i < n; i++) {
cout.width(5);
cout << i;
for (int j = 0; j < n; j++) {
cout.width(5);
cout << w_board[i][j];
}
cout << endl;
}
cout << endl;
*/
}
bool tf;
void search(int cnt, int color)
{
int ncolor[2] = { 0, };
if (color == 1) {
ncolor[0] = 2, ncolor[1] = 1;
}
else {
ncolor[0] = 1, ncolor[1] = 2;
}
int high = 0;
add_weight(ncolor);
deque <info2> save_pos;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int wow = w_board[i][j];
if (wow) {
if (wow == 301||wow==302)wow = 24;
else if (wow >= 118 && wow <= 200)wow = 320;
save_pos.push_back({ i,j,wow });
high = max(high, wow);
}
}
}
sort(save_pos.begin(), save_pos.end(), cmp);
//4배 이상 차이나면 딱 거기까지 만 넣는다.
//그리고 5개 끊자
int MAX = save_pos[0].weight;
int idx = 0;
for (int i = 1; i < save_pos.size(); i++) {
idx = i;
int num = save_pos[i].weight;
if (num != MAX)break;
}
save_pos.erase(save_pos.begin() + idx, save_pos.end());
/*cout << "color " << color << " cnt " << cnt << endl;
cout << "weight board" << endl;
cout << " x/y ";
for (int j = 0; j < n; j++) {
cout.width(5);
cout << j;
}
cout << endl;
for (int i = 0; i < n; i++) {
cout.width(5);
cout << i;
for (int j = 0; j < n; j++) {
cout.width(5);
cout << w_board[i][j];
}
cout << endl;
}
cout << endl;
cout << "map" << endl;
Print();*/
int temp_color;
if (color == 1)temp_color = 2;
else temp_color = 1;
if (cnt%2==1&&check(temp_color)) {
return;
}
if (tf)return;
if (!tf&&(cnt%2==1 &&( (MAX>=326&&MAX<406)||MAX>=521))) {
if (!((105 <= MAX && MAX <= 300) || (4000 <= MAX && MAX < 20000))) {
/*cout << "############################################################" << endl;
cout << "############################################################" << endl;
cout << "############################################################" << endl;
cout << "MAX " << MAX << endl;
cout << "FIND victory!" << endl;
cout << "cnt " << cnt << " color " << color << endl;
cout << "weight board" << endl;
cout << " x/y ";
for (int j = 0; j < n; j++) {
cout.width(5);
cout << j;
}
cout << endl;
for (int i = 0; i < n; i++) {
cout.width(5);
cout << i;
for (int j = 0; j < n; j++) {
cout.width(5);
cout << w_board[i][j];
}
cout << endl;
}
cout << endl;
cout << "map" << endl;
Print();*/
tf = true;
ansx = stx, ansy = sty;
return;
}
}
if (cnt == 30) {//30수까지 내다본다.
return;
}
if (color == 1) {
for (int i = 0; i < save_pos.size(); i++) {
int x = save_pos[i].x, y = save_pos[i].y;
map[x][y] = color;
search(cnt + 1, 2);
map[x][y] = 0;
}
}
else if (color == 2) {
for (int i = 0; i < save_pos.size(); i++) {
int x = save_pos[i].x, y = save_pos[i].y;
map[x][y] = color;
search(cnt + 1, 1);
map[x][y] = 0;
}
}
}
void AI(int user_color, int ai_color) {
tf = false;
int color[2] = { user_color,ai_color };
memset(real_high, 0, sizeof(real_high));
//AI 알고리즘 설정
add_weight(color);
deque <info2> save_pos;
save_pos.clear();
int high = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int wow = w_board[i][j];
if (wow) {
if (wow == 301 || wow == 302)wow = 24;
else if (wow >= 118 && wow <= 200)wow = 320;
save_pos.push_back({ i,j,wow });
if (high < wow) {
high = wow;
ansx = i, ansy = j;
}
}
}
}
sort(save_pos.begin(), save_pos.end(), cmp);
//50 이상이면 그 수들부터 10개까지만 탐색시키고
//50 미만이면 5개까지 탐색 ㄱㄱ
int MAX = save_pos[0].weight;
//cout << "MAX " << MAX << endl;
/*int idx = 0;
for (int i = 1; i < save_pos.size(); i++) {
idx = i;
int num = save_pos[i].weight;
if (num != MAX)break;
}
save_pos.erase(save_pos.begin() + idx, save_pos.end());*/
//알고리즘
if (!((MAX >= 326 && MAX<406) || MAX >= 521)) {
/*
cout << "search " << endl;
for (int i = 0; i < save_pos.size(); i++) {
cout << "weight "<<save_pos[i].weight << " x " << save_pos[i].x << " y " << save_pos[i].y;
}
cout << endl;
cout << "weight board" << endl;
cout << " x/y ";
for (int j = 0; j < n; j++) {
cout.width(5);
cout << j;
}
cout << endl;
for (int i = 0; i < n; i++) {
cout.width(5);
cout << i;
for (int j = 0; j < n; j++) {
cout.width(5);
cout << w_board[i][j];
}
cout << endl;
}
cout << endl;*/
//가중치가 0이 아닌 놈들을 대상으로 search 시작
//search안에서 add_weight로 map 탐색하는대신 true false 해야함
for (int i = 0; i < save_pos.size(); i++) {
int x = save_pos[i].x, y = save_pos[i].y;
stx = x, sty = y;
map[x][y] = ai_color;
search(0, user_color);
map[x][y] = 0;
}
}
map[ansx][ansy] = ai_color;
cout << "ai input ( " << ansx << " , " << ansy << " )" << endl;
}
void Print() {
cout << "x|y";
for (int j = 0; j < n; j++) {
cout.width(3);
cout << j;
}
cout << endl;
for (int i = 0; i < n; i++) {
cout.width(3);
cout << i;
for (int j = 0; j < n; j++) {
cout.width(3);
if(map[i][j])
cout << map[i][j];
else cout << "";
}
cout << endl;
}
}
void input(int type) {
int x, y;
while (true) {
cout << "Waht is your next position (x,y)?: ";
cin >> x >> y;
if (x >= 0 && y >= 0 && x < n&&y < n&&map[x][y] == 0) {
map[x][y] = type;
break;
}
else {
cout << "try other position" << endl;
}
}
cout << endl;
}
bool check(int color) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == color) {
for (int d = 0; d < 8; d++) {
int cnt = 1;
while (true) {
int nx = i + (cnt*dir[d][0]), ny = j + (cnt*dir[d][1]);
if (nx < 0 || ny < 0 || nx >= n || ny >= n)break;
if (map[nx][ny] != color)break;
cnt++;
}
if (cnt == 5)return true;
}
}
}
}
return false;
}
void game_type(int type) {
if (type == 1) {
cout << "your color is black(1). please input 1! " << endl << endl;
int turn = 0;
bool victory;
while (true) {
cout << "Your turn" << endl;
Print();
input(type);
tf = check(1);
if (tf) {
Print();
cout << " you win!" << endl;
return;
}
//AI turn
cout << "AI turn" << endl;
Print();
Sleep(1000);
AI(1, 2);
tf = check(2);
if (tf) {
Print();
cout << " AI win!" << endl;
return;
}
turn++;
}
}
else if (type == 2) {
cout << "your color is white(2). please input 2! " << endl << endl;
int turn = 0;
while (true) {
//AI turn
cout << "AI turn" << endl;
Print();
Sleep(1000);
if (turn == 0) {
map[9][9] = 1;
}
else AI(2, 1);
tf = check(1);
if (tf) {
Print();
cout << " AI win!" << endl;
return;
}
cout << "Your turn" << endl;
Print();
input(type);
tf = check(2);
if (tf) {
Print();
cout << " you win!" << endl;
return;
}
turn++;
}
}
else if (type == 3) {
cout << "show AI match! " << endl;
int turn = 0;
while (true) {
//AI turn
cout << "AI_1 turn" << endl;
Print();
Sleep(2000);
if (turn == 0) {
map[9][9] = 1;
}
else AI(2, 1);
tf = check(1);
if (tf) {
Print();
cout << " AI_1 win!" << endl;
return;
}
//AI turn
cout << "AI_2 turn" << endl;
Print();
Sleep(2000);
AI(1, 2);
tf = check(2);
if (tf) {
Print();
cout << " AI_2 win!" << endl;
return;
}
turn++;
}
}
}
int main() {
init();//가중치 설정
cout << "well come, Five dols!" << endl;
cout << "1: play black, 2: play white, 3: show AI's match" << endl;
int start;
cin >> start;
game_type(start);
}'코딩테스트 > 코딩테스트 알고리즘' 카테고리의 다른 글
| 코딩테스트 문제 풀이 전, 시/공간 복잡도 이해하기 (0) | 2023.09.05 |
|---|---|
| [C] 이진 탐색 (Binary Search) 알고리즘 개념과 예제 (0) | 2023.08.23 |
| 투 포인터 알고리즘(Two Pointers Algorithm) (0) | 2023.08.13 |
| 달팽이 방향으로 배열 순회 (0) | 2022.11.24 |
| 스위핑 알고리즘 (Sweeping algorithm) (0) | 2022.11.23 |