프로젝트 개요
이 프로젝트는 React와 TypeScript를 사용하여 만든 오셀로(리버시) 게임으로, Minimax 알고리즘을 기반으로 한 인공지능(AI)의 다양한 전략과 최적화 기법을 탐구합니다.
기술스택
|
|
|
|
| React | TypeScript | Vite | Tailwind CSS |
Click to play
1. Version 1의 한계와 동기
Version 1의 단순 평가 함수를 사용하는 AI를 시뮬레이션한 결과, 후공(백)이 일방적으로 승리하는 문제가 관찰되었습니다. 이는 단순 평가 함수(돌 개수 계산)가 AI의 전략적 깊이를 제한하는 한계를 가지고 있었기 때문입니다. 이를 검증하기 위해 두 가지 가설을 세우고 순차적으로 실험을 진행했습니다.
-
가설 1: 기본적인 위치 전략(코너, 변 등)을 반영한 '임의의 가중치 맵'만으로도 단순 AI보다 나은 성능을 보일 것이다.
-
가설 2: 전문가의 선행 연구를 통해 검증된 가중치 맵은, 임의의 가중치 맵보다 더 뛰어난 성능을 보일 것이다.
2. 실험 1: 임의 가중치 맵 기반 AI 테스트
오셀로 게임을 살펴보면, 게임판의 네 귀퉁이에 놓인 돌은 어떠한 상황에서도 뒤집을 수 없으며, 연결된 변과 중앙을 공격할 수 있습니다. 반대로 네 귀퉁이와 인접한 칸들은 나는 귀퉁이에 돌을 놓을 수 없게 하면서도, 상대방이 귀퉁이에 돌을 놓을 수 있도록 해주는 위험한 자리입니다.
이러한 자리들은 이미 오셀로 게임에서 코너, X-Square, C-Square로 불리며 젼략적으로 분석되어 있습니다.
가. 가설 및 평가 함수 설정
첫 번째 실험을 위해, 오셀로의 기본적인 위치 전략(코너의 가치, X/C-Square의 위험성 등)을 바탕으로 '임의의 위치 가중치 맵'을 구성했습니다. 실제 가중치 맵 구성에는 Google의 Gemini 2.5 Pro의 도움을 받았습니다.
- 평가 방식: (자신의 돌이 놓인 칸의 가중치 합) - (상대 돌이 놓인 칸의 가중치 합)
function evaluateBoard(board: State[], player: Player): number {
const opponent = player === 'b' ? 'w' : 'b';
let playerScore = 0;
let opponentScore = 0;
// 모든 칸을 순회하며,
for (let i = 0; i < 64; i++) {
// 각 플레이어가 차지한 칸의 가중치를 통해 가치를 매깁니다.
if (board[i] === player) {
playerScore += POSITIONAL_WEIGHTS[i];
} else if (board[i] === opponent) {
opponentScore += POSITIONAL_WEIGHTS[i];
}
}
// 현재 플레이어를 기준으로 한 상대 가치 반환
return playerScore - opponentScore;
}| A | B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|---|
| 1 | 120 | -20 | 20 | 5 | 5 | 20 | -20 | 120 |
| 2 | -20 | -40 | -5 | -5 | -5 | -5 | -40 | -20 |
| 3 | 20 | -5 | 15 | 3 | 3 | 15 | -5 | 20 |
| 4 | 5 | -5 | 3 | 3 | 3 | 3 | -5 | 5 |
| 5 | 5 | -5 | 3 | 3 | 3 | 3 | -5 | 5 |
| 6 | 20 | -5 | 15 | 3 | 3 | 15 | -5 | 20 |
| 7 | -20 | -40 | -5 | -5 | -5 | -5 | -40 | -20 |
| 8 | 120 | -20 | 20 | 5 | 5 | 20 | -20 | 120 |
const ARBITRARY_POSITIONAL_WEIGHTS = [
120, -20, 20, 5, 5, 20, -20, 120,
-20, -40, -5, -5, -5, -5, -40, -20,
20, -5, 15, 3, 3, 15, -5, 20,
5, -5, 3, 3, 3, 3, -5, 5,
5, -5, 3, 3, 3, 3, -5, 5,
20, -5, 15, 3, 3, 15, -5, 20,
-20, -40, -5, -5, -5, -5, -40, -20,
120, -20, 20, 5, 5, 20, -20, 120,
];나. 시뮬레이션 결과 및 분석
| 탐색 깊이 (Depth) | 총 게임 수 | 향상된 AI 승리 | 단순 AI 승리 | 무승부 | 최종 승자 | 주요 관찰 |
|---|---|---|---|---|---|---|
| 4 | 30 | 15 | 15 | 0 | 백(White) | 평가 함수와 무관하게 후공(백)이 반드시 승리. |
| 5 | 15 | 7 | 8 | 0 | 백(White) | 여전히 후공(백)이 반드시 승리. 가중치 AI가 질 때 더 큰 점수 차로 패배. |
| 6 | 8 | 8 | 0 | 0 | 향상된 AI | 평가 함수의 차이가 승패를 결정. 가중치 맵을 사용한 AI가 선공/후공과 무관하게 전승. |
분석: 얕은 탐색 깊이(4, 5)에서는 두 AI 모두 근시안적인 플레이를 하여, 평가 함수의 차이가 큰 의미를 갖지 못하고 후공(백)이 유리한 양상이 나타났습니다. 하지만 탐색 깊이가 6 이상으로 충분해지자, 기본적인 위치 가중치를 반영한 것만으로도 AI의 성능이 단순 AI를 압도함을 확인하여 가설1을 검증하였습니다.
3. 실험 2: 연구 기반 가중치 맵 AI 테스트
가. 가설 및 평가 함수 설정
첫 번째 실험을 통해 가중치 맵의 효용성은 확인했지만, 더 정교하게 튜닝된 가중치 맵을 사용하면 더 얕은 탐색 깊이에서도 우위를 점할 수 있을 것이라는 가설 2를 검증하고자 했습니다. 이를 위해 여러 선행 연구[^1][^2][^3][^4]에서 공통적으로 인용되는 Yoshioka et al.의 Heuristic weights를 정수화하여 사용했습니다.
| A | B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|---|
| 1 | 100 | -25 | 10 | 5 | 5 | 10 | -25 | 100 |
| 2 | -25 | -25 | 1 | 1 | 1 | 1 | -25 | -25 |
| 3 | 10 | 1 | 5 | 2 | 2 | 5 | 1 | 10 |
| 4 | 5 | 1 | 2 | 1 | 1 | 2 | 1 | 5 |
| 5 | 5 | 1 | 2 | 1 | 1 | 2 | 1 | 5 |
| 6 | 10 | 1 | 5 | 2 | 2 | 5 | 1 | 10 |
| 7 | -25 | -25 | 1 | 1 | 1 | 1 | -25 | -25 |
| 8 | 100 | -25 | 10 | 5 | 5 | 10 | -25 | 100 |
const RESEARCH_BASED_POSITIONAL_WEIGHTS = [
100, -25, 10, 5, 5, 10, -25, 100,
-25, -25, 1, 1, 1, 1, -25, -25,
10, 1, 5, 2, 2, 5, 1, 10,
5, 1, 2, 1, 1, 2, 1, 5,
5, 1, 2, 1, 1, 2, 1, 5,
10, 1, 5, 2, 2, 5, 1, 10,
-25, -25, 1, 1, 1, 1, -25, -25,
100, -25, 10, 5, 5, 10, -25, 100,
];나. 시뮬레이션 결과 및 분석
| 탐색 깊이 (Depth) | 총 게임 수 | 향상된 AI 승리 | 단순 AI 승리 | 무승부 | 최종 승자 | 주요 관찰 |
|---|---|---|---|---|---|---|
| 4 | 30 | 30 | 0 | 0 | 향상된 AI | 향상된 AI가 큰 점수차로 승리(평균 40.5점 차). |
| 5 | 16 | 16 | 0 | 0 | 향상된 AI | 여전히 향상된 AI가 승리하지만 점수 차가 좁혀짐(평균 5점 차). |
| 6 | 8 | 8 | 0 | 0 | 향상된 AI | 여전히 향상된 AI가 승리하면서 다시 점수 차가 벌어짐(평균 33점 차). |
분석: 선행 연구 기반의 가중치 맵은 임의의 가중치 맵과 달리, 탐색 깊이 4라는 매우 얕은 수준에서부터 단순 AI를 압도했습다. 이는 더 정교한 휴리스틱이 AI의 '직관'을 크게 향상시켜 적은 수읽기만으로도 훨씬 뛰어난 성능을 발휘하게 함을 의미합니다. 가설2를 검증했습니다.
4. 종합 결론 및 한계
두 번의 실험을 통해, 복잡한 전략 게임 AI의 성능은 평가 함수의 정교함과 탐색의 깊이라는 두 축이 함께 발전해야 함을 명확히 확인했습니다. 특히 잘 설계된 휴리스틱 평가 함수는 AI가 더 얕은 탐색 깊이에서도 강력한 성능을 발휘하게 하는 핵심 요인이었습니다.
또한 탐색 깊이 5에서 일시적으로 점수 차가 좁혀지는 현상은, 향상된 AI가 더 깊은 수(6수)를 내다볼 때 비로소 단기적인 교착 상태를 넘어 장기적인 전략적 우위를 점할 수 있음을 보여줍니다. 이는 우수한 게임 AI는 단기 전술뿐만 아니라 게임 전체를 조망하는 전략적 시야를 갖추어야 함을 시사합니다.
현재의 가장 큰 한계는 순수 Minimax 탐색의 엄청난 계산량입니다. 이로 인해 실시간 게임에 적용하기에는 탐색 속도가 너무 느립니다. 다음 단계에서는 알파-베타 가지치기(- pruning)를 적용하여 불필요한 탐색을 줄이고, 새로 적용된 강력한 평가 함수를 실시간으로 활용할 수 있도록 최적화를 진행할 예정입니다.
회고
평가 함수를 개선하기 위해 몇가지 방안을 수행해보면서 느낀점은, 역시 박사님들이 참 대단하시다는 것이었습니다. 임의적으로 구성한 위치 가중치에 비해 선행연구에서 사용하는 위치 가중치가 확실히 성능이 좋았습니다. 덕택에 불필요한 시뮬레이션 과정과 최적화 과정이 많이 줄었습니다.
아주 간단한, 부족한 프로젝트이지만 이 내용도 누군가에게 도움이 되었으면 좋겠습니다.
틀린 내용, 부족한 내용에 대한 지적은 언제나 환영입니다.
참고문헌
[^4]: Yoshioka, Taku, Shin Ishii, and Minoru Ito. "Strategy acquisition for the game." IEICE TRANSACTIONS on Information and Systems 82.12 (1999): 1618-1626.
