The game 2048 has attracted millions of people with its simple yet challenging gameplay, leading to the development of numerous computer players. Most successful computer players for 2048 use evaluation functions trained through temporal difference learning (TD learning) or its variants. While TD learning is highly effective and can improve evaluation functions quickly, the performance of these functions often plateaus after a certain number of timesteps. Therefore, it is important to refine those evaluation functions to further enhance the performance of computer players. In this paper, we extend the conventional TD learning approach and propose two refinement algorithms for 2048. Firstly, we conducted detailed experiments to refine the best open-source neural network, and achieved significant performance improvements, increasing the average score from$2.49 \times 10^{5}$to$3.37 \times 10^{5}$in greedy play (1-ply lookahead) and from$4.87 \times 10^{5}$to$5.45 \times 10^{5}$with 3-ply expectimax search. We also applied our refinement method to the state-of-the-art N-tuple network, improving the average score from$5.85\times 10^{5}$to$6.10\times 10^{5}$with 6-ply expectimax search and the tile-downgrading trick.

DouDizhuis an imperfect information game involving three players, with two different bidding and cardplay phases. The large state and action spaces of the game add to its complexity. Previous studies ofDouDizhuhave primarily concentrated on the cardplay phase, which is the more challenging phase. As research on the cardplay agent deepens, researchers have become interested in how to train agents for the completeDouDizhugame. However, recent studies have overlooked that a poor bidding agent, which always bids 3, hinders the training of the cardplay agent. To enhance the performance of the cardplay agent (and accordingly the complete agent), this study employs a concurrent training method, in which a bidding agent is trained together with a cardplay agent and can quickly learn a good bidding play. To overcome the training difficulty encountered when the complete agent trained with the game score target, we propose a multistage training method: in the initial stage, the complete agent aims to maximize the win rate; in subsequent stages, it gradually shifts to targeting the maximum game score. OurCT-MS3-FullDouZero+agent achieves the highest average game score at0.228$\pm$0.060, while two competing agents, the state-of-the-artCoG23+PerfectDouandST-FullDouZero+, recorded only$-$0.002$\pm$0.058and$-$0.226$\pm$0.056, respectively.

abstract- Reinforcement learning is now an important method for developing strong computer players for games. One of the most fundamental issues in reinforcement learning is the exploration-exploitation dilemma. For Game 2048, existing reinforcement learning algorithms mostly pursued exploitation only, and learning with optimistic initialization has recently achieved state-of-the-art results. In this study, we investigate how and how much optimistic initialization contributes to exploration by using the results of the perfect analysis of Mini2048, a reduced variant of 2048. We find room for improvement in terms of exploration after the detailed analysis, and then we design two learning algorithms with exploratory move selection enhanced with two strategies. The results of the proposed training methods outperform learning with optimistic initialization only, especially when combined with deep search. We also discuss the applicability of our results to the original 2048.

Imperfect information games (IIGs) are a popular subject in the field of artificial intelligence. In this study, we consider them and propose that they can be classified according to the impact and visualizability of the imperfect information. We useGeister, a Board IIG, to create multiple variant games that we use as an abstraction for IIGs. We then train agents to play each variant using deep regret minimization with advantage baselines and model-free learning, a neural-network variation of counterfactual regret minimization. We observe the performance of our agents and use them to qualitatively assess the characteristics of our IIGs with regards to our proposed terminology.

DouDizhu is a challenging game that includes aspects of both competition and cooperation. In this game, players start by bidding based on their hand cards. They then follow by a round of cardplay in which the goal is to empty one’s hand of cards first. So far, other teams have elected to mainly concentrate on the cardplay phase in which agents such as DouZero and PerfectDou have recently achieved top performances. In this paper, we focus on bidding as it is a key component that greatly influences the starting states of the cardplay phase. We train bidding agents with an algorithm similar to DouZero and use PerfectDou for the cardplay phase. We then compare our agent to win-rate based and cheating agents. Our trained agent beat the win-rate agents.

2048 is a popular game for which plenty of computer players have been created. However, many created 2048 players, especially all DNN-based ones, only implicitly use tile values as inputs and access tile position information. In this study, we take one of the best DNN-based 2048 players as a baseline and propose a 2048 player directly using both tile values and tile positions as inputs. Additionally, we explore the possibility of embedding all tile values and positions that we then concatenate with the network's regular value inputs. We first train these variations in a short session and then select the best two models with the baseline to be further trained in a long session. Our best two methods performed better than the baseline DNN player in both short and long training sessions.

Abstract The vertex-centric programming model is now widely used for processing large graphs. User-defined vertex programs are executed in parallel over every vertex of a graph, but the imperative and explicit message-passing style of existing systems makes defining a vertex program unintuitive and difficult. This article presents Fregel, a purely functional domain-specific language for processing large graphs and describes its model, design, and implementation. Fregel is a subset of Haskell, so Haskell tools can be used to test and debug Fregel programs. The vertex-centric computation is abstracted using compositional programming that uses second-order functions on graphs provided by Fregel. A Fregel program can be compiled into imperative programs for use in the Giraph and Pregel+ vertex-centric frameworks. Fregel’s functional nature without side effects enables various transformations and optimizations during the compilation process. Thus, the programmer is freed from the burden of program optimization, which is manually done for existing imperative systems. Experimental results for typical examples demonstrated that the compiled code can be executed with reasonable and promising performance.

Geister is a board imperfect information game created in Germany and presenting an interesting challenge for the field of artificial intelligence. In this study we apply DREAM (Deep Regret Minimization with Advantage Baselines and Model-free Learning), a neural-network variation of Counterfactual Regret Minimization developed by Steinberger et al., to multiple variants of Geister. This paper shows a methodological approach of evaluating game strategies on different variants of Geister and illustrates the possible generalizability of the DREAM algorithm on other board games.

The vertex-centric programming model, known as “think like a vertex”, is being used more and more to support various big graph processing methods through iterative supersteps that execute in parallel a user-defined vertex program over each vertex of a graph. However, the imperative and message-passing style of existing systems makes defining a vertex program unintuitive. In this paper, we show that one can benefit more from “Thinking like a vertex” by “Behaving like a function” rather than “Acting like a procedure” with full use of side effects and explicit control of message passing, state, and termination. We propose a functional approach to vertex-centric graph processing in which the computation at every vertex is abstracted as a higher-order function and present Fregel, a new domain-specific language. Fregel has clear functional semantics, supports declarative description of vertex computation, and can be automatically translated into Pregel, an emerging imperative-style distributed graph processing framework, and thereby achieve promising performance. Experimental results for several typical examples show the promise of this functional approach.

Automata play important roles in wide area of computing and the growth of multicores calls for their efficient parallel implementation. Though it is known in theory that we can perform the computation of a finite automaton in parallel by simulating transitions, its implementation has a large overhead due to the simulation. In this paper we propose a new automaton called simultaneous finite automaton (SFA) for efficient parallel computation of an automaton. The key idea is to extend an automaton so that it involves the simulation of transitions. Since an SFA itself has a good property of parallelism, we can develop easily a parallel implementation without overheads. We have implemented a regular expression matcher based on SFA, and it has achieved over 10-times speedups on an environment with dual hexa-core CPUs in a typical case.

Divide-and-conquer is an important technique in parallel programming. However, algebraic data structures do not fit divide-and-conquer parallelism. For example, the usual pointer-based implementation of lists cannot efficiently be divided at their middle, which prevents us from developing list-iterating divide-and-conquer parallel programs. Tree-iterating programs possibly face a similar problem, because trees might be ill-balanced and list-like shapes. This paper examines parallel programming based on balanced trees: we consider balanced-tree structures and develop recursive functions on them. By virtue of their balancing nature, either bottom-up or top-down recursive functions exploit divide-and-conquer parallelism. Our main contribution is to demonstrate the promise of this approach. We propose a way of systematically developing balanced trees from parallel algorithms, and then, we show that efficient parallel programs on them can be developed by equational reasoning powered by Reynolds' relational parametricity. We consider functions that operate either lists or binary trees, and show that our methods can uniformly deal with both cases. The developed parallel programs are purely functional, correct by construction, and sometimes even simpler than known algorithms.

With the current generalisation of parallel architectures arises the concern of applying formal methods to parallelism. The complexity of parallel, compared to sequential, programs makes them more error-prone and difficult to verify. Bulk Synchronous Parallelism (BSP) is a model of computation which offers a high degree of abstraction like PRAM models but yet a realistic cost model based on a structured parallelism. We propose a framework for refining a sequential specification toward a functional BSP program, the whole process being done with the help of the Coq proof assistant. To do so we define BH, a new homomorphic skeleton, which captures the essence of BSP computation in an algorithmic level, and also serves as a bridge in mapping from high level specification to low level BSP parallel programs.

Parallel programs on lists have been intensively studied. It is well known that associativity provides a good characterization for divide-and-conquer parallel programs. In particular, the third homomorphism theorem is not only useful for systematic development of parallel programs on lists, but it is also suitable for automatic parallelization. The theorem states that if two sequential programs iterate the same list leftward and rightward, respectively, and compute the same value, then there exists a divide-and-conquer parallel program that computes the same value as the sequential programs.While there have been many studies on lists, few have been done for characterizing and developing of parallel programs on trees. Naive divide-and-conquer programs, which divide a tree at the root and compute independent subtrees in parallel, take time that is proportional to the height of the input tree and have poor scalability with respect to the number of processors when the input tree is ill-balanced.In this paper, we develop a method for systematically constructing scalable divide-and-conquer parallel programs on trees, in which two sequential programs lead to a scalable divide-andconquer parallel program. We focus on paths instead of trees so as to utilize rich results on lists and demonstrate that associativity provides good characterization for scalable divide-and-conquer parallel programs on trees. Moreover, we generalize the third homomorphism theorem from lists to trees.We demonstrate the effectiveness of our method with various examples. Our results, being generalizations of known results for lists, are generic in the sense that they work well for all polynomial data structures.

Divide-and-conquer algorithms are suitable for modern parallel machines, tending to have large amounts of inherent parallelism and working well with caches and deep memory hierarchies. Among others, list homomorphisms are a class of recursive functions on lists, which match very well with the divide-and-conquer paradigm. However, direct programming with list homomorphisms is a challenge for many programmers. In this paper, we propose and implement a novel systemthat can automatically derive cost-optimal list homomorphisms from a pair of sequential programs, based on the third homomorphism theorem. Our idea is to reduce extraction of list homomorphisms to derivation of weak right inverses. We show that a weak right inverse always exists and can be automatically generated from a wide class of sequential programs. We demonstrate our system with several nontrivial examples, including the maximum prefix sum problem, the prefix sum computation, the maximum segment sum problem, and the line-of-sight problem. The experimental results show practical efficiency of our automatic parallelization algorithm and good speedups of the generated parallel programs.

Tree contraction algorithms, whose idea was first proposed by Miller and Reif, are important parallel algorithms to implement efficient parallel programs manipulating trees. Despite their efficiency, the tree contraction algorithms have not been widely used due to the difficulties in deriving the tree contracting operations. In particular, the derivation of the tree contracting operations is much difficult when multiple values are referred and updated in each step of the contractions. Such computations often appear in dynamic programming problems on trees. In this paper, we propose an algebraic approach to deriving tree contraction programs from recursive tree programs, by focusing on the properties of commutative semirings. We formalize a new condition for implementing tree reductions with the tree contraction algorithms, and give a systematic derivation of the tree contracting operations. Based on it, we implemented a code generator for tree reductions, which has an optimization mechanism that can remove unnecessary computations in the derived parallel programs. As far as we are aware, this is the first step towards an automatic parallelization system for the development of efficient tree programs.