Thanks for the help guys. I've stopped cloning the game state and instead just undo moves which sped it up a lot, but now I'm using more complicated heuristics that mean I can still only look 5 moves ahead. :( I think the Node creation might be slowing it down, but I can't pass the scores around without objects so I'm pretty stuck there and haven't found a profiler that works with the appletviewer yet. I've updated the online game and the source code if you want to check it out. I'm not sure which of the heuristics I can drop without making it dumber, maybe you can check it out please?

Right now the heuristics are:
- Dominate the middle of the board, especially if the user is dropping coins there.
- All possible 2 and 3+ links are scored for each player and then subtracted from the other.
- Double checks that all moves it wants to use won't give the user an instant win.
- And then the base heuristics if the state is a win, lose, or tie.

The AI plays quite well now and it managed to beat the four online connect 4 games I found, except for the one using an 8-ply database, so I'd say it's good enough and I should really stop obsessing over it for now and work on network play instead! :)

Again, thanks for the help. Really impressed with the community here, much more helpful than other boards I've looked at where noobs just get shot down.