오목 AI를 만들어보자! [2편] - 오목 알고리즘 (미완)

1편 쓰고 당일에 또 2편을 쓰기 시작한 감자(?)다.

 

결국에 우리가 할 것은 적대적 탐색을 통한 오목 AI기 때문에, 금수 자리 판독, 승패 판정 등을 최적화 해주어야 한다. 그러나, 최적화 따위는 나중에 생각하고 일단 알고리즘을 만들어보자.

 

아 그리고 어떤 분이 주석좀 달아달라고 해서, 코드에 주석을 좀 추가해봤다.

 

---

1. 승패 판정

승패 판정이 제일 간단하기 때문에 먼저 해보겠다.

승패는 가장 마지막에 둔 돌에 의해서만 판단 되기 때문에 그 돌 기준으로만 판단해주면 된다.

class Engine:

    DIRECTIONS = ((1, 0), (1, 1), (0, 1), (-1, 1))
    COLOR_MAP = {-1:"Black", 1:"White"}

    def _check_sequence_one_way(
            plate: list[list[int]],
            color: int,
            pos: tuple[int, int],
            vector: tuple[int, int],
            count:int = 1,
            way:int = 1,
            ) -> tuple[int, int]:
        '''
        Recursively counts the number of consecutive stones of the same color in one direction.

        Parameters:
         * plate: 15x15 matrix representing the game board
         * color: int: -1 for black; 1 for white
         * pos: tuple[int, int]: (x, y) coordinates of the starting stone
         * vector: tuple[int, int]: (x, y) direction vector
         * count: int = 1: current count of consecutive stones
         * way: int: direction multiplier (1 for forward, -1 for backward)

        Returns:
         int: The count of consecutive stones in the specified direction
        '''

        newX, newY = pos[0] + vector[0] * way, pos[1] + vector[1] * way  # Calculate new position

        if not (0 <= newX < 15 and 0 <= newY < 15):  # Check if the new position is within bounds
            return count

        next = plate[newY][newX]
        
        if (next != color): return count # Stop counting if a different color is encountered

        return Engine._check_sequence_one_way(plate, color, (newX, newY), vector, count+1, way)
    
    def _check_sequence(
            plate: list[list[int]],
            color: int,
            pos: tuple[int, int],
            vector: tuple[int, int],
            ) -> tuple[int, int]:
        '''
        Counts the total number of consecutive stones in both directions of the given vector.

        Parameters:
         * plate: 15x15 matrix representing the game board
         * color: int: -1 for black; 1 for white
         * pos: tuple[int, int]: (x, y) coordinates of the starting stone
         * vector: tuple[int, int]: (x, y) direction vector

        Returns:
         int: The total count of consecutive stones in both directions
        '''

        sequence = Engine._check_sequence_one_way(plate, color, pos, vector, 1, 1)  # Count forward
        sequence += Engine._check_sequence_one_way(plate, color, pos, vector, 0, -1)  # Count backward

        return sequence

    def check_win(
            plate:list[list[int]],
            last:tuple[int, int]
            ) -> bool:
        
        '''
        Evaluates whether the last move resulted in a win.

        Parameters:
         * plate: 15x15 matrix representing the game board
         * last: tuple[int, int]: (x, y) coordinates of the last-placed stone

        Returns:
         bool: True if the last move resulted in a win, False otherwise
        '''

        assert isinstance(plate, (tuple, list)), "Invalid 'plate' type. Must be a tuple or list."
        assert isinstance(last, (tuple, list)), "Invalid 'last' type. Must be a tuple or list."
        assert len(last) == 2, "Invalid length of 'last', must be (x, y)."
        
        turn: int = plate[last[1]][last[0]]  # Determine the color of the last-placed stone

        assert turn != 0, f"Position {last} is not occupied."

        maximum = max([  # Calculate the maximum sequence length for each direction
            Engine._check_sequence(plate, turn, last, vec)  # Evaluate sequence length for the given direction
            for vec in Engine.DIRECTIONS
        ])

        # In Renju, Black cannot have a sequence longer than 5.
        # If the sequence length is 5 or greater, return True.
        if (maximum >= 5): return True

        return False

 

원리는 간단하다. 마지막으로 둔 돌의 위치 기준으로 연속된 돌의 개수가 몇개인지 측정한다.

알고리즘 설명

 

이때, 연속된 돌은 반대 방향으로도 계산해야하기 때문에, 정방향 개수와 역방향 개수를 더해주어야 한다. 그래서 _check_sequence 함수에서 _check_sequence_one_way를 정방향(1) 역방향(-1)로 계산해서 더해준다.

 

개수를 셀 때는 재귀 함수 형태로 해서 만들면 편하다. 코드에서 _check_sequence_one_way 가 재귀함수로 작동해서 같은 색이 아닐 때, 혹은 판이 끝났을 때 까지 돌 개수를 센다.

 

렌주룰에 따라 흑은 장목이 안되기 때문에 5목이 되었을 때에만, 백은 5개 이상이 되었을 때 True를 반환해야 하지만,

렌주룰에 따라 애초에 흑은 장목이 나올 수 없기에, 그냥 5이상이 되면 True를 반환한다.

 

---

2. 금수 판정

금수판정은 위에서 만든 _check_sequence 함수를 활용해서 만들 수 있다. 다만, 문제는 승패 판정 때와는 달리, 띤삼과 같은 것도 3개로 측정해야 하며, 닫힌 3인지 열린 3인지와 같은 것도 따로 생각해줘야한다.

 

일단  _check_sequence 함수를 이용해 간단한 금수 판정 함수를 만들어준다.

class Engine:
    ...
    def check_valid_place(
            plate: list[list[int]],
            color: int,
            pos: tuple[int, int],
            ) -> bool:
        
        '''
        Determines if a move is invalid based on Renju rules.

        Parameters:
         * plate: 15x15 matrix representing the game board
         * color: int: -1 for black; 1 for white
         * pos: tuple[int, int]: (x, y) coordinates of the move

        Returns:
         bool: True if the move is valid, False otherwise
        '''

        if (plate[pos[1]][pos[0]] != 0): return False # Already occupied
        if (color == 1): return True # No restrictions for White in Renju

        sequences = [
            Engine._check_sequence(plate, color, pos, vec) # Evaluate sequence length for the given direction
            for vec in Engine.DIRECTIONS
        ]
        
        CountThree = sequences.count(3) # Count of three-length-sequence
        CountFour = sequences.count(4) # Count of four-length-sequence

        if (CountThree + CountFour >= 2): return False

        return True

 

아까 만든 함수를 이용한 금수 판정 함수 코드이다. 승패 판정과 동일하게 각 방향별 sequence 수를 계산한 뒤, 3의 개수와 4의 개수를 따로 세준다. 렌주룰에서는 흑이 3-3, 4-4, 4-3-3, 4-4-3이 금지 된다. 그래서 그냥 3의 개수와 4의 개수가 더해서 2가 넘어가면 False를 반환하게 하면 된다.

 

그리고 아까 말한 띤삼과 열린/닫힌 판정을 해야하므로 _check_sequence_one_way 함수를 조금 손 봐야한다.

물론 미래의 내가 할거다.