This paper describes the high-performance alpha-beta-based search engine used in CHINOOK, the World Man-Machine Checkers Champion. Previous experience in designing a chess program was important in...
Using Generative Design Patterns to Develop Network Server Applications (2009)
Zhuang Guo, Jonathan Schaeffer, Duane Szafron, Patrick Earl X
Abstract — Design patterns are generic solutions to recurring software design problems. The Correct Object-Oriented Patternbased Parallel Programming System (CO2P3S) uses design pattern templates...
� Search depth � Number of state transitions (moves) from the root of the search to the current state (position)
Dynamic Control in Path-Planning with Real-Time Heuristic Search (2008)
Vadim Bulitko, Yngvi Björnsson, Jonathan Schaeffer, Sverrir Sigmundarson
Real-time heuristic search methods, such as LRTA*, are used by situated agents in applications that require the amount of planning per action to be constant-bounded regardless of the problem size....
Adi Botea, Martin Müller, Jonathan Schaeffer, Ken Bauer
➲ Path-finding in real-time is important ➲ Memory and CPU resource limitations ➲ Multiple units competing for resources ➲ A * has unacceptable memory costs ➲ IDA * unacceptably slow ➲...
Peng Zhao, Peng Zhao, David Padua, Bruce Cockburn, Jonathan Schaeffer, Duane Szafron
Permission is hereby granted to the University of Alberta Library to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes...
against the computer program CHINOOK. After an (2008)
Jonathan Schaeffer, Robert Lake, Paul Lu, Martin Bryant
intense, tightly contested match, Tinsley fought back from behind to win the match by scoring four wins to CHINOOK’s two, with 33 draws. This match was the first time in history that a human world...
Adi Botea, Markus Enzenberger, Martin Müller, Jonathan Schaeffer
This document describes Macro-FF, an adaptive planning system developed on top of FF version 2.3. The original FF is a fully automatic planner that uses a heuristic search approach. In addition,...
Comparison of Different Grid Abstractions for Pathfinding on Maps (2008)
Yngvi Björnsson, Markus Enzenberger, Robert Holte, Jonathan Schaeffer, Peter Yap
Pathfinding on a map is a fundamental problem in many applications, including robotics and computer games. Typically a grid is superimposed over the map where each cell in the grid forms a unique...
A Visual Tool for Generative Scripting in Computer Role-Playing Games (2008)
James Michael Redford, James Michael Redford, Jonathan Schaeffer, Jim Hoover, Craig Montgomerie
Permission is hereby granted to the University of Alberta Library to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes...
Automatic Generation of Search Engines (2008)
Markian Hlynka, Jonathan Schaeffer
Abstract. A plethora of enhancements are available to be used together with the αβ search algorithm. There are so many, that their selection and implementation is a non-trivial task, even for the...
Developing Network Server Applications Using Generative Design Patterns By (2008)
Zhuang Guo, Tg T, Zhuang Guo, Duane Szafron, Jonathan Schaeffer, Mike Macgregor, ...
copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. The author reserves all other publication and other rights in association with the...
Haizhi Zhong, Athabasca Hall, Haizhi Zhong, Jonathan Schaeffer
copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. The author reserves all other publication and other rights in association with the...
The Evolution of Knowledge and Search in Game-Playing Systems (2008)
Abstract. The field of artificial intelligence (AI) is all about creating systems that exhibit “intelligent ” behavior. Computer games have been one of the most visible application areas for...
� Two-player adversary search is nice, but not all interesting problems can be mapped to games � Large class of optimization problems that all have the same search properties � Find the best...
with Automatically Generated Frameworks (2008)
Steve Macdonald, Duane Szafron, Jonathan Schaeffer, Steve Macdonald, Duane Szafron, Jonathan Schaeffer
Rights to individual papers remain with the author or the author's employer. Permission is granted for noncommercial reproduction of the work for educational or research purposes. This copyright...
A Demonstration of ScriptEase Interruptible and Resumable Behaviors for CRPGs (2008)
Maria Cutumisu, Duane Szafron, Jonathan Schaeffer, Kevin Waugh, Curtis Onuczko, Jeff Siegel, ...
Intelligent non-player characters that exhibit realistic ambient behaviors produce more captivating and immersive stories for the player. However, the creation of nonrepetitive and entertaining...
Pre-Searching 1 PRE-SEARCHING (2008)
Markian Hlynka, Jonathan Schaeffer
This paper introduces the idea of pre-searching a position—searching it before αβ determines that it needs to be searched. Consider the case where an iteration of αβ search comes across a...
Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, ...
The game of checkers has roughly 500 billion billion possible positions (5 × 10 20). The task of solving the game, determining the final result in a game with no mistakes made by either player, is...
Feng-hsiung Hsu, T. Anthony Marsland, Robert Levinson (chairperson, Jonathan Schaeffer, David E Wilkins
Our eminent researchers including John McCarthy, Allen Newell, Claude Shannon, Herb Simon, Ken Thompson and Alan Turing put significant effort into computer chess research. Now that computers have...
A Demonstration of ScriptEase Motivational Ambient and Latent Behaviors for Computer RPGs (2008)
Maria Cutumisu, Duane Szafron, Jonathan Schaeffer, Kevin Waugh, Curtis Onuczko, Jeff Siegel, ...
This demonstration describes the generation of ambient and latent NPC behavior scripts using generative behavior patterns with ScriptEase. Our behavior model supports behavior roles, a powerful...
Invited Talk Interactive Story Writing Using ScriptEase (2008)
Jonathan Schaeffer, Mike Carbonarro, Maria Cutumisu, Matthew Mcnaughton, Curtis Onuczko, Thomas Roy, ...
ScriptEase is a tool for writing interactive stories in roleplaying games that frees the author from doing explicit computer programming. A story is created by selecting and customizing patterns for...
“Whoever called snooker ‘chess with balls ’ was rude, but right” (2008)
Michael Smith, Clive James, Michael Smith, Jonathan Schaeffer, Duane Szafron, Gordon Swaters
of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. The author reserves all other publication and other rights in association with the...
Motivational Ambient and Latent Behaviors in Computer RPGs (2008)
Maria Cutumisu, Duane Szafron, Jonathan Schaeffer, Kevin Waugh
Character behaviors in computer role-playing games have a significant impact on game-play, but are often difficult for game authors to implement and adapt. We present a behavior model that requires...
Partial pattern databases (2008)
Kenneth Anderson, Robert Holte, Jonathan Schaeffer
Abstract. Perimeters and pattern databases are two similar memorybased techniques used in single-agent search problems. We present partial pattern databases, which unify the two approaches into a...
Temperature Discovery Search (2008)
Martin Müller, Markus Enzenberger, Jonathan Schaeffer
Temperature Discovery Search (TDS) is a new minimaxbased game tree search method designed to compute or approximate the temperature of a combinatorial game. TDS is based on the concept of an enriched...
ABSTRACT Man Versus Machine for the World Checkers Championship (2008)
Jonathan Schaeffer, Norman Treloar, Paul Lu, Robert Lake
his title against the computer program Chinook. The best-of-40-game match was won by Dr. Tinsley who scored 4 wins to Chinook’s 2 with 33 games drawn. This was the first time in history that a...
Probabilities and Simulations in Poker (2008)
"Gracias a la vida que me ha dado tanto... " Violeta Parra A mis padres... por todo. (To my parents... for everything)
Greg Lobe, Duane Szafron, Jonathan Schaeffer
The Enterprise programming environment supports the development of applications that run concurrently on a network of workstations. This paper describes the object-oriented components of Enterprise,...
Running head: "Parallel Sorting by Regular Sampling" Contact author: (2007)
Hanmao Shi, Resewrch Council, Grant Number Ogp, Jonathan Schaeffer, Jonathan Schaeffer
A new parallel sorting algorithm suitable for MIMD multiprocessors is presented. The algorithm reduces memory and bus contention, which many parallel sorting algorithms suffer from, by using a...
artificial intelligence (2007)
The AI research community has made one of the most profound contributions of the 20th century to mankind's knowledge. This research has led to the realization that intelligence is not uniquely...
Running Head: APHID: Asynchronous Parallel Game-Tree Search Send Proofs To: (2007)
Mark G. Brockington, Jonathan Schaeffer, Jonathan Schaeffer
Most parallel game-tree search approaches use synchronous methods, where the work is concentrated within a specific part of the tree, or at a given search depth. This article shows that asynchronous...
Diego Novillo, Ronald C. Unrau, Jonathan Schaeffer
Abstract. We present two new compiler optimizations for explicitly parallel programs based on the CSSAME form: Lock-Independent Code Motion (LICM) and Mutex Body Localization (MBL). We have...
Usability of Parallel I/O Templates (2007)
Ian Parsons, Ron Unrau, Jonathan Schaeffer, Duane Szafron
This paper presents an alternative high-level approach to parallelizing file I/O. Each parallel file descriptor is annotated with a high-level specification, or template, of the expected parallel...
A Platform-Independent Graphical User Interface for SEQSEE and XALIGN (2007)
David Wishart Scott, Scott Fortin, David R. Woloschuk, Jonathan Schaeffer, Duane Szafron
sophisticated GUI's that look and operate almost identically across all major platforms and operating systems. In many respects, Smalltalk, which was originally developed by Xerox's PARC in...
Program Design and Animation in the Enterprise Parallel Programming Environment (2007)
Greg Lobe, Duane Szafron, Jonathan Schaeffer
The Enterprise programming environment supports the development of applications that run concurrently on a network of workstations. This paper describes the object-oriented components of Enterprise,...
An Algorithm Faster than NegaScout and SSS* in Practice (2007)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
In this paper we introduce a framework for best first search of minimax trees. Existing best first algorithms like SSS* and DUAL* are formulated as instances of this framework. The framework is built...
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
In 1979 Stockman introduced the SSS* minimax search algorithm that dominates Alpha-Beta in the number of leaf nodes expanded. Further investigation of the algorithm showed that it had three serious...
Using PI/OT to Support Complex Parallel I/O (2007)
Ian Parsons, Jonathan Schaeffer, Duane Szafron, Ron Unrau
This paper describes PI/OT, a template-based parallel I/O system. In PI/OT, I/O streams have annotations associated with them that are external to the source code. These annotations specify an I/O...
Comparison of Different Grid Abstractions for Pathfinding on Maps (2007)
Yngvi Bj Ornsson, Markus Enzenberger, Robert Holte, Jonathan Schaeffer, Peter Yap
Pathfinding on a map is a fundamental problem in many applications, including robotics and computer games. Typically a grid is superimposed over the map where each cell in the grid forms a unique...
Imperfect Information Endgame Databases (2006)
Yngvi Björnsson, Jonathan Schaeffer, Nathan R. Sturtevant
Abstract. Endgame databases have previously been built based on complete analysis of endgame positions. In the domain of Checkers, where endgame databases consisting of 39 trillion positions have...
Imperfect Information Endgame Databases (2006)
Yngvi Björnsson, Jonathan Schaeffer, Nathan R. Sturtevant
Abstract. Endgame databases have previously been built based on complete analysis of endgame positions. In the domain of Checkers, where endgame databases consisting of 39 trillion positions have...
Generating Ambient Behaviors in Computer Role-Playing Games (2006)
Maria Cutumisu, Duane Szafron, Jonathan Schaeffer, Matthew Mcnaughton, Thomas Roy, Curtis Onuczko, ...
Abstract. Many computer games use custom scripts to control the ambient behaviors of non-player characters (NPCs). Therefore, a story writer must write fragments of computer code for the hundreds or...
Generating Ambient Behaviors in Computer Role-Playing Games (2006)
Maria Cutumisu, Duane Szafron, Jonathan Schaeffer, Matthew Mcnaughton, Thomas Roy, Curtis Onuczko, ...
Abstract. Many computer games use custom scripts to control the ambient behaviors of non-player characters (NPCs). Therefore, a story writer must write fragments of computer code for the hundreds or...
Learning partial-order macros from solutions (2005)
Adi Botea, Martin Müller, Jonathan Schaeffer
Despite recent progress in AI planning, many problems remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting...
Interactive Story Writing in the Classroom: Using Computer Games (2005)
Mike Carbonaro, Maria Cutumisu, Matthew Mcnaughton, Curtis Onuczko, Thomas Roy, Jonathan Schaeffer, ...
Interactive story writing is a new medium for creative expression. The story “writer ” uses a computer game (such as BioWare’s Neverwinter Nights) to create an interactive story where the...
John E. Laird, Michael Van Lent, Doug Church, Chris Crawford, Damian Isla (halo, W. Bingham Gordon, ...
• Research: Combining AI for commercial game techniques for immersive training simulations.
Interactive Story Writing in the Classroom: Using Computer Games (2005)
Mike Carbonaro, Maria Cutumisu, Matthew Mcnaughton, Curtis Onuczko, Thomas Roy, Jonathan Schaeffer, ...
Interactive story writing is a new medium for creative expression. The story "writer" uses a computer game (such as BioWare's Neverwinter Nights) to create an interactive story where...
Fringe search: beating A* at pathfinding on game maps (2005)
Yngvi Björnsson, Markus Enzenberger, Robert C. Holte, Jonathan Schaeffer
Abstract- The A * algorithm is the de facto standard used for pathfinding search. IDA * is a space-efficient version of A*, but it suffers from cycles in the search space (the price for using no...
Learning partial-order macros from solutions (2005)
Adi Botea, Martin Müller, Jonathan Schaeffer
Despite recent progress in AI planning, many benchmarks remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting...
Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators (2005)
Adi Botea, Markus Enzenberger, Martin Müller, Jonathan Schaeffer
Despite recent progress in AI planning, many benchmarks remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting...
Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators (2005)
Adi Botea, Markus Enzenberger, Martin Müller, Jonathan Schaeffer
Despite recent progress in AI planning, many benchmarks remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting...
Using component abstraction for automatic generation of macro-actions (2004)
Adi Botea, Martin Müller, Jonathan Schaeffer
Despite major progress in AI planning over the last few years, many interesting domains remain challenging for current planners. This paper presents component abstraction, an automatic and generic...
Near optimal hierarchical path-finding (2004)
Adi Botea, Martin Müller, Jonathan Schaeffer
The problem of path-finding in commercial computer games has to be solved in real time, often under constraints of limited memory and CPU resources. The computational effort required to find a path,...
Recognizing safe territories and stones in computer Go (2004)
Xiaozhen Niu, Xiaozhen Niu, Robert Hayes, Jonathan Schaeffer
copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. The author reserves all other publication and other rights in association with the...
ABSTRACT NEAR OPTIMAL HIERARCHICAL PATH-FINDING (2004)
Adi Botea, Martin Müller, Jonathan Schaeffer
The problem of path-finding in commercial computer games has to be solved in real time, often under constraints of limited memory and CPU resources. The computational effort required to find a path,...
Game tree search with adaptation in stochastic imperfect information games (2004)
Darse Billings, Aaron Davidson, Terence Schauenberg, Neil Burch, Michael Bowling, Robert Holte, ...
The game of poker has become a popular domain for exploring challenging AI problems. This has led to the development of programs that are competitive with strong human players. The current best...
Rethinking the Pipeline as Object-Oriented States with Transformations (2004)
Steve MacDonald, Duane Szafron, Jonathan Schaeffer
The pipeline is a simple and intuitive structure to speed up many problems. Novice parallel programmers are usually taught this structure early on. However, expert parallel programmers typically...
Using component abstraction for automatic generation of macro-actions (2004)
Adi Botea, Martin Müller, Jonathan Schaeffer
Despite major progress in AI planning over the last few years, many interesting domains remain challenging for current planners. This paper presents component abstraction, an automatic and generic...
Near optimal hierarchical path-finding (2004)
Adi Botea, Martin Müller, Jonathan Schaeffer
The problem of path-finding in commercial computer games has to be solved in real time, often under constraints of limited memory and CPU resources. The computational effort required to find a path,...
minimax performance in backgammon (2004)
Thomas Hauk, Michael Buro, Jonathan Schaeffer
Abstract. This paper presents the first performance results for Ballard’s *-Minimax algorithms applied to a real–world domain: backgammon. It is shown that with effective move ordering and...
Mark Goldenberg, Er Kovarsky, Xiaomeng Wu, Jonathan Schaeffer
goldenbe,kovarsky,xiaomeng,jonathan¡
The Canadian Internetworked Scientific Supercomputer (2003)
Christopher Pinchak, Paul Lu, Jonathan Schaeffer, Mark Goldenberg
pinchak,paullu,jonathan,goldenbe¡
Pattern-based Parallel Programming in a Distributed Memory Environment (2003)
Kai Tan, Edmonton Ab, Kai Tan, Duane Szafron, Jonathan Schaeffer, Robert Hayes, ...
copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. The author reserves all other publication and other rights in association with the...
The Canadian Internetworked Scientific Supercomputer (2003)
Christopher Pinchak, Paul Lu, Jonathan Schaeffer, Mark Goldenberg A
On November 4, 2002, a Canada-wide virtual supercomputer gave a chemistry research team the opportunity to do several years worth of computing in a single day. This experiment, called CISS-1...
Extending PDDL for Hierarchical Planning and Topological Abstraction (2003)
Adi Botea And, Adi Botea, Martin M Uller, Jonathan Schaeffer
Despite major progress in AI planning over the last few years, many interesting domains remain challenging for current planners. Topological abstraction can reduce planning complexity in several...
Why Not Use a Pattern-based Parallel Programming System? (2003)
John Anvik, Jonathan Schaeffer, Duane Szafron, Kai Tan
Parallel programming is seen as an effective technique to improve the performance of computationally-intensive programs. This is done at the cost of increasing the complexity of the program, since...
Why Not Use a Pattern-based Parallel Programming System? (2003)
John Anvik, Jonathan Schaeffer, Duane Szafron, Kai Tan
Parallel programming environments provide a way for users to reap the benefits of parallelism, while reducing the effort required to create parallel applications. The CO2P3S parallel programming...
Pattern-based AI Scripting using ScriptEase (2003)
Matthew Mcnaughton James, James Redford, Jonathan Schaeffer, Duane Szafron
Creating realistic artificially-intelligent characters is seen as one of the major challenges of the commercial games industry. Historically, character behavior has been specified using simple finite...
Kai Tan, Duane Szafron, Jonathan Schaeffer, John Anvik, Steve Macdonald
A design pattern is a mechanism for encapsulating the knowledge of experienced designers into a re-usable artifact. Parallel design patterns reflect commonly occurring parallel communication and...
The Fast Linear Space Alignment (FastLSA) algorithm (2003)
Adrian Driga, Paul Lu, Jonathan Schaeffer, Duane Szafron, Kevin Charter, Ian Parsons
Pairwise sequence alignment is a fundamental operation for homology search in bioinformatics. For two DNA or protein sequences of length , full-matrix (FM), dynamic programming alignment algorithms...
Why Not Use a Pattern-based Parallel Programming System? (2003)
John Anvik, Jonathan Schaeffer, Duane Szafron, Kai Tan
Parallel programming environments provide a way for users to reap the benefits of parallelism, while reducing the effort required to create parallel applications. The CO2P3S parallel programming...
Extending PDDL for Hierarchical Planning and Topological Abstraction (2003)
Adi Botea, Martin Müller, Jonathan Schaeffer
Despite major progress in AI planning over the last few years, many interesting domains remain challenging for current planners. Topological abstraction can reduce planning complexity in several...
TrellisDAG: A System for Structured DAG Scheduling (2003)
Mark Goldenberg, Mark Goldenberg, Jonathan Schaeffer, Peter Minev, Martin Müller
copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. The author reserves all other publication and other rights in association with the...
Multiple agents moving target search (2003)
Mark Goldenberg, Er Kovarsky, Xiaomeng Wu, Jonathan Schaeffer
goldenbe,kovarsky,xiaomeng,jonathan¡ Traditional single-agent search algorithms usually make simplifying assumptions (single search agent, stationary target, complete knowledge of the state, and...
TrellisDAG: A System for Structured DAG Scheduling (2003)
Mark Goldenberg, Paul Lu, Jonathan Schaeffer
High-performance computing often involves sets of jobs or workloads that must be scheduled. If there are dependencies in the ordering of the jobs (e.g., pipelines or directed acyclic graphs) the user...
Why not use a pattern-based parallel programming system (2003)
John Anvik, Jonathan Schaeffer, Duane Szafron, Kai Tan
Abstract. Parallel programming is seen as an effective technique to improve the performance of computationally-intensive programs. This is done at the cost of increasing the complexity of the...
Multiple agents moving target search (2003)
Mark Goldenberg, Er Kovarsky, Xiaomeng Wu, Jonathan Schaeffer
Traditional single-agent search algorithms usually make simplifying assumptions (single search agent, stationary target, complete knowledge of the state, and sufficient time). There are algorithms...
Asserting the utility of CO2P3S using the Cowichan problems (2002)
John Anvik, Jonathan Schaeffer, Duane Szafron, Kai Tan
Parallel programming environments provide a way for programmers to reap the benefits of parallelism, while reducing the effort required to create parallel applications. The CO2P3S parallel...
Generating parallel programs from the wavefront design pattern (2002)
John Anvik, Steve Macdonald, Duane Szafron, Jonathan Schaeffer, Steven Bromling, Kai Tan
Object-oriented programming, design patterns, and frameworks are common techniques that have been used to reduce the complexity of sequential programming. We have applied these techniques to the more...
Transposition Table Driven Work Scheduling in Distributed Game-Tree Search (2002)
Akihiro Kishimoto, Jonathan Schaeffer
1 Introduction Many artificial intelligence applications require real-time responses. Achieving this can be achieved by a combination of software and hardware. On the software side, anytime...
From patterns to frameworks to parallel programs (2002)
Steve Macdonald, Duane Szafron, Jonathan Schaeffer, Steven Bromling
Object-oriented programming, design patterns, and frameworks are abstraction techniques that have been used to reduce the complexity of sequential programming. This paper describes our approach of...
From patterns to frameworks to parallel programs (2002)
Steve Macdonald, Duane Szafron, Jonathan Schaeffer, Steven Bromling
Object-oriented programming, design patterns, and frameworks are abstraction techniques that have been used to reduce the complexity of sequential programming. This paper describes our approach of...
Artificial Intelligence 134 (2002) 201--240 (2002)
The Challenge Of, Darse Billings, Aaron Davidson, Jonathan Schaeffer, Duane Szafron
Poker is an interesting test-bed for artificial intelligence research. It is a game of imperfect information, where multiple competing agents must deal with probabilistic knowledge, risk assessment,...
Using Abstraction for Planning in Sokoban (2002)
Adi Botea, Martin Müller, Jonathan Schaeffer
Abstract. Heuristic search has been successful for games like chess and checkers, but seems to be of limited value in games such as Go and shogi, and puzzles such as Sokoban. Other techniques are...
A Performance Analysis of Transposition-TableDriven Scheduling in Distributed Search (2002)
John W. Romein, Henri E. Bal, Ieee Computer Society, Jonathan Schaeffer, Aske Plaat
Abstract—This paper discusses a new work-scheduling algorithm for parallel search of single-agent state spaces, called Transposition-Table-Driven Work Scheduling, that places the transposition...
Memory-Efficient A* Heuristics for Multiple Sequence Alignment (2002)
Matthew Mcnaughton And, Matthew Mcnaughton, Paul Lu, Jonathan Schaeffer, Duane Szafron
The time and space needs of an A* search are strongly influenced by the quality of the heuristic evaluation function.
Sokoban: Enhancing general single-agent search methods using domain knowledge (2001)
Andreas Junghanns, Jonathan Schaeffer
Keywords: single-agent search, IDA*, Sokoban, transposition table, pattern search, pattern database, rapid random restart 1 Introduction The AI research community has developed an impressive suite of...
Learning to play strong poker (2001)
Jonathan Schaeffer, Darse Billings, Lourdes Peña, Duane Szafron
Poker is an interesting test-bed for artificial intelligence research. It is a game of imperfect knowledge, where multiple competing agents must deal with risk management, opponent modeling,...
Unifying Single-Agent and Two-Player Search (2001)
Jonathan Schaeffer, Aske Plaat, Aske Plaat
. The seminal works of Nilsson and Pearl in the 1970's and early 1980's provide a formal basis for splitting the eld of heuristic search into two subelds: single- and two-agent search. The...
Learning to play strong poker (2001)
Jonathan Schaeffer, Darse Billings, Lourdes Peña, Duane Szafron
Poker is an interesting test-bed for artificial intelligence research. It is a game of imperfect knowledge, where multiple competing agents must deal with risk management, opponent modeling,...
Identifying and Validating Irregular Mutual Exclusion in Concurrent Programs (2000)
Diego Novillo, Ronald C. Unrau, Jonathan Schaeffer
Abstract. Existing work on mutual exclusion synchronization is based on a structural definition of mutex bodies. Although correct, this structural notion fails to identify many important locking...
Generating Parallel Program Frameworks from Parallel Design Patterns (2000)
Steve Macdonald, Duane Szafron, Jonathan Schaeffer, Steven Bromling
. Object-oriented programming, design patterns, and frameworks are abstraction techniques that have been used to reduce the complexity of sequential programming. The CO2P3S parallel programming...
Visualizing Object and Method Granularity for Program Parallelization (2000)
William Hui, Steve Macdonald, Jonathan Schaeffer, Duane Szafron
There are increasing demands foa moan coands . poa Parallel hardware is no. coR[]q[.-Nx and co . be a co2[2.-NIx[I.o sox[I.o Ho2x[].- to many develo]N[.- parallel prolel .Rx] is a user-friendly task...
Generating Parallel Program Frameworks from Parallel Design Patterns (2000)
Steve MacDonald, Duane Szafron, Jonathan Schaeffer, Steven Bromling
Object-oriented programming, design patterns, and frameworks are abstraction techniques that have been used to reduce the complexity of sequential programming. The CO2P3S parallel programming system...
Visualizing Object and Method Granularity for Program Parallelization (2000)
William Hui, Steve Macdonald, Jonathan Schaeffer, Duane Szafron
There are increasing demands for more computing power. Parallel hardware is now commonplace and could be a cost-effective solution. However, to many developers, parallel programming is not a...
Optimizing mutual exclusion synchronization in explicitly parallel programs (2000)
Diego Novillo, Ronald C. Unrau, Jonathan Schaeffer
Abstract. We present two new compiler optimizations for explicitly parallel programs based on the CSSAME form: Lock-Independent Code Motion (LICM) and Mutex Body Localization (MBL). We have...
Running Head: APHID: Asynchronous Parallel Game-Tree Search Send Proofs To: (1999)
Mark G. Brockington, Jonathan Schaeffer, Jonathan Schaeffer
Most parallel game-tree search approaches use synchronous methods, where the work is concentrated within a specific part of the tree, or at a given search depth. This article shows that asynchronous...
Object–oriented pattern–based parallel programming with automatically generated frameworks (1999)
Steve Macdonald, Duane Szafron, Jonathan Schaeffer
The CO2P3S parallel programming system uses design patterns and object–oriented programming to reduce the complexities of parallel programming. The system generates correct frameworks from pattern...
Using probabilistic knowledge and simulation to play poker (1999)
Darse Billings, Lourdes Peña, Jonathan Schaeffer, Duane Szafron
Until recently, artificial intelligence researchers who use games as their experimental testbed have concentrated on games of perfect information. Many of these games have been amenable to...
Domain-Dependent Single-Agent Search Enhancements (1999)
Andreas Junghanns, Jonathan Schaeffer
AI research has developed an extensive collection of methods to solve state-space problems. Using the challenging domain of Sokoban, this paper studies the effect of search enhancements on program...
Domain-dependent single-agent search enhancements (1999)
Andreas Junghanns, Jonathan Schaeffer
AI research has developed an extensive collection of methods to solve state-space problems. Using the challenging domain of Sokoban, this paper studies the effect of search enhancements on program...
Using Probabilistic Knowledge and Simulation to Play Poker (1999)
Darse Billings, Lourdes Pea, Jonathan Schaeffer, Duane Szafron
Until recently, artificial intelligence researchers who use games as their experimental testbed have concentrated on games of perfect information. Many of these games have been amenable to...
Transposition Table Driven Work Scheduling in Distributed Search (1999)
John W. Romein, Aske Plaat, Henri E. Bal, Jonathan Schaeffer
This paper introduces a new scheduling algorithm for parallel single-agent search, transposition table driven work scheduling, that places the transposition table at the heart of the parallel work...
Sokoban: Improving the Search with Relevance Cuts (1999)
Andreas Junghanns, Jonathan Schaeffer
. Humans can effectively navigate through large search spaces, enabling them to solve problems with daunting complexity. This is largely due to an ability to successfully distinguish between relevant...
Learning to Play Strong Poker (1999)
Jonathan Schaeffer, Darse Billings, Duane Szafron
Poker is an interesting test-bed for artificial intelligence research. It is a game of imperfect knowledge, where multiple competing agents must deal with risk management, opponent modeling,...
Learning to Play Strong Poker (1999)
Jonathan Schaeffer Darse, Jonathan Schaeffer, Darse Billings, Duane Szafron
Poker is an interesting test-bed for artificial intelligence research. It is a game of imperfect knowledge, where multiple competing agents must deal with risk management, opponent modeling,...
Transposition Table Driven Work Scheduling in Distributed Search (1999)
John Romein, Aske Plaat, Henri E. Bal, Jonathan Schaeffer
This paper introduces a new scheduling algorithm for parallel single-agent search, transposition table driven work scheduling, that places the transposition table at the heart of the parallel work...
Using Probabilistic Knowledge and Simulation to Play Poker (1999)
Darse Billings, Jonathan Schaeffer, Duane Szafron
Until recently, artificial intelligence researchers who use games as their experimental testbed have concentrated on games of perfect information. Many of these games have been amenable to...
Object--Oriented Pattern--Based Parallel Programming with Automatically Generated Frameworks (1999)
Steve Macdonald, Duane Szafron, Jonathan Schaeffer
The CO 2 P 3 S parallel programming system uses design patterns and object--oriented programming to reduce the complexities of parallel programming. The system generates correct frameworks from...
Learning to Play Strong Poker (1999)
Jonathan Schaeffer, Darse Billings, Lourdes Peña, Duane Szafron
Poker is an interesting test-bed for artificial intelligence research. It is a game of imperfect knowledge, where multiple competing agents must deal with risk management, opponent modeling,...
Using Selective-Sampling Simulations in Poker (1999)
Darse Billings, Denis Papp, Jonathan Schaeffer, Duane Szafron
Until recently, AI research that used games as an experimental testbed has concentrated on perfect information games. Many of these games have been amenable to so-called brute-force search...
Using Selective-Sampling Simulations in Poker (1999)
Darse Billings, Jonathan Schaeffer, Duane Szafron
Until recently, AI research that used games as an experimental testbed has concentrated on perfect information games. Many of these games have been amenable to so-called brute-force search...
Transposition Table Driven Work Scheduling in Distributed Search (1999)
John W. Romein, Aske Plaat, Henri E. Bal, Jonathan Schaeffer
This paper introduces a new scheduling algorithm for parallel single-agent search, transposition table driven work scheduling, that places the transposition table at the heart of the parallel work...
Transposition Table Driven Work Scheduling in Distributed Search (1999)
John W. Romein, Aske Plaat, Henri E. Bal, Jonathan Schaeffer
This paper introduces a new scheduling algorithm for parallel single-agent search, transposition table driven work scheduling, that places the transposition table at the heart of the parallel work...
Using Probabilistic Knowledge and Simulation to Play Poker (1999)
Darse Billings, Lourdes Peña, Jonathan Schaeffer, Duane Szafron
Until recently, artificial intelligence researchers who use games as their experimental testbed have concentrated on games of perfect information. Many of these games have been amenable to...
Object-Oriented Pattern-Based Parallel Programming with Automatically Generated Frameworks (1999)
Steve Macdonald, Duane Szafron, Jonathan Schaeffer
The CO 2 P 3 S parallel programming system uses design patterns and object-oriented programming to reduce the complexities of parallel programming. The system generates correct frameworks from...
Solving Under Uncertainty, Darse Billings, Lourdes Peña, Jonathan Schaeffer, Duane Szafron
Until recently, AI research that used games as an experimental testbed has concentrated on perfect information games. Many of these games have been amenable to so-called brute-force search...
Using Selective-Sampling Simulations in Poker (1999)
Darse Billings, Lourdes Peña, Jonathan Schaeffer, Duane Szafron
Until recently, AI research that used games as an experimental testbed has concentrated on perfect information games. Many of these games have been amenable to so-called brute-force search...
Using probabilistic knowledge and simulation to play poker (1999)
Darse Billings, Lourdes Peña, Jonathan Schaeffer, Duane Szafron
Until recently, artificial intelligence researchers who use games as their experimental testbed have concentrated on games of perfect information. Many of these games have been amenable to...
Simon, Herbert A., Schaeffer, Jonathan
We have seen that the theory of games that emerges from this research is quite remote in both its concerns and its findings from the von Neumann Morgenstern theory. To arrive at actual strategies for...
Poker as a testbed for machine intelligence research (1998)
Darse Billings, Jonathan Schaeffer, Duane Szafron
For years, games researchers have used chess, checkers and other board games as a testbed for machine intelligence research. The success of worldchampionship-caliber programs for these games has...
Using PI/OT to Support Complex Parallel I/O (1998)
Ian Parsons, Jonathan Schaeffer, Duane Szafron, Ron Unrau
This paper describes PI/OT, a template-based parallel I/O system. In PI/OT, I/O streams have annotations associated with them that are external to the source code. These annotations specify an I/O...
Sokoban: Evaluating Standard Single-Agent Search Techniques in the Presence of Deadlock (1998)
Andreas Junghanns, Jonathan Schaeffer
Single-agent search is a powerful tool for solving a variety of applications. Most of the academic application domains used to explore single-agent search techniques have the property that if you...
Relevance Cuts: Localizing the Search (1998)
Andreas Junghanns, Jonathan Schaeffer
. Humans can effectively navigate through large search spaces, enabling them to solve problems with daunting complexity. This is largely due to an ability to successfully distinguish between relevant...
Single-Agent Search in the Presence of Deadlocks (1998)
Andreas Junghanns, Jonathan Schaeffer
Single-agent search is a powerful tool for solving a variety of applications. Most of the application domains used to explore single-agent search techniques have the property that if you start with a...
Data Parallelism In Java (1998)
Michael Philippsen, Jonathan Schaeffer, Kluwer Academic
: Java supports threads and remote method invocation, but it does not support either data parallel or distributed programming. This paper discusses Java's shortcomings with respect to data...
Concurrent SSA Form in the Presence of Mutual Exclusion (1998)
Diego Novillo, Ron Unrau, Jonathan Schaeffer
Most current compiler analysis techniques are unable to cope with the semantics introduced by explicit parallel and synchronization constructs in parallel programs. In this paper we propose new...
Using PI/OT to Support Complex Parallel I/O (1998)
Ian Parsons Jonathan, Jonathan Schaeffer, Duane Szafron, Ron Unrau
This paper describes PI/OT, a template-based parallel I/O system. In PI/OT, I/O streams have annotations associated with them that are external to the source code. These annotations specify an I/O...
Opponent Modeling in Poker (1998)
Darse Billings, Jonathan Schaeffer, Duane Szafron
Poker is an interesting test-bed for artificial intelligence research. It is a game of imperfect knowledge, where multiple competing agents must deal with risk management, agent modeling, unreliable...
Experience with Parallel Programming Using Code Templates (1998)
Ajit Singh, Jonathan Schaeffer, Duane Szafron
For almost a decade we have been working at developing and using template-based models for parallel computing. Template-based models separate the specification of the parallel structuring aspects...
Opponent Modeling in Poker (1998)
Darse Billings, Denis Papp, Jonathan Schaeffer, Duane Szafron
Poker is an interesting test-bed for artificial intelligence research. It is a game of imperfect knowledge, where multiple competing agents must deal with risk management, agent modeling, unreliable...
Analysis and Optimization of Explicitly Parallel Programs (1998)
Diego Novillo, Ronald C. Unrau, Jonathan Schaeffer
Most current compiler analysis techniques are unable to cope with the semantics introduced by explicit parallel and synchronization constructs in parallel programs. In this paper we introduce new...
Opponent Modeling in Poker (1998)
Darse Billings Denis, Jonathan Schaeffer, Duane Szafron
Poker is an interesting test-bed for artificial intelligence research. It is a game of imperfect knowledge, where multiple competing agents must deal with risk management, agent modeling, unreliable...
Relevance cuts: Localizing the search (1998)
Andreas Junghanns, Jonathan Schaeffer
1 Introduction and Motivation It is commonly acknowledged that the human's ability to successfully navigate through large search spaces is due to their meta-level reasoning [4]. The relevance of...
Poker as a testbed for machine intelligence research (1998)
Darse Billings, Jonathan Schaeffer, Duane Szafron
For years, games researchers have used chess, checkers and other board games as a testbed for machine intelligence research. The success of world-championship-caliber programs for these games has...
Opponent modeling in poker (1998)
Darse Billings, Jonathan Schaeffer, Duane Szafron
Poker is an interesting test-bed for artificial intelligence research. It is a game of imperfect knowledge, where multiple competing agents must deal with risk management, agent modeling, unreliable...
Poker as a testbed for machine intelligence research (1998)
Darse Billings, Jonathan Schaeffer, Duane Szafron
For years, games researchers have used chess, checkers and other board games as a testbed for machine intelligence research. The success of world-championship-caliber programs for these games has...
Search Versus Knowledge in Game-Playing Programs Revisited (1997)
Andreas Junghanns, Jonathan Schaeffer
Perfect knowledge about a domain renders search unnecessary and, likewise, exhaustive search obviates heuristic knowledge. In practise, a tradeoff is found somewhere in the middle, since neither...
Diminishing returns for additional search in chess (1997)
Andreas Junghanns, Jonathan Schaeffer, Mark Brockington, Yngvi Bjornsson, Tony Marsl
Advances in technology allow for increasingly deeper searches in competitive chess programs. Several experiments with chess indicate a constant improvement in a program 's performance for deeper...
Search Versus Knowledge in Game-Playing Programs Revisited (1997)
Andreas Junghanns, Jonathan Schaeffer
Perfect knowledge about a domain renders search unnecessary and, likewise, exhaustive search obviates heuristic knowledge. In practise, a tradeoff is found somewhere in the middle, since neither...
Sokoban: A Challenging Single-Agent Search Problem (1997)
Andreas Junghanns, Jonathan Schaeffer
Sokoban is a challenging single-player game -- for both man and machine. The simplicity of the rules belies the complexity of the game. This paper describes our program, Rolling Stone, a first...
Searching with Uncertainty Cut-offs (1997)
Yngvi Björnsson, Tony Marsland, Jonathan Schaeffer, Andreas Junghanns
A new domain-independent pruning method is described that guarantees returning a correct game value. Even though alpha-beta-based chess programs are already searching close to the minimal tree, there...
Pattern-based Object-Oriented Parallel Programming (1997)
Steve Macdonald, Jonathan Schaeffer, Duane Szafron
this paper, we present an architecture and model for CO 2 P 3 S in which we address some of the shortcomings of FrameWorks and Enterprise. Our continuing goal is to produce usable parallel...
Mark G. Brockington, Jonathan Schaeffer
This paper introduces the APHID (Asynchronous Parallel Hierarchical Iterative Deepening) gametree search algorithm. An APHID search is controlled by a master and a series of slave processors. The...
Pattern-based Object-Oriented Parallel Programming (1997)
Steve Macdonald, Jonathan Schaeffer, Duane Szafron
this paper, we present an architecture and model for CO 2 P 3 S in which we address some of the shortcomings of FrameWorks and Enterprise. Our continuing goal is to produce usable parallel...
Jonathan Schaeffer, Gregory V. Wilson
. The simplicity and elegance of the Linda programming model is based on its single, global, typeless tuple space. However, these virtues come at a cost. First, the tuple space can be an impediment...
Pattern--Based Object--Oriented Parallel Programming (1997)
Steve Macdonald, Jonathan Schaeffer, Duane Szafron
this paper, we present an architecture and model for CO 2 P 3 S in which we address some of the shortcomings of FrameWorks and Enterprise. Our continuing goal is to produce usable parallel...
PI/OT, Parallel I/O Templates (1997)
Ian Parsons, Ron Unrau, Jonathan Schaeffer, Duane Szafron
This paper presents a novel, top-down, high-level approach to parallelizing file I/O. Each parallel file descriptor is annotated with a high-level specification, or template, of the expected parallel...
David S. Wishart, Scott Fortin, David R. Woloschuk, Warren Wong, Gary Van Domselaar, ...
ophisticated GUI's that look and operate almost identically across all major platforms and operating systems. In many respects, Smalltalk, which was originally developed by Xerox's PARC in...
This is a pre-print of a paper that has been submitted to a special issue of Parallel (1997)
Computing On Parallel, Ian Parsons, Ron Unrau, Jonathan Schaeffer, Duane Szafron
This paper presents an alternative high-level approach to parallelizing file I/O. Each parallel file descriptor is annotated with a high-level specification, or template, of the expected parallel...
A platform-independent graphical user interface for SEQSEE and XALIGN (1997)
Wishart, David S., Fortin, Scott, Woloschuk, David R., Wong, Warren, Rosborough, Timothy, Van Domselaar, Gay, ...
Searching with pattern databases (1996)
Joseph C. Culberson, Jonathan Schaeffer
Abstract. The efficiency of A * searching depends on the quality of the lower bound estimates of the solution cost. Pattern databases enumerate all possible subgoals required by any solution, subject...
The APHID Parallel fffi Search Algorithm (1996)
Mark G. Brockington, Jonathan Schaeffer
This paper introduces the APHID (Asynchronous Parallel Hierarchical Iterative Deepening) game-tree search algorithm. APHID represents a departure from the approaches used in practice. Instead of...
The APHID Parallel fffi Search Algorithm (1996)
Jonathan Schaeffer, Mark G. Brockington, Mark G. Brockington
This paper introduces the APHID (Asynchronous Parallel Hierarchical Iterative Deepening) gametree search algorithm. An APHID search is a hierarchical search with a master controlling the top of the...
Chinook: The World Man-Machine Checkers Champion (1996)
Jonathan Schaeffer, Robert Lake, Paul Lu, Martin Bryant
In 1992, the seemingly unbeatable World Checker Champion, Dr. Marion Tinsley, defended his title against the computer program Chinook. After an intense, tightly-contested match, Tinsley fought back...
Using a Template-Based Parallel Programming Environment to Eliminate Errors (1996)
Paul Iglinski Nicholas, Nicholas Kazouris, Steven Macdonald, Diego Novillo, Jonathan Schaeffer, Duane Szafron, ...
In this paper we describe how a template-based approach to writing distributed/parallel applications can be used to eliminate parallel programming errors. We take a two phase approach. First, the...
An Experiment to Measure the Usability of Parallel Programming Systems (1996)
Duane Szafron, Jonathan Schaeffer
This paper discusses the design and results of an experiment to objectively compare the usability of two PPSs. Half of the students in a graduate parallel and distributed computing course solved a...
Best-First Fixed-Depth Minimax Algorithms (1996)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
This article has three main contributions to our understanding of minimax search: First, a new formulation for Stockman's SSS* algorithm, based on AlphaBeta, is presented. It solves all the...
Using a Template-Based Parallel Programming Environment to Eliminate Errors (1996)
Paul Iglinski, Nicholas Kazouris, Steven MacDonald, Diego Novillo, Ian Parsons, Jonathan Schaeffer, ...
In this paper we describe how a template-based approach to writing distributed/parallel applications can be used to eliminate parallel programming errors. We take a two phase approach. First, the...
Exploiting Graph Properties of Game Trees (1996)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
The state space of most adversary games is a directed graph. However, due to the success of simple recursive algorithms based on Alpha-Beta, theoreticians and practitioners have concentrated on the...
Views on Template-Based Parallel Programming (1996)
Ajit Singh, Jonathan Schaeffer, Duane Szafron
For almost a decade we have been working at developing and using template-based models for coarse-grained parallel computing. Our initial system, FrameWorks, was positively received but had a number...
Searching with Pattern Databases (1996)
Joseph C. Culberson, Jonathan Schaeffer
. The efficiency of A* searching depends on the quality of the lower bound estimates of the solution cost. Pattern databases enumerate all possible subgoals required by any solution, subject to...
Exploiting Graph Properties of Game Trees (1996)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
The state space of most adversary games is a directed graph. However, due to the success of simple recursive algorithms based on Alpha-Beta, theoreticians and practitioners have concentrated on the...
Using a template-based parallel programming environment to eliminate errors (1996)
Paul Iglinski, Nicholas Kazouris, Steven Macdonald, Diego Novillo, Ian Parsons, Jonathan Schaeffer, ...
In this paper we describe how a template-based approach to writing distributed/parallel applications can be used to eliminate parallel programming errors. We take a two phase approach. First, the...
An Experiment To, Duane Szafron, Jonathan Schaeffer
This paper discusses the design and results of an experiment to objectively compare the usability of two PPSs. Half of the students in a graduate parallel and distributed computing course solved a...
Steve Macdonald, Duane Szafron, Jonathan Schaeffer
This paper describes three basic specializations of design patterns that can be used in implementing the run-time systems of parallel applications. These specializations were discovered while...
This is a Preprint of a Copyrighted Article That Will Appear in a Forthcoming Book. (1996)
Software Engineering Considerations, Jonathan Schaeffer, Duane Szafron
This paper uses the Enterprise programming environment for coarse-grained parallel applications to illustrate the advantages of these tools. For most users, high performance is not an important...
Exploiting Graph Properties of Game Trees (1996)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
The state space of most adversary games is a directed graph. However, due to the success of simple recursive algorithms based on Alpha-Beta, theoreticians and practitioners have concentrated on the...
New advances in Alpha-Beta searching (1996)
Jonathan Schaeffer, Aske Plaat
Alpha-Beta has been the algorithm of choice for game-tree search for over three decades. Its success is largely attributable to a variety of enhancements to the basic algorithm that can dramatically...
The APHID Parallel Search Algorithm (1996)
Mark G. Brockington, Jonathan Schaeffer
This paper introduces the APHID (Asynchronous Parallel Hierarchical Iterative Deepening) game-tree search algorithm. APHID represents a departure from the approaches used in practice. Instead of...
Software Engineering Considerations in the Construction of Parallel Programs (1995)
Jonathan Schaeffer, Duane Szafron
This paper uses the Enterprise programming environment for coarse-grained parallel applications to illustrate the advantages of these tools. For most users, high performance is not an important...
A Minimax Algorithm Better than Alpha-Beta? No and Yes (1995)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
This paper has three main contributions to our understanding of fixed-depth minimax search: (A) A new formulation for Stockman's SSS* algorithm, based on Alpha-Beta, is presented. It solves all...
Best-First Fixed-Depth Game-Tree Search in Practice (1995)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
We present a new paradigm for minimax search algorithms: MT, a memory-enhanced version of Pearl's Test procedure. By changing the way MT is called, a number of practical best-first search...
A Minimax Algorithm Better than Alpha-Beta? No and Yes (1995)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
This paper has three main contributions to our understanding of fixed-depth minimax search: (A) A new formulation for Stockman's SSS* algorithm, based on Alpha-Beta, is presented. It solves all...
Performance Debugging in the Enterprise Parallel Programming System (1995)
David Woloschuk, Paul Iglinski, Steven Macdonald, Diego Novillo, Ian Parsons, Jonathan Schaeffer, ...
Debugging parallel/distributed programs is an iterative process, alternating between correctness debugging and performance debugging. Performance debugging involves identifying bottlenecks in a...
A Minimax Algorithm Better than Alpha-Beta? No and Yes (1995)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
This paper has three main contributions to our understanding of fixed-depth minimax search: (A) A new formulation for Stockman's SSS* algorithm, based on Alpha-Beta, is presented. It solves all...
A new paradigm for minimax search (1994)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
This paper introduces a new paradigm for minimax game-tree search algorithms. MT is a memory-enhanced version of Pearl's Testprocedure. By changing the way MT is called, a number of...
A new paradigm for minimax search (1994)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
This paper introduces a new paradigm for minimax game-tree search algorithms. MT is a memory-enhanced version of Pearl’s Testprocedure. By changing the way MT is called, a number of best-first...
Experimentally Assessing the Usability of Parallel Programming Systems (1994)
Duane Szafron, Jonathan Schaeffer
This paper discusses an experiment to compare the usability of two parallel programming systems (PPS). In this experiment, half of the students in a graduate parallel and distributed computing course...
Nearly Optimal Minimax Tree Search? (1994)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
Knuth and Moore presented a theoretical lower bound on the number of leaves that any fixed-depth minimax tree-search algorithm traversing a uniform tree must explore, the so-called minimal tree....
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
In 1979 Stockman introduced the SSS* minimax search algorithm that dominates Alpha-Beta in the number of leaf nodes expanded. Further investigation of the algorithm showed that it had three serious...
A New Paradigm for Minimax Search (1994)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
This paper introduces a new paradigm for minimax game-tree search algorithms. MT is a memory-enhanced version of Pearl's Test procedure. By changing the way MT is called, a number of best-first...
Nearly Optimal Minimax Tree Search? (1994)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
Knuth and Moore presented a theoretical lower bound on the number of leaves that any fixed-depth minimax tree-search algorithm traversing a uniform tree must explore, the so-called minimal tree....
Experimentally Assessing the Usability of Parallel Programming Systems (1994)
D. Szafron, Jonathan Schaeffer, Duane Szafron, Jonathan Schaeffer
This paper discusses an experiment to compare the usability of two parallel programming systems (PPS). In this experiment, half of the students in a graduate parallel and distributed computing course...
An Experiment to Measure the Usability of Parallel Programming Systems (1994)
Duane Szafron, Duane Szafron, Jonathan Schaeffer, Jonathan Schaeffer
This paper discusses the design and results of an experiment to objectively compare the usability of two PPSs. Half of the students in a graduate parallel and distributed computing course solved a...
A New Paradigm for Minimax Search (1994)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
This paper introduces a new paradigm for minimax game-tree search algorithms. MT is a memory-enhanced version of Pearl's Testprocedure. By changing the way MT is called, a number of best-first...
Solving Large Retrograde Analysis Problems Using a Network of Workstations (1994)
Robert Lake, Jonathan Schaeffer, Paul Lu
Chess endgame databases, while of important theoretical interest, have yet to make a significant impact in tournament chess. In the game of checkers, however, endgame databases have played a pivotal...
Experimentally Assessing the Usability of Parallel Programming Systems (1994)
Duane Szafron, Jonathan Schaeffer
This paper discusses an experiment to compare the usability of two parallel programming systems (PPS). In this experiment, half of the students in a graduate parallel and distributed computing course...
Experimentally Assessing the Usability of Parallel Programming Systems (1994)
Duane Szafron, Jonathan Schaeffer
This paper discusses an experiment to compare the usability of two parallel programming systems (PPS). In this experiment, half of the students in a graduate parallel and distributed computing course...
Efficiently Searching the 15-Puzzle (1994)
Joseph Culberson, Joseph C. Culberson, Jonathan Schaeffer, Jonathan Schaeffer
The A* algorithm for single-agent search has attracted considerable attention in recent years due to Korf's iterative deepening improvement (IDA*). The algorithm's efficiency depends on the...
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
In 1979 Stockman introduced the SSS* minimax search algorithm that dominates Alpha-Beta in the number of leaf nodes expanded. Further investigation of the algorithm showed that it had three serious...
Experimentally Assessing the Usability of Parallel (1994)
Programming Systems Duane, Duane Szafron, Jonathan Schaeffer
This paper discusses an experiment to compare the usability of two parallel programming systems (PPS). In this experiment, half of the students in a graduate parallel and distributed computing course...
University of Alberta SSS * =- + TT (1994)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
In 1979 Stockman introduced the SSS * minimax search algorithm that dominates Alpha-Beta in the number of leaf nodes expanded. Further investigation of the algorithm showed that it had three serious...
Nearly optimal minimax tree search (1994)
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
Knuth and Moore presented a theoretical lower bound on the number of leaves that any fixed-depth minimax tree-search algorithm traversing a uniform tree must explore, the so-called minimal tree....
A Re-Examination of Brute-Force Search (1993)
Jonathan Schaeffer, Paul Lu, Duane Szafron, Robert Lake
In August 1992, the World Checkers Champion, Dr. Marion Tinsley, defended his title against the computer program Chinook. The best-of-40-game match was won by Tinsley with 4 wins to the...
On the Versatility of Parallel Sorting by Regular Sampling (1993)
Xiaobo Li, Paul Lu, Jonathan Schaeffer, John Shillington, Pok Sze Wong, Hanmao Shi
Parallel sorting algorithms have already been proposed for a variety of multiple instruction streams, multiple data streams (MIMD) architectures. These algorithms often exploit the strengths of the...
The Enterprise Model for Developing Distributed Applications (1993)
Jonathan Schaeffer, Duane Szafron, Greg Lobe, Ian Parsons
terests include parallel programming environments for distributed memory applications. He received an MS (in 1992) and a BS (in 1991) in computing science from the University of Alberta, and a BS in...
The Enterprise Model for Developing Distributed Applications (1993)
Jonathan Schaeffer, Duane Szafron, Greg Lobe, Ian Parsons
Although a network of workstations represents a large amount of aggregate computing power, there is a need for software that can harness this power for single, distributed applications. Enterprise is...
Enterprise in Context: Assessing the Usability of Parallel Programming Environments (1993)
Gregory V. Wilson, Jonathan Schaeffer, Duane Szafron
The growth of commercial and academic interest in parallel and distributed computing during the past fifteen years has been accompanied by a corresponding increase in the number of available parallel...
A Re-Examination of Brute-Force Search (1993)
Jonathan Schaeffer, Paul Lu, Duane Szafron, Robert Lake
In August 1992, the World Checkers Champion, Dr. Marion Tinsley, defended his title against the computer program Chinook. The best-of-40-game match was won by Tinsley with 4 wins to the...
On the Versatility of Parallel Sorting by Regular Sampling (1993)
Xiaobo Li, Paul Lu, Jonathan Schaeffer, John Shillington, Pok Sze Wong, Hanmao Shi
Parallel sorting algorithms have been proposed for a variety of multiple instruction streams, multiple data streams (MIMD) architectures. The algorithm often exploits the strengths of the machine to...
Program Design and Animation in the Enterprise Parallel Programming Environment (1993)
Greg Lobe, Duane Szafron, Duane Szafron, Jonathan Schaeffer, Jonathan Schaeffer
The Enterprise programming environment supports the development of applications that run concurrently on a network of workstations. This paper describes the object-oriented components of Enterprise,...
The Enterprise Model, Jonathan Schaeffer, Duane Szafron, Greg Lobe, Ian Parsons
el programming environments for distributed memory applications. He received an MS (in 1992) and a BS (in 1991) in computing science from the University of Alberta, and a BS in chemistry from the...
August Pp The, Greg Lobe, Duane Szafron, Jonathan Schaeffer
The Enterprise programming environment supports the development of applications that run concurrently on a network of workstations. This paper describes the object-oriented components of Enterprise,...
Enterprise In Context, Gregory V. Wilson, Jonathan Schaeffer, Duane Szafron
The growth of commercial and academic interest in parallel and distributed computing during the past fifteen years has been accompanied by a corresponding increase in the number of available parallel...
A world championship caliber checkers program (1992)
Jonathan Schaeffer, Joseph Culberson, Norman Treloar, Brent Knight, Paul Lu, Duane Szafron
The checkers program Chinook has won the right to play a 40-game match for the World Checkers Championship against Dr. Marion Tinsley. This was earned by placing second, after Dr. Tinsley, at the...
Enterprise in Context: Assessing the Usability of Parallel Programming Environments (1992)
Gregory V. Wilson, Gregory V. Wilson, Jonathan Schaeffer, Jonathan Schaeffer, Duane Szafron, Duane Szafron
The explosive growth of commercial and academic interest in parallel and distributed computing during the past fifteen years has been accompanied by a corresponding increase in the number of...
The Enterprise Model for Developing Distributed Applications (1992)
Greg Lobe, Paul Lu, Paul Lu, Stan Melax, Stan Melax, Ian Parsons, ...
Workstations have been in use for more than a decade now. Although a network of workstations represents a large amount of aggregate computing power, there is a need for software that can harness this...
A World Championship Caliber Checkers Program (1992)
Jonathan Schaeffer, Joseph Culberson, Norman Treloar, Brent Knight, Paul Lu, Duane Szafron
The checkers program Chinook has won the right to play a 40-game match for the World Checkers Championship against Dr. Marion Tinsley. This was earned by placing second, after Dr. Tinsley, at the...
Investigation of the Usability of a Visual Editor for Programming Parallel. . . (1992)
Glen D. Smith, Jonathan Schaeffer, Mark Green, Structuring Distributed, Robert Manchek, Jack J. Dongarra, ...
Parallel and Distributed Processing, IEEE Computer Society Press, Los Alamitos, CA. pp. 608--615. [21] OpenWindowsE Developer's Guide 3.0 User's Guide. [1991]. Mountain View, CA: SunSoft....
Enoch Chan, Enoch Chan, Paul Lu, Paul Lu, Jimmy Mohsin, Jimmy Mohsin, ...
Workstation environments have been in use for more than a decade now. Although a network of workstations together represents a large amount of aggregate computing power, single users often cannot...
Herbert Simon, Herbert A. Simon, Jonathan Schaeffer, Jonathan Schaeffer
n, guarantee a win. In this way, large sub-trees of the game tree could be evaluated without search. The only defect in trying to apply this optimal strategy to chess is that neither human beings nor...
Reviving the Game of Checkers (1991)
Jonathan Schaeffer, Joseph Culberson, Norman Treloar, Brent Knight, Paul Lu, Duane Szafron
Chinook is the strongest 8 × 8 checkers program around today. Its strength is largely a result of brute-force methods. The program is capable of searching to depths that make it a feared tactician....
Reviving the Game of Checkers (1991)
Jonathan Schaeffer, Robert Lake
Abstract. In 1962, a checkers-playing program written by Arthur Samuel defeated a self-proclaimed master player, creating a sensation at the time for the fledgling field of computer science called...
Chunking For Experience (1990)
Michael George, Jonathan Schaeffer
Human game players rely heavily on the experience gained by playing over the games of masters. A player may recall a previous game to either obtain the best move (if he has previously seen the...
Representational Difficulties With Classifier Systems (1989)
Dale Schuurmans, Jonathan Schaeffer
Classifier systems are currently in vogue as a way of using genetic algorithms to demonstrate machine learning. However, there are a number of difficulties with the formalization that can influence...
VCS: Variable Classifier Systems (1989)
Lingyan Shu, Jonathan Schaeffer
Classifier systems (CS) have proven to be useful tools for the study of genetic algorithm based learning. Unfortunately, there are a number of difficulties with the formalization that limit the...
The History Heuristic and Alpha-Beta Search Enhancements in Practice (1989)
Many enhancements to the alpha-beta algorithm have been proposed to help reduce the size of minimax trees. A recent enhancement, the history heuristic, is described that improves the order in which...
Experiments in search and knowledge--[microform] /--by Jonathan Schaeffer. (1987)
Thesis (Ph. D.)--University of Waterloo, 1986.
Low overhead alternatives to SSS (1987)
T. A. Marsland, T. A. Marsland, Alexander Reinefeld, Alexander Reinefeld, Jonathan Schaeffer, Jonathan Schaeffer
Of the many minimax algorithms, SSS * is noteworthy because it usually searches the smallest game trees. Its success can be attributed to the accumulation and use of information acquired while...
New Advances in Alpha-Beta Searching
Jonathan Schaeffer, Aske Plaat
Alpha-Beta has been the algorithm of choice for game-tree search for over three decades. Its success is largely attributable to a variety of enhancements to the basic algorithm that can dramatically...
Best-First and Depth-First Minimax Search in Practice
Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie De Bruin
Most practitioners use a variant of the Alpha-Beta algorithm, a simple depth-first procedure, for searching minimax trees. SSS*, with its best-first search strategy, reportedly offers the potential...
New Advances in Alpha-Beta Searching
Jonathan Schaeffer, Aske Plaat
Alpha-Beta has been the algorithm of choice for game-tree search for over three decades. Its success is largely attributable to a variety of enhancements to the basic algorithm that can dramatically...
Jonathan Schaeffer, Robert Lake
In 1962, a checkers-playing program written by Arthur Samuel defeated a self-proclaimed master player, creating a sensation at the time for the fledgling field of computer science called artificial...