Other common improvements to game tree searching can be added to this sequential version to obtain further speedups. Some of these improvements can simply be ported over the existing parallel version which I will discuss, with little adjustment to the existing algorithm. Others will require an entire overhaul in the parallel organization and structure.
The first adjustment to the sequential algorithm should be move ordering. This would provide a structure to search the game tree which will yield the greatest cutoffs in the alpha-beta search. The list of generated moves can be ordered according to some arbitrary, but strategically significant, algorithm such as which moves yield the most pieces, or which moves provide stable squares. Usually, moves are ordered according to scores generated by the static evaluation function. If the probable best possible move is searched first, then when other moves are examined, optimal cutoff bounds are set which will greatly reduce the time needed to fully search the tree.
Paired with move ordering is a technique called iterative deepening. Since deeper searches yield more informed, and therefore better moves, searching as deep as is feasible is the best strategy. Iterative deepening searches all moves at one depth, orders the moves it finds and then searches at one level deeper, examining the moves in the order it placed them it at the previous level. It is used to augment strategy for many games in tournaments where each move is allowed a certain amount of time. (Marsland, Olafsson, and Schaeffer, 1986) Thus, faced with few moves to evaluate, it can make use of the surplus of time provided by the simple problem and can be used to search deeper for a better move. Move ordering is essential to minimize the time needed at each level in the search by generating as many cutoffs as possible. While this method would seem to cause so much redundant searching so as to be a waste of time, the extra cutoffs provided by move-ordering often allow it to be faster than an unordered minimax search to a specified depth.
The data structures and function management can be rewritten to streamline the existing code. One area this could make a lot of difference concerns passing board information. Currently, the board is an array of 64 items storing square occupation information, packaged with other information like the number of pieces and the player who is next to move. If the board were passed by reference instead of copied to each function that refers to it, there is the possibility for more reductions in time.
Another speedup concerns move generation. The current move generator wastes a certain amount of time searching squares that are not adjacent to occupied squares. It also searches filled squares. A list of squares where moves might be possible, i.e. empty squares adjacent to filled squares, would give more generation more focus.