몬테카를로 트리 검색에서 노드 당 시뮬레이션 수

Question

위키피디아에서 설명한 mcts 알고리즘에서 각 노드 선택에서 정확하게 하나의 재생 (시뮬레이션)을 수행합니다. 자, 나는이 알고리즘을 간단한 connect-k 게임에서 실험하고있다. 실제로, 우리는 차이를 줄이기 위해 더 많은 연극을 수행합니까?

정확히 하나의 무작위 재생 (비 바이어스)으로 원본 알고리즘을 시도했습니다. 알파 베타 제거 기능을 사용한 경험적 검색과 비교할 때 그 결과가 나쁩니다. 그것은 매우 천천히 수렴합니다. 대신 500 개의 재생을 수행하면 잡음이 훨씬 적습니다. 그러나 각 노드 시뮬레이션은 알고리즘이 주어진 시간에 트리의 다른 부분을 탐색하기에는 너무 느리므로 때로는 가장 중요한 동작을 놓치게됩니다.

그런 다음 AMAF (특히 RAVE 전환이있는) 휴리스틱 스를 기본 MCTS에 추가했습니다. 분산이 이미 낮기 때문에 500 개의 플레이 아웃과 너무 많은 차이를 느끼지 않습니다. 아직 1 개의 재생으로 결과를 분석하지 않았습니다.

누구나 통찰력을 줄 수 있습니까?

Answer 1

일반적으로 선택 단계마다 정확히 하나의 재생을 수행합니다. 그러나 후속 선택 단계는 동일한 노드를 여러 번 통과 할 수 있습니다.

예를 들어 루트 노드에서 두 가지 이동 만 사용할 수있는 경우를 고려하십시오. 그런 다음 MCTS (10,000 회 반복 = 선택 + 확장 + 재생 + Backpropagation)의 10,000 회 반복을 실행한다고 가정하면 루트 노드 아래의 두 노드는 대략 5,000 번 선택됩니다 (또는 하나가 선택됩니다). 첫 번째가 seocnd보다 더 나은 옵션 인 경우 9,000 번 및 다른 1,000 번,하지만 여전히 두 번 이상 선택됨).

현재 구현중인 작업과 일치합니까? 그렇지 않다면 현재 가지고있는 코드를 제공하여 잘못 된 부분을 볼 수 있도록하십시오. 그러나 이것이 당신이 그것을 어떻게 구현했는지 (이것이 어떻게되어야하는지)라면, 선택 단계마다 단 하나의 플레이 아웃을하는 데 아무런 문제가 없어야합니다.