Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMorpion Solitaire 5D: a new upper bound of 121 on the maximum score
85
0
0.0
(
0
)
Added by
Yushi Uno
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Morpion Solitaire is a pencil-and-paper game for a single player. A move in this game consists of putting a cross at a lattice point and then drawing a line segment that passes through exactly five consecutive crosses. The objective is to make as many moves as possible, starting from a standard initial configuration of crosses. For one of the variants of this game, called 5D, we prove an upper bound of 121 on the number of moves. This is done by introducing line-based analysis, and improves the known upper bound of 138 obtained by potential-based analysis.
rate research
Read More
Morpion Solitaire is a popular single player game, performed with paper and pencil. Due to its large state space (on the order of the game of Go) traditional search algorithms, such as MCTS, have not been able to find good solutions. A later algorithm, Nested Rollout Policy Adaptation, was able to find a new record of 82 steps, albeit with large computational resources. After achieving this record, to the best of our knowledge, there has been no further progress reported, for about a decade. In this paper we take the recent impressive performance of deep self-learning reinforcement learning approaches from AlphaGo/AlphaZero as inspiration to design a searcher for Morpion Solitaire. A challenge of Morpion Solitaire is that the state space is sparse, there are few win/loss signals. Instead, we use an approach known as ranked reward to create a reinforcement learning self-play framework for Morpion Solitaire. This enables us to find medium-quality solutions with reasonable computational effort. Our record is a 67 steps solution, which is very close to the human best (68) without any other adaptation to the problem than using ranked reward. We list many further avenues for potential improvement.
Let $ G $ be a graph. A subset $S subseteq V(G) $ is called a total dominating set if every vertex of $G$ is adjacent to at least one vertex of $S$. The total domination number, $gamma_{t}$($G$), is the minimum cardinality of a total dominating set of $G$. In this paper using a greedy algorithm we provide an upper bound for $gamma_{t}$($G$), whenever $G$ is a bipartite graph and $delta(G)$ $geq$ $k$. More precisely, we show that if $k$ > 1 is a natural number, then for every bipartite graph $G$ of order $n$ and $delta(G) ge k$, $ $$gamma_{t}$($G$) $leq$ $n(1- frac{k!}{prod_{i=0}^{k-1}(frac{k}{k-1}+i)}).$
A fan $F_n$ is a graph consisting of $n$ triangles, all having precisely one common vertex. Currently, the best known bounds for the Ramsey number $R(F_n)$ are $9n/2-5 leq R(F_n) leq 11n/2+6$, obtained by Chen, Yu and Zhao. We improve the upper bound to $31n/6+O(1)$.
We report on the results of a six-month photometric study of the main-belt binary C-type asteroid 121 Hermione, performed during its 2007 opposition. We took advantage of the rare observational opportunity afforded by one of the annual equinoxes of Hermione occurring close to its opposition in June 2007. The equinox provides an edge-on aspect for an Earth-based observer, which is well suited to a thorough study of Hermiones physical characteristics. The catalog of observations carried out with small telescopes is presented in this work, together with new adaptive optics (AO) imaging obtained between 2005 and 2008 with the Yepun 8-m VLT telescope and the 10-m Keck telescope. The most striking result is confirmation that Hermione is a bifurcated and elongated body, as suggested by Marchis et al., (2005). A new effective diameter of 187 +/- 6 km was calculated from the combination of AO, photometric and thermal observations. The new diameter is some 10% smaller than the hitherto accepted radiometric diameter based on IRAS data. The reason for the discrepancy is that IRAS viewed the system almost pole-on. New thermal observations with the Spitzer Space Telescope agree with the diameter derived from AO and lightcurve observations. On the basis of the new AO astrometric observations of the small 32-km diameter satellite we have refined the orbit solution and derived a new value of the bulk density of Hermione of 1.4 +0.5/-0.2 g cm-3. We infer a macroscopic porosity of ~33 +5/-20%.
We prove that, for an undirected graph with $n$ vertices and $m$ edges, each labeled with a linear function of a parameter $lambda$, the number of different minimum spanning trees obtained as the parameter varies can be $Omega(mlog n)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
