서론: Hare and Hounds
처음 들으면 사실 생소한 게임이다. 본인도 닌텐도 스위치에 있는 Clubhouse Games™: 51 Worldwide Classics라는 게임에서 처음 접한 미니 게임이다. 단순한 보드게임인 만큼 트리 탐색 알고리즘을 통해서 컴퓨터 플레이어를 충분히 만들 수 있을 것이라 생객해서 alpha-beta pruning을 이용한 python CLI 게임을 간단히 만들어 보았다. 무슨 게임인지 빠르게 체험해보고 싶으면 다른 사람이 구현한 사이트를 참고해보아도 좋을 것 같다.
게임 규칙
말은 사냥개(hound)와 토끼(hare) 총 2종류가 존재하며, 각각의 승리 조건이 존재한다.
- 사냥개는 토끼를 움직일 수 없도록 가두면 승리
- 토끼는 맨 왼쪽 끝에 도달하거나 일정 턴수를 넘기면 승리
턴수 제한은 사냥개가 시작 지점에서 비키지 않으면 토끼가 절대 승리하지 못하기 때문에 존재하는 것 같다. 말을 움직이는 방법은 다음과 같다.
- 사냥개 선공
- 말은 한 번에 한 칸씩만 움직일 수 있음
- 이동은 흰색 선을 따라서만 가능
- 토끼는 모든 방향으로 이동 가능하지만, 사냥개는 뒤(왼쪽) 방향으로 이동 불가
코드
휴리스틱 함수
이 코드는 Hare and Hounds 게임에서 사용될 휴리스틱 함수(heuristic)를 구현한 부분이다. 휴리스틱 함수는 게임 상태를 평가하여 AI가 최적의 수를 선택하는 데 도움을 주는 함수이다. 휴리스틱 함수는 현재 말판 상태만으로 상황을 점수화 시켜서 판단할 수 있어야 하는데, 어느 상태가 사냥개 혹은 토끼한테 확실히 유리한 상황인지를 직접 플레이하면서 휴리스틱 함수의 요소와 각각의 가중치를 설정하였다. 휴리스틱 함수에 사용된 주요 요소들은 다음과 같다:
-
토끼 왼쪽에 늑대가 있는 경우: 토끼가 늑대의 왼쪽에 있을수록 높은 점수를 부여,
-
맨 오른쪽 구석에 들어갈 시 페널티: 늑대가 맨 오른쪽에 들어가는 수는 무조건 안 좋은 수, 승리할 수 있는 방법이 사라짐.
-
공간 점수:
3-1. 늑대로 토끼와 도착지점 사이를 분리시킬 경우 점수
3-2. 토끼 주변에 갈수 있는 영역의 수에 따라서 점수 제공, 가까울수록 높은 가중치의 점수
이렇게 구현된 휴리스틱 함수를 Alpha-Beta 알고리즘과 함께 사용하여 AI가 게임을 플레이하고 최적의 수를 선택하도록 할 수 있다. 완벽한 휴리스틱이라고는 자신할 수 없지만, 위에 링크한 사이트의 HARD 인공지능과 대결 시키면 거의 최적의 수를 제공한다고 생각할 정도의 성능을 보여준다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
def heuristic(state):
total_h = 0
# h func for hound
# minus score for hare
# 1. 토끼 왼쪽에 늑대 있을 수록 점수
cnt = 0
for x in range(3):
for y in range(5):
if state[x, y] == 'R':
hare = (x, y)
hounds = []
for x in range(3):
for y in range(5):
if state[x, y] == 'H':
hounds.append((x, y))
if hare[1] > hounds[-1][1]:
cnt += 1
total_h += 500 * cnt
# 2. 맨 오른쪽 구석에 들어갈 시 페널티
if state[1, 4] == 'H':
total_h += -5000
# 3. 늑대로 닫힌 공간을 만들 경우 점수, 공간이 좁아질 수록 점수 높아짐
# BFS
visited = [[False] * 5 for _ in range(3)]
visited[0][0] = True
visited[0][-1] = True
visited[-1][0] = True
visited[-1][-1] = True
distance = [[0] * 5 for _ in range(3)]
for x, y in hounds:
visited[x][y] = True
q = deque([hare])
while q:
current_node = q.popleft()
x, y = current_node
for next_x, next_y in connections[x][y]:
if not visited[next_x][next_y]:
visited[next_x][next_y] = True
distance[next_x][next_y] = distance[x][y] + 1
q.append((next_x, next_y))
cnt = 0
for x in range(3):
for y in range(5):
if not visited[x][y]:
cnt += 1
# 3-1. 토끼가 1,0에 도달하지 못하는 경우, 즉 늑대에 의해서 둘러 싸인 경우
if not visited[1][0]:
total_h += 5000
# 3-2. 토끼 기준 주변 공간 점수, 가까운 영역일수록 높은 점수(늑대 기준 음수)
distance_weight = [0, 10, 5, 2, 1, 1, 1, 1]
for x in range(3):
for y in range(5):
total_h += -100 * distance_weight[distance[x][y]]
return total_h