Minimax 알고리즘 : 비용/평가 함수?

Question

학교 프로젝트는 컴퓨터 플레이어가 알파 베타 제거 기능이있는 Minimax 알고리즘을 구현해야하는 C++ (예 : http://www.cut-the-knot.org/Curriculum/Games/Date.shtml)로 날짜 게임을 작성합니다. 지금까지, 나는 상대방이 그들을 축소한다고 가정하면서 잠재적 인 이익을 극대화한다는 관점에서 알고리즘의 목표가 무엇인지 이해합니다.

그러나 내가 읽은 자료 중 어느 것도 minimax가 결정하는 모든 것을 기반으로하는 평가 기능을 설계하는 방법을 이해하는 데 도움이되지 않았습니다. 모든 예제는 리프 노드에 임의의 숫자를 할당했지만, 실제로 그 노드에 의미있는 값을 할당해야합니다.

Intuition은 승 리프 노드의 경우 +1, 손실의 경우 -1을 알지만 중간 노드는 어떻게 평가합니까?

모든 도움을 주시면 감사하겠습니다.

Answer 1

가장 기본적인 miniax는 승리, 손실 및 그리기를 표시하는 리프 노드 만 평가하고 중간 노드 값을 결정하기 위해 해당 값을 트리 위로 백업합니다. 게임 트리가 다루기 힘든 경우에는 미니 맥스 함수의 추가 매개 변수로 컷오프 깊이를 사용해야합니다. 깊이에 도달하면 불완전한 상태에 대해 일종의 평가 함수를 실행해야합니다.

minimax 검색에서 대부분의 평가 기능은 특정 도메인이므로 특정 게임에 대한 도움을 찾는 것이 어려울 수 있습니다. 평가는 특정 플레이어 (일반적으로 최대, 네가 맥스 구현을 사용할 때가 아니라)에 대한 우승이라는 일종의 기대치를 반환해야한다는 것을 기억하십시오. 덜 연구 된 게임에 관해서는 좀 더 연구 된 게임과 매우 흡사하게 될 것입니다. 이 게임은 [픽업 스틱] [1]과 매우 밀접하게 연계되어 있습니다. 미니 맥스 (alpha)와 알파 베타 (alpha beta)만을 사용하면 게임이 다루기 쉽다.

비 터미널 위치에 대한 평가 함수를 작성해야하는 경우 여기에 스틱 게임 분석에 대한 약간의 도움이 주어지며, 데이트 게임에 유용할지 여부를 결정할 수 있습니다.

터미널 위치와 그 위치로 이어질 수있는 모든 동작을 살펴봄으로써 결과를 얻는 방법을 모색합니다. 스틱 게임에서, 마지막 위치에 마지막 스틱이 3 개 이하 남아 있습니다. 그 터미널 위치가 즉각적으로 진행되는 위치는 상대방에게 4 개의 스틱을 남겨 둡니다. 목표는 무엇이든 상관없이 상대방에게 4 개의 스틱을 남기고 상대방에게 5, 6 또는 7 개의 스틱을 남겨두고 수행 할 수 있으며 상대방이 당신을 그 자리에 남겨두고 싶습니다. 상대방이 5, 6, 7 중 하나에 있어야하는 장소는 8입니다.이 논리를 계속 반복하면 패턴이 매우 빠르게 사용할 수있게됩니다. 항상 상대방에게 4로 나눌 수있는 숫자를 남겨두고 승리하면, 다른 것은 잃게됩니다.

이것은 다소 단순한 게임이지만 휴리스틱을 결정하는 방법은 과제에 직접 적용될 수 있기 때문에 중요합니다. 마지막으로 이동하는 것이 먼저 일어나고, 한 번에 오직 하나의 날짜 속성 만 변경할 수 있기 때문에 정확히 2 개의 이동이 남아 있어야합니다.등등.

행운을 빈다. 끝까지 무엇을하는지 알려주세요.

[1] : http://emkay.unpointless.com/Blog/?p=42 당신이에 링크 된 날짜 게임의 이해가 무엇에서

Answer 2

가장 단순한 평가 함수의 경우는 1 회, +1은 손실, 0은 완료되지 않은 위치입니다. 당신의 나무가 충분히 깊다면,이 간단한 기능조차도 당신에게 좋은 선수를 줄 것입니다. 높은 브랜치 팩터를 가진 중요한 게임의 경우 일반적으로 몇 가지 휴리스틱 (예 : 체스의 경우 조각에 가중치를 할당하고 합계를 찾을 수있는 등)을 사용하여 더 나은 기능이 필요합니다. Date 게임의 경우 모든 중간 노드에 0을 사용하는 간단한 평가 함수를 사용합니다.

보조 노트로, minimax는이 특정 게임을위한 최상의 알고리즘이 아닙니다. 하지만 이미 알고있는 것 같아요.

Answer 3

, (경우에 저를 수정하시기 바랍니다 선수에 대한 유일한 가능한 결과가이기거나 사이가없는 잃게되는 것 같다 내가 틀렸다).

이 경우 승리 위치 (현재 플레이어는 12 월 31 일에 도착)에 값 1을 지정하고 잃는 위치에 -1 값을 지정합니다 (다른 플레이어는 12 월 31 일에 도착 함).

A_move(day): 
    if day==December 31: 
     return +1 
    else: 
     outcome=-1 
     for each day obtained by increasing the day or month in cur_date: 
      outcome=max(outcome,B_move(day)) 
     return outcome 

B_move(day): 
    if day==December 31: 
     return -1 
    else: 
     outcome=+1 
     for each day obtained by increasing the day or month in cur_date: 
      outcome=min(outcome,A_move(day)) 
     return outcome