abstract

This work expounds the results about the examination of subtraction games with view of long periods — ”long“ in proportion to the largest valid move. Sharper lower and upper bounds of the period lengths, as known up to now, are given. The notion of the symmetric move sets is introduced and its significance is exposed. A structur-verification algorithm is established, implemented on a computer and used for the first time proof of the win/loss-sequence of some families of subtraction games. Many well-founded conjectures about period lengths are formulated. Especially, there is strong evidence that there are families of subtraction games whose periodlengths are growing exponentielly in n ∈ ℕ, but their move values grow only linearly in n.

Zusammenfassung

Diese Arbeit legt meine Ergebnisse der Untersuchung von Subtraktions-Spielen mit Blickrichtung auf lange Perioden dar. Schärfere untere und obere Schranken der Periodenlängen, als bisher bekannt sind, werden bewiesen. Der Begriff der symmetrischen Zugmengen wird eingeführt und deren Bedeutung herausgestellt. Ein Struktur-Verifikations-Algorithmus wird vorgestellt, auf einem Rechner implementiert und zum erstmaligen Beweis von Gewinn/Verlust-Folgen einiger Familien von Subtraktions-Spielen benutzt. Viele Vermutungen über Periodenlängen werden formuliert und gut fundiert. Insbesondere gibt es starke Indizien, daß Familien von Subtraktions-Spielen existieren, deren Periodenlängen exponentiell in einem freien Parameter n ∈ ℕ wachsen, aber deren Zugwerte nur linear mit diesem n anwachsen.

Summarium

The following two-person game is considered: Given k natural numbers s_{1} < s_{2} < ... < s_{k}, which define the valid moves of both players, and a number n ∈ ℕ_{0}, which is called the heapsize. Alternatingly, both players decrease the present heapsize by an actual chosen move from the list of valid moves L = (s_{1}, s_{2}, …, s_{k}). Each such game terminates. It reckons as lost for the player who would be forced to make the heapsize negatively. Such a game is called a subtraction game.

If it is played optimally, — this means, the player who can win enforces this,

— then the heapsize at the beginning determines whether either the starting or the following player will win the game. For a given set L, we call the heapsize n a P- or a N -position, according to the fact, whether the moving player can produce a win (positiv) or not (negativ). We look at the sequence of these P- and N -positionen for a given L, whereby n passes through the natural numbers. It is known, that this sequence (v_{L}(n))_{n=0}^{∞} gets periodicly after atmost 2^{max L} values, because the calculation formula of v_{L}(n) can be considered as a shiftregister of length max L.

This work expounds new results about the examination of subtraction games with view of long periods — ”long“ in proportion to the largest valid move max L. Further aspects of subtraction games are explored, too, and generalizations in view of shiftregisters are exhibited. As the main results of this work, I like to list in the order of my estimated importance of this branch of mathematics:

1. the significant improved assessment of the distribution of period lengths of finite subtraction games, especially the 3-move-games.

The wealth of the new, in the work collected, single-results, enlarges the knowledge about subtraction games in substantial extent.

2. The introduction of the notion of symmetric move sets, its identification und characterisation.

The symmetric move sets simplify the study of large period lengths, because the number of independent moves of the move set is decreased to the half. Nevertheless many, for the structur of the P-N -sequences, relevant properties of subtraction games — excluded the preperiods — still exists in this subset of subtraction games.

3. The creation of a consistence-verification-program for a subset of the subtraction games.

With this tool, for the first time the structur of the P-N -sequence of, in their period lengths cubic, growing families of subtraction games could be proved. Moreover, it offers the possibility, to verify given structur descriptions of polynomiel in their period lengthes, respectively preperiod lengthes, increasing subtraction games. The program can easily be generalized to further kinds of shiftregister rules, which can be considered as certain kinds of formative laws of position valuations v(n).

4. The hardening of the conjecture of the existence of in their period length exponentielly growing families of subtraction games.

The proof of the existence of such subtraction games is still waiting; especially, no such family could be stated explicitly. Yet, the, with the help of extensive computer computations, gathered facts let seem their existence very probable.

5. A combinatoric proof of a sharper upper bound of the period lengths of a large set of subtractions games.

This proof mediates a relation between the counting combinatoric and the graph-theory. With this, in the future new results about the number of independent sets of regular graphs can improve the upper bound farther.

translated 1998-03-01