96 Result(s)
within
Chapter
**e **an
Popular Science
Algorithm Analysis and Problem Complexity
Artificial Intelligence
-
Chapter and Conference Paper
Automatic Strategy Verification for Hex
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 **g Y...
-
Chapter and Conference Paper
Automated Chess Tutor
While recently the strength of chess-playing programs has grown immensely, their capability of explaining in human understandable terms why some moves are good or bad has enjoyed little attention. Progress tow...
-
Chapter and Conference Paper
A Skat Player Based on Monte-Carlo Simulation
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 Br...
-
Chapter and Conference Paper
An Open Boundary Safety-of-Territory Solver for the Game of Go
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 reg...
-
Chapter and Conference Paper
Improving Depth-First PN-Search: 1 + ε Trick
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. Howe...
-
Chapter and Conference Paper
Virtual Global Search: Application to 9×9 Go
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...
-
Chapter and Conference Paper
Counting the Number of Three-Player Partizan Cold Games
We give upper and lower bounds on S 3[n] equal to the number of three-player partizan cold games born by day n. In particular, we give an upper bound of
-
Chapter and Conference Paper
On the Symbolic Computation of the Hardest Configurations of the RUSH HOUR Game
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 othe...
-
Chapter and Conference Paper
Combinatorics of Go
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 c...
-
Chapter and Conference Paper
Computing Proper Equilibria of Zero-Sum Games
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 dimension...
-
Chapter and Conference Paper
Monte-Carlo Methods in Pool Strategy Game Trees
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 th...
-
Chapter and Conference Paper
Gender and Cultural Differences (If Any!): South African School Children and Computer Games
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 resear...
-
Chapter and Conference Paper
Computer Analysis of Chess Champions
Who is the best chess player of all time? Chess players are often interested in this question that has never been answered authoritatively, because it requires a comparison between chess players of different e...
-
Chapter and Conference Paper
Feature Construction for Reinforcement Learning in Hearts
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 ach...
-
Chapter and Conference Paper
A New Heuristic Search Algorithm for Capturing Problems in Go
We propose a highly selective heuristic search algorithm for capturing problems in Go. This iterative deepening search works on the crucial chain in which the prey block is located. The algorithm starts using ...
-
Chapter and Conference Paper
A Retrograde Approximation Algorithm for One-Player Can’t Stop
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 va...
-
Chapter and Conference Paper
Monte-Carlo Proof-Number Search for Computer Go
In the last decade, proof-number search and Monte-Carlo methods have successfully been applied to the combinatorial-games domain. Proof-number search is a reliable algorithm. It requires a well defined goal to...
-
Chapter and Conference Paper
Search Versus Knowledge Revisited Again
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 ...
-
Chapter and Conference Paper
Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search
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 p...
-
Chapter and Conference Paper
LUMINES Strategies
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 pla...
