In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.

Q: We analyze the structure of the state space of chess by means of transition path sampling Monte Carlo simulation. Based on the typical number of moves required to transpose a given configuration of chess pieces into another, we conclude that the state space consists of several pockets between which transitions are rare. Skilled players explore an even smaller subset of positions that populate some of these pockets only very sparsely. These results suggest that the usual measures to estimate both, the size of the state space and the size of the tree of legal moves, are not unique indicators of the complexity of the game, but that topological considerations are equally important. Chess is a two-player board game with a small set of rules according to which pieces can be moved. It belongs to the class of games with perfect information that have not been solved yet, due to the sheer size of its state space. The computerized analysis of chess started with a seminal paper by Claude Shannon in 1950 [1], and since about the year 2000 computer programs can regularly beat top-level human players [2]. They do so by employing well-tailored heuristic evaluation functions for the game’s states, which allow one to short-cut the exploration of the vast game tree of possible moves. In this context, chess is often compared to Go, where computers only very recently started to match the performance of human champions [3]. The difference is usually attributed to the different sizes of the games’ state spaces: the game-tree complexity of Go exceeds that of chess by some 200 orders of magnitude. However, while size is an important factor in determining the complexity of a game, the topology of the state space may be equally important. Intuitively, the different kinds of moves performed by different chess pieces impose a highly nontrivial (and directed) topology. It is not at all straightforward to establish whether a given point in the state space is reachable from another one by a sequence of legal moves. We thus face an interesting sampling problem: given two chess configurations, can one establish whether they are connected, i.e., whether there exists a sequence of legal moves that transforms the first configuration into the second? Furthermore, what is the typical distance (in plies, or half moves) between such configurations? Clearly, direct enumeration or standard Monte Carlo sampling are out of reach: after each ply, the game tree is estimated to branch into 30 to 35 subtrees [1]. Here we demonstrate that it is possible to analyze the topological structure of the state space of chess by stochastic-process rare-event sampling (SPRES) [4]. SPRES is a transition-path Monte Carlo sampling scheme that works in full non-equilibrium conditions, where the dynamics is neither stationary nor reversible. 1 Combining SPRES with an optimized chess-move generator [5], we estimate the distribution of path lengths between both randomly generated configurations and those encountered in games played by humans. Analyzing these distributions in terms of random-graph theory, we conjecture that the state space of chess consists of multiple distinct pockets, interconnected by relatively few paths. These pockets are only very sparsely populated by the states that are relevant for skilled play. Previous statistical-physics analyses of chess have focused mostly on the distribution of moves in human gameplay, or on games played by computer chess engines. For example, the popularity of opening sequences follows a power-law distribution according to Zipf’s law [6] (in this 1Our analysis of chess also serves to demonstrate the versatility and power of SPRES as a technique that applies to abstract nonphysical dynamics. p-1 ar X iv :1 60 9. 04 64 8v 1 [ cs .A I] 1 4 Se p 20 16 A. Atashpendar, T. Schilling, and Th. Voigtmann context, Go is rather similar [7]), highly biased by the skill of the players involved [8, 9]. Optimal play (in the sense that moves are evaluated favorably by modern computer chess engines) has also been analyzed in the language of free-energy landscapes [10]. Our approach is entirely different: we consider the set of all legal moves, irrespective of their engine evaluation, in order to establish the connectivity of the state space of chess. Within this space, we then also study the relative size and structure of the subset of positions encountered in games played by chess masters. The state of a chess game at any point in time is entirely described by the board configuration (the positions of all chess pieces), a small set of additional variables that track the possibility of special moves (castling or en-passant capture) and the information regarding which player’s turn it is. The set of possible states is given by all states that involve up to 16 chess pieces per color (there may be fewer due to captures, and the number of pieces and pawns may change due to pawn promotions). Only a subset of all possible states is legal, as for example, the two kings cannot be in check at the same time. Of interest in the following are states that are legal and also accessible from the given initial configuration. As an example of an inaccessible but legal state, consider the case where the position of a bishop differs from its initial position, while the positions of the pawns do not. This state is inaccessible, because pawns are initially placed in front of the other pieces of their colour, their moves are always irreversible and the other pieces (apart from the knights) cannot jump over the pawns. Thus, although the state is legal, it cannot be reached by legal moves. To sample the structure of the state space, we generate sequences of accessible states by randomly drawing moves evenly from all legal moves (Monte Carlo, MC). Most of these states entail dramatic disadvantages for at least one side. Therefore, the set of states encountered in optimalstrategy play is vastly smaller than the set we sample. As a proxy to these unknown optimal states, we use database (DB) states extracted from a database of about two million human-played games [11]. In both cases (MC and DB), we then pick pairs of states randomly and establish their connectivity with respect to the game tree by all legal (MC) moves, i.e., irrespective of whether the connecting pathway contains unfavorable positions in terms of gameplay. In the vicinity of the starting configuration, many randomly drawn pairs of positions are necessarily disconnected, since pawns only move forward and many of the pieces still have to gain freedom to move. At the other end of the game, mating positions act as absorbing states. And in addition, the MC dynamics has a set of absorbing states where only the kings are left on the board. In order to sample states that reflect the intrinsic topology of the state space, we thus restrict the discussion to pairs of states drawn from a depth between 5 and 50 plies into the game. This corresponds loosely to chess players’ notion of the middle game. Inside this window, we did not find an obvious correlation between the ply-depth from which a pair of states was drawn and the separation between them. We sample the pathways between states by means of SPRES [4]. In this method, interfaces in state space are defined by constant values of a scalar reaction coordinate, which quantifies the progress made from one state to the other. Then adaptive sampling of dynamic pathways is carried out such that a constant number of forward transitions between these interfaces is obtained. Once the sampling is completed, observables can be averaged over the ensemble of sampled pathways. In the case of chess, we are in particular interested in the length (number of plies) of the shortest path between two configurations. While the choice of an optimal reaction coordinate is a topic in its own right [10], we make use of the fact that SPRES will sample paths faithfully even for non-optimal choices [4]. As the reaction coordinate, we chose a Euclidean geometric measure of distance from the target configuration. For each piece, the geometric distance is calculated using a metric that is adapted to the type of moves performed by that piece: Chebyshev metric for queens, kings, and bishops, the ceil of half the Chebyshev distance for knights, the Manhattan distance for rooks, and the rank separation for pawns. (For details, see Ref. [5]). Pairs are discarded as disconnected if they are farther apart than 120 plies; this approximation is adapted to the typical length of real chess games. Trivially disconnected pairs are discarded by an initial test based on the reaction coordinate, the pawn structure and the piece count. For the estimation of path lengths, 4000 (3000) pairs generated from MC (DB) that have passed this test have been sampled. Figure 1 shows the histogram of path lengths between those randomly chosen pairs that are connected according to SPRES (corresponding to 79% of all randomly drawn MC pairs and 85% of all pairs drawn from the DB). For pairs generated via MC, the path-length distribution has two distinct contributions, one with a peak at `1 ≈ 20 plies, and a smaller one at `2 ≈ 45 plies. The path-length distribution between pairs sampled from the database is biased to smaller path lengths and has only one prominent peak at a path length slightly below `1, `1 ≈ 18 plies. A tail towards large distances is still seen as a remnant of the second peak found in the MC distribution. Note that the paths found by SPRES for the DB pairs almost certainly pass through non-DB states (i.e. states that are usually not found in games played by humans). A typical engine evaluation function (Stockfish [13]) displays huge fluctuations along the SPRES paths, indicating that these paths will probably never be chosen by skilled human players. The results shown in Fig. 1 reveal that real chess games take place in a subspace that is much more tightly connected than the space of accessible states. The doublepeaked histogram suggests a “blob” structure (see sketch

A: epl draft Sequencing Chess
****
Q: Distributed controllers are oftentimes used in largescale SDN deployments where they run a myriad of network applications simultaneously. Such applications could have different consistency and availability preferences. These controllers need to communicate via east/west interfaces in order to synchronize their state information. The consistency and the availability of the distributed state information are governed by an underlying consistency model. Earlier, we suggested [1] the use of adaptivelyconsistent controllers that can autonomously tune their consistency parameters in order to meet the performance requirements of a certain application. In this paper, we examine the feasibility of employing adaptive controllers that are built on-top of tunable consistency models similar to that of Apache Cassandra. We present an adaptation strategy that uses clustering techniques (sequential k-means and incremental k-means) in order to map a given application performance indicator (χ) into a feasible consistency level (Φ) that can be used with the underlying tunable consistency model. In the cases that we modeled and tested, our results show that in the case of sequential k-means, with a reasonable number of clusters (≥ 50), a plausible mapping (low RMSE) could be estimated between the application performance indicators (χ) and the consistency level indicator (Φ). In the case of incremental k-means, the results also showed that a plausible mapping (low RMSE) could be estimated using a similar number of clusters (≥ 50) by using a small threshold (≃ 0.01).

A: A Clustering-based Consistency Adaptation Strategy for Distributed SDN Controllers
****
Q: I propose a framework for an agent to change its probabilistic beliefs when a new piece of propositional information α is observed. Traditionally, belief change occurs by either a revision process or by an update process, depending on whether the agent is informed with α in a static world or, respectively, whether α is a ‘signal’ from the environment due to an event occurring. Boutilier suggested a unified model of qualitative belief change, which “combines aspects of revision and update, providing a more realistic characterization of belief change.” In this paper, I propose a unified model of quantitative belief change, where an agent’s beliefs are represented as a probability distribution over possible worlds. As does Boutilier, I take a dynamical systems perspective. The proposed approach is evaluated against several rationality postulated, and some properties of the approach are worked out. Information acquired can be due to evolution of the world or revelation about the world. That is, one may notice via some ‘signal’ generated by the changing environment that the environment has changed, or, one may be informed by an independent agent in a static environment that some ‘fact’ holds. In the present work, I deal with belief change of agents who handle uncertainty by maintaining a probability distribution over possible situations. The agents in this framework also have models for nondeterministic events, and noisy observations. Noisy observation models can model imperfect sensory equipment for receiving environmental signals, but they can also model untrustworthy informants in a static world. In this paper, I provide the work of Boutilier (1998) as background, because it has several connections with and was the seed for the present work. However, I do not intend simply to give a probabilistic version of his Generalized Update Semantics. Whereas Boutilier (1998) presents a model for unifying qualitative belief revision and update, I build on his work to present a unified model of belief revision and update in a stochastic (probabilistic) setting. I also take a dynamical systems perspective, like him. Due to my quantitative approach, an agent can maintain a probability distribution Copyright c © 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. over the worlds it believes possible, using an expectation semantics of change. This is in contrast to Boutilier’s “generalized update” approach, which takes a most-plausible event and most-plausible world approach. Finally, my proposal requires a trade-off factor to mix the changes in probability distribution over possible worlds brought about due to the probabilistic belief revision process and, respectively, the probabilistic belief update process. Boutilier’s model has revision and update more tightly coupled. For this reason, his approach is better called “unified” while mine is called “hybrid”. The belief change community does not study probabilistic belief update; it is studied almost exclusively in frameworks employing Bayesian conditioning – for modeling events and actions in dynamical domains (e.g., DBNs, MDPs, POMDPs) (Koller and Friedman, 2009; Poole and Mackworth, 2010, e.g.). The part of my approach responsible for updating stays within the Bayesian framework, but combines the essential elements of belief update with unobservable events and belief update as partially observable Markov decision process (POMDP) state estimation. On the other hand, there is plenty of literature on probabilistic belief revision (Voorbraak, 1999; Grove and Halpern, 1998; Kern-Isberner, 2008; Yue and Liu, 2008, e.g.). The subject is both deep and broad. There is no one accepted approach and to argue which is the best is not the focus of this paper. I shall choose one reasonable method for probabilistic belief revision suitable to the task at hand. In the first section, Boutilier’s ‘generalized update’ is reviewed. Then, in the next section, I introduce stochastic update and stochastic revision, culminating in the ‘hybrid stochastic belief change’ (HSBC) approach. The final section presents an example inspired by Boutilier’s article (1998) and analyses the results. Some proofs of propositions are omitted to save space; they are available on request. Boutilier’s Generalized Update I use Boutilier’s notation and descriptions, except that I am more comfortable with α and β to represent sentences, instead of A and B. It is assumed that an agent has a deductively closed belief set K, a set of sentences drawn from some logical language reflecting the agent’s beliefs about the current state of the world. For ease of presentation, I assume ar X iv :1 60 4. 02 12 6v 1 [ cs .A I] 7 A pr 2 01 6 a logically finite, classical propositional language, denoted L (LCPL in Boutilier (1998)), and consequence operation Cn . The belief set K will often be generated by some finite knowledge base KB (i.e., K = Cn(KB)). The identically true and false propositions are denoted > and ⊥, respectively. Given a set of possible worlds W (or valuations over L) and α ∈ L, the set of α-worlds, that is, the elements of W satisfying α, is denoted by ||α||. The worlds satisfying all sentences in a set K is denoted ||K||.

A:
On Stochastic Belief Revision and Update and their Combination
****