Chapter 17. 미니맥스(Minimax) 알고리즘의 의사결정 트리 구조 Chapter 17. 미니맥스(Minimax) 알고리즘의 의사결정 트리 구조 17.1미니맥스 알고리즘의 역사적 기원과 이론적 배경 17.2미니맥스 알고리즘의 형식적 정의와 최적 전략 개념 17.3의사결정 트리(Decision Tree)의 구조적 정의와 표현 17.4게임 트리에서의 최대화 노드(MAX)와 최소화 노드(MIN) 구분 17.5단말 노드(Terminal Node)의 효용 값 할당 원리 17.6미니맥스 값(Minimax Value)의 재귀적 정의 17.7미니맥스 알고리즘의 의사코드와 단계별 실행 흐름 17.8미니맥스 알고리즘의 재귀적 구현과 호출 스택 분석 17.9깊이 제한(Depth-Limited) 미니맥스 탐색의 설계 17.10정적 평가 함수(Static Evaluation Function)의 설계 원리 17.11평가 함수의 선형 가중 합(Linear Weighted Sum) 모델 17.12위치 평가에서의 특징 추출(Feature Extraction) 기법 17.13미니맥스 알고리즘의 최적성 증명 17.14미니맥스 알고리즘의 완전성(Completeness) 조건 분석 17.15미니맥스 알고리즘의 시간 복잡도: O(b^d) 분석 17.16미니맥스 알고리즘의 공간 복잡도: 깊이 우선 탐색 기반 분석 17.17분기 계수(Branching Factor)와 탐색 깊이의 상호 관계 17.18다자간 게임(Multi-Player Game)으로의 미니맥스 확장 17.19다자간 게임에서의 효용 벡터(Utility Vector)와 파레토 균형 17.20확률적 게임(Stochastic Game)과 기대 미니맥스(Expectiminimax) 알고리즘 17.21기회 노드(Chance Node)의 도입과 확률적 분기 처리 17.22기대 미니맥스의 시간 복잡도 분석: O(b^d · n^d) 17.23네가맥스(Negamax) 알고리즘의 정의와 구현 단순화 17.24네가맥스와 미니맥스의 수학적 동치성 증명 17.25탐색 깊이와 계산 자원 간의 최적 균형 전략 17.26반복 심화(Iterative Deepening) 미니맥스의 구조와 장점 17.27시간 제한 탐색(Time-Limited Search)에서의 불완전 결정 처리 17.28전이 테이블(Transposition Table)을 이용한 중복 상태 제거 17.29킬러 이동 휴리스틱(Killer Move Heuristic)의 원리 17.30이력 휴리스틱(History Heuristic)을 이용한 이동 순서 최적화 17.31틱택토(Tic-Tac-Toe)에서의 미니맥스 완전 탐색 사례 17.32체스 엔진에서의 미니맥스 기반 탐색 구조 분석 17.33오셀로(Othello)에서의 평가 함수 설계와 미니맥스 적용 17.34커넥트 포(Connect Four)에서의 게임 트리 탐색 사례 17.35미니맥스 알고리즘의 계산적 한계와 가지치기 필요성 17.36미니맥스에서 알파-베타 가지치기로의 이론적 확장