비 재귀 알파 베타 전정 알고리즘

Question

하드웨어 (fpga)에서 게임 응용 프로그램을 구현하려고합니다. 인식 할 수있는 하드웨어 문제로 인해 함수 재귀를 구현할 수 없습니다. 난 minimax 트리에서 비 재귀 알파 베타 제거 알고리즘을 검색했습니다. 불행히도 적절한 것은 없습니다. 스택 또는 다른 데이터 구조를 사용하여 재귀 문제를 해결하는 알고리즘이나 구현은 인정 될 것입니다.

Answer 1

내 알파 - 베타 maximin 코드를 보면 내가 제안이 :이 방법은 다른에 의해 불려

/** 
    * Returns maximin value of node with alpha-beta pruning for a certain level of forecasting. 
    */ 
double getMaxAlphaBeta(Node currentState, Player player, int level, double alpha, double beta) { 
// [ . . . ] 
if(player == MAX){ 
for(State s : currentState.nextStates){ 
    utility = getMaxAlphaBeta(s, MIN, level - 1, alpha, beta); 
    if (utility > alpha) 
     alpha = utility; 
    if (alpha >= beta) 
     break; 
} 
} 
else{ // [. . .] MIN is playing, do the same things with oppisite sign } 

return newBeta; 
} 

: 하나의 재귀 방법은 다음과 같이 내 알고리즘에있다

이 같은 방법은 :

public Action getMinimaxStrategy(Node currentState, Player player, int level) { 
    double max = this.getMaxAlphaBeta(currentState, player, level, -inf, +inf); 
// [ . . . ] 

내가 뭘 할 것은 이런 일에 두 번째 방법을 변경하는 것입니다 :

,

public Action getMinimaxStrategy(Node currentState, Player player, int level) { 
    DATA max = new DATA(currentState); 
    for(!max.isOptimal){ 
    Array<Node> nextNodes = max.currentState.getNextNodes(); 
    for(Node max.s : nextNodes){ 
     max = this.getMaxAlphaBeta(currentState, player, level, currentAlpha, currentBeta); 
     // [ . . .] 
    } 
    } 
    // [ . . . ] 

여기서 DATA는 재귀 인수 (현재 상태, 플레이어, 레벨, 알파, 베타)와 최적 성 (재귀에서 반환 할 조건)으로 모두 전달하는 데이터 구조입니다.
그런 다음 동일한 논리를 사용하여 첫 번째 방법을 수정할 수 있습니다. 이 솔루션은 최적화 될 수 있으며 시도하지 않았습니다.

원한다면 사용해보십시오. 좋은지 말해보세요.