Author name cluster

Joseph Barker

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

AAAI Conference 2015 Conference Paper

Limitations of Front-To-End Bidirectional Heuristic Search

Joseph Barker
Richard Korf

We present an intuitive explanation for the limited effectiveness of front-to-end bidirectional heuristic search, supported with extensive evidence from many commonly-studied domains. While previous work has proved the limitations of specific algorithms, we show that any front-to-end bidirectional heuristic search algorithm will likely be dominated by unidirectional heuristic search or bidirectional brute-force search. We also demonstrate a pathological case where bidirectional heuristic search is the dominant algorithm, so a stronger claim cannot be made. Finally, we show that on the four-peg Towers Of Hanoi with arbitrary start and goal states, bidirectional brute-force search outperforms unidirectional heuristic search using pattern-database heuristics.

PDF Details

AAAI Conference 2012 Conference Paper

Solving Dots-And-Boxes

Joseph Barker
Richard Korf

Dots-And-Boxes is a well-known and widely-played combinatorial game. While the rules of play are very simple, the state space for even very small games is extremely large, and finding the outcome under optimal play is correspondingly hard. In this paper we introduce a Dots-And-Boxes solver which is significantly faster than the current state-of-the-art: over an order-of-magnitude faster on several large problems. Our approach uses Alpha-Beta search and applies a number of techniques—both problem-specific and general—that reduce the search space to a manageable size. Using these techniques, we have determined for the first time that Dots-And- Boxes on a board of 4 × 5 boxes is a tie given optimal play; this is the largest game solved to date.

PDF Details

AAAI Conference 2012 Conference Paper

Solving Peg Solitaire with Bidirectional BFIDA*

Joseph Barker
Richard Korf

We present a novel approach to bidirectional breadth-first IDA* (BFIDA*) and demonstrate its effectiveness in the domain of peg solitaire, a simple puzzle. Our approach improves upon unidirectional BFIDA* by usually avoiding the last iteration of search entirely, greatly speeding up search. In addition, we provide a number of improvements specific to peg solitaire. We have improved duplicate-detection in the context of BFIDA*. We have strengthened the heuristic used in the previous state-of-the-art solver. Finally, we use bidirectional search frontiers to provide a stronger technique for pruning unsolvable states. The combination of these approaches allows us to improve over the previous state-of-the-art, often by a two-orders-of-magnitude reduction in search time.

PDF Details

AAAI Conference 2011 Conference Paper

Solving 4×5 Dots-And-Boxes

Joseph Barker
Richard Korf

Dots-And-Boxes is a well-known and widely-played combinatorial game. While the rules of play are very simple, the state space for even small games is extremely large, and ﬁnding the outcome under optimal play is correspondingly hard. In this paper we introduce a Dots-And-Boxes solver which is signiﬁcantly faster than the current state-of-the-art: over an order-of-magnitude faster on several large problems. We describe our approach, which uses Alpha-Beta search and applies a number of techniques—both problem-speciﬁc and general—to reduce the number of duplicate states explored and reduce the search space to a manageable size. Using these techniques, we have determined for the ﬁrst time that Dots- And-Boxes on a board of 4x5 boxes is a tie given optimal play. This is the largest game solved to date.

PDF Details