C++ 트리 생성 최적화

Question

Tic-Tac-Toe 게임 트리 (첫 번째 이동 후 9 초)가 생성되며 몇 밀리 초만 걸릴 것이라고합니다. 그래서 내가 CodeAnalyst를 통해 실행, 그것을 최적화하기 위해 노력하고있어 이들 상위 5 개 통화가 이루어지고있다 (필자는 틱택 보드를 표현하기 위해 bitsets을 사용) :

std::_Iterator_base::_Orphan_me 

std::bitset<9>::test 

std::_Iterator_base::_Adopt 

std::bitset<9>::reference::operator bool 

std::_Iterator_base::~_Iterator_base 

void BuildTreeToDepth(Node &nNode, const int& nextPlayer, int depth) 
{ 
    if (depth > 0) 
    { 
     //Calculate gameboard states 
     int evalBoard = nNode.m_board.CalculateBoardState(); 
     bool isFinished = nNode.m_board.isFinished(); 
     if (isFinished || (nNode.m_board.isWinner() > 0)) 
     { 
     nNode.m_winCount = evalBoard; 
     } 
     else 
     { 
     Ticboard tBoard = nNode.m_board; 
     do 
     { 
      int validMove = tBoard.FirstValidMove(); 
      if (validMove != -1) 
      { 
       Node f; 
       Ticboard tempBoard = nNode.m_board; 
       tempBoard.Move(validMove, nextPlayer); 
       tBoard.Move(validMove, nextPlayer); 
       f.m_board = tempBoard; 
       f.m_winCount = 0; 
       f.m_Move = validMove; 
       int currPlay = (nextPlayer == 1 ? 2 : 1); 
       BuildTreeToDepth(f,currPlay, depth - 1); 
       nNode.m_winCount += f.m_board.CalculateBoardState(); 
       nNode.m_branches.push_back(f); 
      } 
      else 
      { 
       break; 
      } 
     }while(true); 
     } 
    } 
} 

어디에서보고되어야한다 그것을 최적화? 이 5 가지 호출을 최적화하려면 어떻게해야합니까? (나는 인식하지 못합니다.)

Answer 1

tic-tac-toe 게임 트리가 매우 중복되어 있습니다. 회전 및 미러링 된 보드를 제거하면 게임 트리의 최종 플라이가 3 ~ 4 배 감소합니다. 최적화의 양은 intortort만큼 빠르지 않습니다.

struct Game_board; 

struct Node 
{ 
    Game_board game_board; 
    Node* parent; 
    std::vector<Node*> children; 
    enum { X_Win, Y_Win, Draw, Playing } outcome; 
}; 

// returns the same hash value for all "identical" boards. 
// ie boards that can be rotated or mirrored to look the 
// same will have the same hash value 
int hash(const Game_board& game_board); 

// uses hash() function to generate hashes from Node* 
struct Hash_functor; 

// nodes yet to be explored. 
std::hash_set<Node*,Hash_functor> open; 

//nodes already explored. 
std::hash_set<Node*,Hash_functor> closed; 

while(! open.empty()) 
{ 
    Node* node_to_expore = get_a_node(open); 
    assert(node_to_expore not in close or open sets) 
    if(node_to_expore is win lose or draw) 
    { 
     Mark node as win lose or draw 
     add node to closed set 
    } 
    loop through all children of node_to_expore 
    { 
     if(child in close) 
     { 
     add node from closed set to children list of node_to_expore 
     } 
     else if(child in open) 
     { 
     add node from open set to children list of node_to_explore 
     } 
     else 
     { 
     add child to open set 
     add child to children list of node_to_expore 
     } 
    } 
} 

Answer 2

데이터 구조가 모두 포장되어 있습니다. 트리를 작성하지 말고 그냥 걸어 가십시오. 검색 트리의 각 노드에서 보드를 수정하고 취소하면 수정되지 않습니다.

그리고 무엇을하고 있는지 알고 싶으면 무작위로 일시 중지 버튼을 누르십시오.

Answer 3

이러한 기능은 대개 사소한 것입니다. 즉, 최적화 된 ("릴리스") 빌드는 일반적으로 인라인됩니다. 디버그 빌드는 그렇지 않습니다. 결과는 디버그 빌드가 느리지 만 해당 함수에 중단 점을 설정할 수있게합니다. 따라서 "밀리 초 주석"을 릴리스 빌드에 적용해야합니다.이 빌드에서는 더 이상 이러한 기능을 사용할 수 없습니다.

Answer 4

정직하게 말하자면,이 코드는 슬램이 아닙니다. 더 큰 코드베이스에서 더 작은 부분 인 코드를 잘 살펴 봐야합니다. 많은 정보를 제공하는 컨텍스트가 없습니다. 나는 개인적으로 다른 사람들의 코드를 조사함으로써 자신들이 아직 스스로 조사하기 위해 할 수있는 모든 일을했다는 것을 알지 못했을 때 (나는 당신이나 다른 사람에게 화가났다는 말을하지 않는다. 그냥 내 눈이 당신의 코드를 보며 유약하고있다).

프로필러를 통해 코드를 실행하고 정확히 시간이 오래 걸리는지 확인하는 것이 좋습니다. 디버깅하는 것처럼이 프로파일 링을 처리하십시오. 오랜 시간 동안 모듈을 찾았다면 작은 부분에서 모듈을 검사하여 (버그를 사냥하는 것처럼) 이유를 확인하십시오.

이렇게하면 여전히 물어볼 필요가있는 정보가 많이 묻는 질문을 할 수 있습니다.

Answer 5

시스템에 작업을 수행하는 데 9 초가 걸렸다면 이는 무언가가해야하는 것보다 수십억 배 이상 불리우는 것을 의미합니다. 릴리스 수준 프로파일 링 기능이없는 경우 코드에 몇 개의 전역 카운터를 배치하고 코드가 호출 될 때마다 코드를 증가 시키십시오. 이것은 릴리스 빌드에서 작동하는 가난한 사람의 프로파일을 제공합니다. 예상하지 못한 어딘가에서 수십억 달러의 통화를 보게되면 이제 더 가까이 다가 갈 수있는 기회가 생깁니다.

실제로 Tic-Tac-Toe의 전체 이동 트리는 속도가 필요한 경우 해시로 저장하는 것이 쉽습니다. 9! 움직이는 것만으로는 도메인 (그 이상)이 그다지 크지 않습니다. 362k 이동은 은행을 붕괴해서는 안되며, 이것은 무차별 대결 분석입니다. 이 도메인은 모든 다양한 데이터를 고려할 때 잘릴 수 있습니다.

나는 심지어 트리 경로, 단지 몇 가지 규칙을 갈 것이며, 수행 할 수 :

바하마, 여기 사람들이 봉투 수학의 내 다시에 래치했기 때문에 내가 코딩 된 경우 내가 그것을 할 것입니다 방법입니다.
Turn 1. 가운데로 이동합니다.
턴 2. 센터가 비어 있다면 거기로 가십시오. 그렇지 않으면 코너에 들어갑니다.
3 턴. 상대방이 코너를 채우는 경우, 반대쪽 코너로 가십시오.
4. 필요한 경우 차단하십시오.Xs가 반대 모서리를 차지하면 모서리를 채 웁니다. Xs가 중심과 반대편 모서리를 차지하면 코너를 채우십시오. Xs가 반대편 가장자리를 차지하면 코너를 채우고 승리하십시오. X가 인접한 모서리를 채우는 경우 모서리를 채 웁니다.
가능한 경우 5를 켭니다. 필요한 경우 차단하십시오. 다른 모서리에 인접한 가장자리 이동 및 승리의 모퉁이에 가십시오.
가능한 경우 6-9 승리하십시오. 필요한 경우 차단하십시오. 그렇지 않으면 무작위로 그리다.

Answer 6

코드를 너무 적게 게시했습니다.

Answer 7

코드를 최적화하는 방법을 묻는 중이지만 알고리즘을 최적화하는 방법을 묻는 것이 좋습니다.

즉시 볼 수있는 두 가지 사항이 있습니다.

1. "마이클 도간"이 명시한대로 움직이는 나무를 한 번 생성합니다.

2. 트리에서 몇 개의 브로드 밴드를 생성하고 있습니까? 362880? 코드가 중복 항목을 생성하는 것으로 보입니다. 예를 들어, 빈 보드에서는 실제로 9 개의 이동이 아닌 3 개의 이동이 있습니다. 다른 모든 조합은 회전 된 보드 (동일한)입니다. 생성해야하는 보드 수를 줄이고 트리 생성 속도를 높일 수 있습니다. 여기

이

 
| | 
|X| 
| | 

|X| 
| | 
| | 

X| | 
| | 
| |