체스 C : Negamax 구현은 작동하지만 때로는 1을 찾지 못합니다.

Question

알파 베타 제거 및 퀴즈 검색을 사용하여 negamax를 구현했는데 작동하는 것처럼 보입니다 ... 때때로 컴퓨터는 1, 심지어는 비록 그것을 막기 위해 할 수있는 움직임이 있었지만 (이것은 깊이있는 4에서 일어 났고, 그것은 분명히 발견되어 져야만했습니다).

static double alphaBetaMax(double alpha, double beta, int depthleft, game_t game, bool player) 
{ 
move_t *cur; 
move_t *tmp; 
double score = 0; 
    bool did_move = false; 

cur = getAllMoves(game, player); //getAllMoves initilizes a global list of moves, firstMove 
if(cur == NULL) /* check mate*/ 
    return -9999999*(player*2-1); 
tmp = firstMove; 
firstMove = 0; 

while (cur != NULL) 
{ 
    game_t copy; 
    if(depthleft<=0 && !isCapture(game, cur)) { /* Quiescence search */ 
      cur = cur->next; 
       continue; 
    } 
      did_move = true; 
    copyGame(game, &copy); 
    makeMove(&copy, *cur); 
    firstMove = NULL; 
    score = -alphaBetaMax(-beta, -alpha, depthleft - 1, copy, !player); 
    if(board_count > MAX_BOARDS) 
     break; 

    freeGame(copy); 
    if(score > alpha) 
     alpha = score; 

    if (beta <= alpha) 
     break; 
    cur = cur->next; 
} 
firstMove=tmp; 
freeMoves(); 

    if(!did_move) 
     alpha = evaluate(game)*(player*2-1); 
return alpha; 
} 

move_t* getBestMove(game_t game, int player, unsigned int depth) // initial call 
{ 
move_t *cur = NULL, *best = NULL; 
move_t *tmp; 
double alpha = -DBL_MAX, score = 0; 
freeMoves(); 
firstMove = NULL; 
cur = getAllMoves(game, player); 
tmp = firstMove; 
firstMove = 0; 

while (cur != NULL) 
{ 
    game_t copy; 
    copyGame(game, &copy); 
    makeMove(&copy, *cur); 
    firstMove = NULL; 
    score = -alphaBetaMax(-DBL_MAX, -alpha, depth-1, copy, !player); 
#ifdef PRINT_SCORES 
    printf(" <%c,%d> to ", cur->x1 + 'a', cur->y1 + 1); 
    printf("<%c,%d>", cur->x2 + 'a', cur->y2 + 1); 
    printf(" - score %f\n", score); 
#endif 
    freeGame(copy); 

    if(board_count > MAX_BOARDS) 
     break; 

    if (score > alpha) { 
     alpha = score; 

     if (best != NULL) { 
     best->next = NULL; 
     free(best); 
     } 
     best = copyMove(*cur); 
    } 
    cur = cur->next; 
} 
firstMove = tmp; 
freeMoves(); 

if(board_count > MAX_BOARDS) { 
    free(best); 
    return 0; 
} 
return best; 

} 

Answer 1

귀하의 코드는 Q-검색, 평가 및 검색 알고리즘 등 많은 분야에서 잘못 구현 : 경험이 많은 사람이 내 코드를보고 아마도 내가하지 않은 것을 볼 수 있다면 나는 그것을 감사 정말 것 그 자체. 예를 들어 qsearch가 올바르지 않습니다. 스탠드 팻 점수를 얻고 모든 포획과 비 움직임을 생성해야합니다. qsearch에 이러한 동작을 재귀 적으로 사용하십시오.

하지만 대부분 이며, 수표에 대해 반환하는 점수는 잘못되었습니다. Nega-max의 경우, 장군의 체크 카드 점수는 턴에 대해 플레이어에게 반환되어야하며 반환되어야합니다. 즉, 메이트에의 음수 값 을 반환해야합니다.

귀하의 코드

반환 -9999999 * (플레이어 * 2-1);

은 플레이어가 false (false == 0) 인 경우 양수 값을 반환합니다. nega-max는 http://en.wikipedia.org/wiki/Negamax으로 읽습니다. 알고리즘에 = -∞

: 당신이

bestValue를 볼 수 있습니까? 당신은 턴이 누구인지는 상관하지 않습니다. 당신은 상대자에 대해 부정적인 가치를 돌려 주어야합니다.