분기 계수

Branching factor
가지 계수 2를 가진 빨간색-검은색 나무

컴퓨팅, 트리 데이터 구조 및 게임 이론에서 분기 요인은 각 노드의 자녀 수, 즉 아웃도입니다.이 값이 균일하지 않으면 평균 분기 계수를 계산할 수 있습니다.

예를 들어, 체스에서, "노드"가 법적 위치로 간주되면, 평균 분기 계수는 [1][2]약 35로 알려져 왔고, 250만 개 이상의 게임을 통계적으로 분석한 결과 평균 [3]31이 밝혀졌다.이것은 평균적으로 한 선수가 각 턴마다 31에서 35개의 법적 조치를 취할 수 있다는 것을 의미한다.이에 비해 바둑의 평균 분기 계수는 250이다.[1]

분기 계수가 높을수록 노드 수가 기하급수적으로 증가하기 때문에 모든 노드의 모든 분기를 따르는 알고리즘(완전한 무차별 포스 검색 등)의 계산 비용이 비싸지고 조합이 폭발적으로 증가합니다.

예를 들어 분기 계수가 10인 경우 현재 위치보다 한 레벨 아래 노드 10개, 두23 레벨 아래 노드 10개(또는 100개), 세 레벨 아래 노드 10개(또는 1,000개)가 있습니다.분기 계수가 높을수록 이 "폭발"이 더 빨리 발생합니다.분기 계수는 플루닝 알고리즘에 의해 삭감할 수 있습니다.

평균 분기 계수는 루트 노드 수(트리의 크기에서 1을 뺀 값 또는 에지 수)를 리프 노드 수(자녀가 있는 노드 수)로 나눈 값으로 빠르게 계산할 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Levinovitz, Alan (12 May 2014). "The Mystery of Go, the Ancient Game That Computers Still Can't Win". Wired. Retrieved 2014-06-02. The rate at which possible positions increase is directly related to a game’s “branching factor,” or the average number of moves available on any given turn. Chess’s branching factor is 35. Go’s is 250. Games with high branching factors make classic search algorithms like minimax extremely costly.
  2. ^ Laramée, François Dominic (6 August 2000). "Chess Programming Part IV: Basic Search". GameDev.net. Retrieved 2007-05-01.
  3. ^ Barnes, David. "What is the average number of legal moves per turn?". Chess Stack Exchange. Retrieved 2019-06-01.