Finding interactions using randomForest I am trying to use randomForest in R to find interaction terms to add to a model.  My plan was to fit trees with maxnodes=4 (two deep stubs), then compute how often var A is a child of var B and its improved accuracy to measure the importance of the A*B interaction.  Essentially this is leveraging randomForest for the sampling.
To make this work I also wanted mtry=# variables, so all variables would have a chance at being the child of the root variable.
This strategy failed in my data because all trees after the first few were identical. I did decrease cp, but that did not help.  I removed mtry=#vars, and still got all 95% of  trees the same (the last 95%, the first few are different).
When maxnodes=32, I got a good set of trees, but that's not what I needed for determining interactions.  I need to do this because I can't deploy a randomForest in production.
Any ideas why this wouldn't work?  I am coding this myself now using rpart on 2 variable models iterating over the potential good pairs.
 A: You may actually want a really low value of mTry. Setting this equal to a high value or #vars means that you are evaluating every variable as a potential splitter at each node and will result in more deterministic behavior like you are seeing because the best splitter will always be chosen. This phenomena is known as "masking" with regards to importance scores. A lower value of mTry will randomize things more and increase the diversity of the trees. Another way to increase the randomness would be to decrease the number of samples bagged for each tree.
(Note: some implementations use an algorithm that insists on examining at least one non constant variable per node even if they have to examine more then mtry features.  This usually increases accuracy but makes them less sensitive to choice of mTry and can result in more deterministic trees. I'm considering making it optional in my implementation.)
Some work on variable importance including this paper "Understanding variable importances in forests of randomized trees" has suggested that more randomization is good going so fat as to use Extra-Trees. As the splits and splitter become more randomized you would need to incorporate impurity decrease in such an analysis.
The first few trees being the only unique ones sounds like a bug unless the trees are somehow sorted. It is quite possible that there are only a few different trees but the growth of each tree should be independent.
I've done a bit of this sort of analysis and found it useful and interesting in highly dimensional datasets. I'm not sure I would call the results interactions as the two variables could conceivably be entirely independent except in how they relate to the target variable. I'm no sure if there is a terminology widely used in the literature but I think of the downstream variable as having increased local importance on that side of the split (and likely decreased importance on the other).
We also often run random forests to predict every variable in the data set and use importance scores to pick up on non linear relationships between variables not related to a specific target. 
A: Just for clarity, setting mtry=nvar means that you're Bagging trees, and no longer using Random Forests. 
Also, both Bagging and RF should be used with very deep trees (in the original version, fully grown unpruned trees), so requesting 4 terminal nodes does not really make sense.

To make this work I also wanted mtry=# variables, so all variables would have a chance at being the child of the root variable.

If you want to give all variables a chance to play a role in tree structure, you want to set a rather low value of mtry. Otherwise, from the way the CART algorithm works, the splits of all trees will be made on the exact same variables (this is even more true if your trees are shallow). In Bagging trees, the extreme case where mtry=nvar, a major issue is that all trees resemble each other so much that their predictions are very correlated. This is for this very reason that Breiman introduced Random Forests.
