Search

Spring 2018

Burch, Neil

Decision-making problems with two agents can be modeled as two player games, and a Nash equilibrium is the basic solution concept describing good play in adversarial games. Computing this equilibrium solution for imperfect information games, where players have private, hidden information, is...

2014

Burch, Neil, Holte, Robert, Arneson, Broderick

This manual describes PSVN, a language for describing state space search problems using multi-valued variables that lends itself to efficient calculation of state's successors and predecessors without having to fully ground the operators. It also describes the PSVN compiler, psvn2c, which accepts...

2012

Lanctot, Marc, Gibson, Richard, Burch, Neil, Szafron, Duane

In large extensive form games with imperfect information, Counterfactual Regret Minimization (CFR) is a popular, iterative algorithm for computing approximate Nash equilibria. While the base algorithm performs a full tree traversal on each iteration, Monte Carlo CFR (MCCFR) reduces the per...

2009

Holte, Robert, Zilles, Sandra, Ball, Marcel

Technical report TR09-04. Abstraction is a popular technique for speeding up planning and search. A problem that often arises in using abstraction is the generation of abstract states, called spurious states, from which the goal state is reachable in the abstract space but for which there is no...

2008

Niewiadomski, Robert, Amaral, Jose Nelson, Holte, Robert

Technical report TR08-18. We present an advanced Bidirectional A* algorithm featuring an application of Frontier Search and a strategy for the performance-efficient utilization of External Memory. We present the results of an experimental evaluation demonstrating that this algorithm is capable of...

2008

Schaeffer, Jonathan, Sturtevant, Nathan, Holte, Robert, Anderson, Ken

Technical report TR08-05. The following report describes some techniques that generalize and attempt to improve upon the Coarse-to-Fine Dynamic Programming (CFDP) algorithm developed by Christopher Raphael. CFDP uses a hierarchy of abstraction graphs, iteratively searches to find optimal...

2007

Culberson, Joseph, Yang, Fan, Holte, Robert

Technical report TR07-06. The effectiveness of heuristics search is influnced by the accuracy of the heuristic values. State space abstractions have been proved to be effective for generating admissible heuristics. In this paper, A general definition for abstractions is given. As a demonstration...

2007

Arneson, Broderick

2006

Harms, Janelle, Li, Yuxi, Holte, Robert

Technical report TR06-22. QoS routing has been shown to be NP-hard. A recent study of its hardness shows that the ``worst-case'' may not occur in practice [13]. This suggests that there may exist fast exact algorithms for the multi-constraint shortest path (MCSP) problem, an instance of QoS...

2006

Li, Yuxi, Bai, Baochun, Harms, Janelle, Holte, Robert

Technical report TR06-11. Intra-domain traffic engineering is essential for the operation of an Internet Service Provider (ISP). Demand-oblivious routing (Applegate and Cohen 2003) promises excellent performance guarantee with changing and uncertain traffic demands. However, it is non-trivial...