Wer gewinnt dieses Spiel?

[D. I. (Gast)]

Ich grüble derzeit über eine kleine Programmieraufgabe, wo ich mir 
ziemlich sicher bin dass sie sich mithilfe dynamischer Programmierung 
lösen lässt und das auch nicht zu schwierig, aber ich scheitere daran 
die richtige Rekursion dafür aufzustellen. Vielleicht mag ja jemand mit 
einsteigen.

Problem:

Es handelt sich um ein 2-Spieler Spiel. Gegeben ist eine natürliche Zahl 
n (n <= 2.000.000.000). Das Spiel beginnt mit k = 1 und die Spieler 
(beginnend mit Spieler 1) können die Zahl k entweder mit 2 oder 9 
multiplizieren (nach jeder Multiplikation ist der jeweils andere Spieler 
dran). Wer zuerst die Zahl n erreicht oder überschreitet gewinnt das 
Spiel. Nun soll man zu einem gegebenen n den Gewinner ermitteln.

Meine Ideen bisher:

- Wenn eine Strategie für P1 existiert die nicht von P2s Entscheidungen 
abhängt gewinnt P1, ansonsten P2.

- Wer den anderen dazu bringen kann auf n/9 zu kommen, gewinnt das Spiel 
da er dann nur noch mit 9 multiplizieren muss.

- Den aktuellen Zustand kodiere ich mit S(i,j) = 2^i * 9^j ist also wohl 
ein 2-dimensionales Problem

- Wenn S(i,j+1) >= n, gewinnt der aktuelle Spieler, ansonsten muss ich 
die bessere Wahl zwischen S(i+1,j) oder S(i,j+1) treffen und das ist der 
Punkt an dem ich scheitere

Hat jemand Input für mich?

[A. $. (mikronom)]

Ich bin gerade zu faul zum nachdenken, deshalb ein ähnliches Beispiel.

Zwei Spieler und es liegen 20 Streichhölzer auf dem Tisch. Sie nehmen 
abwechselnd 1, 2 oder 3 Streichhölzer weg. Wer das letzte nehmen muss 
hat verloren.

Das ist das gleiche mit Addition und runterzählen und schon allein 
dadurch viel einfacher. Pro Runde können 2 bis 6 Hölzer weggenommen 
werden. Der clevere Spieler sorgt dafür, dass es immer 4 sind. Vielleich 
tkommst du ja damit weiter.

[D. I. (Gast)]

Jo das ist die einfache Version die mir auch schonmal in den Sinn 
gekommen ist. Leider hat es für den zündenden Funken nich nicht 
gereicht.

Im Wesentlichen kann man sich das ja wie ein Schachbrett vorstellen. 
Landet man auf einem "schwarzen" Feld dass >= n ist gewinnt der eine 
Spieler, ist es "weiß" der andere.
Der zweite Spieler hat immer nur die Möglichkeit in einer die Runde die 
vom ersten Spieler vorgegebene richtung beizubehalten oder sie Richtung 
Diagonale wieder auszugleichen.
Mh...

[Andreas W. (andy_w)]

Hallo,
das kann man tatsächlich auf das Streichholzspiel zurückführen, einfach 
logarithmieren. Also als Startwert log(Startzahl) und jeder darf 
entweder log(2) oder log(9) abziehen. Wer Null erreicht oder einen 
negativen Wert, gewinnt.

Eine Gewinnstellung ist dann die Zahl log(2)+log(9), egal, was der 
Gegner macht, er erreicht nicht das Ende, man selber danach aber schon. 
Um diese Stellung sicher zu erreichen, ist 2*(log(2)+log(9)) auch eine 
Gewinnstellung usw.

Also sollte man im Originalspiel n/18 erreichen, vorher n/(18*18), 
n/(18*18*18) usw. Sind die genauen Zahlen keine ganzen Zahlen, ist die 
nächst höhere anzustreben.

Viel interessanter ist dagegen das NIM-Spiel, mehrere Haufen 
Streichhölzer (oder Münzen oder sonst was), von einem dieser Haufen kann 
man soviel wegnehmen, wie man will, mindestens eins und maximal alle. 
Wer das letzte vom letzten Haufen nehmen muß, verliert. Für ein 
Computerprogramm ist die Sache extrem einfach, aber man muß erst einmal 
auf die Strategie kommen...

Gruß
Andy_W

[D. I. (Gast)]

Narf, manchmal sieht man den Baum vor lauter Wäldern nicht. Es ist 
eigentlich ganz einfach, die Rekursion aufzubauen: Entweder ich kann mit 
dem nächsten Zug gewinnen oder der nächste Zug sorgt dafür dass der 
andere nicht gewinnt. Wenn beides nicht zutrifft gewinnt der andere.

Ich hab das mal in ein kleines Ruby-Programm gegossen. Ich denke das 
sollte passen, was meint ihr?

@table = nil

def rec(i, j, n)
  return @table[i][j] if !@table[i][j].nil?
  
  if (2**i) * (9**j) * 9 >= n #can we win now?
    @table[i][j] = true
  else #can we make a move thus the other player doesn't win?
    @table[i][j] = !rec(i+1, j, n) || !rec(i, j+1, n) 
  end
  return @table[i][j]
end

def first_player_wins?(n)
  @table = Array.new(100) { Array.new(100) { nil } }
  return rec(0, 0, n)
end

n = ARGV[0].to_i
puts (first_player_wins?(n) ? "Spieler 1 gewinnt" : "Spieler 2 gewinnt")

[Yalu X. (yalu) (Moderator)]

Wenn folgender Ausdruck eine gerade Zahl ergibt, gewinnt der erste
Spieler, sonst der zweite:

$$\left\lceil\log_2\frac{36n}{18^{\lceil\log_{18}(4n)\rceil}}\right\rceil \quad(n\ge 10)$$

Für 2≤n≤9 gewinnt der erste Spieler, und für n=1 ist es eine Frage der
Definition, da das Spiel ja endet, bevor überhaupt jemand einen Zug
gemacht hat. Ich würde sagen, der zweite Spieler gewinnt in diesem Fall.

Man sollte allerdings die Logarithmen nicht mit FP-Funktionen berechnen,
da durch die Aufrundfunktion schon kleine Rundungsfehler zu falschen
Ergebnissen führen. Besser ist es, ganzzahlige Potenzen in einer Schlei-
fe hochzuzählen, bis das Argument erreicht oder überschritten ist, z.B.
so:

int gewinner(unsigned int n) {
  unsigned long long n4 = 4ULL*n, n36=36ULL*n, p;
  int i, ret;

  if(n == 1)
    ret = 2;
  else if(n < 10)
    ret = 1;
  else {
    p = 1;
    while(p < n4)
      p *= 18;
    i = 0;
    while(p < n36) {
      p *= 2;
      i++;
    }
    ret = i&1 ? 2 : 1;
  }
  return ret;
}

Die Spielstrategie:

Wenn es für die aktuelle Zahl k ein i gibt, so dass

$$2n\le k\cdot 18^i<4n$$

dann multipliziere die Zahl mit 9, sonst mit 2. Vielleicht gibt es etwas
einfacheres, mir ist aber nichts eingefallen

D. I. schrieb:
> Ich hab das mal in ein kleines Ruby-Programm gegossen. Ich denke das
> sollte passen, was meint ihr?

Das scheint mit meinen Ergebnissen zusammenzupassen:

        von         bis   Gewinner
——————————————————————————————————
          1           1      2
          2           9      1
         10          18      2
         19          36      1
         37          72      2
         73         162      1
        163         324      2
        325         648      1
        649        1296      2
       1297        2916      1
       2917        5832      2
       5833       11664      1
      11665       23328      2
      23329       52488      1
      52489      104976      2
     104977      209952      1
     209953      419904      2
     419905      944784      1
     944785     1889568      2
    1889569     3779136      1
    3779137     7558272      2
    7558273    17006112      1
   17006113    34012224      2
   34012225    68024448      1
   68024449   136048896      2
  136048897   306110016      1
  306110017   612220032      2
  612220033  1224440064      1
 1224440065  2448880128      2
 2448880129  4294967295      1
——————————————————————————————————

Das Ganze geht auch mit dynamischer Programmierung, wie du es ursprüng-
lich vorgehabt hast. Du macht eine Tabelle mit allen möglichen Zahlen-
werten

   |  9⁰   9¹   9²   9³ ...
———————————————————————————
2⁰ |   1    9   81  729 ...
   |
2¹ |   2   18  162 1458 ...
   |
2² |   4   36  324 2916 ...
   |
2³ |   8   72  648 5832 ...
 : |   :    :    :    :

und markierst alle Zahlen, die größer oder gleich n sind, als "Gewinn-
zahlen". Danach werden die restlichen Zahlen von rechts nach links und
von unten nach oben ebenfalls als Gewinn- oder Verlustzahlen markiert:
Eine Zahl ist genau dann eine Gewinnzahl, wenn der rechte und der untere
Nachbar beide Verlustzahlen sind.

Als letztes wird die 1 markiert. Ist sie eine Gewinnzahl, gewinnt der
zweite Spieler, sonst der erste.

Letztendlich ist das genau das gleiche wie dein rekursiver Algorithmus,
nur von hinten aufgezäumt und eben nicht rekursiv.