A depth-first search generates a lot data. Oridinally, in .NET, that would be fine. You create the data, process it and forget about it - the .NET garbage collector (GC) will release the data from memory when required. That isn't true of Mono 2.6. The garbage collector in Mono 2.6 is kind of rubbish. (See what I did there?) Mono 2.8 has a new garbage collector, but Unity 3.5 uses Mono 2.6. And my Othello game uses Unity 3.5.
For my Othello implementation, every turn by the computer player was a new search. It leaked memory all over the place because the GC wasn't dumping the data. It could easily use a gig of RAM over a game, even with shallow searches (depths of 5 or less).
To resolve this issue, I - though Andrew came up with the idea - used a struct instead of a class for the objects used in the search (EvaluationNode and GameState). I re-used memory by storing search results in arrays where the indexes were reset every turn of the game. This negated the need for garbage collection. In the source code, the classes that manage this process are called the EvaluationNodeBuffer and EvaluationNodeCollection.
These changes turned out to be a really good use and re-use of memory. It is also an excellent example to demonstrate the differences between a struct and a class. It also allowed me to search to much greater depths for the computer player.
A problem with this technique is that it makes it very difficult to write code to re-use part of the search tree between turns. Finding which parts of the tree to prune and to then re-organise the arrays and indexes would be technically tricky and CPU intensive. Therefore, for now, the computer player continues to re-searche all game states between turns. Furthermore, any sort of parallel programming to speed-up the search would be hindered by this approach.
What about Unity 4? That's out soon. Will that support the newer version of Mono? Unfortunately not.
We will be shipping Mono 2.6 with Unity 4.0. This will allow the same subsets of .NET features as in Unity 3, depending on the profile you choose in your player settings. (Unity 4 FAQ)