Minimax 재귀는 정확히 어떻게 작동합니까?

StackOverflow https://stackoverflow.com//questions/11703846

문제

그래서 Tic-Tac-Toe 게임을 위해 Mini-max를 찾고 있었는데 재귀가 어떻게 작동하는지 이해할 수 없었나요?좋습니다. 기본적으로 제 질문은 다음과 같습니다.

  1. 미니맥스는 누구 차례인지 어떻게 알 수 있나요?자신의 차례가 생성되는 플레이어를 나타내는 가장 좋은 방법은 무엇입니까?
  2. 가능한 움직임을 어떻게 생성합니까?
  3. 터미널 노드에 있는지 어떻게 알 수 있으며 터미널 노드를 어떻게 생성합니까?

예를 들어 이 의사 코드에서

function integer minimax(node, depth)
if node is a terminal node or depth <= 0:
    return the heuristic value of node
α = -∞
for child in node: # evaluation is identical for both players
    α = max(α, -minimax(child, depth-1))
return α

ㅏ node 보드 맞나요?그리고 코드가 재귀적으로 내려가야 하는 깊이는 몇 겹입니까?또한 무엇입니까? max 함수와 노드는 어디에서 생성됩니까?

이제 지금까지 보드를 생성하는 코드는 다음과 같습니다.

class Board{
    public:
        Board();
        ~Board(){};
    public: // The board
        // In the board, 1 is x, 2 is o, 0 is empty square.
        int board[3][3];
};

하지만 누구 차례인지 어떻게 알 수 있나요?그리고 보드의 하위 노드를 어떻게 생성합니까?

도움이 되었습니까?

해결책

먼저 tic-tac-toe를 예로 들어보겠습니다.

  • 미니맥스 알고리즘은 플레이어가 교대로 회전하는 게임에 가장 적합하지만 플레이어가 턴당 여러 번 움직일 수 있는 게임에 적용할 수 있습니다.단순화를 위해 전자를 가정하겠습니다.이 경우 각 노드에 'X to move' 또는 'O to move'를 저장할 필요가 없습니다. 왜냐하면 이는 노드 깊이의 패리티(걸음 수가 짝수인지 홀수인지 여부)에 따라 결정될 수 있기 때문입니다. 위에서부터 단계 수).
  • 각 위치에서 가능한 이동을 생성하려면 해당 이동이 누구인지 알아야 하며(이전과 같이 결정될 수 있음) 특정 위치에서 합법적인 이동에 대한 규칙을 알아야 합니다.tic-tac-toe와 같은 간단한 게임의 경우 위치가 주어지면 현재 위치의 복사본과 현재 플레이어에 속하는 새 조각(각 빈 사각형에 차례로 배치됨)으로 구성된 모든 상태를 열거하는 것으로 충분합니다.Othello와 같은 게임의 경우 각 배치를 확인하여 규칙을 따르는지 확인하고 규칙의 결과에 따라 최종 위치를 업데이트해야 합니다(Othello의 경우 여러 조각의 색상을 뒤집음).일반적으로 추적 중인 각 유효한 위치에서 새 조각의 가능한 모든 위치를 열거하고 규칙 세트에서 허용되는 위치를 확인합니다.
  • 일반적으로 게임 트리 크기는 지구의 저장 용량을 쉽게 초과할 수 있으므로 전체 트리를 생성하지 마십시오.항상 최대 반복 깊이를 설정합니다.그러면 터미널 노드는 단순히 최대 깊이에 있는 노드이거나 합법적인 이동이 존재하지 않는 노드입니다(tic-tac-toe의 경우 모든 사각형이 채워진 보드).터미널 노드를 미리 생성하지 않습니다.게임 트리를 구성하는 동안 자연스럽게 생성됩니다.Tic-tac-toe는 충분히 간단합니다. ~할 수 있다 전체 게임 트리를 생성하되 tic-tac-toe 코드를 사용하지 마세요.오델로.

의사코드를 살펴보면 다음과 같습니다.

  • max(a, b) 다음 중 더 큰 값을 반환하는 함수입니다. a 또는 b.이는 일반적으로 수학 라이브러리 또는 유사한 라이브러리에서 제공됩니다.
  • 그만큼 depth 검색할 최대 깊이입니다.
  • 계산하는 경험적 가치는 보드의 가치를 설명하는 숫자 값입니다.전체 게임 트리를 열거할 수 있을 만큼 간단한 tic-tac-toe와 같은 게임의 경우 다음을 지정할 수 있습니다. 1 분석을 수행하는 플레이어가 승리하는 보드 위치에 대해 -1 다른 플레이어가 승리하는 보드 포지션에 대해 0 결정적이지 않은 입장에 대해.일반적으로 휴리스틱을 직접 만들거나 잘 수용되는 휴리스틱을 사용해야 합니다.
  • 상위 노드를 기반으로 분석하는 동안 즉시 노드를 생성합니다.루트 노드는 항상 분석을 수행하는 위치입니다.

아직 그래프나 트리 작업을 해본 적이 없다면 먼저 작업해 보시기 바랍니다.특히 트리 프리미티브는 다음과 같습니다. 필수적인 이 문제에.

주어진 노드에 대한 차례를 결정하는 예를 요청하는 이 스레드의 의견에 대한 답변으로 다음 의사 Python을 제공합니다.

who_started_first = None

class TreeNode:
    def __init__(self, board_position = EMPTY_BOARD, depth = 0):
        self.board_position = board_position
        self.children = []
        self.depth = depth
    def construct_children(self, max_depth):
        # call this only ONCE per node!
        # even better, modify this so it can only ever be called once per node
        if max_depth > 0:

            ### Here's the code you're actually interested in.
            if who_started_first == COMPUTER:
                to_move = (COMPUTER if self.depth % 2 == 0 else HUMAN)
            elif who_started_first == HUMAN:
                to_move = (HUMAN if self.depth % 2 == 0 else COMPUTER)
            else:
                raise ValueError('who_started_first invalid!')

            for position in self.board_position.generate_all(to_move):
                # That just meant that we generated all the valid moves from the
                # currently stored position. Now we go through them, and...
                new_node = TreeNode(position, self.depth + 1)
                self.children.append(new_node)
                new_node.construct_children(max_depth - 1)

각 노드는 '루트' 노드로부터의 절대 깊이를 추적할 수 있습니다.다음 이동을 위해 보드 위치를 생성하는 방법을 결정하려고 할 때 깊이의 패리티(의 결과)를 기반으로 누구의 이동인지 확인합니다. self.depth % 2) 그리고 누가 먼저 이사했는지 기록합니다.

다른 팁

1) Minimax는 어떻게 알 수 있습니까?플레이어가 발생하는 플레이어를 나타내는 가장 좋은 방법은 무엇입니까?

depth 인수가 있습니다.깊이가 심지어 짝수라면 하나의 플레이어의 차례입니다. 이상한 경우 다른 플레이어의 차례입니다.

2) 가능한 움직임을 어떻게 생성합니까?

게임의 규칙을 사용합니다.TIC TAC TOE에서는 가능한 이동 수단을 자유 셀에 넣는 것을 의미합니다.

3) 터미널 노드에있을 때 어떻게 알 수 있으며 터미널 노드를 어떻게 생성합니까?

터미널 노드는 누군가가이긴 노드입니다.재귀로 그들을 생성합니다.각 재귀 적 전화는 보드의 현재 상태를 제공해야합니다.나는 그것이 의사 코드에서 node 및 child 매개 변수라고 생각한다.그래서 그 상황에서 누군가가 이겼다면 그것은 터미널입니다. 그렇지 않으면 모든 법적 움직임을 시도하고 재발구합니다.

TIC-TAC-TOE의 MINIMAX 알고리즘을 썼기 때문에 찾고있는 것에 대한 아이디어를 약간 제공 할 수 있습니다.

에 직접 질문에 답하십시오 :

  1. My Minimax 알고리즘은 그것을 결정하지 않았습니다. 알고리즘이 사용한 플레이어를 결정한 논증을 수락했습니다.

  2. 플레이어가 이동하도록 알고, 보드의 모든 공백 사각형을 루프하고 각각에 대해서는 해당 플레이어의 토큰을 사용하여 노드를 생성합니다. 거기에서 반복적으로 진행됩니다.

  3. 게임이 끝났는지 여부와 그 무승부인지 여부를 나타내는 값을 반환 한 함수를 사용했습니다.

    4. 내 기본 알고리즘이 이렇게했습니다.

    • 입력 : 플레이어가 이동하고, 보드의 상태.
    • 보드에 남은 모든 공백을 찾습니다.
      • 플레이어가 해당 공간에서 움직이는 새 보드를 생성합니다.
      • 게임이 끝나면 게임의 결과로 노드를 생성하십시오.
      • 다른 플레이어와 새 보드를 통과하고, 상대방의 이상적인 움직임의 결과로 노드를 생성하고, 알고리즘을 실행하고, 상대방의 이상적인 이동의 결과로 노드를 생성합니다.
    • 어떤 노드 (이동)가 최상의 최악의 경우를 결정합니다.
    • 출력 : 최상의 이동 및 게임의 결과에 대한 정보.
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top