Optimizing C++ Tree Generation
- by cam
Hi,
I'm generating a Tic-Tac-Toe game tree (9 seconds after the first move), and I'm told it should take only a few milliseconds. So I'm trying to optimize it, I ran it through CodeAnalyst and these are the top 5 calls being made (I used bitsets to represent the Tic-Tac-Toe board):
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);
}
}
}
Where should I be looking to optimize it? How should I optimize these 5 calls (I don't recognize them=.
