C#으로 오목 AI 구현해보기 #1

들어가며

평소 스프링 공부만 주구장창 하던 나는 매일 똑같은 공부에 슬럼프가 제대로 왔고 2주간 멍하게 있다가 뭐라도 해봐야지하고 사이드 프로젝트로 오목 프로그램을 만들게되었다.

---

사용할 알고리즘

이번 오목 게임트리에 적용할 알고리즘은 Minimax와 Alpha-beta pruning 알고리즘이다.

먼저 Minimax 알고리즘은 바둑, 체스와 같은 게임에서 상대의 수를 예측하고 최선의 수를 두기 위한 알고리즘이다. 상대 또한 자신에게 유리한 수를 둘 것이므로 상대에게 최선이 되는 수 또한 계산하기 위해 Minimax 알고리즘을 사용한다.

이 때, 수를 둘 수 있는 경우의 수는 기하급수적으로 커지는데 이러한 문제를 해결하기 위해 Alpha-beta pruning 알고리즘을 적용한다.

예를 들어 어떤 경우가 자신에게 유리한 것이 확정되어 더이상의 탐색이 불필요할 때(상대가 그 것을 택하지 않을 확률이 높은 경우) 가지치기를 하여 시간복잡도를 단축시키는 목적으로 사용된다. (알파-베타 가지치기 에서 alpha-cut 하는 과정을 볼 수 있다)

---

설계 방향

일단 오목판 GUI적 설계나 이벤트 처리를 간단히 하기위해 C# Winform 어플리케이션을 사용하였다.

현재까지 19x19 오목판, 마우스 이벤트 처리, 좌표 설정, 오목 판정 등을 마친 상태이다.

오목 판정 코드는 다음과 같다.

        public Boolean isCorrectRange(int x, int y)
        {
            if (x >= 0 && y >= 0 && x < 19 && y < 19) return true;
            return false;
        }

        public Boolean fourWaySearch(int x, int y, Boolean flag)
        {
            STONE currentStone = flag ? STONE.WHITE : STONE.BLACK;

            for (int i = 0; i < 4; i++)
            {
                int nx = x;
                int ny = y;
                Boolean s = true;

                for(int k = 0; k < 4; k++)
                {
                    nx += omok_dirX[i];
                    ny += omok_dirY[i];

                    Console.WriteLine(nx + " " + ny);
            
                    if (!isCorrectRange(nx, ny) || currentStone != board[nx, ny])
                    {
                        s = false;
                    }
                }

                if (s == true)
                {
                    return true;
                }
            }
            return false;
        }

        public Boolean isOmok(Boolean flag)
        {
            STONE currentStone = flag ? STONE.WHITE : STONE.BLACK;
            for (int i = 0; i < 19; i++)
            {
                for(int k = 0; k < 19; k++)
                {
                    if(currentStone == board[i, k])
                    {
                        if(fourWaySearch(i, k, flag))
                        {
                            MessageBox.Show(currentStone + "이 이겼습니다.");
                            return true;
                        }
                    }
                }
            }

            return false;
        }

0, 0부터 시작해서 ↗,→,↘, ↓ 방향으로만 탐색하여 연속되는 돌이 있는지 완전탐색을 한다.

보드판을 수열로 나타내어 비트마스킹을 적용해볼까라는 생각도 해보았지만 탐색 공간이 그리 크지 않아 성능에 별 차이가 없을 것같아 그대로 진행하였다.

---

여기까진 스무스하게 진행되었지만 이제부터 시작이라 할 수 있다.

일단 가장 큰 문제는 Minimax 알고리즘의 단말 노드에 적용할 상태 값을 구하는 함수를 구현하는 것이다. (구글링을 해도 통 자료가 나오지 않는다)

또한 상태 함수를 구현하기 위해서는 현재 보드판에 아군, 적군의 열린1, 닫힌1, 한칸 띄워진 2, ..., 한 쪽 열린 삼사, 닫힌 삼사, 한 쪽만 열린 삼사 등등 패턴들을 하나하나 분석하고 그에 따른 가중치를 부여할 필요가 있는데 이런 패턴들을 어떻게 파악할지도 아직 감이 잡히질 않는다.

처음에는 비트마스킹을 생각해보았지만 패턴의 경우의 수가 너무 많아 코드가 진흙탕될 것같아 바로 접었고 완전 탐색 또한 생각하면 할 수록 경우의 수가 끝없이 나와 상당히 골치아플 것으로 보인다.

일단 이 부분에 대해서는 다음주에 계속해서 연구해볼 생각이다.