Abstract We investigate the problem of cost-optimal planning in ASP. Current ASP planners can be trivially extended to a cost-optimal one by adding weak constraints, but only for a given makespan (number of steps). It is desirable to have a planner that guarantees global optimality. In this paper, we present two approaches to addressing this problem. First, we show how to engineer a cost-optimal planner composed of two ASP programs running in parallel. Using lessons learned from this, we then develop an entirely new approach to cost-optimal planning,stepless planning, which is completely free of makespan. Experiments to compare the two approaches with the only known cost-optimal planner in SAT reveal good potentials for stepless planning in ASP.

AlphaGo Zero pioneered the concept of two-head neural networks in Monte Carlo Tree Search (MCTS), where the policy output is used for prior action probability and the state-value estimate is used for leaf node evaluation. We propose a three-head neural net architecture with policy, state- and action-value outputs, which could lead to more efficient MCTS since neural leaf estimate can still be back-propagated in tree with delayed node expansion and evaluation. To effectively train the newly introduced action-value head on the same game dataset as for two-head nets, we exploit the optimal relations between parent and children nodes for data augmentation and regularization. In our experiments for the game of Hex, the action-value head learning achieves similar error as the state-value prediction of a two-head architecture. The resulting neural net models are then combined with the same Policy Value MCTS (PV-MCTS) implementation. We show that, due to more efficient use of neural net evaluations, PV-MCTS with three-head neural nets consistently performs better than the two-head ones, significantly outplaying the state-of-the-art player MoHex-CNN.

Using deep convolutional neural networks for move prediction has led to massive progress in computer Go. Like Go, Hex has a large branching factor that limits the success of shallow and selective search. We show that deep convolutional neural networks can be used to produce reliable move evaluation in the game of Hex. We begin by collecting self-play games of MoHex 2.0. We then train the neural networks by canonical maximum likelihood. The trained model was evaluated by playing against top programs Wolve and MoHex 2.0. Without any search, the resulting neural network produces similar playing strength as the highly optimized Resistance evaluation function used in Wolve. Finally, using the neural networks as prior knowledge, the reigning Monte-Carlo-tree-search-based world champion player MoHex 2.0 can be enhanced.

Proof Number search (PNS) is an effective algorithm for searching theoretical values on games with non-uniform branching factors. Focused depth-first proof number search (FDFPN) with dynamic widening was proposed for Hex where the branching factor is nearly uniform. However, FDFPN is fragile to its heuristic move ordering function. The recent advances of Convolutional Neural Networks (CNNs) have led to considerable progress in game playing. We investigate how to incorporate the strength of CNNs into solving, with application to the game of Hex. We describe FDFPN-CNN, a new focused DFPN search that uses convolutional neural networks. FDFPN-CNN integrates two CNNs trained from games played by expert players. The value approximation CNN provides reliable information for defining the widening size by estimating the value of the node to expand, while the policy CNN selects promising children nodes to the search. On 8x8 Hex, experimental results show FDFPN-CNN performs notably better than FDFPN, suggesting a promising direction for better solving Hex positions where learning from strong players is possible.

For some two-player games (e.g. Go), no accurate and inexpensive heuristic is known for evaluating leaves of a search tree. For other games (e.g. chess), a heuristic is known (sum of piece values). For other games (e.g. Hex), only a local heuristic — one that compares children reliably, but non-siblings poorly — is known (cell voltage drop in the Shannon/Anshelevich electric circuit model). In this paper we introduce a search algorithm for a two-player perfect information game with a reasonable local heuristic. Sibling Conspiracy Number Search (SCNS) is an anytime best-first version of Conspiracy Number Search based not on evaluation of leaf states of the search tree, but — for each node — on relative evaluation scores of all children of that node. SCNS refines CNS search value intervals, converging to Proof Number Search. SCNS is a good framework for a game player. We tested SCNS in the domain of Hex, with promising results. We implemented an 11-by-11 SCNS Hex bot, DeepHex. We competed DeepHex against current Hex bot champion MoHex, a Monte-Carlo Tree Search player, and previous Hex bot champion Wolve, an Alpha-Beta Search player. DeepHex widely outperforms Wolve at all time levels, and narrowly outperforms MoHex once time reaches 4min/move.

For connection games such as Hex or Y or Havannah, finding guaranteed cell-to-cell connection strategies can be a computational bottleneck. In automated players and solvers, sets of such virtual connections are often found with Anshelevich's H-search algorithm: initialize trivial connections, and then repeatedly apply an AND-rule (for combining connections in series) and an OR-rule (for combining connections in parallel). We present FastVC Search, a new algorithm for finding such connections. FastVC Search is more effective than H-search when finding a representative set of connections quickly is more important than finding a larger set of connections slowly. We tested FastVC Search in an alpha-beta player Wolve, a Monte Carlo tree search player MoHex, and a proof number search implementation called Solver. It does not strengthen Wolve, but it significantly strengthens MoHex and Solver.

Fully homomorphic cryptography allows arbitrary computations to be carried out on encrypted data and an encrypted result to be obtained which encrypts the result of the computation performed on the plaintext. The first fully homomorphic cryptosystem was introduced by Gentry in the summer of 2009. In this research, we are interested in evaluating the performance of Gentry's algorithm applied to cloud computing. To conduct the experiments, a cloud was built using Open Stack to provide the virtualized infrastructure for execution. The software architecture was then designed to support parallel processing of Gentry's algorithm on the cloud. The cloud and architecture together provide an environment for experimental instrumentation and study. This paper focuses on the design of an architecture for the study of parallel processing of fully homomorphic algorithms on the cloud.

Hex, the classic board game invented by Piet Hein in 1942 and independently by John Nash in 1948, has been a domain of AI research since Claude Shannon's seminal work in the 1950s. Until the Monte Carlo Go revolution a few years ago, the best computer Hex players used knowledge-intensive alpha-beta search. Since that time, strong Monte Carlo Hex players have appeared that are on par with the best alpha-beta Hex players. In this paper, we describe MoHex, the Monte Carlo tree search Hex player that won gold at the 2009 Computer Olympiad. Our main contributions to Monte Carlo tree search include using inferior cell analysis and connection strategy computation to prune the search tree. In particular, we run our random game simulations not on the actual game position, but on a reduced equivalent board.

We use a new structural theorem on the presence of two-pairs in weakly chordal graphs to develop improved algorithms. For the recognition problem, we reduce the time complexity from O( mn 2 ) to O( m 2 ) and the space complexity from O( n 3 ) to O( m + n ), and also produce a hole or antihole if the input graph is not weakly chordal. For the optimization problems, the complexity of the clique and coloring problems is reduced from O( mn 2 ) to O( n 3 ) and the complexity of the independent set and clique cover problems is improved from O( n 4 ) to O( mn ). The space complexity of our optimization algorithms is O( m + n ).

The class of weakly triangulated comparability graphs and their complements are generalizations of interval graphs and chordal comparability graphs. We show that problems on these classes of graphs can be solved efficiently by transforming them into problems on chordal bipartite graphs. We show that recognition and independent set on weakly triangulated comparability graphs can be solved in O(n 2 ) time in this manner, and that the number of weakly triangulated comparability graphs is $2^{\Theta ( n {{\log}^2} n)}$.\ We also give algorithms to compute transitive closure and transitive reduction in O(n 2 loglogn) time if the underlying undirected graph of the transitive closure is a weakly triangulated comparability graph.