Parallelizing checkers game tree generation and searching using MPI

Question

I'm trying to implement an optimal game of checkers in C.

In order to find the optimal move of the checker board that can be made by the machine, I have generated a n-ary game tree using (GLib) in C based on the contemporary state of the checker board by fixing the depth.

And, the heuristic value is calculated for all the leaf nodes present in the game tree which is defined as the number of Machine’s pieces left in the board subtracted by the number of player Opponent’s pieces because kings have more powerful ability than pawns, the heuristic counts each king as two normal pawns, using which alpha beta search is applied.

Its more likely, that increasing the depth of the game tree will finally produce an optimized move, if I try to increase the depth its taking much time to generate the tree and do the heuristic search.

My idea is to generate the first level of the tree independently and distribute the child nodes among the available processors for further execution using MPI?

Is it possible? If yes, how could I parallelize the tree generation and heuristic search using MPI?

And if it’s not efficient, please suggest me some other ways on how I could implement it. Thanks.

Answer 1

Well, it can be parallelized, the question is, how much improvement you expect to get. You are probably generating the sons of initial state in a loop - at the first level, it can be parallelized by splitting the creation of n sons among k threads. Since these tasks will be quite computationally demanding (recursively creating further subtrees), it should be fairly thread-efficient.

However, since you are likely to have a branching factor of the tree larger than the number of cores (or similar), even if your parallelization is linearly effective (and it will not), you will get be able to generate one layer more only.

Do you use alpha-beta pruning? I believe that it would bring much larger benefit than this sort of parallelizing things.