Alpha-Beta is the most common game tree search algorithm, due to its high-performance and straightforward implementation. In practice one must find the best trade-off between heuristic evaluation time and bringing the subset of nodes explored closer to a minimum proof graph. In this paper we present a series of structural properties of minimum proof graphs that help us to prove that finding such graphs is NP-hard for arbitrary DAG inputs, but can be done in linear time for trees. We then introduce the class of fastest-cut-first search heuristics that aim to approximate minimum proof graphs by sorting moves based on approximations of sub-DAG values and sizes. To explore how various aspects of the game tree (such as branching factor and distribution of move values) affect the performance of Alpha-Beta we introduce the class of ``Prefix Value Game Trees'' that allows us to label interior nodes with true minimax values on the fly without search. Using these trees we show that by explicitly attempting to approximate a minimum game tree we are able to achieve performance gains over Alpha-Beta with common extensions.

Monte Carlo tree search has brought significant improvements to the level of computer players in games such as Go, but so far it has not been used very extensively in games of strongly imperfect information with a dynamic board and an emphasis on risk management and decision making under uncertainty. In this paper we explore its application to the game of Kriegspiel (invisible chess), providing three Monte Carlo methods of increasing strength for playing the game with little specific knowledge. We compare these Monte Carlo agents to the strongest known minimax-based Kriegspiel player, obtaining significantly better results with a considerably simpler logic and less domain-specific knowledge.

Many problems have a huge state space and no good heuristic to order moves so as to guide the search toward the best positions. Random games can be used to score positions and evaluate their interest. Random games can also be improved using random games to choose a move to try at each step of a game. Nested Monte-Carlo Search addresses the problem of guiding the search toward better states when there is no available heuristic. It uses nested levels of random games in order to guide the search. The algorithm is studied theoretically on simple abstract problems and applied successfully to three different games: Morpion Solitaire, SameGame and 16x16 Sudoku.

The Canadian Traveler Problem (CTP) is a navigation problem where a graph is initially known,  but some edges may be blocked with a known probability.  The task is to minimize travel effort of reaching the goal. We generalize CTP to allow for remote sensing actions, now requiring minimization  of the sum of the travel cost and the remote sensing cost. Finding optimal policies for both versions is intractable. We provide optimal solutions for special case graphs. We then develop a framework that utilizes heuristics to determine when and where to sense the environment in order to minimize total costs. Several such heuristics, based on the expected total cost are introduced.  Empirical evaluations show the benefits of our heuristics and support some of the theoretical results.

Real-time heuristic search algorithms are used for planning by agents in situations where a constant-bounded amount of deliberation time is required for each action regardless of the problem size.  Such algorithms interleave their planning and execution to ensure real-time response. Furthermore, to guarantee completeness, they typically store improved heuristic estimates for previously expanded states.  Although subsequent planning steps can benefit from updated heuristic estimates, many of the same states are expanded over and over again.   Here we propose a variant of the A* algorithm, Time-Bounded A* (TBA*), that guarantees real-time response. In the domain of path-finding on video-game maps TBA* expands an order of magnitude fewer states than traditional real-time search algorithms, while finding paths of comparable quality. It reaches the same level of performance as recent state-of-the-art real-time search algorithms but, unlike these, requires neither state-space abstractions nor pre-computed pattern databases.

Kidneys are the most prevalent organ transplants, but demand dwarfs supply. Kidney exchanges enable willing but incompatible donor-patient pairs to swap donors. These swaps can include cycles longer than two pairs as well, and chains triggered by altruistic donors. Current kidney exchanges address clearing(deciding who gets kidneys from whom) as an offline problem: they optimize the current batch. In reality, clearing is an online problem where patient-donor pairs and altruistic donors appear and expire over time. In this paper, we study trajectory-based online stochastic optimization algorithms (which use a recent scalable optimal offline solver as a subroutine) for this. We identify tradeoffs in these algorithms between different parameters. We also uncover the need to set the batch size that the algorithms consider an atomic unit. We develop an experimental methodology for setting these parameters, and conduct experiments on real and generated data. We adapt the REGRETS algorithm of Bent and van Hentenryck for the setting. We then develop a better algorithm. We also show that the AMSAA algorithm of Mercier and van Hentenryck does not scale to the nationwide level. Our best online algorithm saves significantly more lives than the current practice of solving each batch separately.

In this paper we address the problem of designing an interruptible system in a setting in which n problem instances, all equally important, must be solved. The system involves  scheduling executions of contract algorithms (which offer a trade-off between allowable computation time and quality of the solution) in m identical parallel processors. When an interruption occurs, the system must report a solution to each of the n problem instances. The quality of this output is then compared to the best-possible algorithm that has foreknowledge of the interruption time and must, likewise, produce solutions to all n problem instances. This extends the well-studied setting in which only one problem instance is queried at interruption time. We propose a schedule which we prove is optimal for the case of a single processor. For multiple processors, we show that the quality of the schedule is within a small factor from optimal.

Understanding the computational complexity of manipulation in elections is arguably the most central agenda in Computational Social Choice. One of the influential variations of the the problem involves a coalition of manipulators trying to make a favorite candidate win the election. Although the complexity of the problem is well-studied under the assumption that the voters are weighted, there were very few successful attempts to abandon this strong assumption. In this paper, we study the complexity of the unweighted coalitional manipulation problem (UCM) under several prominent voting rules. Our main result is that UCM is NP-complete under the maximin rule; this resolves an enigmatic open question. We then show that UCM is NP-complete under the ranked pairs rule, even with respect to a single manipulator. Furthermore, we provide an extreme hardness-of-approximation result for an optimization version of UCM under ranked pairs. Finally, we show that UCM under the Bucklin rule is in P.

An important problem in computational social choice concerns whether it is possible to prevent manipulation of voting rules by making it computationally intractable. To answer this, a key question is how frequently voting rules are manipulable. We [Xia and Conitzer, 2008] recently defined the class of generalized scoring rules (GSRs) and characterized the frequency of manipulability for such rules. We showed, by examples, that most common rules seem to fall into this class. However, no natural axiomatic characterization of the class was given, leaving the possibility that there are natural rules to which these results do not apply. In this paper, we characterize the class of GSRs based on two natural properties: it is equal to the class of rules that are anonymous and finitely locally consistent. Generalized scoring rules also have other uses in computational social choice. For these uses, the order of the GSR (the dimension of its score vector) is important. Our characterization result implies that the order of a GSR is related to the minimum number of locally consistent components of the rule. We proceed to bound the minimum number of locally consistent components for some common rules.

We consider all possible games that have unique PNE payoffs. Our starting point is the classes of games that can be expressed by a conjunction class of two-person strictly competitive games. We first formulate of two binary clauses, and our program rediscovered the notions of games, strictly competitive games and Kats and Thisse's class of weakly unilaterally PNEs in first-order logic. Under our formulation, a class of competitive two-person games, and came games corresponds to a first-order sentence. In particular, the up with several other classes of games that have sentence that corresponds to the class of strictly competitive unique pure Nash equilibrium payoffs. It also came games is a conjunction of two binary clauses with all variables up with new classes of strict games that have unique universally quantified. So we implemented a program pure Nash equilibria, where a game is strict if for that examines all these universally quantified conjunctions of both player different profiles have different payoffs.