프로젝트 개요
이 프로젝트는 React와 TypeScript를 사용하여 만든 오셀로(리버시) 게임으로, Minimax 알고리즘을 기반으로 한 인공지능(AI)의 다양한 전략과 최적화 기법을 탐구합니다.
기술스택
|
|
|
|
| React | TypeScript | Vite | Tailwind CSS |
Click to play
1. Version 3의 한계와 동기
Version 3에서 알파-베타 가지치기를 적용하여 탐색 효율을 크게 개선했지만, 여전히 '맹목적인' 탐색이라는 한계가 있었습니다. 알파-베타 가지치기 알고리즘은 어떤 순서로 수를 탐색하는지에 따라 성능이 크게 달라지는데, 최적의 수를 먼저 탐색할수록 더 많은 가지를 쳐낼 수 있기 때문입니다. 그러나 이전 버전에서는 단순히 게임판 전체를 순서대로(인덱스 0~63) 탐색하여 이러한 장점을 제대로 활용하지 못했습니다.
따라서 이번 Version 4의 목표는 유망한 수를 먼저 탐색하도록 순서를 정렬(Move Ordering)하여 알파-베타 가지치기의 효율을 극대화하는 것입니다.
2. 무브 오더링 전략 설계 및 실험
가지치기 효율을 비교하기 위해 세 가지 전략을 설계하고 성능을 비교하였습니다.
- None(순차 탐색): 이전 버전과 동일하게 게임판을 순서대로 탐색하는 대조군으로 설정하였습니다.
- Position(위치 가중치 기반 정렬): 일반적으로 오셀로를 플레이할 때 좋은 자리에 둘 수 있는지 먼저 생각해본다는 점에 착안하였습니다. Version 2에서 사용했던 위치 가중치가 높은 칸을 먼저 탐색도록 한 정적(Static) 정렬 방식을 적용했습니다.
const possibleMoves: { move: number, states: State[] }[] = [];
// 보드를 순회하며 착수 가능한 지점을 찾는다.
for (let idx = 0; idx < 64; idx++) {
const states = validateAndFlip(board, idx, player)
if (states) {
possibleMoves.push({
move: idx,
states: states
});
}
}
// 착수 가능한 지점의 위치 가중치(POSITIONAL_WEIGHTS)가 큰 순서대로 정렬한다.
possibleMoves.sort((a, b) => POSITIONAL_WEIGHTS[b.move] - POSITIONAL_WEIGHTS[a.move])- Intuition(얕은 탐색 기반 정렬): 게임을 많이 플레이하다 보면 깊이 수읽기를 하지 않아도 직관적으로 '좋은 자리'가 보인다는 점에서 착안했습니다. 모든 가능한 수에 대해 깊이 3의 얕은 탐색을 미리 수행하고, 그 평가값이 높은 순서대로 정렬하는 동적(Dynamic) 정렬 방식을 적용했습니다.
const moveValueMap: { [move: number]: number } = {};
// 착수 가능한 점에 대해 얕은 깊이(3)로 가치를 판단하여 저장한다.
possibleMoves.forEach(({ move, states}) => moveValueMap[move] = minimaxABRecursive(states, opponent, 3, alpha, beta, player, { count: 0 }));
// 저장된 가치가 큰 순서대로 정렬한다.
possibleMoves.sort((a, b) => moveValueMap[b.move] - moveValueMap[a.move]);3. 시뮬레이션 결과 및 분석
가. 결과 요약
- 효율성(평균 탐색 노드 수)
| 탐색 깊이 | None (순차) | Position (위치 가중치) | Intuition (얕은 탐색) | 효율성 순위 |
|---|---|---|---|---|
| 3 | 1,075 | 825 | 817 | Intuition > Position > None |
| 4 | 5,726 | 5,141 | 4,752 | Intuition > Position > None |
| 5 | 21,912 | 17,357 | 15,724 | Intuition > Position > None |
| 6 | 103,834 | 89,850 | 91,879 | Position > Intuition > None |
| 7 | 369,598 | 320,732 | 363,748 | Position > None > Intuition |
| 8 | 1,987,434 | 1,974,373 | 1,751,863 | Intuition > Position > None |
- 상대전적(승리 횟수 - 패배 횟수)
| 탐색 깊이 | None vs Position | None vs Intuition | Position vs Intuition | 특징 |
|---|---|---|---|---|
| 3 | None이 2승 | 동률 (1승 1패) | Intuition이 2승 | 동률의 경우 흑이 승리함. |
| 4 | 동률 (1승 1패) | 동률 (1승 1패) | 동률 (1승 1패) | 흑이 전부 승리. |
| 5 | 동률 (1승 1패) | None이 2승 | 동률 (1승 1패) | 동률의 경우 흑이 승리함. |
| 6 | None이 2승 | 동률 (1승 1패) | 동률 (1승 1패) | |
| 7 | None이 2승 | 동률 (1승 1패) | 동률 (1승 1패) | 동률의 경우 흑이 승리함. |
| 8 | 동률 (1승 1패) | 동률 (1승 1패) | Position이 2승 | 동률의 경우 흑이 승리함. |
나. 분석: 무브 오더링의 효율성 입증과 승패의 문제
실험 결과 무브 오더링의 효율성이 입증되었습니다. 탐색 깊이 7에서 Intuition이 None에 비해 약 1.6% 가량 평균 탐색량이 많았던 예외적인 경우를 제외하면, 무브 오더링을 적용한 전략이 대조군에 비해 효율적이었습니다. 특히 Intuition 전략은 탐색 깊이 6과 7을 제외한 나머지 4개 구간에서 가장 적은 노드를 탐색했으며, 탐색 깊이 5에서는 대조군에 비해 탐색 노드 수를 약 28% 가량 낮추었습니다. 얕은 탐색을 위한 추가적인 계산 비용을 감안하더라도 가지치기의 이득이 훨씬 크다고 볼 수 있습니다. 다만 탐색 깊이 6, 7에서 볼 수 있듯이, 특정 수준 또는 특정 게임의 국면에서는 보다 단순한 정적 휴리스틱(Position)이 더 효율적일 수 있습니다.
또한 계산의 효율성이 반드시 승리로 이어지지는 않는다는 사실을 확인했습니다. 이는 Minimax 계열 알고리즘의 결정론적(Deterministic) 특성에서 기인합니다. 세 전략은 모두 동일한 평가 함수를 공유하고 있으므로 효율성의 차이만 있을 뿐, 같은 탐색 깊이에 대해 '같은 결론'을 내립니다. 다만 평가값이 동일한 최선의 수가 여러 개일 경우, 어떤 수를 먼저 검토하는지에 따라 최종 선택이 달라질 수 있습니다. 따라서 특정 전략이 상대적 우위를 보이는 것은 그 전략이 더 우월해서가 아니라, 그 전략의 동점자 처리 경향이 우연히 유리한 게임 경로를 선택했기 때문입니다.
다. 활용
Version 4에서는 전체적으로 균형잡힌 Intuition 전략을 적용합니다. 현재 게임에 적용되어 있는 최대 탐색 깊이가 7이므로 해당 구간에서 Intuition 전략이 약간의 비효율성을 보이지만, 다른 대부분의 구간에서 가장 효율적이었고 상대 전적 또한 어느 한쪽에 치우치지 않는 안정적인 모습을 보여주었기 때문입니다.
4. 종합 결론 및 다음 과제
무브 오더링은 알파-베타 탐색의 성능을 한 단계 끌어올리는 최적화 기법임을 확인했습니다. 특히 현재 국면을 반영하여 유망한 수를 동적으로 찾아내는 Intuition 전략이 효율성과 안정성 측면에서 균형잡힌 모습을 보여주었습니다. 그러나 특정 수준 또는 국면에서는 위치 가중치에 따른 정적 정렬 방식처럼 보다 단순한 전략이 더 효율적일 수 있다는 점도 발견했습니다.
이제 Minimax 계열 알고리즘의 최적화를 넘어, 보다 복잡한 몬테-카를로 트리 탐색(Monte-Carlo Tree Search, MCTS)을 게임에 적용하여 새로운 AI 알고리즘과 전략, 최적화에 대해 탐구해보고자 합니다.
회고
간단한 정렬을 먼저 수행하는게 탐색량을 상당히 줄여주었습니다. 어떻게 보면 당연한 결과이기도 합니다. 흔히 탐색 알고리즘에 대해 생각해볼 때, 이분 탐색처럼 주어진 자료가 이미 정렬되어 있는 경우에 탐색량을 줄일 수 있는 경우가 왕왕 있기 때문입니다. 이분 탐색이 정렬된 자료의 중간을 기준으로 절반을 덜어내는 것처럼, 알파-베타 가지치기는 노드의 가치를 기준으로 탐색 노드를 덜어내기 때문에,
- 유망한 노드의 가치를 결정하는 기준
- 적절한 정렬을 통한 탐색 순서의 결정
에 의해 탐색량을 줄일 수 있었다 생각합니다.
이 내용이 누군가에게 도움이 되었으면 좋겠습니다.
틀린 부분 또는 수정할 부분에 대한 지적은 언제나 환영합니다.
