"인형 용"

Question

저는 알고리즘에 익숙하지 않고 미니 맥스를 이해하려고 노력하고 있었지만 많은 기사를 읽었습니다. 그러나 여전히 그것을 tic-tac-toe로 구현하는 방법은 없습니다. 파이썬에서 게임. 가짜 코드 또는 파이썬 코드를 사용하여 가능한 한 쉽게 설명해 주시겠습니까?

어떻게 작동하는지 알아야합니다. 나는 그것에 대해 많은 것을 읽었고 기본을 이해했다. 그러나 나는 여전히 그것이 어떻게 움직일 수 있는지를 알 수 없다.

제 튜토리얼과 (http://en.literateprograms.org/Tic_Tac_Toe_(Python)와 같은 샘플을 링크하지 마십시오. 좋은 점은 알고 있지만 간단히 바보 설명이 필요합니다.

당신의 시간 :

Answer 1

"미니 맥스 (miniax)"라는 생각은 2 인용 게임에서 한 선수가 점수의 형태를 최대화하려고 시도하고 다른 플레이어가 최소화하려고 시도한다는 것입니다. 예를 들어 Tic-Tac-Toe에서 X의 우승은 +1, O의 우승은 -1로 계산됩니다. X는 최종 점수를 최대화하려고하는 최대 플레이어이고 O는 최종 점수를 최소화하려고하는 최소 플레이어가됩니다.

X는 X의 이동 일 때 X가 이동 한 후 결과를 최대화하는 이동을 선택해야하기 때문에 X를 최대 플레이어라고합니다. O 선수의 경우 O는 이동 후 결과를 최소화하는 이동을 선택해야합니다. 이러한 규칙은 재귀 적으로 적용되므로 예를 들어 플레이 할 보드 위치가 3 개 밖에없는 경우, X의 가장 좋은 플레이는 O가 가능한 한 높은 값을 갖는 최소값 이동을 선택하게합니다. 환언

는 기판 위치 B에 대한 게임 이론적 최소 최대 값 V 그렇지

V(B) = 1 if X has won in this position 
V(B) = -1 if O has won in this position 
V(B) = 0 if neither player has won and no more moves are possible (draw) 

V(B) = max(V(B1), ..., V(Bn)) where board positions B1..Bn are 
     the positions available for X, and it is X's move 
V(B) = min(V(B1), ..., V(Bn)) where board positions B1..Bn are 
     the positions available for O, and it is O's move 

로 정의 X위한 최적의 전략을 B로 이동하도록 항상 V (Bi)가 최대가되도록, 즉 gametheoretic 값 V (B)에 대응하는 Bi와, 마찬가지로 유사하게 최소 후속 위치를 선택하는 Bi.

그러나 일반적으로 체스와 같은 게임에서는 계산할 수 없습니다. 왜냐하면 gametheoretic 값을 계산하기 위해서는 최종 위치까지 전체 게임 트리를 열거하고 그 트리가 대개 매우 커야하기 때문입니다. 따라서 표준 접근법은 보드 위치를 gametheoretic 값과 관련이있는 점수로 매핑하는 "평가 함수"를 만드는 것입니다. 예 : 체스 프로그램에서 평가 함수는 물질적 이점, 열린 열 등에 대해 긍정적 인 점수를 부여하는 경향이 있습니다. 미니 맥스 알고리즘은 보드 위치의 실제 (계산 불가능한) gametheoretic 값 대신에 평가 함수 점수를 최소화합니다.

minimax에 대한 중요한 표준 최적화는 "알파 베타 제거"입니다. 미니 맥스 검색과 동일한 결과를 제공하지만 빠릅니다. Minimax는 모든 검색 수준에서 점수의 부호가 반전되는 "negamax"와 관련하여도 캐스팅 될 수 있습니다. 미니 맥스를 구현하는 대신 플레이어를 통일 된 방식으로 처리하는 것입니다. 다른 게임 트리 검색 방법에는 반복 심화, 증명 번호 검색 등이 있습니다.

Answer 2

최소 최대가 교대로 번갈아있는 2 인용 게임의 잠재적 이동의 공간을 탐험하는 방법이다 주셔서 감사합니다. 당신은이기려고 노력하고 상대방은 당신을 이기지 못하게하려고합니다.

중요한 직감은 현재 자신의 차례라면, 상대방이 당신과 협조하지 않기 때문에 승리를 보장하는 2 단계 이동 순서가 유용하지 않다는 것입니다. 당신은 이기기의 당신의 기회를 극대화하는 움직임을 만들고 당신의 상대는 승리의 기회를 최소화하는 움직임을 만듭니다.

그런 이유로, 당신이 나빠질 수있는 이동에서 지점을 탐색하거나 상대방이 이동하는 지점을 탐색하는 것이 그리 유용하지는 않습니다.