اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMorpion Solitaire 5D: a new upper bound of 121 on the maximum score
82
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 algorith
m, 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 o
f $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 H
ermione 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)$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
