Evolving Neural Networks to imax Search * cus

AAAI Conferences

Neural networks were evolved through genetic algorithms to focus minimax search in the game of Othello. At each level of the search tree, the focus networks decide which moves are promising enough to be explored further. The networks effectively hide problem states from minimax based on the knowledge they have evolved about the limitations of minimax and the evaluation function. Focus networks were encoded in markerbased chromosomes and were evolved against a full-width minimax opponent that used the same evaluation function. The networks were able to guide the search away from poor information, resulting in stronger play while examining fewer states. When evolved with a highly sophisticated evaluation function of the Bill program, the system was able to match Bill's performance while only searching a subset of the moves.


Best-First Minimax Search: Othello Results

AAAI Conferences

The best chess machines are competitive with the best humans, but generate millions of positions per move. Their human opponents, however, only examine tens of positions, but search much deeper along some lines of play. Obviously, people are more selective in their choice of positions to examine. The importance of selective search was first recognized by (Shannon 1950). Most work on game-tree search has focussed on algorithms that make the same decisions as fullwidth, fixed-depth minimax. This includes alpha-beta pruning (Knuth & Moore 1975), fixed and dynamic node ordering (Slagle & Dixon 1969), SSS* (Stockman 1979), Scout (Pearl 1984), aspiration-windows (Kaindl, Shams, & Horacek 1991), etc.


Memory-Bounded Bidirectional Search

AAAI Conferences

Previous approaches to bidirectional search require exponential space, and they are either less efficient than unidirectional search for finding optimal solutions, or they cannot even find such solutions for difficult problems. Based on a memory-bounded unidirectional algorithm for trees (SMA*), we developed a graph search extension, and we used it to construct a very efficient memory-bounded bidirectional algorithm. This bidirectional algorithm can be run for difficult problems with bounded memory. In addition, it is much more efficient than the corresponding unidirectional search algorithm also for finding optimal solutions to difficult problems. In summary, bidirectional search appears to be the best approach to solving difficult problems, and this indicates the extreme usefulness of a paradigm that was neglected for long.


Efficient Li

AAAI Conferences

Although A* is usually very efficient in terms of number of node expansions [2], it requires an exponential amount of memory, and thus runs out of memory even on problem instances of moderate size.



Exploiting Algebraic Structure in arallel State Space Search

AAAI Conferences

In this paper we present an approach for performing very large state-space search on parallel machines. While the majority of searching methods in Artificial Intelligence rely on heuristics, the parallel algorithm we propose exploits the algebraic structure of problems to reduce both the time and space complexity required to solve these problems on massively parallel machines. Our algorithm runs in O(N1'4/p) time using O(Nl/*) space with P processors where N is the size of the state space and P is the number of processors. The technique we present is applicable to several classes of exhaustive searches. Applications include the knapsack problem and the shortest word problem in permutation groups which is a natural generalization of several common planning benchmarks such as Rubik's Cube and the n-puzzle.


Hierarchical Chunking in Classifier Systems

AAAI Conferences

For a more comprehensive introduction the reader is referred to (Booker, Goldberg, & Holland, 1989; Goldberg, 1989; Wilson & Goldberg, 1989).


Genetic Programming and AI Planning Syste

AAAI Conferences

Genetic programming (GP) is an automatic programming technique that has recently been applied to a wide range of problems including blocks-world planning. This paper describes a series of illustrative experiments in which GP techniques are applied to traditional blocks-world planning problems.


Imtxovinrr Search through

AAAI Conferences

Adding diversity to symbolic search techniques has not been explored in artificial intelligence. Adding a diversity criterion provides us with a powerful new mechanism for finding global maxima in complex search spaces and helps to alleviate the problem of premature convergence to local maxima. A theoretical analysis is presented of issues in diversity searching which previously haven't been addressed, and a domain-independent diversity-search algorithm for practical breadth-first searching is developed.