Search

This paper concerns the problem of enhancing the well-known alpha-beta search technique for intelligent game playing. It is a well-established principle that the alpha-beta technique benefits greatly, that is to say, achieves more efficient tree pruning, if the moves to be examined are ordered properly. This refers to placing the best moves in such a way that they are searched first. However, if the superior moves were known a priori, there would be no need to search at all. Many move ordering heuristics, such as the Killer Moves technique and the History Heuristic, have been developed in an attempt to address this problem. Formerly unrelated to game playing, the field of Adaptive Data Structures ADSs is concerned with the optimization of queries over time within a data structure, and provides techniques to achieve this through dynamic reordering of its internal elements, in response to queries. In earlier works, we had proposed the Threat-ADS heuristic for multi-player games, based on the concept of employing efficient ranking mechanisms provided by ADSs in the context of game playing. Based on its previous success, in this work we propose the concept of using an ADS to order moves themselves, rather than opponents. We call this new technique the History-ADS heuristic. We examine the History-ADS heuristic in both two-player and multi-player environments, and investigate its possible refinements. These involve providing a bound on the size of the ADS, based on the hypothesis that it can retain most of its benefits with a smaller list, and examining the possibility of using a different ADS for each level of the tree. We demonstrate conclusively that the History-ADS heuristic can produce drastic improvements in tree pruning in both two-player and multi-player games, and the majority of its benefits remain even when it is limited to a very small list.

Most game tree search algorithms consider finding the optimal move. That is, given an evaluation function they guarantee that selected move will be the best according to it. However, in practice most evaluation functions are themselves approximations and cannot be considered "optimal". Besides, we might be satisfied with nearly optimal solution if it gives us a considerable performance improvement. In this paper we present the approximation based implementations of the fuzzified game tree search algorithm. The paradigm of the algorithm allows us to efficiently find nearly optimal solutions so we can choose the "target quality" of the search with arbitrary precision --- either it is 100% (providing the optimal move), or selecting a move which is superior to 95% of the solution space, or any other specified value. Our results show that in games this kind of approximation could be an acceptable tradeoff. For example, while keeping error rate below 2%, the algorithm achieved over 30% speed improvement, which potentially gives us the possibility to search deeper over the same time period and therefore make our search smarter. Experiments also demonstrated 15% speed improvement without significantly affecting the overall playing strength of the algorithm.

Fuzzified game tree search algorithm is based on the idea that the exact game tree evaluation is not required to find the best move. Therefore, pruning techniques may be applied earlier resulting in faster search and greater performance. Applied to an abstract domain, it outperforms the existing ones such as Alpha-Beta, PVS, Negascout, NegaC*, SSS*/ Dual* and MTD(f). In this paper we present experimental results in real domain games, where the proposed algorithm demonstrated 10 percent performance increase over the existing algorithms.

We define Realtime Online solving of Quantified Constraint Satisfaction Problems (QCSPs) as a model for realtime online CSP solving. We use a combination of propagation, lookahead and heuristics and show how all three improve performance. For adversarial opponents we show that we can achieve promising results through good lookahead and heuristics and that a version of alpha beta pruning performs strongly. For random opponents, we show that we can frequently achieve solutions even on problems which lack a winning strategy and that we can improve our success rate by using Existential Quantified Generalised Arc Consistency, a lower level of consistency than SQGAC, to maximise pruning without removing solutions. We also consider the power of the universal opponent and show that through good heuristic selection we can generate a significantly stronger player than a static heuristic provides.

The NeuroDraughts is a good automatic draughts player which uses temporal difference learning to adjust the weights of an artificial neural network whose role is to estimate how much the board state represented in its input layer by NET-FEATUREMAP is favorable to the player agent. The set of features is manually defined. The search for the best action corresponding to a current state board is performed by minimax algorithm. This paper presents new and very successful results obtained by substituting an efficient tree-search module based on alpha-beta pruning, transposition table and iterative deepening for the minimax algorithm in NeuroDraughts. The runtime required for training the new player was drastically reduced and its performance was significantly improved.

An algorithm, Aspiration Scout/MTD(f), is derived from an analysis of alpha-beta (α-β) tree search. When compared to its predecessors, it results in an average 10.1% reduction in search effort with a best case of 17.4%. 1 The search space is usually referred to as a tree, however in games such as chess and draughts it is actually a directed acyclic graph (DAG). Programs search a dynamically unfolding DAG.

The standard means of applying a discrete search to a continuous or hybrid system is the uniform discretization of control actions and action timing. Such discretization is fixed a priori and does not allow search to benefit from information gained at run-time. This paper introduces Information-Based Alpha-Beta Search, a new algorithm that preserves and benefits from the continuous or hybrid nature of the search. In a novel merging of alpha-beta game-tree search and information-based optimization, Information-Based Alpha-Beta Search makes trajectory-sampling decisions dynamically based on the maximum-likelihood of search pruning. The result is a search algorithm which, while incurring higher computational overhead for the optimization, manages to so increase the quality of the sampling, that the net effect is a significant increase in performance. We present a new piecewise-parabolic variant of the algorithm and provide empirical evidence of its performance relative to random and uniform discretizations in the context of a variant of the homicidal chauffeur game.

The efficiency of the αβ-algorithm as a minimax search procedure can be attributed to its effective pruning at so called cut-nodes; ideally only one move is examined there to establish the minimax value. This paper explores the benefits of investing additional search effort at cut-nodes by expanding other move alternatives as well. Our results show a strong correlation between the number of promising move alternatives at cut-nodes and a new principal variation emerging. Furthermore, a new forward pruning method is introduced that uses this additional information to ignore potentially futile subtrees. We also provide experimental results with the new pruning method in the domain of chess.

This paper analyzes Nn,d, the average number of terminal nodes examined by the α-β pruning algorithm in a uniform game-tree of degree n and depth d for which the terminal values are drawn at random from a continuous distribution. It is shown that Nn,d attains the branching factor ℝα−β(n)=ξn/l-ξn where ξn is the positive root of xn+x-l=0. The quantity ξn/1-ξn has previously been identified as a lower bound for all directional algorithms. Thus, the equality ℝα−β(n)=ξn/1-ξn renders α-β asymptotically optimal over the class of directional, game-searching algorithms.

A refinement of minimax to determine the optimal move in a game. Nodes that are not needed to evaluate the possible moves of the top node are ‘pruned’. Suppose that MAX is to move at parent node P. and that it is known from previous calculations that daughter D1 guarantees a minimum gain of say +20 for MAX. Now we start exploring D2 and discover that the opponent can force a maximal gain of +10 by reacting to D2 with D2. 1. In this case there is no need to explore other daughters of D2, because MAX can never gain more than +10 and therefore will always prefer D1. Following this line of reasoning, both from the point of view of MAX and of MIN, large parts of the tree need not be explored and an optimal solution will still be found.