게임 트리

Game tree
조합 게임 이론이 아닌 게임 이론에서 사용되는 게임 트리는 확장 형식의 게임을 참조하십시오.

일반적으로 완벽한 정보를 가진 순차적 게임을 연구하는 조합 게임 이론의 맥락에서 게임 트리는 이러한 게임 내에서 가능한 모든 게임 상태를 나타내는 그래프입니다.이러한 게임에는 체스, 체커, 바둑, 틱택토와 같은 유명한 게임들이 포함된다.이것은 게임이 성공할 수 있는 모든 가능한 방법을 나타내기 때문에 게임의 복잡성을 측정하는 데 사용될 수 있습니다.체스와 같은 복잡한 게임의 큰 게임 트리 때문에, 이 클래스의 게임을 하도록 설계된 알고리즘은 부분적인 게임 트리를 사용할 것이고, 이것은 현대 컴퓨터에서 계산을 가능하게 할 것이다.게임 트리를 해결하기 위한 다양한 방법이 존재합니다.완전한 게임 트리를 생성할 수 있으면 역방향 유도나 역방향 분석 등의 결정론적 알고리즘을 이용할 수 있다.완전한 게임 트리가 불가능할 경우 랜덤화 알고리즘 및 MCTS 등의 미니맥스 알고리즘을 사용할 수 있습니다.

게임 트리의 이해

게임 트리를 더 잘 이해하기 위해 플레이어가 게임에서 이기기 위해 취할 행동을 결정하는 적대적 게임을 분석하는 기술로 생각할 수 있습니다.게임 이론에서 게임 트리는 노드가 게임 내 위치이고(예를 들어 보드 게임 내 피스 배열), 가장자리가 움직이는(예를 들어 보드 상의 한 위치에서 다른 [1]피스 이동) 방향 그래프이다.

게임의 완전한 게임 트리는 초기 위치에서 시작하여 각 위치에서 가능한 모든 움직임을 포함하는 게임 트리입니다. 완전한 트리는 광범위한 형식의 게임 표현에서 얻은 것과 동일한 트리입니다.좀 더 구체적으로 말하면, 게임이론에서 완전한 게임은 게임의 표준이다.그것은 많은 중요한 측면을 명확하게 표현할 수 있다.예를 들어 이해관계자가 취할 수 있는 조치의 순서, 각 의사결정 지점의 선택, 각 이해관계자가 결정을 내릴 때 다른 이해관계자가 취한 조치에 대한 정보, 가능한 모든 게임 [2]결과의 이점 등이 있습니다.

틱택토용 게임 트리의 처음 두 개의 플라이.

이 그림은 틱택토 게임 트리의 처음 두 레벨(플라이)을 나타내고 있습니다.포지션의 회전과 반사가 동일하기 때문에 첫 번째 플레이어는 중앙, 가장자리 또는 코너에서 세 가지 동작을 선택할 수 있습니다.첫 번째 선수가 중앙에서 경기했다면 두 번째 선수는 두 가지 선택지를 가지고 있고, 그렇지 않으면 다섯 가지 선택지를 가지고 있다.기타 등등.

완전한 게임 트리의 리프 노드 수는 게임을 실행할 수 있는 다양한 방법의 수입니다.예를 들어 tic-tac-toe의 게임 트리는 255,168개의 리프 노드가 있습니다.

게임 트리는 인공지능에서 중요하다. 왜냐하면 게임에서 가장 좋은 수를 고르는 한 가지 방법은 나무를 가지치기 위한 미니맥스 같은 규칙과 결합된 수많은 나무 검색 알고리즘 중 하나를 사용하여 게임 트리를 검색하는 것이기 때문이다.tic-tac-toe용 게임 트리는 쉽게 검색할 수 있지만, 체스와 같은 대형 게임용 게임 트리는 검색하기에 너무 큽니다.대신 체스 플레이 프로그램은 부분 게임 트리를 검색합니다.일반적으로 현재 위치에서 가능한 한 많은 플레이가 사용 가능한 시간에 검색됩니다."병리적인" 게임[3] 트리의 경우를 제외하고(실제로 매우 드문 것으로 보인다), 검색 깊이(즉, 검색된 플레이의 수)를 높이면 일반적으로 최적의 수를 선택할 가능성이 높아집니다.

2인용 게임은 나무 또는 트리로 나타낼 수도 있습니다.첫 번째 선수가 게임에서 이기려면 두 번째 선수의 모든 동작에 대한 승부수가 있어야 한다.이는 첫 번째 플레이어의 대체 동작을 나타내기 위해 분리를 사용하고 두 번째 플레이어의 모든 동작을 나타내기 위해 분리를 사용하여 트리에 표시됩니다.

게임 트리 해결

결정론적 알고리즘 버전

완전한 게임 트리를 통해 게임을 "해결"할 수 있습니다. 즉, 첫 번째 또는 두 번째 플레이어가 따라갈 수 있는 일련의 움직임으로 해당 플레이어가 최상의 결과를 얻을 수 있습니다(보통 승리 또는 무승부).결정론적 알고리즘(일반적으로 역귀납 또는 역귀분석이라고 함)은 다음과 같이 재귀적으로 설명할 수 있다.

  1. 플레이어 1의 모든 우승이 한 방향으로(그림의 파란색), 플레이어 2의 모든 우승이 다른 방향으로(그림의 빨간색), 모든 동점이 세 번째 방향으로(그림의 회색) 색칠되도록 게임 트리의 마지막 플레이에 색을 입힙니다.
  2. 다음 층을 보세요.현재 플레이어와 반대되는 색상의 노드가 있는 경우 해당 플레이어에 대해서도 이 노드를 색칠합니다.즉시 하위 노드가 모두 동일한 플레이어에 대해 색상이 지정된 경우 이 노드도 동일한 플레이어에 대해 색상이 지정됩니다.그렇지 않은 경우 이 노드에 동점 색상을 지정합니다.
  3. 모든 노드가 색칠될 때까지 위쪽으로 이동하면서 각 플라이에 대해 반복합니다.루트 노드의 색상이 게임의 성격을 결정합니다.

이 다이어그램은 위의 알고리즘을 사용하여 색을 입힌 임의의 게임의 게임 트리를 보여줍니다.

게임 트리의 서브셋만을 사용하여 게임을 해결할 수 있습니다.많은 게임에서 같은 플레이어에게 더 나은 다른 움직임(예를 들어 알파 베타 가지치기를 많은 결정론적인 게임에서 사용할 수 있음)이 있을 경우, 그 움직임을 분석할 필요가 없기 때문입니다.

게임을 해결하기 위해 사용할 수 있는 서브트리를 결정 트리라고 하며, 다양한 모양의 결정 트리의 크기를 게임 [4]복잡성의 척도로 사용한다.

랜덤화 알고리즘 버전

랜덤화된 알고리즘을 사용하여 게임 트리를 해결할 수 있습니다.이러한 유형의 구현에는 속도와 실용성의 두 가지 주요 이점이 있습니다.게임 트리의 해결의 결정론적 버전은 ORO(n)로 할 수 있지만, 다음의 랜덤화 알고리즘은 게임 트리 내의 모든 노드가 차수 2를 가질 경우 예상되는 실행 시간은 θ(n0.792)이다.또한 랜덤화된 알고리즘은 적에게 공격을 가할 수 있기 때문에 해결 순서가 랜덤이기 때문에 게임 트리를 풀 때 사용되는 알고리즘을 알면 상대가 게임 트리의 시스템을 이길 수 없기 때문에 실용적이다.

다음은 랜덤화된 게임 트리 솔루션 [5]알고리즘의 구현입니다.

방어하다 gt_eval_rand(u) -> 부울:     "이 노드가 이기면 True를 반환하고 그렇지 않으면 False를 반환합니다."     한다면 u.잎사귀:         돌아가다 u.당첨되다     또 다른:         랜덤_자녀 = (gt_eval_rand(어린아이) 위해서 어린아이 에 랜덤 순서(u.아이들.))         한다면 u.동작 == 'OR':             돌아가다 조금도(랜덤_자녀)         한다면 u.동작 == "그리고":             돌아가다 모든.(랜덤_자녀)

알고리즘은 루트 노드가 "단락"으로 간주되는 경우 "단락" 개념을 사용합니다.OR" 연산자는 True가 1개 발견되면 루트가 True로 분류됩니다.반대로 루트 노드가 "AND" 연산자로 간주되면 False가 1개 발견되면 루트는 False로 분류됩니다.

[6]

「 」를 참조해 주세요.

레퍼런스

  1. ^ Zuckerman, Inon; Wilson, Brandon; Nau, Dana S. (2018). "Avoiding game-tree pathology in 2-player adversarial search". Computational Intelligence. 34 (2): 542–561. doi:10.1111/coin.12162. ISSN 1467-8640. S2CID 46926187.
  2. ^ Huang, Zishuo; Yu, Hang; Chu, Xiangyang; Peng, Zhenwei (2018-05-01). "A novel optimization model based on game tree for multi-energy conversion systems". Energy. 150: 109–121. doi:10.1016/j.energy.2018.02.091. ISSN 0360-5442.
  3. ^ Nau, Dana (1982). "An investigation of the causes of pathology in games". Artificial Intelligence. 19 (3): 257–278. doi:10.1016/0004-3702(82)90002-9.
  4. ^ Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF). Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0.
  5. ^ Daniel Roche (2013). SI486D: Randomness in Computing, Game Trees Unit. United States Naval Academy, Computer Science Department.
  6. ^ Pekař, Libor; Matušů, Radek; Andrla, Jiří; Litschmannová, Martina (September 2020). "Review of Kalah Game Research and the Proposition of a Novel Heuristic–Deterministic Algorithm Compared to Tree-Search Solutions and Human Decision-Making". Informatics. 7 (3): 34. doi:10.3390/informatics7030034.

추가 정보