Berechnen Sie die Gewinnstrategie eines Subtraktionsspiels

Question

Problem:
Bei 100 Steinen wechseln zwei Spieler Steine ​​aus. Man kann jede Zahl von 1 bis 15 nehmen; Allerdings kann man keine Nummer nehmen, die bereits vergeben wurde. Wenn am Ende des Spiels k Steine ​​übrig sind, aber 1 bis k wurden alle vorher genommen, kann man k Steine ​​nehmen. Wer den letzten Stein nimmt, gewinnt. Wie kann der erste Spieler immer gewinnen?

Meine Idee
Verwenden Rekursion (oder dynamische Programmierung). Basisfall 1, wo Spieler 1 eine Gewinnstrategie hat. Reduzieren: Für n Steine ​​links, wenn Palyer 1 m1 Steine ​​nimmt, muss er sicherstellen, dass für alle Optionen, die Spieler 2 hat (m2), er eine Gewinnstrategie hat. Somit reduziert sich das Problem auf (n - m1 - m2).

Follow Up Frage:
Nutzt man DP, die mögliche Anzahl von Tabellen zu füllen ist groß (2^15), da die zur Verfügung stehenden linksen Optionen auf der Geschichte ab, die 2^15 Möglichkeiten.
Wie können Sie optimieren?

Answer 1

Angenommen, die verbleibende Anzahl von Zahlen kann als R dargestellt werden, die höchste verbleibende Zahl nach der Auswahl kann durch RH dargestellt werden und die niedrigste verbleibende Zahl kann RL sein. Der Trick besteht darin, die vorletzte Bewegung zu verwenden um die Zahl auf < 100-RH zu erhöhen, aber> 100-RH-RL. Das zwingt deinen Gegner dazu, eine Zahl zu nehmen, die dich in die Gewinnreichweite bringt.

Der letzte Bereich zu gewinnen, mit der Gesamtzahl, die Sie mit Ihrem zweiten bis letzten Schritt zu erstellen, ist:

N < 100-RH 
N > 100-RH-RL 

Durch Beobachtung stellte ich fest, dass RH als 15 so hoch sein kann und so niedrig als 8. RL kann so niedrig wie 1 und so hoch wie 13 sein. Aus diesem Bereich habe ich die Gleichungen ausgewertet.

N < 100-[8:15]   => N < [92:85] 
N > 100-[8:15]-[1:13] => N > [92:85] - [1:13] => N > [91:72] 

Andere Überlegungen können diese Lücke verkleinern. RL zum Beispiel ist nur 13 in einem Randumstand, der immer zu einem Verlust für Spieler A führt, also liegt der wahre Bereich zwischen 72 und 91. Es gibt ein ähnliches Problem mit RH und dem unteren Ende davon, also die Endbereiche und Berechnungen sind:

N < 100-[9:15]   => N < [91:85] 
N > 100-[9:15]-[1:12] => N > [91:85] - [1:12] => N > [90:73] 
[90:73] < N < [91:85] 

Vor diesem jedoch explodieren die Möglichkeiten. Denken Sie daran, dies ist nach der Wahl Ihrer vorletzten Nummer, nicht vorher. An diesem Punkt sind sie gezwungen, eine Zahl zu wählen, mit der Sie gewinnen können.

Beachten Sie, dass 90 keine gültige Wahl ist, um zu gewinnen, obwohl es möglicherweise existiert. Somit kann die maximale es ist 89. Der wahre Bereich von N ist:

[88:73] < N < [90:85] 

Es ist jedoch möglich, den Bereich der Anzahl zu berechnen, die Sie mit Ihrem Gegner in einem no- setzen Gewinnsituation. In der Situation, finden Sie sich in die niedrigste Zahl oder die höchste Zahl könnte derjenige sein, der Sie gewählt haben, also wenn RHC ist die höchste Zahl, die Sie wählen können und RLC ist die niedrigste Zahl, die Sie auswählen können, dann

RHc = [9:15] 
RLc = [1:12] 

Mit dieser Information kann ich beginnen, einen relativen Algorithmus zu konstruieren, der am Ende des Spiels beginnt.

N*p* - RHp - RLp < Np < N*p* - RHp, where p = iteration and *p* = iteration + 1 
RHp = [8+p:15] 
RLp = [1:13-p] 
p = -1 is your winning move 
p = 0 is your opponent's helpless move 
p = 1 is your set-up move 
Np is the sum of that round. 

So den Algorithmus für die Set-up-Bewegung zu lösen, p = 1, erhalten Sie:

N*p* - [9:15] - [1:12] < Np < N*p* - [9:15] 
100 <= N*p* <= 114 

Ich bin immer noch die Mathematik für diese Arbeit aus, so Anpassungen erwarten. Wenn Sie einen Fehler sehen, lassen Sie es mich wissen und ich werde mich entsprechend anpassen.

Answer 2

Hier ist ein einfacher, Brute-Force-Python-Code:

# stoneCount: number of stones to start the game with 
# possibleMoves: which numbers of stones may be removed? (*sorted* list of integers) 
# return value: signals if winning can be forced by first player; 
#    if True, the winning move is attached 
def isWinningPosition(stoneCount, possibleMoves): 
    if stoneCount == 0: 
     return False 
    if len(possibleMoves) == 0: 
     raise ValueError("no moves left") 
    if stoneCount in possibleMoves or stoneCount < possibleMoves[0]: 
     return True,stoneCount 
    for move in possibleMoves: 
     if move > stoneCount: 
      break 
     remainingMoves = [m for m in possibleMoves if m != move] 
     winning = isWinningPosition(stoneCount - move, remainingMoves) 
     if winning == False: 
      return True,move 
    return False 

Für die gegebene Problemgröße dieser Funktion in weniger als 20 Sekunden auf einem Intel i7 zurück:

>>> isWinningPosition(100, range(1,16)) 
False 

(So ist die erste Das Spiel kann in dieser Situation keinen Sieg erzwingen. Was auch immer er macht, es wird eine Gewinnposition für den zweiten Spieler ergeben.)

Natürlich gibt es viel Platz für die Laufzeitoptimierung aktion. In der obigen Implementierung werden viele Situationen immer wieder erreicht und neu berechnet (zB wenn das erste Spiel einen Stein nimmt und der zweite Spieler zwei Steine ​​nimmt, wird der erste Spieler in die gleiche Situation gebracht wie wenn die Anzahl der Steine ​​von jedem Spieler genommen wird rückgängig gemacht). Die erste (größere) Verbesserung besteht darin, bereits errechnete Situationen zu speichern. Dann könnte man sich für effizientere Datenstrukturen entscheiden (z. B. Codieren der Liste möglicher Bewegungen als Bitmuster).