Machine learning components commonly appear in larger decision-making pipelines; however, the model training process typically focuses only on a loss that measures accuracy between predicted values and ground truth values. Decision-focused learning explicitly integrates the downstream decision problem when training the predictive model, in order to optimize the quality of decisions induced by the predictions. It has been successfully applied to several limited combinatorial problem classes, such as those that can be expressed as linear programs (LP), and submodular optimization. However, these previous applications have uniformly focused on problems from specific classes with simple constraints. Here, we enable decision-focused learning for the broad class of problems that can be encoded as a Mixed Integer Linear Program (MIP), hence supporting arbitrary linear constraints over discrete and continuous variables. We show how to differentiate through a MIP by employing a cutting planes solution approach, which is an exact algorithm that iteratively adds constraints to a continuous relaxation of the problem until an integral solution is found. We evaluate our new end-to-end approach on several real world domains and show that it outperforms the standard two phase approaches that treat prediction and prescription separately, as well as a baseline approach of simply applying decision-focused learning to the LP relaxation of the MIP.

Analyzing reachability in large discrete transition systems is an important sub-problem in several areas of AI, and of CS in general. State space search is a basic method for conducting such an analysis. A wealth of techniques have been proposed to reduce the search space without affecting the existence of (optimal) solution paths. In particular, strong stubborn set (SSS) pruning is a prominent such method, analyzing action dependencies to prune commutative parts of the search space. We herein show how to apply this idea to star-topology decoupled state space search, a recent search reformulation method invented in the context of classical AI planning. Star-topology decoupled state space search, short decoupled search, addresses planning tasks where a single center component interacts with several leaf components. The search exploits a form of conditional independence arising in this setting: given a fixed path p of transitions by the center, the possible leaf moves compliant with p are independent across the leaves. Decoupled search thus searches over center paths only, maintaining the compliant paths for each leaf separately. This avoids the enumeration of combined states across leaves. Just like standard search, decoupled search is adversely affected by commutative parts of its search space. The adaptation of strong stubborn set pruning is challenging due to the more complex structure of the search space, and the resulting ways in which action dependencies may affect the search. We spell out how to address this challenge, designing optimality-preserving decoupled strong stubborn set (DSSS) pruning methods. We introduce a design for star topologies in full generality, as well as simpler design variants for the practically relevant fork and inverted fork special cases. We show that there are cases where DSSS pruning is exponentially more effective than both, decoupled search and SSS pruning, exhibiting true synergy where the whole is more than the sum of its parts. Empirically, DSSS pruning reliably inherits the best of its components, and sometimes outperforms both.

A deep-learning algorithm has been developed which can solve the Rubik's cube faster than any human can. It never fails to complete the puzzle, with a 100 per cent success rate and managing it in around 20 moves. Humans can beat the AI's mark of 18 seconds, the world record is around four seconds, but it is far more inefficient and people often require around 50 moves. It was created by University of California Irvine and can be tried out here. Given an unsolved cube, the machine must decide whether a specific move is an improvement on the existing configuration.

"These characteristics are shared by many other problems in robotics and other domains that require some kind of planning," added Baldi. "Imagine a robot tasked with cleaning up your kitchen: there is an astronomical number of sequences of moves, but only very few lead to a clean kitchen. And randomly moving dirty dishes around is not going to do it." "More broadly, this work is part of a general effort to bridge machine learning AI and symbolic AI to address complex problems that humans solve through planning and reasoning," added Baldi. In the study, researchers wanted to understand how and why the AI made its moves and how long it took to perfect its method.

Finding an energy minimum in the Ising model is an exemplar objective, associated with many combinatorial optimization problems, that is computationally hard in general, but occurs in all areas of modern science. There are several numerical methods, providing solution for the medium size Ising spin systems. However, they are either computationally slow and badly parallelized, or do not give sufficiently good results for the large systems. In this paper, we present a highly parallel algorithm, called Mean-field Annealing from a Random State (MARS), incorporating the best features of the classical simulated annealing (SA) and Mean-Field Annealing (MFA) methods. The algorithm is based on the mean-field descent from a randomly selected configuration and temperature. Since a single run requires little computational effort, the effectiveness can be achieved by massive parallelisation. MARS shows excellent performance both on the large Ising spin systems and on the set of exemplary maximum cut benchmark instances in terms of both solution quality and computational time.

Matching tile games are an extremely popular game genre. Arguably the most popular iteration, Match-3 games, are simple to understand puzzle games, making them great benchmarks for research. In this paper, we propose developing different procedural personas for Match-3 games in order to approximate different human playstyles to create an automated playtesting system. The procedural personas are realized through evolving the utility function for the Monte Carlo Tree Search agent. We compare the performance and results of the evolution agents with the standard Vanilla Monte Carlo Tree Search implementation as well as to a random move-selection agent. We then observe the impacts on both the game's design and the game design process. Lastly, a user study is performed to compare the agents to human play traces.

Games have benchmarked AI methods since of a single game, discovering a few new variations on the inception of the field, with classic board games such existing research topics. The set of · Deckbuilding · Gameplaying · Player Modeling AI problems associated with video games has in recent decades expanded from simply playing games to win, to playing games in particular styles, generating game content, 1 Introduction modeling players etc. Different games pose very different challenges for AI systems, and several different For decades classic board games such as Chess, Checkers, AI challenges can typically be posed by the same and Go have dominated the landscape of AI and game. In this article we analyze the popular collectible games research. Often called the "drosophila of AI" in card game Hearthstone (Blizzard 2014) and describe reference to the drosophila fly's significance in biological a varied set of interesting AI challenges posed by this research, Chess in particular has been the subject game. Collectible card games are relatively understudied of hundreds of academic papers and decades of research in the AI community, despite their popularity and [18]. At the core of many of these approaches is designing the interesting challenges they pose. Analyzing a single algorithms to beat top human players. However, game in-depth in the manner we do here allows us to despite IBM's Deep Blue defeating Garry Kasparov in see the entire field of AI and Games through the lens the 1997 World Chess Championships and DeepMind's AlphaGo defeating Lee Sedol in the 2016 Google Deep-Mind Challenge Match [47], such programs have yet While there is value in designing algorithms to win (e.g.

Among the many achievements of machine learning in recent years, some of the most striking are the victories of the machine against human players in games, such as Google's DeepMind group's conquest of Go in 2016. In such milestones, researchers are often guided by theoretical math that says there can be an optimal strategy to be found, given a good algorithm and enough compute. But what do you do when theory breaks down? Two researchers at Carnegie Mellon University and Facebook went back to the drawing board to solve "heads-up no-limit Texas hold'em," the most popular form of multiplayer poker in the world. Theory isn't computable for this form of the card game, so they designed some elegant search strategies for their computer program, "Pluribus," to beat the best human players in 10,000 hands of poker.

Building on the view of machine learning as search, we demonstrate the necessity of bias in learning, quantifying the role of bias (measured relative to a collection of possible datasets, or more generally, information resources) in increasing the probability of success. For a given degree of bias towards a fixed target, we show that the proportion of favorable information resources is strictly bounded from above. Furthermore, we demonstrate that bias is a conserved quantity, such that no algorithm can be favorably biased towards many distinct targets simultaneously. Thus bias encodes trade-offs. The probability of success for a task can also be measured geometrically, as the angle of agreement between what holds for the actual task and what is assumed by the algorithm, represented in its bias. Lastly, finding a favorably biasing distribution over a fixed set of information resources is provably difficult, unless the set of resources itself is already favorable with respect to the given task and algorithm.