MiniMax에 대한 혼란 알고리즘

Question

그래서 현재 Mancala와 NIM의 조합 인 게임에서 MiniMax 알고리즘을 중심으로하는 과제를 수행하고 있습니다. 프로그램이 작동하는 방식은 사용자에게 보드의 현재 상태를 묻는 것이며 프로그램은 게임에서 승리하기 위해 사용자가 취해야 할 첫 번째 움직임을 뱉어 내고 있다고 가정합니다. 난 그냥 혼란 스러울거야 가능한 모든 솔루션과 함께 전체 게임 트리를 생성하고 리프 노드에서 먼저 유틸리티 함수를 가지고 MiniMax 알고리즘을 재귀 적으로 실행하거나 MiniMax 알고리즘 내에서 트리를 생성합니까? ? 이 질문이 매우 불투명하다면 미안하지만 나는이 아이디어에 딱 붙어서 이해할 수없는 것 같습니다.

Answer 1

minimax 함수를 작성하는 적절한 방법은 이동을 만들고 해제하여 검색 트리를 탐색하는 것입니다. 한 번에 하나의 게임 상태 만 저장하고, 해당 게임 상태에서 움직이거나 움직이면 전체 트리를 탐색합니다. 이것이 혼란 스럽다면 미니 맥스 psudocode를 살펴 보는 것이 도움이 될 것입니다. minimalax, regularax 및 negamax의 두 가지 공통적으로 사용되는 변종이 있음에 유의하십시오.

int max(int depth){ 
if(this state is terminal){//won, lost, drawn, or desired search depth is reached 
    return value 
} 
//if the state is non terminal 
//we want to examine all child nodes. We do this by making all possible moves from this state, calling the min function 
//(all childs of max nodes are min nodes) and then unmaking the moves. 
int bestVal = -infinity; 
generate move list; 
for(all moves in move list){ 
    makeMove(this move in move list); 
    int val = min(depth -1); 
    unMakeMove(this move in move list); 
    bestVal = max(val,bestVal); 
} 
return bestVal; 

} 따라서

int min(int depth){ 
    if(this state is terminal){//won, lost, drawn, or desired search depth is reached 
     return value 
    } 
    //if the state is non terminal 
    //we want to examine all child nodes. We do this by making all possible moves from this state, calling the max function 
    //(all childs of min nodes are max nodes) and then unmaking the moves. 
    int bestVal = +infinity; 
    generate move list; 
    for(all moves in move list){ 
     makeMove(this move in move list); 
     int val = min(depth -1); 
     unMakeMove(this move in move list); 
     bestVal = min(val,bestVal); 
    } 
    return bestVal; 
} 

가 하나의 트랙을 유지하여 전체 트리를 탐색 : 더 intuituve하지만 실제로 나는 negamax 변형을 추천 할 것입니다 있기 때문에 훨씬 간단하기 때문에 psudeocode는 최소 최대입니다 게임 상태를 재귀 적으로 만들고 미동 중으로 만들 수 있습니다. 알파 베타 가지 치기에 대한이 견해를 이해하면 또한이 함수는 이동 자체가 아닌 최상의 이동 값만 반환한다는 점도 알아 두십시오. 루트에서 호출 할 수있는 최적의 이동을 추적하는 특수 기능이 필요합니다.