저는 Norse tafl 보드 게임 패밀리 (project here, source file at issue here)의 인공 지능을 작성하고 있습니다. 그들은 체스 AI에 대한 지식을 폭넓게 사용하여 여기에 적용 할 수 있습니다. 문제의 변형은 방사형 대칭 시작 위치를 가진 7x7 보드에서 재생됩니다. 흰색은 가운데에서 시작하고 검정색은 가장자리에서 시작합니다. 알파 베타 검색을 구현 한 방법에 대해 궁금한 점이 있습니다. 고정 깊이로 검색 한 결과는 알파 베타 제거 외에 최적화가 활성화되지 않았으므로 노드를 탐색하는 순서에 따라 달라집니다.알파 베타 검색에서 예기치 않은 경로 의존성이 있습니까?
문제의 파일에서 중요한 방법은 'explore', 'exploreChildren', 'handleEvaluationResults'및 'generateSuccessorMoves'입니다. 전치 테이블 히트 (이 테스트를 위해 다른 곳에서는 사용할 수 없음)가 있는지 확인하기 위해 '탐색'체크를하고, 승리 또는 리프 노드라면 상태를 평가하거나 exploreChildren을 호출합니다. exploreChildren은 자식 노드에 대한 재귀 적 검색을 수행합니다. generateSuccessorMoves는 현재 상태를 벗어나는 이동을 생성 (및 선택적으로 정렬)합니다. handleEvaluationResults는 자식 평가로 인해 컷오프가 발생했는지 여부를 결정합니다.
그래서 최소한의 테스트 케이스를 작성했습니다. generateSuccessorMoves는 먼저 정렬 작업을 수행하지 않으며, 정렬 작업 대신 이동 목록을 간단히 셔플 처리합니다. 검색 결과는 결과에 해당하지 않으며, 결과에 대칭을 고려하거나 값 :
MAIN SEARCH
# cutoffs/avg. to 1st a/b a/b
Depth 0: 0/0 0/0
Depth 1: 0/22 0/1
Depth 2: 42/0 3/0
Finding best state...
Best move: d3-g3 with path...
d3-g3
e1-f1
e4-e1xf1
End of best path scored -477
Observed/effective branching factor: 23.00/9.63
Thought for: 72msec. Tree sizes: main search 893 nodes, continuation search: 0 nodes, horizon search: 0 nodes
Overall speed: 12402.77777777778 nodes/sec
Transposition table stats: Table hits/queries: 0/0 Table inserts/attempts: 0/0
1. move: d3-g3 value: -477
Using 5000msec, desired 9223372036854775807
Depth 3 explored 1093 states in 0.037 sec at 29540.54/sec
MAIN SEARCH
# cutoffs/avg. to 1st a/b a/b
Depth 0: 0/0 0/0
Depth 1: 0/21 0/2
Depth 2: 104/0 2/0
Finding best state...
Best move: d3-f3 with path...
d3-f3
d2-c2
d5-f5xf4
End of best path scored -521
Observed/effective branching factor: 23.00/10.30
Thought for: 37msec. Tree sizes: main search 1093 nodes, continuation search: 0 nodes, horizon search: 0 nodes
Overall speed: 29540.540540540544 nodes/sec
Transposition table stats: Table hits/queries: 0/0 Table inserts/attempts: 0/0
7. move: d3-f3 value: -521
이것은 분명히, 극단적 인 경우이지만,이 상황에서 알파 - 베타 (즉 나의 이해입니다 , 'alpha-beta pruning'이외의 기능이없는) 검색 순서가 어찌 상관없이 안정해야합니다. 최소한 같은 값의 노드를 반환해야합니다. 내가 잘못? 내가 뭔가 잘못하고 있는거야?
첫 번째 수정 :이 문제의 설명에서 분명하다고 생각되지만, 내 알파 베타 구현에 아직 알려지지 않은 버그가 있음이 밝혀졌습니다. 추가 테스트를 통해 순수 minimax와 동일한 결과를 제공하지 않는다는 것을 알 수 있습니다.
두 번째 편집 : 위 링크 된 파일에 구현 된 알파 베타 검색의 의사 코드 버전입니다.
explore(depth, maxDepth, alpha, beta)
// some tafl variants feature rules where one player moves more than once in a turn
// each game tree node knows whether it's maximizing or minimizing
var isMaximizing = this.isMaximizing()
var value = NO_VALUE
if(isTerminal(depth, maxDepth))
value = eval()
else
for(move in successorMoves)
if(cutoff) break
nodeValue = nextNode(move).explore(depth + 1, maxDepth, alpha, beta)
if(value == NO_VALUE) value = nodeValue
if(isMaximizing)
value = max(value, nodeValue)
alpha = max(alpha, value)
if(beta <= alpha) break
else
value = min(value, nodeValue)
beta = min(beta, value)
if(beta <= alpha) break
rootNode.explore(0, 5, -infinity, infinity)
링크 된 코드를 검사했습니다. 재귀 (탐색)에서 깊이 (currentMaxDepth, mCurrentMaxDepth, overallMaxDepth)가 증가하는 곳은 어디에도 없습니다. 설명 할 수 있니? –
AiWorkspace.explore()에서 반복 심화가 발생합니다. GameTreeState.exploreChildren()에서 상태가 재귀 호출을 할 때 지정된 심화 단계에서의 검색 심도가 증가합니다. – Fishbreath