This is some output from my program when searching from the starting position. It might help you get an idea of whether your search is looking at too many positions, and how much slower than mine it is. The node count is actually how many times Board::make_move has been called since the search started. I search depth 1, 2, 3... until I run out of time. This is running on my laptop:
New best move: side=0 depth=1 move=25 score=12 nodes=1 time=0.00011301 nps=8848.74
Depth complete: side=0 depth=1 move= 25 score=12 nodes=131 time=0.00980401 nps=13361.9
New best move: side=0 depth=2 move=25 score=10 nodes=263 time=0.0124841 nps=21066.8
Depth complete: side=0 depth=2 move= 25 score=10 nodes=524 time=0.018996 nps=27584.8
New best move: side=0 depth=3 move=25 score=10 nodes=1046 time=0.0243661 nps=42928.4
Depth complete: side=0 depth=3 move= 25 score=10 nodes=17980 time=0.134464 nps=133716
New best move: side=0 depth=4 move=25 score=8 nodes=51817 time=0.318163 nps=162863
Depth complete: side=0 depth=4 move= 25 score=8 nodes=86064 time=0.521238 nps=165115
New best move: side=0 depth=5 move=25 score=12 nodes=200464 time=1.14466 nps=175130
Depth complete: side=0 depth=5 move= 25 score=12 nodes=2310718 time=13.1338 nps=175937
New best move: side=0 depth=6 move=25 score=8 nodes=6715517 time=37.9794 nps=176820
Depth complete: side=0 depth=6 move= 25 score=8 nodes=11346684 time=65.374 nps=173566

So I am searching around 170K nodes per second, and finishing a depth-4 search took a total of 86K nodes.

Did you do any optimization to get those numbers?

My depth 2 on the starting position is exploring about 17k nodes taking about 46 seconds to do so :S

Did you do any optimization to get those numbers?

No, nothing special. My more ordering is something like North, South, East, West, place horizontal walls, place vertical walls. Not really anything smart.

My depth 2 on the starting position is exploring about 17k nodes taking about 46 seconds to do so :S[/quote]
17k nodes is essentially the full size of the tree, which means that your alpha-beta search is not producing any beta cuts. That doesn't seem right. Regarding the nodes per second (where you are getting something like a slowdown by a factor of 500), it's a matter of picking the right language (I would argue you should use something low-levelish like C or C++ for this task) and understanding a couple of things about what operations are cheap and which ones are expensive.

By the way, my pathfinding function still needs improvement, and I expect to get more nodes per second that way. Transposition tables and some move-ordering heuristics should allow me to search deeper for a given number of nodes.

edit: wish I could delete this post. Going try and re do the search by scratch and hope I get a better result this time

I'm glad to see that I was looking in roughly the right directions, memory allocation and inner loop speed. It's a shame that the pruning isn't working right, I must admit that's not my area of expertise. Overall don't get down that your first cut didn't go so well. Every coder makes mistakes. A friend once decided to write his own sort. Unfortunately he forgot what with handy things like indexer operators in C# that the underlying datatype was a linked list. His solution ended up being O(n^4) and choked on around 10,000 items. Focus on the items to take away from this: frequent memory allocation isn't cheap, everything in the inner loop counts, check that your pruning is working correctly, and learn more about profiling.

Sorry for kind of necroing this, but I just managed to get negamax working (correctly) and while my program is still slow (3-5min a turn), it's still a huge improvement over my 1hour initial time.

Still trying to cut back on my A* searches and find general improvements, but a working copy has been put up at: http://thetaraday.somee.com/Games?id=7 and wanted to thank everyone here for the help.