예상 미니맥스
Expectiminimax| 학급 | 검색 알고리즘 |
|---|---|
| 최악의 경우 성능 | ( m ){ style {} （ ^ { } ^ { }。서n { n}은 뚜렷한 주사위 던지기 횟수입니다. |
| 베스트 케이스 성능 | ( ) \ \ { } （^ { m} 모든 주사위 던짐을 사전에 알고 있는 경우 |
| 그래프와 트리 검색 알고리즘 |
|---|
| 최단 경로 |
| 리스트 |
| 관련 토픽 |
expectiminimax 알고리즘은 미니맥스 알고리즘의 변형으로, 백개먼과 같은 2인용 제로섬 게임을 하는 인공지능 시스템에서 사용됩니다.이 시스템에서는 플레이어의 기술과 주사위 굴림 등의 우연한 요소의 조합에 따라 결과가 달라집니다.기존 미니맥스 트리의 "최소" 및 "최대" 노드 외에 이 변형에는 랜덤 이벤트 [1]발생의 예상 값을 취하는 "천연적으로 이동") 노드가 있습니다.게임 이론에서 기대 미니맥스 트리는 완벽하지만 불완전한 정보의 광범위한 형태의 게임 트리입니다.
전통적인 미니맥스 방법에서는 트리의 깊이가 한계에 도달할 때까지 트리의 레벨이 max에서 min으로 번갈아 표시됩니다.expectminimax 트리에서 "찬스" 노드는 최대 및 최소 노드와 인터리브됩니다.확률 노드는 자녀의 효용값의 최대값 또는 최소값을 취하는 대신 가중 평균을 취하며 가중치는 자녀가 도달할 [1]확률입니다.
인터리빙은 경기에 따라 달라집니다.게임의 각 "턴"은 "최대" 노드(AI 플레이어의 턴을 나타냄), "최적" 노드(잠재적으로 최적의 상대의 턴을 나타냄) 또는 "찬스" 노드(랜덤 효과 또는 [1]플레이어를 나타냄)로 평가됩니다.
예를 들어, 각 라운드가 한 번의 다이스로 구성되어 있고, 그 다음 AI 플레이어와 다른 지능적인 상대가 결정을 내리는 게임을 생각해 보십시오.이 게임에서 노드의 순서는 "찬스", "최대", "최소"[1] 순으로 번갈아 표시됩니다.
유사 코드
expectiminimax 알고리즘은 미니맥스 알고리즘의 변형으로 1966년 [2]Donald Michie에 의해 처음 제안되었다.그 의사 코드는 다음과 같습니다.
노드가 터미널 노드 또는 깊이인 경우 expectminimax(노드, 깊이) = 0인 경우 노드의 휴리스틱 값을 반환합니다. // 최소값 하위 노드의 값을 반환하면 노드 α := min(α, expectminimax(child, 깊이-1)의 하위 노드 α := +pectminimax(ch-1)가 반환됩니다.at node // 최대값 하위 노드의 값을 반환합니다. 노드에서 랜덤 이벤트가 발생하면 α := max(α, expectiminax(child, depth-1)의 하위 노드 값을 α := 0으로 예측합니다. (확률[child])] × expectminimax(자녀, 깊이-1) 반환α
랜덤 노드의 경우 각 자녀에 도달할 확률이 이미 알려져 있어야 합니다(대부분의 경우 자녀 노드는 균등하게 가중치가 부여됩니다.즉, 반환값은 단순히 모든 자녀 값의 평균이 될 수 있습니다).
「 」를 참조해 주세요.
레퍼런스
- ^ a b c d Stuart J. Russell; Peter Norvig (2009). Artificial Intelligence: A Modern Approach. Prentice Hall. pp. 177–178. ISBN 978-0-13-604259-4.
- ^ D. 미치(1966년).게임 플레이 및 게임 학습 오토마타.L. Fox(ed.)에서 프로그래밍 및 비수치 계산의 발전, 페이지 183-200.
