Given that the depth of the recursion might not be known you might want to stop to at a reasonable limit like 10 moves in advance and/or ignore trees that have a lower utility score. By adding extra constraints such as these you can also ensure that a solution will be found quickly without having to optimize extensively.

As echoed by others it sounds like you probably have a bug given your large number of iterations. It might be possible to prune out a variety of rules or chose a different search strategy to reduce the number of iterations required, such as iterative deepenning, A* or perhaps a Genetic Algorithm for fun,

It would be much better to return a result even if it is not perfect rather than failing after searching the tree too deep.

Good luck.

I guess you are using a depth first search. This isn t too useful when the search space is so large. When implementing minimax you can use a breadth first search implemented as a depth first search with iterative deepening.

You should have a maximum number of levels you are allowed to recurse as a parameter to your functions, and decrease that by one each time you call your function recursively, until you hit zero when you stop and backtrack. Start with a small maximum depth and slowly increase it until you find an acceptable solution, or else run out of time.

Most chess search programs can only search to depth 9 or 10. This is not enough to overflow the stack at all.

You probably have an error in your program. In any case, you do need to have a depth limit on your search as you will not be able to do full-width search (exploring all possibilities across all moves up to a given depth) without a depth limit, since a chess game is potentially of unlimited depth (except for the repeated positions or limit on moves rule).

After you search to about depth 9, you have to use a static board evaluation function to evaluate and score the position. You then use the mini-max algorithm to prune branches of the search tree. It s still an exponential search though.

There are also techniques such as quiescent search, where you continue searching in positions where the position is not stable (i.e. if a piece can be taken or the king is in check).

if you are interested in learning how to write a C# Chess Engine I invite you to visit the Computer Chess Blog

The blog describes a creation of a C# Chess Engine from the first steps, providing C# code examples.

The page you might be the most interested in is: Move Searching and Alpha Beta

This article gives a detailed explanation of Min Max and the Alpha Beta search algorithms including C# code examples of both.