A very recent algorithm shows search of games of imperfect information has been around how both theoretical problems can be fixed (Lisý, Lanctot, for many years. The approach is appealing, for a number of and Bowling 2015), but has yet to be applied to large games reasons: it allows the usage of well-known methods from typically used for search. More recently overestimation of perfect information games, its complexity is magnitudes MAX's knowledge is also dealt with in the field of general lower than the problem of weakly solving a game in the game play (Schofield, Cerexhe, and Thielscher 2013). To the sense of game theory, it can be used in a justin-time manner best of our knowledge, all literature on the deficiencies of (no precalculation phase needed) even for games with PIMC concentrates on the overestimation of MAX's knowledge.

In the field of General Game Playing the imperfectinformationgames present a special challenge for researchers.In general the search space is larger, and thelack of information requires a different decision makingtechnique. A simple Monte Carlo sampling using a particlefilter may serve for the simple games, but this soonfails when more complex games are played. The HyperPlaytechnique was one such ”simple” player, soonenhanced to HyperPlay-II capable of handling the mostcomplex of games. However, this technique is very resourcehungry and may not scale well for larger games.We explore the scalability of HyperPlay-II for a varietyof imperfect-information games and test some perfectinformationpruning techniques to see if they will improveefficiency.

Wildlife poaching presents a serious extinction threat to many animal species. In order to save wildlife in designated wildlife parks, park rangers conduct patrols over the park area to combat such illegal activities. An important aspect of the patrolling activity of the rangers is to anticipate where the poachers are likely to catch animals and then respond accordingly. Previous work has applied defender-attacker Stackelberg Security Games (SSGs) to solve the problem of wildlife protection, wherein attacker behavioral models are used to predict the behaviors of the poachers. However, these behavioral models have several limitations which limit their accuracy in predicting poachers' behavior. First, existing models fail to account for the rangers' imperfect observations w.r.t poaching activities (due to the limited capability of rangers to patrol thoroughly over a vast geographical area). Second, these models are built upon discrete choice models that assume a single agent choosing targets, while it is infeasible to obtain information about every single attacker in wildlife protection. Third, these models do not consider the effect of past poachers' actions on the current poachers' activities, one of the key factors affecting the poachers' behaviors. In this work, we attempt to address these limitations while providing three main contributions. First, we propose a novel hierarchical behavioral model, HiBRID, to predict the poachers' behaviors wherein the rangers' imperfect detection of poaching signs is taken into account --- a significant advance towards existing behavioral models in security games. Furthermore, HiBRID incorporates the temporal effect on the poachers' behaviors. The model also does not require a known number of attackers. Second, we provide two new heuristics: \textit{parameter separation} and \textit{target abstraction} to reduce the computational complexity in learning the model parameters. Finally, we use the real-world data collected in Queen Elizabeth National Park (QENP) in Uganda over 12 years to evaluate the prediction accuracy of our new model.

Over the last decade, building on advances in the areas of knowledge compilation and weighted model counting has drastically increased the scalability of inference in probabilistic logic programs. In this paper, we provide an overview of how this has been possible and point out some open challenges.

This paper overviews recent work on compilation of relational queries into lossless factorized representations. The primary motivation for this compilation is to avoid redundancy in the representation of query results and speed up their computation and subsequent analytics.

The role of decomposition-trees (also known as junction and clique trees) in probabilistic inference is widely known and has been the basis for many well known inference algorithms.Recent approaches have demonstrated that such trees have a "hidden structure," which enables the characterization of tractable problem instances as well as lead to insights that enable boosting the performance of inference algorithms. We consider the MPE problem on a Boolean formula in CNF where each literal in the formula is associated with a weight.We describe techniques for exploiting the junction-tree structure of these formulas in the context of a branch-and-bound algorithm for MPE.

Compiling a Bayesian network into a secondary structure, such as a junction tree or arithmetic circuit allows for offline computations before observations arrive, and quick inference for the marginal of all variables. However, query-based algorithms, such as variable elimination and recursive conditioning, that compute the posterior marginal of few variables given some observations, allow pruning of irrelevant variables, which can reduce the size of the problem. Madsen and Jensen show how lazy evaluation of junction trees can allow both compilation and pruning. In this paper, we adapt the lazy evaluation to arithmetic circuits, allowing the best of both worlds: pruning due to observations and query variables as well as compilation while exploiting local structure and determinism.

While it is empirically confirmed folklore that conjunctive normal form (CNF) is not the ideal input format for QBF solvers, most tool developers and therefore also the users focus on formulas in this restricted structure. One important factor for establishing non-CNF solving is the input format. To overcome drawbacks of available formats, the QCIR format has recently been presented. The QCIR format is a circuit-based input format for quantified Boolean formulas which supports structure sharing. In contrast to previous formats, the representation is very compact, yet still easy to parse and to read for the human user. In this paper, we analyze the QCIR format in detail and provide tools and benchmarks which, we hope, will make its usage attractive and motivate tool developers to support this format as well as users to formulate their encodings in this format.

Increasingly large Knowledge Bases are being created, by crawling the Web or other corpora of documents, and by extracting facts and relations using machine learning techniques. To manage the uncertainty in the data, these KBs rely on probabilistic engines based on Markov Logic Networks (MLN), for which probabilistic inference remains a major challenge. Today's state of the art systems reduce the task of inference to weighted model counting and use an MCMC algorithm wrapped around SampleSAT to generate approximately uniform samples. This approach offers no theoretical error guarantees and, as we show, suffers from poor performance in practice. In this paper we describe SlimShot (Scalable Lifted Inference and Monte Carlo Sampling Hybrid Optimization Technique), a probabilistic inference engine for Web-Scale knowledge bases. SlimShot converts the MLN to a tuple-independent probabilistic database, then uses a simple Monte Carlo-based inference, with three key enhancements: (1) it combines sampling with safe query evaluation, (2) it estimates a conditional probability by jointly computing the numerator and denominator, and (3) it adjusts the proposal distribution based on the sample cardinality. In combination, these three techniques allow us to give formal error guarantees, and we demonstrate empirically that SlimShot outperforms today's state of the art probabilistic inference engines used in knowledge bases.

SAT and #SAT are at the heart of many important problem formulations in AI, the most prominent being reasoning and learning in first-order and probabilistic knowledge bases. In practice, all contemporary systems resort to domain closure: objects in the universe are all and only the ones mentioned in the knowledge base. This is in stark contrast to the natural ability of human beings to infer things about sensory inputs and unforeseen data: they infer the existence of objects from their observations; no predefined list of objects is given or known in advance. In this paper, we introduce the formal foundations for reasoning in open universes in a general way, purely based on SAT and #SAT technology.