오목 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 함수를 조금 손 봐야한다.
물론 미래의 내가 할거다.