Tic Tac Toe의 미니 맥스 알고리즘에 대한 가능한 움직임 찾기

Question

11x11 보드로 Tic Tac Toe 게임을 만들기로 결정했습니다. 우승 조건은 5 셀 X 또는 O 연속 (세로, 가로 또는 대각선) 또는 보드가 꽉 찬 경우입니다 , 즉 이동이 불가능합니다.

저는 미니 맥 알고리즘을 사용하여 보드에서 최상의 움직임을 찾는 AI 상대방을 만듭니다. (알파 - 베타 가지 치기와) 최소 최대의 의사 코드는 다음과 같다 :

function alphabeta(node, depth, α, β, maximizingPlayer) 
    if the game ends: 
     return the heuristic value of the current state 
    if maximizingPlayer 
     v := -∞ 
     for each possible move in board // notice this 
      v := max(v, alphabeta(child, depth – 1, α, β, FALSE)) 
      α := max(α, v) 
      if β ≤ α 
       break (* β cut-off *) 
     return v 
    else 
    .... 

원래, 틱택 토 보드의 크기가 루프 최소 최대에 빈 셀이 더 많이 없습니다 의미 만 3 × 3입니다. 하지만 11x11 보드에는 121 개의 셀이 있습니다!

예를 들어, 첫 번째 턴이 X 인 경우 O은 120 개의 가능한 이동을가집니다. O는 최선의 가치를 찾기 위해 각 이동을 시도 할 것이기 때문에 함수의 실행 시간은 120의 계승입니다.

제 질문은 가능한 움직임을 어떻게 줄일 수 있습니까? 예를 들어, 첫 번째 플레이어가 중앙의 어딘가로 이동하면 일부 모서리 또는 가장자리 셀에 대해 minimax를 확인할 필요가 없습니다.

Answer 1

질문을 올바르게 이해했다면 Alpha-Beta-Pruning 자체는 각 최대 값 또는 최소값이 발견되면 중지하여 조사 된 이동 수를 줄이기위한 것입니다. 이것이 충분하지 않으면 일부 휴리스틱을 사용해야합니다. 이것은 게임 트리가 나뭇잎 (위의 의사 코드 설명에서는 수행하지 않음)까지 조사되지 않지만 반복 깊이에 대한 일부 인공적인 경계가 도입되었음을 의미합니다. 재귀 깊이에 도달하면 터미널 상태가 아닌 경우 보드를 경험적으로 평가해야합니다.