C# minimax tree realization

Question

I'm trying to write C# Chess AI.

At that moment I have to build my minmax tree. I try by using recursion, but my recursive functions has to call itself about 1 000 000 times for every node. I get Stack Overflow exception after about... 60 000 calls.

Answer 1

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.

Answer 2

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.

Answer 3

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).

Answer 4

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.