Optimizing C++ Tree Generation

Question

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=.

Answer 1

You're getting all wrapped up in data structure. Don't build the tree, just walk it. Have only one copy of the board. At each node in the search tree, just modify the board, and on the way back out, un-modify it.

And if you want to know what it's doing, just hit the pause button at random. It will show you why it's in those routines you don't recognize that are taking all the time.

Answer 2

Those functions are typically trivial. That means that an optimized ("release") build will typically have them inlined. However, in a debug build they're not. The result is that a debug build is slower, but allows you to set breakpoints on those functions. So, the "milliseconds comment" should be applied to the release build, where you wouldn't even have those functions anymore.

Answer 3

Honestly, and I don't mean this as a slam against you, you're asking us to examine a poorly documented piece of code that is a smaller part to a larger code base. We don't have the context that gives much information. I personally am also turned off by examining others' code when it doesn't appear that they've done all they can do to examine it themselves yet (and I don't mean this to say I'm annoyed at you or anything, just that my eyes are glazing over looking at your code).

I recommend you run your code through a profiler and determine what exactly is taking so much time. Treat this profiling like you're debugging. When you find a module taking a long time, examine that module in small sections (as if you're hunting for a bug) to see why.

This will allow you to ask a much more informed question if you still need to ask something.

Answer 4

Let me add that if your system is taking 9 seconds to do its work, that means that something is being called billions and billions of times more than it should. If you don't have release level profiling abilities, place a few global counters in your code and increment them every time the code they are in is called. This will give you a poor man's profile that will work on release builds. If you see a billions calls somewhere you don't expect, you now have a place to look closer.

In reality, Tic-Tac-Toe's entire move tree should be trivial to store as a hash if you need the speed. 9! moves just isn't that big of a domain (anymore). 362k moves shouldn't break the bank, and that's a brute force analysis. That domain can be cut way down when you take into consideration all the various symetries of data.

Bah, here's how I would do it if I was coding it since people have latched onto my back of the envelope math:

I wouldn't even go the tree route, just some rules and be done.
Turn 1. Go in center.
Turn 2. If center unoccupied, go there, else go in corner
Turn 3. If opponent filled a corner, go in opposite corner, else go in corner - you've won.
Turn 4. Block if needed. If Xs occupy opposite corners, fill edge. If Xs occupy center and opposite corner, fill corner. If Xs occupy opposite edges, fill corner and win. If Xs fill adjacent edges, Fill corner betweem them.
Turn 5 Win if possible. Block if needed. Else go in corner opposite of adjacent edge move and win.
Turn 6-9 Win if possible. Block if needed. Else, place random towards draw.

Answer 5

You've posted far too little of your code.

Answer 6

The tic-tac-toe game tree is very redundant. Eliminating rotated and mirrored boards will reduce the final ply of the game tree by 3 or 4 orders of magnitude. No amount of optimizations will make bubblesort as fast as introsort.

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 7

You are asking how to optimize the code however you should also be asking how to optimize the algorithm.

There are two things that I immediately see.

1. As "Michael Dorgan" stated generate the tree of moves once.

2. How many broads are you generating in your tree? 362880? Your code appears to be generating redundant entries. For example, with an empty board there are actually three moves not nine moves. All other combinations are the board rotated (which are equal). You can reduce the number of boards that needs to be generated and speed up the generation of the tree.

Here are the three first moves(rotate the last two board to generate the other boards)

 | |
 |X|
 | |

 |X|
 | |
 | |

X| |
 | |
 | |