As computing power has grown, the trend in experimental design has been from techniques requiring little computation towards techniques providing better, more general results at the cost of additional computation. This paper continues this trend presenting three new methods for designing experiments. A summary of previous work in experimental design is provided and used to show how these new methods generalize previous criteria and provide a more accurate analysis than prior methods. The first method generates experimental designs by maximizing the uncertainty of the experiment's result, while the remaining two methods minimize an approximation of the variance of a function of the parameters. The third method uses a computationally expensive discrete approximation to determine the variance. The methods are tested and compared using the logistic model and a Bayesian classifier. The results show that at the expense of greater computation, experimental designs more effective at reducing the uncertainty of the decision boundary of the Bayesian classifier can be generated.

In a real‐time task an action must be executed given limited computation. One approach to limited computation is to search a tree of possible action sequences to a fixed depth and then execute an action with the lowest associated backed‐up cost. The standard algorithm for such a search is Depth‐First Branch‐and‐Bound (DFBB), also known in the Artificial Intelligence literature as Minimin with Alpha Pruning. This article shows that a depth‐bounded extension of a popular iterative algorithm called IDA has a surprisingly large range of search trees on which it outperforms DFBB—something previous analytical results do not predict. We prove that the extended algorithm, which we call DIDA, is correct, is guaranteed to terminate, and is asymptotically (i.e., on its last iteration) as efficient as DFBB—assuming a consistent heuristic is used. We also prove that both algorithms are guaranteed not to decrease their accuracy with a deeper search, assuming a consistent heuristic. Because accuracy is generally correlated with decision quality, the time saved by visiting fewer states translates to deeper searches which translates to better decisions. Results from random search trees show that DIDA is most efficient when the path cost + leaf node heuristic value is distributed with low variance; as branching factor increases, the range for which DIDA is more efficient also increases. Results with Eight, Fifteen, Twenty‐four, and Ninety‐nine Puzzle implementations of both algorithms—all domains with low variance of path cost + leaf node heuristic value—show that DIDA significantly outperforms DFBB.

The article presents an algorithm that combines Minimax's alpha-beta pruning with IDA*'s depth-first iteration and forward pruning. We prove that the algorithm, which we call Two - agent IDA* (TIDA*), is correct and is guaranteed to terminate—provided its heuristic is consistent. Minimax search has been applied with other ‘forward’ pruning or selective search techniques, but none of these techniques is guaranteed to compute the correct minimax result. We also prove that TIDA*'s accuracy monotonically increases with search depth, thus avoiding certain pathologies. Empirical results with 3×3, 4×4 and 5×5 Tic-Tac-Tff grids show that TIDA* outperforms MAB, provided both algorithms use the same consistent heuristic. However, results on a more complex search space—the 3D version of Tic-Tac-Tff—show that MAB with a good inconsistent heuristic can outperform TIDA* with a consistent heuristic even though TIDA* searches 1 to 1·5 levels deeper. This result and other empirical results suggest that an algorithm that starts with MAB and an inconsistent heuristic and then shifts near the end of the game to TIDA* with a consistent heuristic can outperform either algorithm. Finally, we present results on a forward-pruning version of MAB and show that under certain conditions it can outperform TIDA*, provided both use the same consistent heuristic.

. IDA* is the standard linear-space single-agent search algorithm, and here has been extended by adding upper-bound heuristics for earlier pruning. It is proved that the extended algorithm, called UIDA*, will visit no more states than IDA*, is correct and is guaranteed to terminate. It is also proved that the more accurate its heuristics, the better its performance. Empirical results from random trees validate these theoretical results. Results from an Eight Puzzle implementation of UIDA* show that upper-bound heuristics reduce search complexity most on shallow search trees and sometimes eliminate search entirely.