Lassen Sie uns ein Spiel spielen:

Es gibt n Stapel Münzen in einer Reihe. Der i-te Stapel besteht aus d_i Münzen. Zwei Spieler: Spieler1, Spieler2 ziehen abwechselnd. Der Spieler kann seinerseits nur den ersten oder den letzten Stapel oder beide nehmen. Das Spiel endet, wenn keine Münzen mehr vorhanden sind. Jeder Spieler möchte am Ende so viele Münzen wie möglich haben. Spieler1 startet.

Ich habe mich gefragt, welchen Algorithmus (klingt nach einem gierigen Algorithmus) es gibt, wie viele Münzen jeder Spieler am Ende des Spiels hat, wenn beide optimal spielen.

Ich habe keine Ahnung, wie ich mich solchen Algorithmen nähern soll. Ratet mal, Strategie oder gibt es eine Möglichkeit, daraus zu schließen? Oder ist es vielleicht ein zu komisches Problem, einen Algorithmus zu implementieren?

Beispiele (Münzen in Stapeln vom ersten bis zum n-ten):

1, 100, 1 - Spieler haben 2 bzw. 100 Münzen (leider kann der erste Spieler nur den ersten und den letzten Stapel nehmen - der zweite Spieler nimmt immer den Stapel mit 100 Münzen)

1, 1, 100, 1, 1, 5 - Spieler haben 8 bzw. 101 Münzen (ich denke, dies ist nach dem optimalen Spiel - nehmen Sie zuerst 5 und 1, dann 1, um zu verhindern, dass Spieler 1 mit 100 Münzen stapelt. Wenn Spieler 1 nehmen Sie weniger als 6 Münzen in seinem ersten Zug, er wird immer weniger als 8 Münzen haben).

Ich hoffe, ich habe das Problem ausreichend spezifiziert. Stimmen Sie zu, dass es interessant ist? :) Kann jemand helfen?