들어가며
이제 핵심적인 구현은 마쳤고, 오목을 플레이 해보면 나 자신과 대국하였을 때 기준으로 50% 정도의 승률이 보인다. 구현하면서 핵심 코드인 부분과 몇 가지 아쉬운 부분을 적어볼려 한다.
구현한 기능
- PVP, AI 모드 선택
- AI 모드일 시 흑 / 백 선택 가능
핵심 코드
- alphaBetaPruning() - 가장 핵심이 되는 코드라 할 수 있다.
public int alphabetaPruning(int depth, int alpha, int beta)
{
if (depth == 4)
{
//Console.WriteLine(getStatus());
return getStatus();
}
if (depth % 2 == 0) //AI 차례
{
int v = int.MinValue; // AI 입장에선 최댓값을 구하기 위해 -INF 선언
Boolean pruning = false;
for (int x = 0; x < 19; x++) //for each child of node
{
for (int y = 0; y < 19; y++)
{
STONE curStone = board[x, y];
Boolean flag = false;
//현재 좌표에 돌이 없을 시 주변에 돌이 있을 시 돌을 놓음
if (curStone == STONE.NONE)
{
int nx, ny;
for (int k = 0; k < 8; k++)
{
nx = x + dirX[k];
ny = y + dirY[k];
if (!isCorrectRange(nx, ny)) continue;
if (board[nx, ny] != STONE.NONE)
{
flag = true;
break;
}
}
if (flag)
{
calCnt++;
board[x, y] = STONE.WHITE;
int temp = alphabetaPruning(depth + 1, alpha, beta);
if (v < temp)
{
v = temp;
if (depth == 0)
{
aiX = x;
aiY = y;
}
}
board[x, y] = STONE.NONE;
alpha = Math.Max(alpha, v);
// 가지치기
if (beta <= alpha)
{
pruning = true;
break;
}
}
}
if (pruning) break;
}
if (pruning) break;
}
return v;
}
else //Player 차례
{
int v = int.MaxValue;
Boolean pruning = false;
for (int x = 0; x < 19; x++) //for each child of node
{
for (int y = 0; y < 19; y++)
{
STONE curStone = board[x, y];
Boolean flag = false;
//현재 좌표에 돌이 없을 시 주변에 돌이 있을 시 돌을 놓음
if (curStone == STONE.NONE)
{
int nx, ny;
for (int k = 0; k < 8; k++)
{
nx = x + dirX[k];
ny = y + dirY[k];
if (!isCorrectRange(nx, ny)) continue;
if (board[nx, ny] != STONE.NONE)
{
flag = true;
break;
}
}
if (flag)
{
board[x, y] = STONE.BLACK;
v = Math.Min(v, alphabetaPruning(depth + 1, alpha, beta));
board[x, y] = STONE.NONE;
beta = Math.Min(beta, v);
if (beta <= alpha)
{
pruning = true; break;
}
}
}
if (pruning) break;
}
if (pruning) break;
}
return v;
}
}
(위키백과에 있는 의사코드를 참조하였다)
위 코드를 이해할려면 알파-베타 가지치기 알고리즘을 이해해야만 한다.
(해당 영상에서 굉장히 쉽게 가르켜주신다 Step by Step: Alpha Beta Pruning)
간단한 로직을 설명하자면 depth가 4로 설정되어있는데 이는 앞으로 4수까지의 모든 경우의 수를 계산하여 그 중 최적의 수를 찾겠다는 의미이다.
그리고 19X19 바둑판을 완전 탐색해가며 만약 현재 위치에 돌이 없다?
그럼 8방향 (동, 서, 남, 북, 북서, 북동, 남서, 남동)을 탐색하여 돌이 있는지 확인하고 아래와 같은 조건문을 타게된다.
if(주변에 돌이 있다면 && 백차례) {
현재 위치에 백돌을 놓는다
}
else if(주변에 돌이 있다면 && 흑차례){
현재 위치에 흑돌을 놓는다
}
else{
continue;
}그리고 alphaBetapruning(depth+1, alpha, Beta) 재귀함수를 호출하고 그 다음줄에 다시 현재 위치에 돌을 제거한다.
그리고 함수 진입할 때 depth == 4이다?
그럼 현재 보드판을 기준으로 가중치를 계산하여 반환시키면 된다.
즉, 현재 위치에 돌이 없고 주변에 돌이 있다면 재귀를 호출하는 4수를 뽑는 조합 알고리즘이라 생각하면 된다.
(본인이 설명을 잘 못해 이해가 잘 안될 수도 있다..)
- getStatus() - alphaBetaPruning() 함수에서 터미널 노드의 가중치(상태 값)을 구하는 함수이다.
코드가 너무 길어 로직만 이해할 수 있도록 함축시켰다.
for (int x = 0; x < 19; x++)
{
for (int y = 0; y < 19; y++)
{
if (board[x, y] == STONE.NONE) continue; //현재 위치에 돌이 없으면 무시
for(8방향 탐색){
if (!isFitFive(x, y, k)) continue; //만약 양방향으로 오목이 들어가지 않는다면 무시
---
여기 부분에서 연결된 돌의 상태를 확인함
1. 돌의 개수 확인
2. 한 칸 띄워져 있는지
3. 한 쪽이 막혀 있는지
---
그리고 각 상태에 따른 가중치 계산을 하게됨
(한 부분만 가져옴)
//수가 2개일 때
if (stoneCnt == 2)
{
//한 쪽이 막혔을 때
if (isOneSideBlock && !isOneSpace)
{
sum += 50;
}
//한 쪽이 막히고 한 칸 띄워졌을 때
else if (isOneSideBlock && isOneSpace)
{
sum += 30;
}
//안막혔을 때
else if (!isOneSideBlock && !isOneSpace)
{
sum += 70;
}
//안막히고 한 칸 띄워졌을 때
else
{
sum += 50;
}
...
그리고 마지막에 현재 돌이 AI 돌이면 AI 점수에 더하고,
유저가 둔 돌이면 유저 점수에 더함
}
}
}
이제 19X19 보드판의 가중치를 모두 구했으므로 AI 점수에서 유저 점수를 뺀 값을 반환함
(값이 크다면 AI가 유리, 값이 작다면 유저가 유리하므로 Minimax 알고리즘에 적용시킬 수 있음)
}전체적인 로직은 현재 주어진 19X19 보드판을 돌 하나하나를 완전탐색해가며 각각의 가중치를 구하는 작업이다.
일단 코드에 나름 이해하기 쉽게 적어봤는데 보충해서 설명하자면 연결된 돌의 상태를 확인할 때는 반드시 양방향으로 탐색해야된다.
그리고 처음에 오목이 들어갈 수 있는지부터 확인했는데 그 이유는 해당하는 자리에 오목이 들어갈 수 없다면 점수 계산이 의미가 없기 때문이다.
그리고 돌의 상태를 확인할 때는 본인도 현재 한 눈에 알아보기 힘든 조건문과 flag 변수를 사용해서 어찌어찌 구현을 하여 나중 가중치를 구하기 쉽도록 3가지 변수에 할당하였다.
마지막으로 가장 중요한 각 상태에 따른 적절한 가중치를 더하는 작업이다.
사실 처음에 적절한 가중치를 구하기 너무 막막해 구글링을 하여 오목 관련 논문을 참조했지만 공격과 방어가 처음에는 너무 생뚱맞아 수정과 보완을 거듭해(?) 어느정도 두는 단계까지 구현하였다.
일단 핵심적인 구현 부분은 여기까지인 것 같다
한계와 앞으로 보완할 점
사실 보완할 점이 너무 많지만 몇 가지만 적어보겠다..
- 시간이 너무 걸린다. (depth 4이상일 경우)
게임이 진행될 수록 MiniMax 트리의 상태공간이 급격히 커지면서 계산할 말단 노드의 개수가 너무 많아진다는 것이다.
몰론 이를 해결하기 위해 Alpha-beta-pruning 알고리즘을 사용하지만 어차피 결국은 terminal state까지 도달해야하며 AI에게 유리한 상황이 오지않는다면 결국은 가지치기도 못하고 완전탐색을 하게 된다.
이 부분에 있어 해결 방안을 몇 가지 고민해봤었는데 다음과 같다.
- 메모이제이션
게임을 진행할 수록 깊이 4까지의 수를 구하는 말단 노드는 굉장히 많아진다.
(1수만 있더라도 8가지의 말단 노드가 생성된다.)
하지만 게임이 진행되고 수가 많아질 수록 보드판의 상태에 따른 중복 계산도 덩달아 많아진다.
그래서 이 보드판에 대한 상태값을 캐시 배열 또는 맵으로 나타낼 수 없을까 생각해봤지만 교묘하게 상태 값이 계속 바뀌어 도무지 중복 처리를 할 수 있는 방법이 떠오르지 않았다...
- Alpha-Beta-Pruning에서 말단 노드 정렬(?)
이 방법은 구체적으로는 생각은 안해봤지만 알파-베타 가지치기를 최대한 빠르게 적용시킬 수 없을까해서 생각한 아이디어다.
- 유저가 수를 둘 동안 미리 계산(?)
아직 가능할지도 모르겠고 어디서부터 손대야할지 모르겠어 생각만 해둔 상태이다.
그리고 유튜브를 찾던 도중 ABP에 대한 성능 이슈를 다룬 영상이 있어 정리해보았다.
ABP 성능 이슈
- 창의적인 수 제한
alphaBetaPruning() 함수에서 4수에 대한 조합을 계산할 때 주변에 돌이 있다면 현재 위치에 돌을 두는 방식으로 조합을 계산한다.
그렇지만 실제 오목을 둘 때는 꼭 주변돌에 붙어서 둘 필요가 없으며 오히려 떨어진 곳에서 더욱 좋은 수가 생기는 경우 또한 있기 마련이다.
그렇다고 아무래도 시간이 오래걸리는 와중에 19X19 보드판에서 4수 조합의 경우의 수를 모두 계산하는 것은 미친 짓이라 할 수 있다.
이 부분에 있어서는 우선적으로 시간 단축에 성공한다면 제대로 고민해볼 생각이다.
- 가중치를 구하기 위한 패턴이 제한적이다.
getSutats() 함수에서 현재 돌의 패턴을 구하기 위한 변수는 3가지이다.
1. 돌의 개수 확인하는 변수
2. 돌 한 쪽이 막혔는지 확인하는 변수
3. 돌이 한 칸 띄워져있는지 확인하는 변수
즉, 현재 돌의 한 줄에 있는 패턴만 읽을 수 있다.
하지만 좀 더 정확한 가중치 계산을 위해 3-4라던지 2-3, 4-4 등 두 줄 이상의 패턴으로 구성된 수 또한 읽을 수 있다면 더욱 효과적인 방어와 공격이 가능해진다.
사실 위 3가지만 어느정도 보완이 된다면 실제 잘하는 사람과 대국하여도 어느정도 비견되지 않을까(?) 생각한다.
lleell6@naver.com으로 연락 부탁드립니다