2024 교육장비개발 및 아이디어 경진대회 교육장비개발 부문 동상 (한국실천공학교육학회)
한국실천공학교육학회 2024 종합학술발표대회 논문집 교육장비개발 부문 논문 게재 (PP. 243~244)
본 연구는 Quoridor AI 에이전트 성능 향상을 위한 최적의 길찾기 알고리즘을 탐색하는 것을 목적으로 한다. Quoridor 게임의 복잡성과 AI 에이전트의 성능 향상 필요성을 고려할 때, 효율적인 길찾기 알고리즘의 선택이 중요하다. 본 연구에서는 BFS, DFS, A*, D* Lite, JPS와 같은 다양한 길찾기 알고리즘을 구현하고, 실험을 통해 성능을 비교 분석하였다. 분석 결과, D* Lite와 JPS 알고리즘이 Quoridor 게임 환경에서 가장 효율적인 성능을 보였으며, 계산 속도와 최적 경로 탐색 측면에서 우수한 결과를 나타냈다. 특히 최단 경로 탐색에서 두 알고리즘은 실행 시간과 이동 횟수 면에서 균형 잡힌 성능을 보여주었다. 본 연구는 Quoridor AI 에이전트에 D* Lite나 JPS 알고리즘을 적용함으로써 Quoridor 앱의 성능을 크게 향상시킬 수 있음을 보여주었으며, 이는 앱의 경쟁력 강화에 기여할 것으로 기대된다.
Key Word
강화학습(RL), 길찾기 알고리즘(PathFind Alg.), BFS, DFS, A*, D* Lite, Jump-Point-Search
실험에서 사용할 길찾기 알고리즘은 다음과 같다.
- BFS (Breadth-First Search)
- DFS (Depth-First Search)
- A*
- D* Lite
- JPS (Jump-Point Search)
실험은 가로형, 세로형, 대칭 1출구형, 대칭 다출구형, 복합형 각 2종의 맵에 Quoridor의 최대 벽 20개를 설치하여 구현한다. 각 알고리즘은 관련 논문과 도서를 바탕으로 Quoridor 규칙에 맞게 변형하여 구현한다. 구현된 맵에서 각 알고리즘을 10회 실행하여 평균 실행 시간과 이동 거리를 측정하고, 이를 바탕으로 알고리즘별 최종 평균값을 산출한다.
실행 환경은 다음과 같다.
|
Apple M3 APL1201 SoC |
Apple Everest 3.60GHz 4-core + Apple Sawtooth 2.48GHz 4-core |
| Apple G16G 1,380 MHz 10-core | |
| Intergrated 24GB LPDDR5-6400) | |
| OS | macOS Sequoia 15.0.1 |
| C++ | Apple Clang 16.0.0 |
다음은 실험에서 사용하는 맵 10종이다.
| 가로형 | 세로형 | 대칭 1출구형 | 대칭 다출구형 | 복합형 |
|---|---|---|---|---|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
실험 결과는 아래와 같다.
실행 시간(ms):
| Map | BFS | DFS | A* | D* Lite | JPS |
|---|---|---|---|---|---|
| 01 | 1.1734 | 0.0570 | 1.0477 | 0.5516 | 0.5626 |
| 02 | 1.4825 | 0.0595 | 1.3955 | 0.5072 | 0.9569 |
| 03 | 0.8713 | 0.0682 | 0.9481 | 0.5700 | 0.5922 |
| 04 | 0.9855 | 0.0441 | 0.9494 | 0.5599 | 0.5860 |
| 05 | 0.7602 | 0.0350 | 0.9964 | 0.5583 | 0.5195 |
| 06 | 0.9807 | 0.0554 | 0.8051 | 0.5317 | 0.5605 |
| 07 | 1.0483 | 0.0401 | 0.7628 | 0.5430 | 0.5409 |
| 08 | 1.0318 | 0.0304 | 1.0408 | 0.5963 | 0.6571 |
| 09 | 0.9192 | 0.0532 | 0.8358 | 0.5460 | 0.5947 |
| 10 | 1.6681 | 0.0888 | 1.5610 | 0.5137 | 0.8229 |
| Avg. | 1.0921 | 0.0532 | 1.0342 | 0.5478 | 0.6393 |
이동 횟수(Steps):
| Map | BFS | DFS | A* | D* Lite | JPS |
|---|---|---|---|---|---|
| 01 | 44.0 | 48.0 | 44.0 | 44.0 | 44.0 |
| 02 | 41.0 | 54.0 | 41.0 | 41.0 | 41.0 |
| 03 | 38.0 | 42.0 | 38.0 | 38.0 | 38.0 |
| 04 | 23.0 | 24.0 | 23.0 | 23.0 | 23.0 |
| 05 | 24.0 | 28.0 | 24.0 | 24.0 | 24.0 |
| 06 | 25.0 | 31.0 | 25.0 | 25.0 | 25.0 |
| 07 | 25.0 | 32.0 | 25.0 | 25.0 | 25.0 |
| 08 | 24.0 | 28.0 | 24.0 | 24.0 | 24.0 |
| 09 | 25.0 | 33.0 | 25.0 | 25.0 | 25.0 |
| 10 | 44.0 | 66.0 | 44.0 | 44.0 | 44.0 |
| Avg. | 31.3 | 38.6 | 31.3 | 31.3 | 31.3 |
위 실험에서 구현된 길찾기 알고리즘들의 성능을 맵 종류별로 분석한 결과, DFS는 모든 맵 유형에서 가장 빠른 실행시간(평균 0.0532ms)을 보였으나, 이동횟수가 다른 알고리즘보다 약 23% 많은 38.6steps로 측정되었다. 특히 복합형 맵에서는 최대 66steps까지 증가하여 실제 게임에서 부적합한 것으로 판단되었다. 반면 D* Lite와 JPS는 모든 맵 유형에서 최적 이동횟수(31.3steps)를 유지하면서도 각각 0.5478ms, 0.6393ms의 준수한 실행시간을 보여 가장 균형 잡힌 성능을 나타냈다. 특히 대칭형 맵들에서 효과적이었으며, 게임에서 요구되는 빠른 응답과 최적 경로 제공을 모두 만족하였다. BFS와 A* 는 최적 이동횟수를 보이지만 가장 느린 실행시간(각각 1.0921ms, 1.0342ms)을 보여 D* Lite나 JPS로 대체 가능함을 확인하였다.
위의 결과를 기반으로, Quoridor AI의 성능을 플레이어의 선호도와 게임 상황에 맞춰 최적화할 수 있도록 알고리즘 선택 기능을 제공할 예정이다. 실행 시간과 이동 횟수의 균형이 중요한 일반적인 상황에서는 D* Lite를, 보다 빠른 응답이 필요한 경우에는 JPS를 선택할 수 있게 하여 사용자 경험을 향상시킬 계획이다.
- Thomas H. Cormen et el., "Introduction to Algorithms, 4th Edition" March 2022. p.554
- Thomas H. Cormen et el., "Introduction to Algorithms, 4th Edition" March 2022. p.563
- Peter E. Hart et el., "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" IEEE July 1968.
- Sven Koenig et el., "D* Lite" AAAI July 2002.
- Daniel Harabor et el., "Online Graph Pruning for Pathfinding on Grid Maps" AAAI August 2011.
- Hidekatsu Furukawa, "알파제로를 분석하며 배우는 인공지능" Jpub June 2020.
Copyright © 2024 RegistryHJ