minmax 알고리즘에 대한 의사 코드

Question

minmax 알고리즘에 대한 의사 코드를 가져오고 싶습니다. 나는 2 개의 함수, def maxAgent (gameState, depth)와 minAgent를 만들어야 만한다. 그것에 대한 권리와 쉬운 의사 코드를 가진 시체가 있습니까?

Answer 1

두 명의 플레이어 A와 B가 차례로 게임을합니다.

주어진 보드 위치 P를 평가하는 점수 함수 f가 주어집니다. f (P)의 값이 클수록 A는 더 좋고 B는 더 나음 (즉 f (P)는 "양호한" P는 더 이상 미리보기를하지 않고 A에 대한 것임). P가 잎 노드의 경우

는 보드 위치 P.

을 고려 우리가 점수로 F (P)을 반환 (즉, P는 승리 위치 또는 우리가 원하는대로 우리는 멀리 앞서 보았다) 이 노드에 대해.

그렇지 않으면 P는 리프 노드가 아니며 자식 C1, ..., Cn을가집니다. 우리는 S1, ..., Sn을 제공하여 아이들의 점수를 재귀 적으로 계산합니다.

만약 A가 P에서 뛰면, A는 항상 그의 이점을 극대화하기 위해 플레이 할 것이기 때문에 P에 대한 점수는 max {S1, ..., Sn}이됩니다.

B가 A에서의 이점을 최소화하기 위해 항상 재생되므로 B가 P에서 재생되면 P의 점수는 min {S1, ..., Sn}이됩니다.

코드로 전환하기에 충분해야합니다.

일단 해보신 후에는 알파 베타 제거 (prune)를 수행하십시오. 그러면 검색의 양이 급격히 줄어 듭니다. Alpha-beta pruning은 A가 B가 A의 최대 이점을 M으로 강제 할 수 있다고 추론하면 B가 A 옵션을 허용하지 않으므로 M보다 큰 모든 하위 트리를 고려할 필요가 없다는 아이디어에 기반합니다.

Answer 2

minmax 알고리즘은 플레이어 A의 점수를 최대화하고 플레이어 B의 점수를 최소화하려고합니다. 노드가 주어지면 최대 (A의 경우) 또는 최소 (B의 경우)를 취하여 최적의 플레이에서 최종 결과를 찾을 수 있습니다. 후계 노드에 대한 점수의 리프 노드는 (A의 1 -1 B에 대한) 우승자를 할당한다고 가정하면 다른 모든 노드는 0의 점수가 동안 다음

getMaxScore(node) { 
    score = node.score; 
    for each child node 
     score = max(score, getMaxScore(node)) 
    next 

    return score; 
    } 

처럼 뭔가 A의 최종 승리의 결과를 계산할 수

이것은 기본 알고리즘입니다. 스코어가 1이되고 점수를 얻으면 곧바로 평가할 수 있습니다.

알고리즘은 B, getMinScore와 동일하며 min 함수 만 사용하고 단락이있는 경우, -1을 찾습니다.