Search

When studying computer games several factors come into play. The issue of gender inequality has been a topic of many research projects in the past. The issue of culture is still in its infancy. Previous research regarding game-playing and gender issues seem to indicate that boys play more computer games than girls, that boys prefer more violent, action-oriented games in comparison to girls and that girls would prefer to play games with a feminine appeal. Intuitively it can be assumed that different cultures play different existing games at different frequencies. In this study grade ten school children (ages sixteen to seventeen) from one city in South Africa were questioned in order to establish if the same results hold true. The results indicate that there are no major differences in game playing between genders and cultures for this group. The conclusion is reached that especially with regard to gender the situation changed quite a bit over the past few years in comparison to research results found in the literature. [ABSTRACT FROM AUTHOR]

In this paper we explore the tactical aspects needed for the creation of an intelligent computer-pool player. The research results in three modifications to our previous model. An optimization procedure computes the shot parameters and repositions the cue ball on a given target. Moreover, we take a look at possible heuristics to generate a sound selection of targets repositioning. We thus obtain a greedy but rather good billiard player. [ABSTRACT FROM AUTHOR]

An Eight Ball pool strategy algorithm with look-ahead is presented. The strategy uses a probabilistically evaluated game search tree to discover the best shot to attempt at each turn. Performance results of the strategy algorithm from a simulated tournament are presented. Players looking further ahead in the search tree performed better against their shallower-searching competitors, at the expense of larger execution time. The advantage of a deeper search tree was magnified for players with greater shooting precision. [ABSTRACT FROM AUTHOR]

We consider playing online games on peer-to-peer networks, without assuming servers that control the execution of a game. In such an environment, players may cheat the opponent by, for example, illegally replacing the cards in their hands. The aim of this paper is to examine a possibility of excluding such cheatings. We show that by employing cryptographic techniques, we can exclude some types of cheating at some level. Finally, based on our discussion, we implement the cheat-proof network "Gunjin-Shogi", which is a variant of Japanese Chess. [ABSTRACT FROM AUTHOR]

Rush Hour is a sliding blocks game where blocks represent cars stuck in a traffic jam on a 6 ×6 board. The goal of the game is to allow one of the cars (the target car) to exit this traffic jam by moving the other cars out of its way. In this paper, we study the problem of finding difficult initial configurations for this game. An initial configuration is difficult if the number of car moves necessary to exit the target car is high. To solve the problem, we model the game in propositional logic and we apply symbolic model-checking techniques to study the huge graph of configurations that underlies the game. On the positive side, we show that this huge graph (containing 3.6 ·1010 vertices) can be completely analyzed using symbolic model-checking techniques with reasonable computing resources. We have classified every possible initial configuration of the game according to the length of its shortest solution. On the negative side, we prove a general theorem that shows some limits of symbolic model-checking methods for board games. The result explains why some natural modeling of board games leads to the explosion of the size of symbolic data-structures. [ABSTRACT FROM AUTHOR]

Combinatorial games of the form {{AB}{CD}} can be classified as either left excitable, right excitable, or equitable [2]. Several approximate strategies for playing sums of games of this form have been proposed in the literature [2,3,4]. In this work we propose a new approach for evaluating the different strategies based on the types of the subgames participating in a sum game. While previous comparisons [3,4] were only able to rank the strategies according to their average performance in a large number of randomly generated games, our evaluation is able to pinpoint the strengths and weaknesses of each strategy. We show that none of the strategies can be considered the best in an absolute sense. Therefore we recommend the development of type-based approximate strategies with enhanced performance. [ABSTRACT FROM AUTHOR]

We show that a proper equilibrium of a matrix game can be found in polynomial time by solving a linear (in the number of pure strategies of the two players) number of linear programs of roughly the same dimensions as the standard linear programs describing the Nash equilibria of the game. [ABSTRACT FROM AUTHOR]

We analyze a new popular video-game called Lumines, which was developed by Sony for the PSP platform. It involves a sequence of bichromatic 2×2 blocks that fall in a grid and must be shifted or rotated by the player before they land. Patterns of monochromatic 2×2 blocks in the terrain are regularly deleted. The primary goal is to contain the terrain within a fixed height and, if possible, clear the grid. We deal with questions such as: (1) Can the game be played indefinitely? and (2) Can all terrains be eliminated? We examine how answers to these questions depend on the size of the grid and the rate at which blocks are deleted. [ABSTRACT FROM AUTHOR]

We give upper and lower bounds on S3[n] equal to the number of three-player partizan cold games born by day n. In particular, we give an upper bound of $O(S_2[n]^3)$ and a lower bound of Ω(S2[n]) where S2[n] is the number of surreal numbers born by day n. [ABSTRACT FROM AUTHOR]

The questions focusing on diminishing returns for additional search effort have been a burning issue in computer chess. Despite a lot of research in this field, there are still some open questions, e.g., what happens at search depths beyond 12 plies, and what is the effect of the program's knowledge on diminishing returns? The paper presents an experiment that attempts to answer these questions. The results (a) confirm that diminishing returns in chess exist, and more importantly (b) show that the amount of knowledge a program has influences when diminishing returns will start to manifest themselves. [ABSTRACT FROM AUTHOR]

Various efficient game problem solvers are based on PN-Search. Especially depth-first versions of PN-Search like DF-PN or PDS - contrary to other known techniques - are able to solve really hard problems. However, the performance of DF-PN and PDS decreases drastically when the search space significantly exceeds the available memory. A straightforward enhancement trick to overcome this problem is presented. Experiments on Atari Go and Lines of Action show great practical value of the proposed enhancement. [ABSTRACT FROM AUTHOR]

A one-player, finite, probabilistic game with perfect information can be presented as a bipartite graph. For one-player Can't Stop, the graph is cyclic and the challenge is to determine the game-theoretical values of the positions in the cycles. In this contribution we prove the existence and uniqueness of the solution to one-player Can't Stop, and give an efficient approximation algorithm to solve it by incorporating Newton's method with retrograde analysis. We give results of applying this method to small versions of one-player Can't Stop. [ABSTRACT FROM AUTHOR]

We apply Monte-Carlo simulation and alpha-beta search to the card game of Skat, which is similar to Bridge, but sufficiently different to require some new algorithmic ideas besides the techniques developed for Bridge. Our Skat-playing program, called DDS (Double Dummy Solver), integrates well-known techniques such as move ordering with two new search enhancements. Quasi-symmetry reduction generalizes symmetry reductions, disseminated by Ginsberg's Partition Search algorithm, to search states which are "almost equivalent". Adversarial heuristics generalize ideas from single-agent search algorithms like $\textrm{A}^*$ to two-player games, leading to guaranteed lower and upper bounds for the score of a game position. Combining these techniques with state-of-the-art tree-search algorithms, our program determines the game-theoretical value of a typical Skat hand (with perfect information) in 10 milliseconds. [ABSTRACT FROM AUTHOR]

Temporal difference (TD) learning has been used to learn strong evaluation functions in a variety of two-player games. TD-gammon illustrated how the combination of game tree search and learning methods can achieve grand-master level play in backgammon. In this work, we develop a player for the game of hearts, a 4-player game, based on stochastic linear regression and TD learning. Using a small set of basic game features we exhaustively combined features into a more expressive representation of the game state. We report initial results on learning with various combinations of features and training under self-play and against search-based players. Our simple learner was able to beat one of the best search-based hearts programs. [ABSTRACT FROM AUTHOR]

We present a concise and/or-tree notation for describing Hex strategies together with an easily implemented algorithm for verifying strategy correctness. To illustrate our algorithm, we use it to verify Jing Yang's 7×7 centre-opening strategy. [ABSTRACT FROM AUTHOR]

Expert knowledge is crucial for improving the strength of computer Chinese-Chess programs. Although a great deal of expert knowledge is available in text format that using natural languages, manually transforming it into computer readable forms is time consuming and difficult. Written expert annotations of Chinese-Chess games show different styles. By analyzing and collecting commonly used phrases and patterns from experts' annotations, we introduce a novel pattern matching strategy. It automatically epitomises knowledge from a large number of annotated game records. The results of the experiments on the analysis of the middle phase of games indicate that our strategy achieves a low error rate. We hope to exploit this approach to collect automatically a great diversity of Chinese-Chess knowledge that is currently in text format. [ABSTRACT FROM AUTHOR]

We present several results concerning the number of positions and games of Go. We derive recurrences for L(m,n), the number of legal positions on an m ×n board, and develop a dynamic programming algorithm which computes L(m,n) in time O(m3n2λm) and space O(mλm), for some constant λ< 5.4. An implementation of this algorithm enables us to list L(n,n) for n ≤ 17. For larger boards, we prove the existence of a base of liberties$\lim \sqrt[mn]{L(m,n)}$ of ~2.9757341920433572493. Based on a conjecture about vanishing error terms, we derive an asymptotic formula for L(m,n), which is shown to be highly accurate. We also study the Game Tree complexity of Go, proving an upper bound on the number of possible games of (mn)L(m,n) and a lower bound of $2^{2^{n^2/2\,-O(n)}}$ on n×nboards and $2^{2^{n-1}}$ on 1 ×n boards, in addition to exact counts for mn ≤ 4 and estimates up to mn = 9. Most proofs and some additional results had to be left out to observe the page limit. They may be found in the full version available at [8]. [ABSTRACT FROM AUTHOR]

A Monte-Carlo evaluation consists in estimating a position by averaging the outcome of several random continuations. The method can serve as an evaluation function at the leaves of a min-max tree. This paper presents a new framework to combine tree search with Monte-Carlo evaluation, that does not separate between a min-max phase and a Monte-Carlo phase. Instead of backing-up the min-max value close to the root, and the average value at some depth, a more general backup operator is defined that progressively changes from averaging to min-max as the number of simulations grows. This approach provides a fine-grained control of the tree growth, at the level of individual simulations, and allows efficient selectivity. The resulting algorithm was implemented in a 9×9 Go-playing program, Crazy Stone, that won the 10th KGS computer-Go tournament. [ABSTRACT FROM AUTHOR]

In games, Monte-Carlo simulations can be used as an evaluation function for Alpha-Beta search. Assuming w is the width of the search tree, d its depth, and g the number of simulations at each leaf, then the total number of simulations is at least $g \times (2 \times w^{\frac{d}{2}}$). In games where moves permute, we propose to replace this algorithm by a new algorithm, Virtual Global Search, that only needs g ×2d simulations for a similar number of games per leaf. The algorithm is also applicable to games where moves often but not always permute, such as Go. We specify the application for 9×9 Go. [ABSTRACT FROM AUTHOR]

This paper presents Safety Solver 2.0, a safety-of-territory solver for the game of Go that can solve problems in areas with open boundaries. Previous work on assessing safety of territory has concentrated on regions that are completely surrounded by stones of one player. Safety Solver 2.0 can identify open boundary problems under real game conditions, and generate moves for invading or defending such areas. Several search enhancements improve the solver's performance. The experimental results demonstrate that the solver can find good moves in small to medium-size open boundary areas. [ABSTRACT FROM AUTHOR]