For the experimental stages do you essentially do what I've been doing and just really on whatever current debugging tools you have and fix things along the way and then once you feel your api's are pretty solid you start performing some unit tests/integration tests where applicable?
In my opinion, in a game there isn't much test you can automate. Testing things that are related to user input / behavior is very hard, it would take a lot of time and effort for probably not much result (never done it so it's just my guess). If you want to find bugs in a game you need testers and you need to give them the tools to properly report issues (describe what you want in the report, have a button to report a bug in the game, have the game capture information about it states and possibly a screenshot).
I just debug problems as they come. Sometimes I add some code to validate the state of some data structure to make sure it doesn't get corrupted. But if the data structure changes it's more code to keep up to date and debug.
Though some of the bugs are starting to get difficult to pin down and can take longer than I would like.
If you can identify a "pattern" in those bug it might be possible to change you coding style (the way you think about API or approach a problem) to prevent those bugs or make them easier to fix.
You may also want to add some tools in you codebase to help you debug (logs, a way to graph/visualize data, save states, memory dump, image dump, profiler...). Asserts help a lot.
But some bugs will just take time to track down.