This paper analyzes the behavior of solving Life-and-Death (L&D) problems in the game of Go using current state-of-the-art computer Go solvers with two techniques: the Relevance-Zone Based Search (RZS) and the relevance-zone pattern table. We examined the solutions derived by relevance-zone based solvers on seven L&D problems from the renowned book “Life and Death Dictionary” written by Cho Chikun, a Go grandmaster, and found several interesting results. First, for each problem, the solvers identify a relevance-zone that highlights the critical areas for solving. Second, the solvers discover a series of patterns, including some that are rare. Finally, the solvers even find different answers compared to the given solutions for two problems. We also identified two issues with the solver: (a) it misjudges values of rare patterns, and (b) it tends to prioritize living directly rather than maximizing territory, which differs from the behavior of human Go players. We suggest possible approaches to address these issues in future work.

Human-like agents have long been one of the goals in pursuing artificial intelligence. Although reinforcement learning (RL) has achieved superhuman performance in many domains, relatively little attention has been focused on designing human-like RL agents. As a result, many reward-driven RL agents often exhibit unnatural behaviors compared to humans, raising concerns for both interpretability and trustworthiness. To achieve human-like behavior in RL, this paper first formulates human-likeness as trajectory optimization, where the objective is to find an action sequence that closely aligns with human behavior while also maximizing rewards, and adapts the classic receding-horizon control to human-like learning as a tractable and efficient implementation. To achieve this, we introduce Macro Action Quantization (MAQ), a human-like RL framework that distills human demonstrations into macro actions via Vector-Quantized VAE. Experiments on D4RL Adroit benchmarks show that MAQ significantly improves human-likeness, increasing trajectory similarity scores, and achieving the highest human-likeness rankings among all RL agents in the human evaluation study. Our results also demonstrate that MAQ can be easily integrated into various off-the-shelf RL algorithms, opening a promising direction for learning human-like RL agents. Our code is available at https://rlg.iis.sinica.edu.tw/papers/MAQ.

Vision-language models (VLMs) often struggle with culturally specific content — a challenge largely overlooked by existing benchmarks that focus on dominant languages and globalized datasets. We introduce TᴀɪᴡᴀɴVQA, a VQA benchmark designed for Taiwanese culture to evaluate recognition and reasoning in regional contexts. TᴀɪᴡᴀɴVQA contains 2,736 images and 5,472 manually curated questions covering topics such as traditional foods, public signs, festivals, and landmarks. The official benchmark set includes 1,000 images and 2,000 questions for systematic assessment, with the remainder of the data used as training material. Evaluations on state-of-the-art VLMs reveal strong visual recognition but notable weaknesses in cultural reasoning. To address this, we propose a data augmentation strategy that combines human-annotated and synthesized dialogues to enhance cultural understanding. Fine-tuning yields significant gains on TᴀɪᴡᴀɴVQA while maintaining stable performance on other multimodal tasks. To further explore the models’ cultural understanding, we conducted an open-ended question answering experiment. The results indicate a notable decline in cultural knowledge generation ($\approx$10–20\%), suggesting challenges remain. TᴀɪᴡᴀɴVQA offers a scalable framework for building culturally grounded AI models in low-resource cultures, promoting diversity and fairness in multimodal AI. Our dataset and code are publicly available on [Hugging Face](https://huggingface.co/datasets/hhhuang/TaiwanVQA) and [GitHub](https://github.com/hhhuang/TaiwanVQA).

Mahjongis a four-player stochastic imperfect-information game. In this article, we utilize importance sampling within Monte Carlo tree search (MCTS) to enhance the playing strength of ourMahjongprogram,MeowCaTS. First, we propose a tree structure called the merging solitary tile model, which facilitates the application of importance sampling. This model also reduces the branching factor of the search tree. Second, we apply importance sampling to MCTS and introduce the calculation of importance weights during the backpropagation stage. Finally, we design a multidepth transposition table to accumulate simulation results of similar positions in MCTS, further enhancing the strength ofMeowCaTS. In the experiments, the performance of the proposed methods was analyzed, and the results showed a significant improvement. Notably,MeowCaTSwon the first place in Computer Olympiad 2023.

Proximal Policy Optimization algorithm employing a clipped surrogate objective (PPO-Clip) is a prominent exemplar of the policy optimization methods. However, despite its remarkable empirical success, PPO-Clip lacks theoretical substantiation to date. In this paper, we contribute to the field by establishing the first global convergence results of a PPO-Clip variant in both tabular and neural function approximation settings. Our findings highlight the O(1/√T ) min-iterate convergence rate specifically in the context of neural function approximation. We tackle the inherent challenges in analyzing PPO-Clip through three central concepts: (i) We introduce a generalized version of the PPO-Clip objective, illuminated by its connection with the hinge loss. (ii) Employing entropic mirror descent, we establish asymptotic convergence for tabular PPO-Clip with direct policy parameterization. (iii) Inspired by the tabular analysis, we streamline convergence analysis by introducing a two-step policy improvement approach. This decouples policy search from complex neural policy parameterization using a regression-based update scheme. Furthermore, we gain deeper insights into the efficacy of PPO-Clip by interpreting these generalized objectives. Our theoretical findings also mark the first characterization of the influence of the clipping mechanism on PPO-Clip convergence. Importantly, the clipping range affects only the pre-constant of the convergence rate.

Deep Reinforcement Learning (DRL) has achieved remarkable success, ranging from complex computer games to real-world applications, showing the potential for intelligent agents capable of learning in dynamic environments. However, its application in real-world scenarios presents challenges, including the jerky problem, in which jerky trajectories not only compromise system safety but also increase power consumption and shorten the service life of robotic and autonomous systems. To address jerky actions, a method called conditioning for action policy smoothness (CAPS) was proposed by adding regularization terms to reduce the action changes. This paper further proposes a novel method, named Gradient-based CAPS (Grad-CAPS), that modifies CAPS by reducing the difference in the gradient of action and then uses displacement normalization to enable the agent to adapt to invariant action scales. Consequently, our method effectively reduces zigzagging action sequences while enhancing policy expressiveness and the adaptability of our method across diverse scenarios and environments. In the experiments, we integrated Grad-CAPS with different reinforcement learning algorithms and evaluated its performance on various robotic-related tasks in DeepMind Control Suite and OpenAI Gym environments. The results demonstrate that Grad-CAPS effectively improves performance while maintaining a comparable level of smoothness compared to CAPS and Vanilla agents.

This paper describes a Relevance-Zone pattern table (RZT) that can be used to replace a traditional transposition table. An RZT stores exact game values for patterns that are discovered during a Relevance-Zone-Based Search (RZS), which is the current state-of-the-art in solving life-and-death (L&D) problems in Go. Positions that share the same pattern can reuse the same exact game value in the RZT. The pattern matching scheme for RZTs is implemented using a radix tree, taking into consideration patterns with different shapes. To improve the efficiency of table lookups, we designed a heuristic that prevents redundant lookups. The heuristic can safely skip previously queried patterns for a given position, reducing the overhead to 10% of the original cost. We also analyze the time complexity of the RZT both theoretically and empirically. Experiments show the overhead of traversing the radix tree in practice during lookup remain flat logarithmically in relation to the number of entries stored in the table. Experiments also show that the use of an RZT instead of a traditional transposition table significantly reduces the number of searched nodes on two data sets of$7 \times 7$and$19 \times 19$L&D Go problems.

It is crucial to address the following issues for ubiquitous robotics manipulation applications: (a) vision-based manipulation tasks require the robot to visually learn and understand the object with rich information like dense object descriptors; and (b) sim-to-real transfer in robotics aims to close the gap between simulated and real data. In this paper, we present Sim-to-Real Dense Object Nets (SRDONs), a dense object descriptors that not only understands the object via appropriate representation but also maps simulated and real data to a unified feature space with pixel consistency. We proposed an object-to-object matching method for image pairs from different scenes and different domains. This method helps reduce the effort of training data from real-world by taking advantage of public datasets, such as GraspNet. With sim-to-real object representation consistency, our SRDONs can serve as a building block for a variety of sim-to-real manipulation tasks. We demonstrate in experiments that pre-trained SRDONs significantly improve performances on unseen objects and unseen visual environments for various robotic tasks with zero real-world training.

Deep reinforcement learning has achieved signif-icant results in low-level controlling tasks. However, for some applications like autonomous driving and drone flying, it is difficult to control behavior stably since the agent may suddenly change its actions which often lowers the controlling sys-tem's efficiency, induces excessive mechanical wear, and causes uncontrollable, dangerous behavior to the vehicle. Recently, a method called conditioning for action policy smoothness (CAPS) was proposed to solve the problem of jerkiness in low-dimensional features for applications such as quadrotor drones. To cope with high-dimensional features, this paper proposes image-based regularization for action smoothness (1-RAS) for solving jerky control in autonomous miniature car racing. We also introduce a control based on impact ratio, an adaptive regularization weight to control the smoothness constraint, called IR control. In the experiment, an agent with 1- RAS and IR control significantly improves the success rate from 59% to 95%. In the real-world-track experiment, the agent also outperforms other methods, namely reducing the average finish lap time, while also improving the completion rate even without real world training. This is also justified by an agent based on I-RAS winning the 2022 AWS DeepRacer Final Championship Cup.

Game solving is a similar, yet more difficult task than mastering a game. Solving a game typically means to find the game-theoretic value (outcome given optimal play), and optionally a full strategy to follow in order to achieve that outcome. The AlphaZero algorithm has demonstrated super-human level play, and its powerful policy and value predictions have also served as heuristics in game solving. However, to solve a game and obtain a full strategy, a winning response must be found for all possible moves by the losing player. This includes very poor lines of play from the losing side, for which the AlphaZero self-play process will not encounter. AlphaZero-based heuristics can be highly inaccurate when evaluating these out-of-distribution positions, which occur throughout the entire search. To address this issue, this paper investigates applying online fine-tuning while searching and proposes two methods to learn tailor-designed heuristics for game solving. Our experiments show that using online fine-tuning can solve a series of challenging 7x7 Killall-Go problems, using only 23.54\% of computation time compared to the baseline without online fine-tuning. Results suggest that the savings scale with problem size. Our method can further be extended to any tree search algorithm for problem solving. Our code is available at https://rlg.iis.sinica.edu.tw/papers/neurips2023-online-fine-tuning-solver.

Goal-achieving problems are puzzles that set up a specific situation with a clear objective. An example that is well-studied is the category of life-and-death (L&D) problems for Go, which helps players hone their skill of identifying region safety. Many previous methods like lambda search try null moves first, then derive so-called relevance zones (RZs), outside of which the opponent does not need to search. This paper first proposes a novel RZ-based approach, called the RZ-Based Search (RZS), to solving L&D problems for Go. RZS tries moves before determining whether they are null moves post-hoc. This means we do not need to rely on null move heuristics, resulting in a more elegant algorithm, so that it can also be seamlessly incorporated into AlphaZero's super-human level play in our solver. To repurpose AlphaZero for solving, we also propose a new training method called Faster to Life (FTL), which modifies AlphaZero to entice it to win more quickly. We use RZS and FTL to solve L&D problems on Go, namely solving 68 among 106 problems from a professional L&D book while a previous state-of-the-art program TSUMEGO-EXPLORER solves 11 only. Finally, we discuss that the approach is generic in the sense that RZS is applicable to solving many other goal-achieving problems for board games.

Picking cluttered general objects is a challenging task due to the complex geometries and various stacking configurations. Many prior works utilize pose estimation for picking, but pose estimation is difficult on cluttered objects. In this paper, we propose Cluttered Objects Descriptors (CODs), a dense cluttered objects descriptor which can represent rich object structures, and use the pre-trained CODs network along with its intermediate outputs to train a picking policy. Additionally, we train the policy with reinforcement learning, which enable the policy to learn picking without supervision. We conduct experiments to demonstrate that our CODs is able to consistently represent seen and unseen cluttered objects, which allowed for the picking policy to robustly pick cluttered general objects. The resulting policy can pick 96.69% of unseen objects in our experimental environment that are twice as cluttered as the training scenarios.

The success of AlphaZero (AZ) has demonstrated that neural-network-based Go AIs can surpass human performance by a large margin. Given that the state space of Go is extremely large and a human player can play the game from any legal state, we ask whether adversarial states exist for Go AIs that may lead them to play surprisingly wrong actions.In this paper, we first extend the concept of adversarial examples to the game of Go: we generate perturbed states that are ``semantically'' equivalent to the original state by adding meaningless moves to the game, and an adversarial state is a perturbed state leading to an undoubtedly inferior action that is obvious even for Go beginners. However, searching the adversarial state is challenging due to the large, discrete, and non-differentiable search space. To tackle this challenge, we develop the first adversarial attack on Go AIs that can efficiently search for adversarial states by strategically reducing the search space. This method can also be extended to other board games such as NoGo. Experimentally, we show that the actions taken by both Policy-Value neural network (PV-NN) and Monte Carlo tree search (MCTS) can be misled by adding one or two meaningless stones; for example, on 58\% of the AlphaGo Zero self-play games, our method can make the widely used KataGo agent with 50 simulations of MCTS plays a losing action by adding two meaningless stones. We additionally evaluated the adversarial examples found by our algorithm with amateur human Go players, and 90\% of examples indeed lead the Go agent to play an obviously inferior action. Ourcode is available at \url{https://PaperCode.cc/GoAttack}.

Temporal difference (TD) learning and its variants, such as multistage TD learning and temporal coherence (TC) learning, have been successfully applied to2048. These methods rely on the stochasticity of the environment of2048for exploration. In this article, we propose to employ optimistic initialization (OI) to encourage exploration for2048, and empirically show that the learning quality is significantly improved. This approach optimistically initializes the feature weights to very large values. Since weights tend to be reduced once the states are visited, agents tend to explore those states which are unvisited or visited few times. Our experiments show that both TD and TC learning with OI significantly improve the performance. As a result, the network size required to achieve the same performance is significantly reduced. With additional tunings such as expectimax search, multistage learning, and tile-downgrading technique, our design achieves the state-of-the-art performance, namely an average score of 625 377 and a rate of 72% reaching 32 768-tiles. In addition, for sufficiently large tests, 65 536-tiles are reached at a rate of 0.02%.

Monte Carlo tree search (MCTS) has achieved state-of-the-art results in many domains such as Go and Atari games when combining with deep neural networks (DNNs). When more simulations are executed, MCTS can achieve higher performance but also requires enormous amounts of CPU and GPU resources. However, not all states require a long searching time to identify the best action that the agent can find. For example, in 19x19 Go and NoGo, we found that for more than half of the states, the best action predicted by DNN remains unchanged even after searching 2 minutes. This implies that a significant amount of resources can be saved if we are able to stop the searching earlier when we are confident with the current searching result. In this paper, we propose to achieve this goal by predicting the uncertainty of the current searching status and use the result to decide whether we should stop searching. With our algorithm, called Dynamic Simulation MCTS (DS-MCTS), we can speed up a NoGo agent trained by AlphaZero 2.5 times faster while maintaining a similar winning rate, which is critical for training and conducting experiments. Also, under the same average simulation count, our method can achieve a 61\% winning rate against the original program.

On playing video games, different players usually have their own playstyles. Recently, there have been great improvements for the video game AIs on the playing strength. However, past researches for analyzing the behaviors of players still used heuristic rules or the behavior features with the game-environment support, thus being exhausted for the developers to define the features of discriminating various playstyles. In this paper, we propose the first metric for video game playstyles directly from the game observations and actions, without any prior specification on the playstyle in the target game. Our proposed method is built upon a novel scheme of learning discrete representations that can map game observations into latent discrete states, such that playstyles can be exhibited from these discrete states. Namely, we measure the playstyle distance based on game observations aligned to the same states. We demonstrate high playstyle accuracy of our metric in experiments on some video game platforms, including TORCS, RGSK, and seven Atari games, and for different agents including rule-based AI bots, learning-based AI bots, and human players.

AlphaZero has been very successful in many games. Unfortunately, it still consumes a huge amount of computing resources, the majority of which is spent in self-play. Hyperparameter tuning exacerbates the training cost since each hyperparameter configuration requires its own time to train one run, during which it will generate its own self-play records. As a result, multiple runs are usually needed for different hyperparameter configurations. This paper proposes using population based training (PBT) to help tune hyperparameters dynamically and improve strength during training time. Another significant advantage is that this method requires a single run only, while incurring a small additional time cost, since the time for generating self-play records remains unchanged though the time for optimization is increased following the AlphaZero training algorithm. In our experiments for 9x9 Go, the PBT method is able to achieve a higher win rate for 9x9 Go than the baselines, each with its own hyperparameter configuration and trained individually. For 19x19 Go, with PBT, we are able to obtain improvements in playing strength. Specifically, the PBT agent can obtain up to 74% win rate against ELF OpenGo, an open-source state-of-the-art AlphaZero program using a neural network of a comparable capacity. This is compared to a saturated non-PBT agent, which achieves a win rate of 47% against ELF OpenGo under the same circumstances.

This paper describes the application of modified comparison training for automatic feature weight tuning. The final objective is to improve the evaluation functions used in Chinese chess programs. First, we apply n-tuple networks to extract features. N-tuple networks require very little expert knowledge through its large numbers of features, while simultaneously allowing easy access. Second, we propose a modified comparison training into which tapered eval is incorporated. Experiments show that with the same features and the same Chinese chess program, the automatically tuned feature weights achieved a win rate of 86.58% against the hand-tuned features. The above trained version was then improved by adding additional features, most importantly n-tuple features. This improved version achieved a win rate of 81.65% against the trained version without additional features.

This paper proposes an approach to strength adjustment for MCTS-based game-playing programs. In this approach, we use a softmax policy with a strength index z to choose moves. Most importantly, we filter low quality moves by excluding those that have a lower simulation count than a pre-defined threshold ratio of the maximum simulation count. We perform a theoretical analysis, reaching the result that the adjusted policy is guaranteed to choose moves exceeding a lower bound in strength by using a threshold ratio. The approach is applied to the Go program ELF OpenGo. The experiment results show that z is highly correlated to the empirical strength; namely, given a threshold ratio 0.1, z is linearly related to the Elo rating with regression error 47.95 Elo where −2≤z ≤2. Meanwhile, the covered strength range is about 800 Elo ratings in the interval of z in [−2,2]. With the ease of strength adjustment using z, we present two methods to adjust strength and predict opponents’ strengths dynamically. To our knowledge, this result is state-of-the-art in terms of the range of strengths in Elo rating while maintaining a controllable relationship between the strength and a strength index.

Many of the strongest game playing programs use a combination of Monte Carlo tree search (MCTS) and deep neural networks (DNN), where the DNNs are used as policy or value evaluators. Given a limited budget, such as online playing or during the self-play phase of AlphaZero (AZ) training, a balance needs to be reached between accurate state estimation and more MCTS simulations, both of which are critical for a strong game playing agent. Typically, larger DNNs are better at generalization and accurate evaluation, while smaller DNNs are less costly, and therefore can lead to more MCTS simulations and bigger search trees with the same budget. This paper introduces a new method called the multiple policy value MCTS (MPV-MCTS), which combines multiple policy value neural networks (PV-NNs) of various sizes to retain advantages of each network, where two PV-NNs f_S and f_L are used in this paper. We show through experiments on the game NoGo that a combined f_S and f_L MPV-MCTS outperforms single PV-NN with policy value MCTS, called PV-MCTS. Additionally, MPV-MCTS also outperforms PV-MCTS for AZ training.

Learning rate scheduler has been a critical issue in the deep neural network training. Several schedulers and methods have been proposed, including step decay scheduler, adaptive method, cosine scheduler and cyclical scheduler. This paper proposes a new scheduling method, named hyperbolic-tangent decay (HTD). We run experiments on several benchmarks such as: ResNet, Wide ResNet and DenseNet for CIFAR-10 and CIFAR-100 datasets, LSTM for PAMAP2 dataset, ResNet on ImageNet and Fashion-MNIST datasets. In our experiments, HTD outperforms step decay and cosine scheduler in nearly all cases, while requiring less hyperparameters than step decay, and more flexible than cosine scheduler. Code is available at https://github.com/BIGBALLON/HTD.

Phantom Go is a derivative of Go with imperfect information. It is challenging in AI field due to its great uncertainty of the hidden information and high game complexity inherited from Go. To deal with this imperfect information game with large game tree complexity, a general search framework named belief-state Monte Carlo tree search (BS-MCTS) is put forward in this paper. BS-MCTS incorporates belief-states into Monte Carlo Tree Search, where belief-state is a notation derived from philosophy to represent the probability that speculation is in accordance with reality. In BS-MCTS, a belief-state tree, in which each node is a belief-state, is constructed and search proceeds in accordance with beliefs. Then, Opponent Guessing and Opponent Predicting are proposed to illuminate the learning mechanism of beliefs with heuristic information. The beliefs are learned by heuristic information during search by specific methods, and we propose Opponent Guessing and Opponent Predicting to illuminate the learning mechanism. Besides, some possible improvements of the framework are investigated, such as incremental updating and all moves as first (AMAF) heuristic. Technical details are demonstrated about applying BS-MCTS to Phantom Go, especially on inference strategy. We examine the playing strength of the BS-MCTS and AMAF-BS-MCTS in Phantom Go by varying search parameters, also testify the proposed improvements.

Deep learning (DL) and reinforcement learning (RL) have been applied with great success to many games, including Go and Atari 2600 games. Monte Carlo Tree Search (MCTS), developed in 2006, can be viewed as a kind of online RL. This technique has greatly improved the level of Go-playing programs. MCTS has since become the state of the art for many other games including Hex, Havannah, and general game playing, and has found much success in applications as diverse as scheduling, unit commitment problems, and probabilistic planning. DL has transformed fields such as image and video recognition and speech understanding. In computer games, DL started making its mark in 2014, when teams from the University of Edinburgh and Google DeepMind independently applied deep convolutional neural networks (DCNNs) to the problem of expertmove prediction in Go.Clark and Storkey’s DCNN achieved a move prediction rate of 44%, exceeding all previously published results. DeepMind’s publication followed soon after, with a DCNN that reached 55%. The combination of DL and RL led to great advances in Atari 2600 game playing, and to the ultimate breakthrough in computer Go. In 2017, DeepMind proposed a new deep reinforcement learning (DRL) algorithm and developed AlphaGo Zero, which is significant for not requiring any human knowledge of Go. By removing the requirement for domain knowledge, DRL is also flexible in that the method can be applied to a wide range of games and problems, ushering in a variety of new research opportunities. In this special issue, we are delighted to bring you eight articles on applying DL/RL related techniques to games research.

This paper proposes a new approach to a novel value network architecture for the gameGo, called a multilabeled (ML) value network. In the ML value network, different values (win rates) are trained simultaneously for different settings of komi, a compensation given to balance the initiative of playing first. The ML value network has three advantages: 1) it outputs values for different komi; (2) it supports dynamic komi; and (3) it lowers the mean squared error (MSE). This paper also proposes a new dynamic komi method to improve game-playing strength. This paper also performs experiments to demonstrate the merits of the architecture. First, the MSE of the ML value network is generally lower than the value network alone. Second, the program based on the ML value network wins by a rate of 67.6% against the program based on the value network alone. Third, the program with the proposed dynamic komi method significantly improves the playing strength over the baseline that does not use dynamic komi, especially for handicap games. To our knowledge, up to date, no handicap games have been played openly by programs using value networks. This paper provides these programs with a useful approach to playing handicap games.

Automatically acquiring domain knowledge from professional game records, a kind of pattern learning, is an attractive and challenging issue in computer Go. This paper proposes a supervised learning method, by introducing a new generalized Bradley-Terry model, named Only-One-Victor, to learn patterns from game records. Basically, our algorithm applies the same idea with Elo rating algorithm, which considers each move in game records as a group of move patterns, and the selected move as the winner of a kind of competition among all groups on current board. However, being different from the generalized Bradley-Terry model for group competition used in Elo rating algorithm, Only-One-Victor model in our work simulates the process of making selection from a set of possible candidates by considering such process as a group of independent pairwise comparisons. We use a graph theory model to prove the correctness of Only-One-Victor model. In addition, we also apply the Minorization-Maximization (MM) to solve the optimization task. Therefore, our algorithm still enjoys many computational advantages of Elo rating algorithm, such as the scalability with high dimensional feature space. With the training set containing 115,832 moves and the same feature setting, the results of our experiments show that Only-One-Victor outperforms Elo rating, a well-known best supervised pattern learning method.

Szubert and Jaśkowski successfully used temporal difference (TD) learning together with n -tuple networks for playing the game 2048. However, we observed a phenomenon that the programs based on TD learning still hardly reach large tiles. In this paper, we propose multistage TD (MS-TD) learning, a kind of hierarchical reinforcement learning method, to effectively improve the performance for the rates of reaching large tiles, which are good metrics to analyze the strength of 2048 programs. Our experiments showed significant improvements over the one without using MS-TD learning. Namely, using 3-ply expectimax search, the program with MS-TD learning reached 32768-tiles with a rate of 18.31%, while the one with TD learning did not reach any. After further tuned, our 2048 program reached 32768-tiles with a rate of 31.75% in 10,000 games, and one among these games even reached a 65536-tiles, which is the first ever reaching a 65536-tiles to our knowledge. In addition, MS-TD learning method can be easily applied to other 2048-like games, such as Threes. Based on MS-TD learning, our experiments for Threes also demonstrated similar performance improvement, where the program with MS-TD learning reached 6144-tiles with a rate of 7.83%, while the one with TD learning only reached 0.45%.

An approach called generic job-level (JL) search was proposed to solve computer game applications by dispatching jobs to remote workers for parallel processing. This paper applies JL search to alpha-beta search, and proposes a JL alpha-beta search (JL-ABS) algorithm based on a best-first search version of MTD(f). The JL-ABS algorithm is demonstrated by using it in an opening book analysis for Chinese chess. The experimental results demonstrated that JL-ABS reached a speed-up of 10.69 when using 16 workers in the JL system.

Chinese Dark Chess is an old and very popular game in the Chinese culture sphere. This game is a stochastic game with symmetric hidden information. This paper reviews alpha-beta search with chance nodes and proposes heuristics on Chinese Dark Chess programs. We propose an application of nondeterministic Monte Carlo Tree Search with random nodes for tackling partial observation. The proposed methods were implemented in the program Diablo, which won four Chinese Dark Chess tournaments in TAAI 2011/2012, TCGA 2011/2012 computer game tournaments. Diablo also played hundreds of games with different human players and programs based on alpha-beta search. These results show that the nondeterministic MCTS equipped with our heuristics is promising for Chinese Dark Chess.

A promising technique to improve the write performance of solid-state disks (SSDs) is to use a disk write buffer. The goals of a write buffer is not only to reduce the write traffic to the flash chips but also to convert host write patterns into long and sequential write bursts. This study proposes a new buffer design consisting of a replacement policy and a write-back policy. The buffer monitors how the host workload stresses the flash translation layer upon garbage collection. This is used to dynamically adjust its replacement and write-back strategies for a good balance between write sequentiality and write randomness. When the garbage collection overhead is low, the write buffer favors high write sequentiality over low write randomness. When the flash translation layer observes a high overhead of garbage collection, the write buffer favors low write randomness over high write sequentiality. The proposed buffer design outperformed existing approaches by up to 20% under various workloads and flash translation algorithms, as will be shown in experiment results.

Monte Carlo tree search (MCTS) is a search paradigm that has been remarkably successful in computer games like Go. It uses Monte Carlo simulation to evaluate the values of nodes in a search tree. The node values are then used to select the actions during subsequent simulations. The performance of MCTS heavily depends on the quality of its default policy, which guides the simulations beyond the search tree. In this paper, we propose an MCTS improvement, called incentive learning, which learns the default policy online. This new default policy learning scheme is based on ideas from combinatorial game theory, and hence is particularly useful when the underlying game is a sum of games. To illustrate the efficiency of incentive learning, we describe a game named Heap-Go and present experimental results on the game.

This paper introduces an approach, called generic job-level search, to leverage the game-playing programs which are already written and encapsulated as jobs. Such an approach is well suited to a distributed computing environment, since these jobs are allowed to be run by remote processors independently. In this paper, we present and focus on a job-level proof number search (JL-PNS), a kind of generic job-level search for solving computer game search problems, and apply JL-PNS to solving automatically several Connect6 positions, including some difficult openings. This paper also proposes a method of postponed sibling generation to generate nodes smoothly, and some policies, such as virtual win, virtual loss, virtual equivalence, flagging, or hybrids of the above, to expand the nodes. Our experiment compared these policies, and the results showed that the virtual-equivalence policy, together with flagging, performed the best against other policies. In addition, the results also showed that the speedups for solving these positions are 8.58 on average on 16 cores.

A nonogram puzzle is played on a rectangular grid of pixels with clues given in the form of row and column constraints. The aim of solving a nonogram puzzle, an NP-complete problem, is to paint all the pixels of the grid in black and white while satisfying these constraints. This paper proposes an efficient approach to solving nonogram puzzles. We propose a fast dynamic programming (DP) method for line solving, whose time complexity in the worst case is O(kl) only, where the grid size is l×l and k is the average number of integers in one constraint, always smaller than l. In contrast, the time complexity for the best line-solving method in the past is O(kl2). We also propose some fully probing (FP) methods to solve more pixels before running backtracking. Our FP methods can solve more pixels than the method proposed by Batenburg and Kosters (before backtracking), while having a time complexity that is smaller than theirs by a factor of O(l). Most importantly, these FP methods provide useful guidance in choosing the next promising pixel to guess during backtracking. The proposed methods are incorporated into a fast nonogram solver, named LalaFrogKK. The program outperformed all the programs collected in webpbn.com, and also won both nonogram tournaments that were held at the 2011 Conference on Technologies and Applications of Artificial Intelligence (TAAI 2011, Taiwan). We expect that the proposed FP methods can also be applied to solving other puzzles efficiently.

Wu and Huang (Advances in Computer Games, pp. 180-194, 2006) presented a new family of k-in-a-row games, among which Connect6 (a kind of six-in-a-row) attracted much attention. For Connect6 as well as the family of k -in-a-row games, this paper proposes a new threat-based proof search method, named relevance-zone-oriented proof (RZOP) search, developed from the lambda search proposed by Thomsen (Int. Comput. Games Assoc. J., vol. 23, no. 4, pp. 203-217, 2000). The proposed RZOP search is a novel, general, and elegant method of constructing and promoting relevance zones. Using this method together with a proof number search, this paper solved effectively and successfully many new Connect6 game positions, including several Connect6 openings, especially the Mickey Mouse opening, which used to be one of the popular openings before we solved it.

Abstract Wang et al. (Softw. Pract. Exper. 2007; 37(7):727–745) observed a phenomenon of performance inconsistency in the graphics of Java Abstract Window Toolkit (AWT)/Swing among different Java runtime environments (JREs) on Windows XP. This phenomenon makes it difficult to predict the performance of Java game applications. Therefore, they proposed a portable AWT/Swing architecture, called CYC Window Toolkit (CWT), to provide programmers with high and consistent rendering performance for Java game development among different JREs. They implemented a DirectX version to demonstrate the feasibility of the architecture. This paper extends the above research to other environments in two aspects. First, we evaluate the rendering performance of the original Java AWT with different combinations of JREs, image application programming interfaces, system properties and operating systems (OSs), including Windows XP, Windows Vista, Fedora and Mac OS X. The evaluation results indicate that the performance inconsistency of Java AWT also exists among the four OSs, even if the same hardware configuration is used. Second, we design an OpenGL version of CWT, named CWT‐GL, to take advantage of modern 3D graphics cards, and compare the rendering performance of CWT with Java AWT/Swing. The results show that CWT‐GL achieves more consistent and higher rendering performance in JREs 1.4 to 1.6 on the four OSs. The results also hint at two approaches: (a) decouple the rendering pipelines of Java AWT/Swing from the JREs for faster upgrading and supporting old JREs and (b) use other graphics libraries, such as CWT, instead of Java AWT/Swing to develop cross‐platform Java games with higher and more consistent rendering performance. Copyright © 2009 John Wiley & Sons, Ltd.

Abstract Recently, the performance of Java platforms has been greatly improved to satisfy the requirements for game development. However, the rendering performance of Java 1.1, which is still used by about one‐third of current Web browser users, is not sufficient for high‐profile games. Therefore, practically, Java game developers, especially those who use applets, have to take this into consideration in most environments. In order to solve the above problems, this paper proposes a portable window toolkit architecture called the CYC Window Toolkit (CWT) with the ability to: (1) reach high rendering performance particularly in Java 1.1 applications and applets when using DirectX to render widgets in CWT; (2) support AWT/Swing compatible widgets, so hence the CWT can be easily applied to existing Java games; (3) define a general architecture that supports multiple graphics libraries such as AWT, DirectX and OpenGL, multiple virtual machines such as Java VM and .NET CLR, and multiple operating systems (OSs) such as Microsoft Windows, Mac OS and UNIX‐based OSs; (4) provide programmers with one‐to‐one mapping APIs to directly manipulate DirectX objects and other game‐related properties. The CWT has also been applied to an online Java game system to demonstrate the proposed architecture. Copyright © 2006 John Wiley & Sons, Ltd.

A data extraction model, named the browser-oriented data extraction (BODE) model, was proposed by I-Chen Wu et al. (2005) to extract Web contents with script functions. In this model, the system built on top of browsers accesses pages by simulating users' operations on browsers. Based on this model, this paper defines a scripting language, named the BODED (browser-oriented data extraction description) language, which instructs the system how to do data extraction. This paper proposes a technique, called indirect browser replication to implement a BODE system, and also optimize the performance of this technique.

Detecting strong conjunctive predicates is a fundamental problem in debugging and testing distributed programs. A strong conjunctive predicate is a logical statement to represent the desired event of the system. Therefore, if the predicate is not true, an error may occur because the desired event does not happen. Recently, several reported detection algorithms reveal the problem of unbounded state queue growth since the system may generate a huge number of execution states in a very short time. In order to solve this problem, this paper introduces the notion of removable states which can be disregarded in the sense that detection results still remain correct. A fully distributed algorithm is developed in this paper to perform the detection in an online manner. Based on the notion of removable states, the time complexity of the detection algorithm is improved as the number of states to be evaluated is reduced.

In a distributed system, identifying consistent checkpoints is essential for error recovery and debugging. We design an efficient incremental algorithm capable of identifying all the consistent and removable checkpoints each time a new checkpoint is reported. By doing so, the required memory space can be minimized by removing those removables. While minimizing the memory space, the algorithm requires only O(p/sup 2/M) time in total, where p is the number of processes and M is the number of checkpoints.

Distributed programs often follow some bounded global predicates, for example, the total number of certain tokens is always the same or bounded in a range. In order to detect bounded global predicates, we can first derive the minimum and maximum global snapshots and then check if the minimum and maximum are out of the range. Recently, Chase and Garg proposed an efficient method to derive the minimum global snapshot by reducing this problem to a maximum network flow problem. A restriction of this method is that all message values (e.g., the token number in messages) must be zero and all process state values (e.g., the token number in processes) must be non-negative. In this paper, we propose an elegant technique, called normalization. By using this technique, we can remove the above restriction and also derive the minimum and maximum global snapshots at the same time.

Deriving the minimum and maximum global snapshots is very useful for some error detection problems in distributed programs. Several researchers, e.g., Groselj (1993) and Chen and Wu (1996), have shown that the minimum and maximum global snapshot problems are linear-time reducible to the maximum constant-ratio network flow (MCNF) problem, here defined as the well-known maximum network flow problem with m=/spl Theta/(n), where m is the number of edges and n is the number of vertices in the given flow network. The authors show in a reverse way that the MCNF problem is also linear-time reducible to these global snapshot problems. Thus, one can conclude that the global snapshot problems are "as difficult as" the MCNF problem in terms of time complexity.

In distributed programs, we usually keep some global predicates from being satisfied to make it easy to run the programs correctly. A common type of global predicates are: the total number of certain tokens in the whole distributed system is always the same or in specific ranges. In this paper, we call this summative predicates, classified into the following four: (1) at some global state of the system, N/spl ne/K, (2) NK (or N/spl ges/K), and (4) N=K, where N is the total number of tokens and K is a constant. This paper investigates the methods of detecting various summative global predicates. The first class of summative predicates are trivial to detect by simply checking each message. For the second class of summative predicates, B. Groselj (1993) and V.K. Garg (1995) solved the problem by reducing the problem to a maximum network flow problem. In this paper, we propose an elegant technique, called normalization, to allow the second and third classes of summative predicates to be solved by also reducing the problem to a maximum network flow problem. For the fourth class of summative predicates, we prove that it is an NP-complete problem.

The relationship between parallel computation cost and communication cost for performing divide-and-conquer (D&C) computations on a parallel system of p processors is studied. The parallel computation cost is the maximal number of the D&C nodes that any processor in the parallel system may expand, whereas the communication cost is the total number of cross nodes (nodes generated by one processor but expanded by another processor). A scheduling algorithm is proposed, and lower bounds on the communication cost are derived. The proposed scheduling algorithm is optimal with respect to the communication cost, since the parallel computation cost of the algorithm is near optimal.>

When a sequential algorithm is directly mapped into an array of processing elements, quite likely data broadcasts are required and their source places vary during the computation. The authors introduce a normalization method to fix the positions of the broadcast sources so that the derived design can be further transformed by retimings into a systolic array. The method is fully illustrated in designing systolic arrays for enumeration sort, solving simultaneous linear equations, and transitive closure.>

Based on the modified Booth's algorithm, a fast 1-D serial- parallel systolic multiplier is designed for multiplying two's complement numbers. The circuit with countercurrent data flow pattern accepts the multiplicand serially, the multiplier in parallel, and outputs the product serially. It requires a complementer and N/2 cells, each of which contains a ripple-carry adder and some gates, where N is restricted to even. The number of clocks required to multiply an n-bit (n ≤ N) multiplier and an m-bit multiplicand is equal to n + m − 1, and independent of the circuit size N.