[Gomoku] Day 3. CPU 추가

 

1. 시작에 앞서

원래는 Minimax 알고리즘과 Alpha-Beta Pruning과 같은 알고리즘을 사용해보고 싶었지만,

Toy Project라는 점과 더불어서 목표 기간 내 완성하기엔 Minimax 알고리즘을 사용하면 길어질 것 같아서 참고 논문의 가중치 합 관련 로직을 참고하여 작성하였다.

---

2. 수정 반영 사항

1) GameController 형태 분리

private readonly Board board = new Board();
private readonly BoardRenderer renderer = new BoardRenderer();
private readonly GomokuRule rule = new GomokuRule();

private readonly IPlayer blackPlayer;
private readonly IPlayer whitePlayer;

private Stone turn = Stone.Black;

public GameController()
{
	blackPlayer = new UserPlayer(Stone.Black, renderer);
	whitePlayer = new UserPlayer(Stone.White, renderer);
}

- 기존에는 GameController가 유저 정보를 직접 생성하게 만들었다.

- 하지만, 이제 게임 모드에 따라서 메뉴에서 유저 정보를 생성해 처리하도록 분리하였다.

public GameController(IPlayer blackPlayer, IPlayer whitePlayer, BoardRenderer renderer) // 생성자를 통해 메뉴로부터 플레이어 정보 생성
{
       this.blackPlayer = blackPlayer;
       this.whitePlayer = whitePlayer;
       this.renderer = renderer;
}

private void PlayerVsPlayer()
{
	BoardRenderer renderer = new BoardRenderer();

	IPlayer blackPlayer = new UserPlayer(Stone.Black, renderer);
	IPlayer whitePlayer = new UserPlayer(Stone.White, renderer);

	GameController gameController = new GameController(blackPlayer, whitePlayer, renderer);
	gameController.Run();
		
}

- 위와 같은 방식으로 메뉴에서 직접 부르는 방식으로 처리하였다.

 

2) 방어 코드 추가

public bool IsEmpty(Position pos) // 빈칸 체크
{
    return IsInside(pos) && cells[pos.Row, pos.Col] == Stone.Empty;
}

public Stone GetStone(Position pos) // 돌 정보 얻어오기
{
    if (!IsInside(pos))
        throw new ArgumentOutOfRangeException(nameof(pos), "보드 범위를 벗어난 위치입니다.");

    return cells[pos.Row, pos.Col];
}

public bool TryPlaceStone(Position pos, Stone stone) // 실제 돌 놓기 
{
    if (!IsInside(pos)) return false;

    if (!IsEmpty(pos)) return false;

    cells[pos.Row, pos.Col] = stone;
    return true;
}

public void SetStone(Position pos, Stone stone) // 룰 체크, 시뮬레이션 등등에 활용할 용도의 돌 놓기
{
    if (!IsInside(pos))
        throw new ArgumentOutOfRangeException(nameof(pos), "보드 범위를 벗어난 위치입니다.");

    cells[pos.Row, pos.Col] = stone;
}

- 기존 IsEmpty(), GetStone(), SetStone(), TryPlaceStone()은 입력 값이 어느정도 ‘안전함’ 상태를 전제로 처리하였다.

- 코드가 다소 길어질 여지는 있었지만 안전하지 않음을 전제하여 방어 코드를 추가하였다.

 

3) CPU(AI) Player 추가

- CPU(AI)는 다음과 같은 근거로 움직인다.

① 빈 보드 기준 AI는 중앙을 선호하는 것으로 처리했다.

② 모든 위치를 돌며, 순회하되 돌 놓인 곳과 금수 위치는 제외한다.

③ 내 점수(정확히는 AI 본인의 점수)와 상대 점수(사람)의 점수를 평가하여 합산한다.

④ AI가 두면 좋은 자리이면서, 상대가 두면 위험한 자리는 전략적으로 중요한 자리가 된다.

⑤ 합산 점수가 가장 높은 자리에 AI가 돌을 둔다.

namespace GomokuNewVersion
{
    internal class AIPlayer : IPlayer
    {
        private readonly GomokuRule rule = new GomokuRule();
        private readonly MoveEvaluator evaluator = new MoveEvaluator();
        public Stone Stone { get; }

        public AIPlayer(Stone stone)
        {
            Stone = stone;
        }

        public Position SelectMove(Board board) // AI가 둘 위치 선택
        {
            Position bestMove = new Position(Board.Size / 2, Board.Size / 2); // 빈 보드에서 중앙 선택
            int bestScore = int.MinValue;

            // 상대 돌
            Stone opponent = GetOpponent(Stone);

            // 모든 위치 순회하며 후보 검사
            for (int row = 0; row < Board.Size; row++)
            {
                for (int col = 0; col < Board.Size; col++)
                {
                    Position pos = new Position(row, col);

                    // 돌 놓인 곳 제외
                    if (!board.IsEmpty(pos))
                        continue;

                    // 33 금수 위치 후보 에서 제외
                    if (rule.IsDoubleThree(board, pos, Stone))
                        continue;

                    // AI의 공격(평가) 점수
                    int score = evaluator.Evaluate(board, pos, Stone);

                    // 상대의 공격(평가) 점수 -> AI 입장에서 방어 해야할 점수
                    int opponentScore = evaluator.Evaluate(board, pos, opponent);

                    int totalScore = score + opponentScore;

                    // 가장 높은 점수를 가진 위치에 AI가 둔다.
                    if (totalScore > bestScore)
                    {
                        bestScore = totalScore;
                        bestMove = pos;
                    }
                }
            }

            // 최종적인 위치가 AI가 둘 위치
            return bestMove;
        }
        private Stone GetOpponent(Stone stone)
        {
            return stone == Stone.Black ? Stone.White : Stone.Black;
        }
    }
}

※ 이 방식의 한계점은 단순 랜덤 AI 보다는 좋지만, 몇 수 뒤의 가능성 등에 대한 평가는 배제되어 있고, 일부 복잡한 패턴에는 약하며 공격 우선 / 방어 우선과 같은 판단은 불명확하다는 점이 아쉽다. (즉, 깊은 계산에 대해 미흡하다.)

 

4) 가중치 평가 로직

namespace GomokuNewVersion
{
    internal class MoveEvaluator
    {
        private readonly GomokuRule rule = new GomokuRule();

        // pos에 돌을 놓았음을 가정하여 가치를 점수로 평가.
        public int Evaluate(Board board, Position pos, Stone stone) 
        {
            int totalScore = 0;

            
            board.SetStone(pos, stone);

            try
            {
                if (rule.IsWin(board, pos, stone))
                    return 100000;

                // 4방향 검사
                for (int i = 0; i < 4; i++)
                {
                    int dRow = GomokuDirections.GetRow(i);
                    int dCol = GomokuDirections.GetCol(i);

                    // 정방향, 역방향으로 이어진 돌 개수 계산
                    int forward = rule.CountStone(board, pos, dRow, dCol, stone);
                    int backward = rule.CountStone(board, pos, -dRow, -dCol, stone);

                    // 현재 위치의 돌 1개를 포함한 총 연결 개수.
                    int count = 1 + forward + backward;

                    // 양끝 중 비어있는 끝의 개수 
                    int openEnds = rule.CountOpenEnds(board, pos, dRow, dCol, forward, backward);

                    totalScore += GetPatternScore(count, openEnds);
                }
            }
            finally
            {
                // 평가용 임시 배치돌은 반드시 제거한다.
                board.SetStone(pos, Stone.Empty);
            }

            return totalScore;
        }

        // 참고 논문에서 사용한 패턴 기반 가중치 값을 참고
        private int GetPatternScore(int count, int openEnds) // 돌 개수와 열린 끝 개수를 기준으로 점수 반환
        {
            if (count >= 5) return 100000;

            if (count == 4) 
                return openEnds >= 1 ? 5000 : 0;

            if (count == 3)
                return openEnds == 2 ? 600 : openEnds == 1 ? 57 : 0;

            if (count == 2)
                return openEnds == 2 ? 55 : openEnds == 1 ? 35 : 30;

            if (count == 1)
                return openEnds == 2 ? 13 : openEnds == 1 ? 7 : 5;

            return 0;
        }

    }
}

- 돌을 임시로 놓는 부분에 예외가 발생할 것을 우려하여, 평가용 임시 배치돌은 반드시 제거하도록 finally 로 감싸놨다.

- 논문에서 사용한 패턴 기반 가중치를 참고하였고, 조건문이 복잡해질 것을 우려해 3항 연산자로 표현하였다.

---

3. 플레이 스크린샷

 

---

4. 플레이 영상

https://youtu.be/E-0YAavmnCc?si=YvReKMEj37PqAWia

---

- 내일 Flow Chart랑 순서도를 올리고 토이 프로젝트를 마무리 해보려 한다.