이미 존재하는 Chess Engine에 멀티 쓰레딩 구현 C

Question

멀티 스레딩없이 작동하는 C의 기존 체스 엔진을 멀티 스레딩을 수정할 수 있는지 알고 싶습니다. 나는이 주제에 대한 경험이 없으며 약간의 지침을 고맙게 생각한다.

EDIT : 더 구체적으로 말해서 negamax를 구현하여 멀티 스레드 호환이 가능하도록 추가 할 수있는 것이 있습니까? :

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); 
    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; 
} 

Answer 1

빠른 체스 엔진은 위치 평가 캐싱과 알파/베타 전략에 의존합니다. 캐싱 위치를 지정하고 스레드를 안전하게 처리합니다. 및은 빠릅니다. 알파/베타 전략은 겉으로보기에는 최선의 움직임에 따라 달라집니다. 전에 다른 동작을 평가하기 시작합니다. 또한 여러 스레드를 사용하기가 어렵습니다.

초심자 작곡가 모차르트 : "교향곡을 작곡하는 방법을 말해 줄 수 있습니까?" 모차르트 초보자에게 : "어렸을 때 처음에는 좀 더 쉬운 것을 시도해야 할 것입니다."초심자부터 모차르트 : "내가 지금보다 훨씬 젊었을 때 교향곡을 썼다."모차르트가 초심자에게 : "그렇지만 나는 그렇지 않았다. 누군가에게 물어야한다 "고 말했다.

Answer 2

알파 베타 프 루닝은 기본적으로 본질적으로 단일 스레드입니다. 동적 트리 분할의 변형을 사용하는 성공적인 접근 방식은 기본적으로 동시에 여러 가지 브랜치를 검색하는 것을 의미합니다. 그러나 다음 분기 (또는 베타 컷)가 검색 ​​될 가능성 (잘 조정 된 엔진에서)은 일반적으로 메모리 대기와 같은 다른 병렬 처리 병목 현상보다 중요하지 않습니다.

NegaScout 또는 PVS와 같은 "재검색"알고리즘을 사용하여 검색을 수정하십시오. 작은 코드를 변경하면 현재 순수한 알파 베타보다 우수한 개선 효과를 얻을 수 있습니다. 다음으로 이동 순서를 미세 조정하십시오. 효율적인 베타 컷을 얻을 수 있습니다. 그런 다음 베타 컷 기회를 기반으로 트리를 분할 할 수 있습니다. 일반적으로 트랜스 포즈 테이블이나 킬러 이동에서 움직임이 발견 될 때 컷오프 가능성이 높아지고 나쁜 캡처와 조용한 움직임을 찾기 시작할 때 기회가 줄어 듭니다.

CPW를 살펴보고 YBWC 알고리즘에 대해 생각해보십시오. Young Brothers Wait Concept