알파 베타를 사용하여 노드를 선택하는 방법

Question

Alpha Beta 가지 치기가있는 MiniMax를 사용하여 오델로 게임용 AI를 구현합니다. 내가 얻을 수있는 가치를 말해주는 알파 베타 (Alpha Beta) 알고리즘을 구현했지만 어떤 노드를 선택해야하는지 알 수 없다. 그래서 내 질문은 Alpha-Beta를 사용하여 결과 값이 아닌 노드를 선택해야하는 방법을 알려주는 것입니다. 다음은 알파 베타 (Alpha-Beta) 알고리즘의 의사 코드입니다.

01 function alphabeta(node, depth, α, β, maximizingPlayer) 
02  if depth = 0 or node is a terminal node 
03   return the heuristic value of node 
04  if maximizingPlayer 
05   v := -∞ 
06   for each child of node 
07    v := max(v, alphabeta(child, depth – 1, α, β, FALSE)) 
08    α := max(α, v) 
09    if β ≤ α 
10     break (* β cut-off *) 
11   return v 
12  else 
13   v := ∞ 
14   for each child of node 
15    v := min(v, alphabeta(child, depth – 1, α, β, TRUE)) 
16    β := min(β, v) 
17    if β ≤ α 
18     break (* α cut-off *) 
19   return v 

Answer 1

루트 위치에서 가장 좋은 이동을 알고 싶다면 루트 위치에서 가장 높은 점수를 얻은 이동을 기억하면 충분합니다. 이를 위해 점수를 반환하는 것만으로 충분합니다. 의사 코드의 변경은 필요하지 않습니다.

중요한 노드에 대한 경로를 묻는 중, principal variation을 재구성하는 방법에 대해 묻습니다. 검색에서 예상되는 일련의 동작에 대한 정보를 제공합니다.

이론적으로 재귀 호출에서 값과 주 변형을 반환 할 수 있습니다. 따라서 경로를 재구성 할 수 있습니다. Triangular PV-Tables은 이러한 목적에 최적화 된 데이터 구조입니다.

검색에 transposition table을 사용하는 경우 더 간단한 방법은 근음 위치를 시작하고 전치 테이블에서 최상의 이동을 찾는 것입니다. 그런 다음 게임이 끝나거나 항목이 발견되지 않을 때까지 이동하고 반복하십시오 (최선의 움직임을 찾거나, 최선의 움직임을 취하거나, 다시 검색 등). 결국, 만들어진 움직임이 주요 변화입니다.

전치 테이블 접근법은 주요 변형을 명시 적으로 추적하는 것만 큼 정확하지는 않지만 구현하는 것이 간단하며 검색 중에 오버 헤드가 추가되지 않습니다.