"MiniMax" 재귀를 구현하는 더 나은 방법

StackOverflow https://stackoverflow.com//questions/22007774

문제

나는 게임에 MinMax 알고리즘을 사용하고 있는데 "알파-베타 가지치기"를 사용하더라도 MinMax 재귀가 너무 오래 걸릴 가능성이 많기 때문에

내 코드는 다음과 같습니다.

min(state,depth,alpha,beta):
    if stopingCond: 
        return value

    for moves in allmoves:
        state.do(move)
        beta = min(beta, max(state,depth,alpha,beta) )
        if alpha >= beta: return beta
    return beta

max(state,depth,alpha,beta):
    if stopingCond: 
        return value

    for moves in allmoves:
        state.do(move)
        alpha = max(beta, min(state,depth,alpha,beta) )
        if alpha >= beta: return alpha
    return beta

나는 때때로 당신이 사용할 수 있다는 것을 알고 있습니다 for 재귀 대신 루프를 반복하지만 그것을 변환하는 방법을 찾을 수 없었습니다.

누구든지 좋은 아이디어가 있다면 기꺼이 듣겠습니다!

감사해요,

도움이 되었습니까?

해결책

일반적으로 minmax의 재귀는 동등한 반복 알고리즘으로 대체될 수 없으므로 가능한 한 빨리 재귀 트리의 일부 분기를 중지하여 성능을 향상시키려는 베타 가지치기와 같은 최적화 방법이 있습니다.

게임에 minmax(또는 일반적으로 재귀 알고리즘)가 전혀 필요하지 않고 다른 기술을 사용하여 최적의 솔루션을 찾는 다른 방법이 있을 수도 있지만 정확한 규칙 세트가 없으면 알 수 없습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top