AlphaBeta is not as good as you think: a simple random games model for a better analysis of deterministic game-solving algorithms
Created by
Haebom
Category
Empty
저자
Raphael Boige (LORIA), Amine Boumaza (LORIA), Bruno Scherrer (LORIA)
Deterministic Game-Solving Algorithms: A New Perspective
개요
본 논문은 결정적 게임 해결 알고리즘의 평균 사례 복잡성을 분석하기 위해 새로운 확률적 모델을 제시합니다. 기존의 독립성을 가정한 모델의 한계를 극복하고, 게임 트리에 조상 의존성을 부여하여 실제 게임의 구조적 복잡성을 반영합니다. AlphaBeta 및 Scout과 같은 알고리즘의 평균 사례 복잡성을 특징짓는 재귀 공식을 유도하여 딥 게임 트리에서 알고리즘을 비교합니다.
시사점, 한계점
•
조상 의존성을 도입한 새로운 확률적 모델을 제시하여 게임 해결 알고리즘의 분석을 개선했습니다.
•
AlphaBeta 및 Scout과 같은 알고리즘의 평균 사례 복잡성을 분석하기 위한 재귀 공식을 제공했습니다.
•
딥 게임 트리에서 알고리즘의 성능 차이를 밝혀냈습니다. 특히, AlphaBeta가 Scout에 비해 더 큰 상수 곱셈 인자를 가짐을 보였습니다.
•
모델의 간결성을 유지하면서 실제 게임의 구조적 특징을 더 잘 반영하고자 했습니다.
•
아직은 간단한 모델이며, 모든 종류의 게임에 적용하기에는 한계가 있을 수 있습니다.
•
복잡한 게임의 모든 측면을 포괄하지 못할 수 있으며, 다른 모델과의 비교 연구가 필요합니다.