Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNimbers are inevitable
79
0
0.0
(
0
)
Added by
Julien Lemoine
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This article concerns the resolution of impartial combinatorial games, and in particular games that can be split in sums of independent positions. We prove that in order to compute the outcome of a sum of independent positions, it is always more efficient to compute separately the nimbers of each independent position than to develop directly the game tree of the sum. The concept of nimber is therefore inevitable to solve impartial games, even when we only try to determinate the winning or losing outcome of a starting position. We also describe algorithms to use nimbers efficiently and finally, we give a review of the results obtained on two impartial games: Sprouts and Cram.
rate research
Read More
Sprouts is a two-player topological game, invented in 1967 in the University of Cambridge by John Conway and Michael Paterson. The game starts with p spots, and ends in at most 3p-1 moves. The first player who cannot play loses. The complexity of the p-spot game is very high, so that the best hand-checked proof only shows who the winner is for the 7-spot game, and the best previous computer analysis reached p=11. We have written a computer program, using mainly two new ideas. The nimber (also known as Sprague-Grundy number) allows us to compute separately independent subgames; and when the exploration of a part of the game tree seems to be too difficult, we can manually force the program to search elsewhere. Thanks to these improvements, we reached up to p=32. The outcome of the 33-spot game is still unknown, but the biggest computed value is the 47-spot game ! All the computed values support the Sprouts conjecture: the first player has a winning strategy if and only if p is 3, 4 or 5 modulo 6. We have also used a check algorithm to reduce the number of positions needed to prove which player is the winner. It is now possible to hand-check all the games until p=11 in a reasonable amount of time.
We analyze the computational complexity of the popular computer games Threes!, 1024!, 2048 and many of their variants. For most kno
Evolvability is an important feature that impacts the ability of evolutionary processes to find interesting novel solutions and to deal with changing conditions of the problem to solve. The estimation of evolvability is not straightforward and is generally too expensive to be directly used as selective pressure in the evolutionary process. Indirectly promoting evolvability as a side effect of other easier and faster to compute selection pressures would thus be advantageous. In an unbounded behavior space, it has already been shown that evolvable individuals naturally appear and tend to be selected as they are more likely to invade empty behavior niches. Evolvability is thus a natural byproduct of the search in this context. However, practical agents and environments often impose limits on the reach-able behavior space. How do these boundaries impact evolvability? In this context, can evolvability still be promoted without explicitly rewarding it? We show that Novelty Search implicitly creates a pressure for high evolvability even in bounded behavior spaces, and explore the reasons for such a behavior. More precisely we show that, throughout the search, the dynamic evaluation of novelty rewards individuals which are very mobile in the behavior space, which in turn promotes evolvability.
In a biased weak $(a,b)$ polyform achievement game, the maker and the breaker alternately mark $a,b$ previously unmarked cells on an infinite board, respectively. The makers goal is to mark a set of cells congruent to a polyform. The breaker tries to prevent the maker from achieving this goal. A winning maker strategy for the $(a,b)$ game can be built from winning strategies for games involving fewer marks for the maker and the breaker. A new type of breaker strategy called the priority strategy is introduced. The winners are determined for all $(a,b)$ pairs for polyiamonds and polyominoes up to size four.
A social choice correspondence satisfies balancedness if, for every pair of alternatives, x and y, and every pair of individuals, i and j, whenever a profile has x adjacent to but just above y for individual i while individual j has y adjacent to but just above x, then only switching x and y in the orderings for both of those two individuals leaves the choice set unchanged. We show how the balancedness condition interacts with other social choice properties, especially tops-only. We also use balancedness to characterize the Borda rule (for a fixed number of voters) within the class of scoring rules.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
