Deriving insights from high-dimensional data is one of the core problems in data mining. The difficulty mainly stems from the fact that there are exponentially many variable combinations to potentially consider, and there are infinitely many if we consider weighted combinations, even for linear combinations. Hence, an obvious question is whether we can automate the search for interesting patterns and visualizations. In this paper, we consider the setting where a user wants to learn as efficiently as possible about real-valued attributes. For example, to understand the distribution of crime rates in different geographic areas in terms of other (numerical, ordinal and/or categorical) variables that describe the areas. We introduce a method to find subgroups in the data that are maximally informative (in the formal Information Theoretic sense) with respect to a single or set of real-valued target attributes. The subgroup descriptions are in terms of a succinct set of arbitrarily-typed other attributes. The approach is based on the Subjective Interestingness framework FORSIED to enable the use of prior knowledge when finding most informative non-redundant patterns, and hence the method also supports iterative data mining.

Critical node problems involve identifying a subset of critical nodes from an undirected graph whose removal results in optimizing a pre-defined measure over the residual graph. As useful models for a variety of practical applications, these problems are computational challenging. In this paper, we study the classic critical node problem (CNP) and introduce an effective memetic algorithm for solving CNP. The proposed algorithm combines a double backbone-based crossover operator (to generate promising offspring solutions), a component-based neighborhood search procedure (to find high-quality local optima) and a rank-based pool updating strategy (to guarantee a healthy population). Specially, the component-based neighborhood search integrates two key techniques, i.e., two-phase node exchange strategy and node weighting scheme. The double backbone-based crossover extends the idea of general backbone-based crossovers. Extensive evaluations on 42 synthetic and real-world benchmark instances show that the proposed algorithm discovers 21 new upper bounds and matches 18 previous best-known upper bounds. We also demonstrate the relevance of our algorithm for effectively solving a variant of the classic CNP, called the cardinality-constrained critical node problem. Finally, we investigate the usefulness of each key algorithmic component.

YouTube has updated its search engine in an effort to promote more authoritative videos, hoping to diminish the reach of conspiracy theories, harmful messages and misinformation on the platform, The Wall Street Journal reports. The changes follow the mass shooting in Las Vegas this week, wherein a gunman killed 58 people and wounded more than 500 others at a music festival on the Strip. After the shooting, videos propagating conspiracy theories and misinformation started climbing the ranks in YouTube's search results -- Google and Facebook faced similar problems this week. For example, The WSJ says on Tuesday night, the fifth result for "Las Vegas shooting" on YouTube was a video titled, "Proof Las Vegas Shooting Was a FALSE FLAG attack -- Shooter on 4th Floor," a rumor that has been repeatedly refuted by authorities. YouTube rolled out the changes on Wednesday night, accelerating its existing plans to tweak the search engine.

Real-time heuristic search algorithms follow the agent-centered search paradigm wherein the agent has access only to information local to the agent’s current position in the environment. This allows agents with constant-bounded computational faculties (e.g., memory) to take on search problems of progressively increasing sizes. As the agent’s memory does not scale with the size of the search problem, the heuristic must necessarily be stored externally, in the environment. Storing the heuristic in the environment brings the extra challenge of read/write errors. In video games, introducing error artificially to the heuristics can make the non-player characters (NPC) behave more naturally. In this paper, we evaluate effects of such errors on real-time heuristic search algorithms. In particular, we empirically study the effects of heuristic read redundancy on algorithm performance and compare its effects to the existing technique of using weights in heuristic learning. Finally, we evaluate a recently proposed technique of correcting the heuristic with a one-step error term in the presence of read/write error.

We extend the Expressionist project, and thereby the re-emerging area of grammar-based text generation, by applying a technique from software verification to a critical search problem related to content generation from grammars. In Expressionist, authors attach tags (corresponding to pertinent meanings) to nonterminal symbols in a context-free grammar, which enables the targeted generation of content that expresses requested meanings (i.e., has the requested tags). While previous work has demonstrated methods for requesting content with a single required tag, requests for multiple tags yields a search task over domains that may realistically span quintillions or more elements. In this paper, we reduce Expressionist grammars to symbolic visibly pushdown automata, which allows us to locate in massive search spaces generable outputs that satisfy moderately complex criteria related to tags. While the satisficing of more complex tag criteria is still not feasible using this technique, we forecast a number of opportunities for future directions.

Procedurally generating rich, naturally behaving AI-controlled video game characters is an important open problem. In this paper we focus on a particular aspect of non-playable character (NPC) behavior, long favored by science-fiction writers. Specifically, we study the effects of self-knowledge on NPC behavior. To do so we adopt the well-known framework of agent-centered real-time heuristic search applied to the standard pathfinding task on video-game maps. Such search agents normally use a heuristic function to guide them around a map to the goal state. Heuristic functions are inaccurate underestimates of the remaining distance to goal. What if the agent somehow knew how long it (the agent) would actually take to reach the goal from each state? How would using such self-knowledge in place of a heuristic function affect the agent's behavior? We show that similarly to real life, knowing of one's irrational behavior in a situation can deter the agent from getting into that situation again even if it is, in fact, a part of an optimal solution. We demonstrate the "fear" with a simple example and empirically show that the issue is common in video-game pathfinding. We then analyze the issue theoretically and suggest that "fear" induced by self-knowledge is not a bug but a feature and may potentially be used to develop more naturally behaving NPCs.

A significant amount of work exists on handling partial observability for different game genres in the context of game tree search. However, most of those techniques do not scale up to RTS games. In this paper we present an experimental evaluation of a recently proposed technique, "single believe state generation," in the context of StarCraft. We evaluate the proposed approach in the context of a StarCraft playing bot and show that the proposed technique is enough to bring the performance of the bot close to the theoretical optimal where the bot can observe the whole game state.

Real-Time Strategy games have become a popular test-bed for modern AI system due to their real-time computational constraints, complex multi-unit control problems, and imperfect information. One of the most important aspects of any RTS AI system is the efficient control of units in complex combat scenarios, also known as micromanagement. Recently, a model-based heuristic search technique called Portfolio Greedy Search (PGS) has shown promisingpaper we present the first integration of PGS into the StarCraft game engine, and compare its performance to the current state-of-the-art deep reinforcement learning method in several benchmark combat scenarios. We then perform theperformance for providing real-time decision making in RTS combat scenarios, but has so far only been tested in SparCraft: an RTS combat simulator. In this same experiments within the SparCraft simulator in order to investigate any differences between PGS performance in the simulator and in the actual game. Lastly, we investigate how varying parameters of the SparCraft simulator affect the performance of PGS in the StarCraft game engine. We demonstrate that the performance of PGS relies heavily on the accuracy of the underlying model, outperforming other techniques only for scenarios where the SparCraft simulation model more accurately matches the StarCraft game engine.

Real-time heuristic search algorithms are used for creating agents that rely on local information and move in a bounded amount of time making them an excellent candidate for video games as planning time can be controlled. Path finding on video game maps has become the de facto standard for evaluating real-time heuristic search algorithms. Over the years researchers have worked to identify areas where these algorithms perform poorly in an attempt to mitigate their weaknesses. Recent work illustrates the benefits of tailoring algorithms for a given problem as performance is heavily dependent on the search space. In order to determine which algorithm to select for solving the search problems on a map the developer would have to run all the algorithms in consideration to obtain the correct choice. Our work extends the previous algorithm selection approach to use a deep learning classifier to select the algorithm to use on new maps without having to evaluate the algorithms on the map. To do so we select a portfolio of algorithms and train a classifier to predict which portfolio member to use on a unseen new map. Our empirical results show that selecting algorithms dynamically can outperform the single best algorithm from the portfolio on new maps, as well provide the lower bound for potential improvements to motivate further work on this approach.

Monte Carlo Tree Search (MCTS) is an effective decision making algorithm that often works well without domain knowledge, finding an increasing application in commercial mobile and video games. A promising application of MCTS is creating AI opponents for board and card games, where Information Set MCTS (ISMCTS) can provide a challenging opponent and reduces the cost of creating game-specific AI opponents. Most research to date has aimed at improving the quality of decision making by (IS)MCTS, with respect to time usage. Memory usage is also an important constraint in commercial applications, particularly on mobile platforms or when there are many AI agents. This paper presents the first systematic study of memory bounding techniques for (IS)MCTS. (IS)MCTS is well known to be an anytime algorithm. We also introduce an anyspace version of (IS)MCTS which can make effective use of any pre-specified amount of memory. This algorithm has been implemented in a commercial version of the card game Spades downloaded more than 6 million times. We find that for games of imperfect information high quality decisions can be made with rather small memory footprints, making (IS)MCTS an even more attractive algorithm for commercial game implementations.