Optimizations
A normal game will take at least 49 moves, as the board has 49 boxes. Depending on the rules, games can take shorter if a player is surrounded by a layer of two other pieces, or if a player has no more pieces. Off course games can also take longer, because with a jump move pieces are only replaced. Therefore an ataxx game can go on forever. A normal game will last something around 68 steps, thus 34 steps per player.
Each time black has to think out a move, it has the choice of all possible moves. The number of possible moves lies somewhere between 0 and 100 in a normal game, but can be as much as 200. I don't believe more than 200 moves are possible, but I can not proof that. The average number of possible moves lies around 43, depending on your and the computers play style. If a player is in the advantage and thus has more stones, the number of possible moves for that player increase. To the end of the game, the number of possible moves decreases rapidly, because there are no more empty boxes.
200 possible moves
Let's take 43 as the average number of possible moves and 68 for the duration of the game in steps. That is a very big number. But then I mean a very big number. In the bottom level only are 4368, which is about 10112.
So lets restrain ourselves to a limited depth. A depth of five moves would already result in 150,508,644 boards to be examined. To look three moves ahead, however, is doable, as this takes only 81,400 boards to be examined. One board can be examined in a couple of hundreds of microseconds with modern computers, so to choose the best move would take in the order of 10 seconds.
Looking three moves ahead seems fine, but 10 seconds is still a bit slow. To decrease this number, one can do one of two things: decrease the search depth or decrease the number of possible moves. Decreasing the search depth to two makes decisions take less than a second, but makes the computer rather dumb. So here are some tactics on decreasing the number of possible moves.
Removing duplicates
Probably there is a method/function/procedure in every ataxx game which finds all possible moves. This method generally find out for every black piece in which empty box it can go. So there are no real duplicate moves.
However, there are moves that result in the same board. Whether one moves a piece from (0,0) to (0,1) or from (1,0) to (0,1) makes no difference. In both cases all pieces stay put, except there is an extra piece on (0,1). If you join these moves into one, or remove all but one move which result in the same board, the number of possible moves can be drastically reduced. The number of normal moves can not exceed the number of empty boxes, which is 45 at the start of the game.
Removing jumps
Of course there are also jumps, where it does matter where the move originated from. Here is also some optimization possible. A player would never make a jump move if a normal move to the same position is possible. After all, this adds an extra stone and leaves less room for the opponent. If a normal move can be done to the same place where to a jump can be done, the jump can be removed.
Removing low scores
Normally, search algorithms search all board states. However, one can safely assume that no player will make a move that is not in advantage to him. Furthermore, if he does make such a move, for example a jump move with no surrounding opponent pieces, it is no concern to the other player.
It is important that this function is implemented within the search algorithm. When the low scores are removed before the possible moves are passed to the search algorithm, each board is examined at least twice: one time to remove the boards with low scores, and one time within the search algorithm. This probably do more bad than good.
The effect of optimization
With the first two of above optimizations enabled (removing duplicate moves and removing jumps if a normal move is possible), the average number of possible moves is only 19. Now we have "only" a search space of somewhere near 1087. This is still not searchable off course, but a depth of 3 now takes 7,240 boards instead of 81,400. This is a 1:11 improvement, so choosing a best move is now a matter of seconds. With some tuning and the right algorithm, a depth of 4 is now also reachable: 137,561 boards.