Player 1 and Player 2 both start at 0 and race to 100 points. Player 1 always plays the simple strategy: on each turn, flip one fair coin and score 1 point on heads, 0 on tails. Player 2 has a much richer move: before each turn, choose a positive integer \(T\), then succeed with probability \(2^{-T}\); on success, score \(2^{T-1}\) points, otherwise score nothing. Player 1 moves first, and the question asks for Player 2's maximum possible winning probability under optimal choices of \(T\).
The solutions do not simulate individual games. Instead they solve a finite optimal-control problem on the remaining distances to the target. For the actual target 100, the computed starting probability is \(0.83648556\) to eight decimal places.
The right viewpoint is to forget absolute scores and track only how many points each player still needs. That turns the game into a dynamic program with an explicit Bellman recurrence.
Let \(F(a,b)\) be the optimal probability that Player 2 eventually wins when Player 1 still needs \(a\) points, Player 2 still needs \(b\) points, and it is Player 2's turn to move.
It is also convenient to introduce \(G(a,b)\), the corresponding probability at the start of Player 1's turn with the same remaining distances. The initial position of the real problem is therefore \(G(100,100)\), not \(F(100,100)\), because Player 1 moves first.
The boundary conditions are immediate:
\(F(a,0)=1\) and \(G(a,0)=1\), because Player 2 has already reached the target; \(G(0,b)=0\), because if Player 1 has already arrived before Player 2 gets another move, Player 2 has lost.
Player 1 either scores 1 point with probability \(1/2\) or scores nothing with probability \(1/2\). Therefore, for \(a\ge 1\) and \(b\ge 1\),
$$G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}.$$
This formula is the first invariant used by the code: every time the game passes through Player 1's turn, the continuation value is just the average of two neighboring \(F\)-states.
Suppose Player 2 chooses an integer \(t\ge 1\). Then
$$q_t=2^{-t},\qquad d_t=2^{t-1}$$
are, respectively, the success probability and the number of points gained on success.
Define the success continuation value by
\(S_t(a,b)=1\) if \(d_t\ge b\), because Player 2 wins immediately, and otherwise \(S_t(a,b)=G(a,b-d_t)\), because after scoring \(d_t\) points the turn passes to Player 1.
If \(t\) is fixed, the one-step Bellman equation is therefore
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\,G(a,b).$$
The subtle point is the failure branch: when Player 2 misses, the scores do not change, so the game returns to the start of Player 1's turn at the same pair \((a,b)\). That is why \(F(a,b)\) appears on both sides after we expand \(G(a,b)\).
Substitute \(G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}\) into the previous equation:
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\frac{F(a,b)+F(a-1,b)}{2}.$$
Now solve this linear equation for \(F(a,b)\). After collecting terms,
$$F(a,b)=\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.$$
Since Player 2 chooses the best \(t\), the true recurrence is
$$\boxed{F(a,b)=\max_{t\ge 1}\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.}$$
This closed form is exactly what the implementations evaluate for every state \((a,b)\).
For a fixed state \((a,b)\), the formula only refers to two kinds of previously known values:
\(F(a-1,b)\), which lies in the previous row, and \(S_t(a,b)\), which either equals 1 or involves \(G(a,b-d_t)\) with \(b-d_t<b\).
That means a row-by-row, left-to-right fill order works. When the code reaches \((a,b)\), every state on which it depends has already been computed.
The action set is also finite. Once \(d_t\ge b\), success already means immediate victory, and any larger \(t\) only lowers the success probability \(q_t\). So only \(O(\log b)\) candidates can matter, and a small global cap is enough for the whole target 100 table.
Consider the state \((a,b)=(1,2)\): Player 1 needs 1 more point, Player 2 needs 2 more points, and it is Player 2's turn.
First compute the simpler state \((1,1)\). If Player 2 chooses \(t=1\), then \(q_1=1/2\) and success ends the game immediately. The formula gives
$$F(1,1)=\frac{2\cdot(1/2)\cdot 1+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{3},$$
so
$$G(1,1)=\frac{F(1,1)+F(0,1)}{2}=\frac{2/3+0}{2}=\frac{1}{3}.$$
Now compare two actions at \((1,2)\).
If Player 2 chooses \(t=1\), a success scores only 1 point, so the success branch leads to \(G(1,1)=1/3\). Since \(F(0,2)=0\),
$$F_{t=1}(1,2)=\frac{2\cdot(1/2)\cdot(1/3)+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{9}\approx 0.2222.$$
If Player 2 chooses \(t=2\), then \(q_2=1/4\) but the gain is 2 points, which wins immediately:
$$F_{t=2}(1,2)=\frac{2\cdot(1/4)\cdot 1+(1-1/4)\cdot 0}{1+1/4}=\frac{2}{5}=0.4.$$
So the optimal move at \((1,2)\) is the riskier \(t=2\). This is exactly the kind of local tradeoff the recurrence captures across the whole \(100\times 100\) state space.
The C++, Python, and Java implementations store a two-dimensional table for \(F(a,b)\). The column \(b=0\) is initialized to 1, expressing that Player 2 has already won whenever no further points are needed.
They also precompute the candidate actions: for each tested \(t\), the code stores \(q_t=2^{-t}\) and \(d_t=2^{t-1}\). Because the gains double each time, only a small number of actions must be examined for target 100.
The main loop visits states in increasing order of \(a\) and \(b\). At each cell, the implementation reads the already known value \(F(a-1,b)\), evaluates every admissible action \(t\), computes the corresponding success value \(S_t(a,b)\), plugs those quantities into the closed-form recurrence, and keeps the maximum.
The C++ implementation additionally stores the maximizing choice of \(t\) for each state, while the Python and Java implementations keep only the probability table because the final answer needs only the optimal value.
After the table is complete, the required answer is obtained by one final Player 1 transition:
$$G(100,100)=\frac{F(100,100)+F(99,100)}{2}.$$
The C++ program also includes an independent Bellman value-iteration verifier on smaller targets and checks that its threaded verifier agrees with the single-threaded version. Those checks are not part of the mathematical core, but they confirm that the closed-form recurrence has been implemented correctly.
For a general target \(N\), there are \(N^2\) states \((a,b)\). Each state tests only \(L\) candidate actions, where \(L=O(\log N)\) because the possible gains are powers of two. The running time is therefore \(O(N^2L)=O(N^2\log N)\).
The memory usage is \(O(N^2)\) for the probability table. One implementation also stores an auxiliary policy table and a verification routine, but the main solver itself is still a straightforward \(O(N^2)\)-space dynamic program. For the actual Project Euler input \(N=100\), this is easily fast enough.
Zwei Spieler starten bei 0 Punkten und laufen auf 100 Punkte zu. Spieler 1 hat keinen Freiheitsgrad: In jedem Zug wird genau eine faire Münze geworfen, bei Kopf gibt es 1 Punkt, bei Zahl 0 Punkte. Spieler 2 darf vor jedem Zug eine positive ganze Zahl \(T\) wählen. Dann gelingt der Zug mit Wahrscheinlichkeit \(2^{-T}\); im Erfolgsfall erhält Spieler 2 genau \(2^{T-1}\) Punkte, sonst gar nichts. Spieler 1 beginnt, und gesucht ist die maximal erreichbare Gewinnwahrscheinlichkeit von Spieler 2.
Die Lösungen simulieren keine einzelnen Partien. Stattdessen formulieren sie ein endliches Optimierungsproblem über die noch fehlenden Punkte beider Spieler. Für das tatsächliche Ziel 100 ergibt sich so die Startwahrscheinlichkeit \(0.83648556\) auf acht Nachkommastellen.
Entscheidend ist, nicht mit den bereits erzielten Punkten zu arbeiten, sondern mit den Restdistanzen bis zum Ziel. Dann wird das Spiel zu einer dynamischen Programmierung mit einer expliziten Bellman-Gleichung.
Sei \(F(a,b)\) die optimale Wahrscheinlichkeit dafür, dass Spieler 2 am Ende gewinnt, wenn Spieler 1 noch \(a\) Punkte braucht, Spieler 2 noch \(b\) Punkte braucht und nun Spieler 2 am Zug ist.
Außerdem ist \(G(a,b)\) die entsprechende Wahrscheinlichkeit zu Beginn eines Zuges von Spieler 1 bei denselben Restwerten. Die reale Startposition ist also \(G(100,100)\) und nicht \(F(100,100)\), weil Spieler 1 beginnt.
Die Randbedingungen sind direkt klar: \(F(a,0)=1\) und \(G(a,0)=1\), denn dann hat Spieler 2 das Ziel bereits erreicht. Dagegen ist \(G(0,b)=0\), weil Spieler 1 schon gewonnen hat, bevor Spieler 2 nochmals ziehen darf.
Spieler 1 erzielt mit Wahrscheinlichkeit \(1/2\) einen Punkt und mit Wahrscheinlichkeit \(1/2\) keinen Punkt. Daher gilt für \(a\ge 1\) und \(b\ge 1\)
$$G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}.$$
Diese Mittelungsformel ist die erste zentrale Invariante des Programms: Immer wenn das Spiel durch einen Zug von Spieler 1 geht, ist der Fortsetzungswert nur der Durchschnitt zweier benachbarter \(F\)-Zustände.
Wählt Spieler 2 eine Zahl \(t\ge 1\), dann sind
$$q_t=2^{-t},\qquad d_t=2^{t-1}$$
die Erfolgswahrscheinlichkeit und der Punktgewinn im Erfolgsfall.
Für den Erfolgszweig definieren wir \(S_t(a,b)\) so: Falls \(d_t\ge b\), ist \(S_t(a,b)=1\), weil Spieler 2 sofort gewinnt. Sonst ist \(S_t(a,b)=G(a,b-d_t)\), weil nach dem Punktgewinn wieder Spieler 1 an die Reihe kommt.
Für festes \(t\) lautet die Ein-Schritt-Gleichung damit
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\,G(a,b).$$
Die feine Stelle liegt im Misserfolgszweig: Verfehlt Spieler 2 den Zug, bleiben die Punktestände unverändert und das Spiel geht zu Beginn des Zuges von Spieler 1 im selben Zustand \((a,b)\) weiter. Genau deshalb taucht \(F(a,b)\) nach dem Einsetzen von \(G(a,b)\) auf beiden Seiten auf.
Setzt man \(G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}\) ein, erhält man
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\frac{F(a,b)+F(a-1,b)}{2}.$$
Diese lineare Gleichung lässt sich direkt nach \(F(a,b)\) auflösen:
$$F(a,b)=\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.$$
Da Spieler 2 das beste \(t\) wählt, folgt die eigentliche Rekurrenz
$$\boxed{F(a,b)=\max_{t\ge 1}\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.}$$
Genau diese geschlossene Form wird in allen drei Implementierungen Zustand für Zustand ausgewertet.
Für einen festen Zustand \((a,b)\) verweist die Rekurrenz nur auf zwei Arten bereits bekannter Werte: auf \(F(a-1,b)\) aus der vorherigen Zeile und auf \(S_t(a,b)\), also entweder auf 1 oder auf \(G(a,b-d_t)\) mit strikt kleinerem \(b\).
Darum kann man die Tabelle zeilenweise und innerhalb jeder Zeile von links nach rechts füllen. Wenn \((a,b)\) erreicht wird, sind alle benötigten Werte schon berechnet.
Auch die Aktionsmenge ist endlich. Sobald \(d_t\ge b\) gilt, bedeutet ein Erfolg ohnehin sofortigen Sieg, und ein noch größeres \(t\) senkt nur die Erfolgswahrscheinlichkeit \(q_t\). Deshalb kommen nur \(O(\log b)\) Kandidaten ernsthaft in Frage; für Ziel 100 reicht eine kleine globale Obergrenze.
Betrachten wir den Zustand \((a,b)=(1,2)\): Spieler 1 braucht noch 1 Punkt, Spieler 2 noch 2 Punkte, und Spieler 2 ist am Zug.
Zuerst der einfachere Zustand \((1,1)\). Bei \(t=1\) ist \(q_1=1/2\), und ein Erfolg beendet das Spiel sofort. Damit
$$F(1,1)=\frac{2\cdot(1/2)\cdot 1+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{3},$$
also
$$G(1,1)=\frac{F(1,1)+F(0,1)}{2}=\frac{2/3+0}{2}=\frac{1}{3}.$$
Nun vergleichen wir zwei Entscheidungen bei \((1,2)\).
Für \(t=1\) bringt ein Erfolg nur 1 Punkt, also führt der Erfolgszweig zu \(G(1,1)=1/3\). Wegen \(F(0,2)=0\) folgt
$$F_{t=1}(1,2)=\frac{2\cdot(1/2)\cdot(1/3)+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{9}\approx 0.2222.$$
Für \(t=2\) gilt \(q_2=1/4\), aber der Gewinnsprung beträgt 2 Punkte und reicht damit sofort zum Sieg:
$$F_{t=2}(1,2)=\frac{2\cdot(1/4)\cdot 1+(1-1/4)\cdot 0}{1+1/4}=\frac{2}{5}=0.4.$$
In diesem Zustand ist also gerade der riskantere Zug optimal. Genau solche lokalen Abwägungen löst die Rekurrenz über den gesamten \(100\times 100\)-Zustandsraum hinweg.
Die Implementierungen in C++, Python und Java halten eine zweidimensionale Tabelle für \(F(a,b)\). Die Spalte \(b=0\) wird mit 1 initialisiert, weil Spieler 2 in allen solchen Zuständen bereits gewonnen hat.
Außerdem werden die möglichen Aktionen vorbereitet: Für jedes getestete \(t\) speichert der Code \(q_t=2^{-t}\) und \(d_t=2^{t-1}\). Da die Gewinne sich jeweils verdoppeln, müssen für Ziel 100 nur sehr wenige Aktionen betrachtet werden.
Die Hauptschleife besucht die Zustände in wachsender Reihenfolge von \(a\) und \(b\). In jeder Zelle liest die Implementierung den bereits bekannten Wert \(F(a-1,b)\), berechnet für jedes zulässige \(t\) den Erfolgswert \(S_t(a,b)\), setzt alles in die geschlossene Rekurrenz ein und behält das Maximum.
Die C++-Variante speichert zusätzlich die optimale Wahl von \(t\) pro Zustand. Python und Java halten nur die Wahrscheinlichkeitstabelle, weil für die eigentliche Ausgabe allein der Optimalwert benötigt wird.
Nach dem Füllen der Tabelle wird die gesuchte Startwahrscheinlichkeit durch einen letzten Übergang für Spieler 1 gewonnen:
$$G(100,100)=\frac{F(100,100)+F(99,100)}{2}.$$
Das C++-Programm enthält außerdem eine unabhängige Bellman-Value-Iteration auf kleineren Zielwerten und prüft, dass deren parallele und serielle Ausführung übereinstimmen. Diese Tests gehören nicht zur eigentlichen Herleitung, bestätigen aber die Korrektheit der geschlossenen DP-Formel.
Für ein allgemeines Ziel \(N\) gibt es \(N^2\) Zustände \((a,b)\). Pro Zustand werden nur \(L\) Aktionskandidaten geprüft, wobei \(L=O(\log N)\) ist, weil die möglichen Punktgewinne Zweierpotenzen sind. Die Laufzeit beträgt daher \(O(N^2L)=O(N^2\log N)\).
Der Speicherbedarf ist \(O(N^2)\) für die Wahrscheinlichkeitstabelle. Eine Implementierung führt zusätzlich eine Policy-Tabelle und einen Verifizierer, doch der eigentliche Löser bleibt ein ganz normales dynamisches Programm mit \(O(N^2)\) Speicher. Für den konkreten Project-Euler-Fall \(N=100\) ist das sehr klein.
İki oyuncu da 0 puandan başlayıp 100 puana ulaşmak için yarışır. Oyuncu 1'in hamlesi sabittir: her tur bir adil para atar; yazı gelirse 1 puan, tura gelirse 0 puan alır. Oyuncu 2 ise her turdan önce pozitif bir \(T\) tamsayısı seçebilir. Bu seçimden sonra başarı olasılığı \(2^{-T}\) olur; başarı gerçekleşirse \(2^{T-1}\) puan kazanır, aksi halde puan alamaz. Oyuncu 1 ilk başlayan oyuncudur ve sorulan şey, Oyuncu 2'nin en iyi seçimlerle ulaşabileceği maksimum kazanma olasılığıdır.
Çözüm dosyaları tek tek oyun simülasyonu yapmaz. Bunun yerine, iki oyuncunun hedefe ulaşmak için kaç puana daha ihtiyacı kaldığını izleyen sonlu bir optimal kontrol problemi kurar. Gerçek hedef olan 100 için başlangıç kazanma olasılığı sekiz basamakla \(0.83648556\) bulunur.
Doğru bakış açısı, mevcut skorları değil kalan mesafeleri izlemektir. Bu seçim problemi doğrudan bir Bellman bağıntısına sahip dinamik programlamaya dönüştürür.
\(F(a,b)\), Oyuncu 1'in hedefe ulaşmak için \(a\), Oyuncu 2'nin ise \(b\) puana daha ihtiyacı varken ve sıra Oyuncu 2'deyken, Oyuncu 2'nin sonunda kazanma olasılığı olsun.
Ayrıca \(G(a,b)\), aynı kalan puanlarla sıra Oyuncu 1'deyken aynı olasılığı göstersin. Gerçek problemin başlangıç durumu bu yüzden \(F(100,100)\) değil, \(G(100,100)\)'dür; çünkü ilk hamleyi Oyuncu 1 yapar.
Sınır koşulları doğrudandır: \(F(a,0)=1\) ve \(G(a,0)=1\), çünkü Oyuncu 2 zaten hedefe ulaşmıştır. Buna karşılık \(G(0,b)=0\), çünkü Oyuncu 1, Oyuncu 2 bir daha hamle yapamadan yarışı bitirmiştir.
Oyuncu 1, olasılık \(1/2\) ile 1 puan alır, olasılık \(1/2\) ile puan alamaz. Dolayısıyla \(a\ge 1\) ve \(b\ge 1\) için
$$G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}.$$
Bu ortalama alma formülü programın ilk temel değişmezidir: oyun Oyuncu 1'in turundan geçtiğinde devam değeri yalnızca komşu iki \(F\) durumunun ortalamasıdır.
Oyuncu 2 bir \(t\ge 1\) seçsin. O zaman
$$q_t=2^{-t},\qquad d_t=2^{t-1}$$
sırasıyla başarı olasılığı ve başarılı olursa kazanacağı puandır.
Başarı dalı için \(S_t(a,b)\) değerini tanımlayalım. Eğer \(d_t\ge b\) ise \(S_t(a,b)=1\), çünkü Oyuncu 2 anında kazanır. Aksi halde \(S_t(a,b)=G(a,b-d_t)\) olur; çünkü puanı aldıktan sonra sıra Oyuncu 1'e geçer.
Sabit bir \(t\) için tek adımlık Bellman eşitliği
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\,G(a,b)$$
şeklindedir. İnce nokta başarısızlık dalıdır: Oyuncu 2 tutturamazsa skorlar değişmez ve oyun aynı \((a,b)\) çiftiyle Oyuncu 1'in turunun başına döner. Bu nedenle \(G(a,b)\) açıldığında \(F(a,b)\) iki tarafta da görünür.
\(G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}\) ifadesini yerine koyarsak
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\frac{F(a,b)+F(a-1,b)}{2}$$
elde edilir. Bu doğrusal denklem \(F(a,b)\) için doğrudan çözülebilir:
$$F(a,b)=\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.$$
Oyuncu 2 en iyi \(t\)'yi seçtiğine göre gerçek bağıntı
$$\boxed{F(a,b)=\max_{t\ge 1}\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.}$$
Uygulamalar her \((a,b)\) durumu için tam olarak bu kapalı formu değerlendirir.
Sabit bir \((a,b)\) için formül yalnızca önceden bilinen iki tür değere bakar: önceki satırdaki \(F(a-1,b)\) ve ya 1 olan ya da \(b-d_t<b\) nedeniyle daha küçük bir sütuna giden \(G(a,b-d_t)\).
Bu yüzden satır satır ve her satır içinde soldan sağa ilerlemek yeterlidir. Kod \((a,b)\) hücresine geldiğinde ihtiyaç duyduğu her durum zaten hesaplanmıştır.
Eylem uzayı da sonludur. \(d_t\ge b\) olduktan sonra başarı zaten anında zafer demektir; daha büyük bir \(t\) ise sadece başarı olasılığını \(q_t\) düşürür. Bu nedenle anlamlı aday sayısı \(O(\log b)\) kadardır ve hedef 100 için küçük bir global üst sınır yeterlidir.
\((a,b)=(1,2)\) durumunu düşünelim: Oyuncu 1'in 1, Oyuncu 2'nin 2 puana daha ihtiyacı var ve sıra Oyuncu 2'de.
Önce daha basit \((1,1)\) durumunu çözelim. \(t=1\) seçilirse \(q_1=1/2\) olur ve başarı oyunu hemen bitirir. O halde
$$F(1,1)=\frac{2\cdot(1/2)\cdot 1+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{3},$$
dolayısıyla
$$G(1,1)=\frac{F(1,1)+F(0,1)}{2}=\frac{2/3+0}{2}=\frac{1}{3}.$$
Şimdi \((1,2)\) durumunda iki hamleyi karşılaştıralım.
\(t=1\) seçilirse başarı yalnızca 1 puan kazandırır; yani başarı dalı \(G(1,1)=1/3\) durumuna gider. Ayrıca \(F(0,2)=0\) olduğu için
$$F_{t=1}(1,2)=\frac{2\cdot(1/2)\cdot(1/3)+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{9}\approx 0.2222.$$
\(t=2\) seçilirse \(q_2=1/4\) olur, ama kazanılan puan 2'dir ve bu doğrudan zafer getirir:
$$F_{t=2}(1,2)=\frac{2\cdot(1/4)\cdot 1+(1-1/4)\cdot 0}{1+1/4}=\frac{2}{5}=0.4.$$
Demek ki bu durumda daha riskli olan \(t=2\) daha iyidir. Bütün \(100\times 100\) tablo boyunca yapılan optimizasyon tam olarak bu tür yerel risk-ödül dengelerini çözer.
C++, Python ve Java uygulamaları \(F(a,b)\) için iki boyutlu bir tablo tutar. \(b=0\) sütunu 1 ile doldurulur; çünkü bu durumlarda Oyuncu 2 zaten yarışı kazanmıştır.
Ayrıca denenebilecek hamleler önceden hazırlanır: her \(t\) için \(q_t=2^{-t}\) ve \(d_t=2^{t-1}\) değerleri saklanır. Puan artışları her seferinde iki katına çıktığı için hedef 100 için bakılması gereken hamle sayısı küçüktür.
Ana döngü durumları artan \(a\) ve \(b\) sırasıyla gezer. Her hücrede uygulama önceden bilinen \(F(a-1,b)\) değerini okur, her geçerli \(t\) için başarı değerini \(S_t(a,b)\) hesaplar, bunları kapalı form bağıntısına yerleştirir ve maksimumu seçer.
C++ sürümü buna ek olarak her durum için en iyi \(t\) seçimini de saklar. Python ve Java sürümleri ise yalnızca olasılık tablosunu tutar; çünkü son çıktı için gereken şey optimal değerin kendisidir.
Tablo tamamlandıktan sonra aranan başlangıç olasılığı, Oyuncu 1 için bir son geçiş uygulanarak elde edilir:
$$G(100,100)=\frac{F(100,100)+F(99,100)}{2}.$$
C++ programı ayrıca daha küçük hedeflerde bağımsız bir Bellman değer yineleme doğrulaması yapar ve bu doğrulayıcının çok iş parçacıklı ve tek iş parçacıklı sonuçlarının çakıştığını kontrol eder. Bunlar asıl matematiksel çözümün parçası değildir, ama kapalı form DP'nin doğru kodlandığını gösterir.
Genel hedef \(N\) için toplam \(N^2\) adet \((a,b)\) durumu vardır. Her durumda incelenen aday hamle sayısı \(L\) olup, puan kazançları ikinin kuvvetleri olduğu için \(L=O(\log N)\) olur. Böylece çalışma süresi \(O(N^2L)=O(N^2\log N)\)'dir.
Bellek kullanımı olasılık tablosu için \(O(N^2)\)'dir. Bir uygulama ek olarak bir politika tablosu ve doğrulama altyapısı tutsa da, esas çözücü hâlâ sıradan bir \(O(N^2)\) alanlı dinamik programlamadır. Project Euler'deki gerçek girdi olan \(N=100\) için bu yaklaşım fazlasıyla hafiftir.
Los dos jugadores empiezan con 0 puntos y corren hasta 100. El jugador 1 siempre hace la misma jugada: lanza una moneda justa y anota 1 punto con probabilidad \(1/2\), o 0 puntos con probabilidad \(1/2\). El jugador 2 puede elegir antes de cada turno un entero positivo \(T\). Esa elección le da probabilidad de éxito \(2^{-T}\); si tiene éxito, suma \(2^{T-1}\) puntos, y si falla no suma nada. El jugador 1 mueve primero, y el objetivo es hallar la máxima probabilidad de victoria del jugador 2 bajo juego óptimo.
Las soluciones no simulan partidas completas. En lugar de eso resuelven un problema finito de control óptimo sobre los puntos que aún faltan para llegar a la meta. Para el objetivo real 100, la probabilidad inicial obtenida es \(0.83648556\) con ocho decimales.
La clave es olvidar las puntuaciones absolutas y trabajar solo con lo que le falta a cada jugador para ganar. Con ese cambio, el juego se convierte en una programación dinámica con una recurrencia de Bellman explícita.
Sea \(F(a,b)\) la probabilidad óptima de que el jugador 2 termine ganando cuando al jugador 1 le faltan \(a\) puntos, al jugador 2 le faltan \(b\) puntos y es el turno del jugador 2.
También definimos \(G(a,b)\) como la misma probabilidad, pero al comienzo del turno del jugador 1 con esos mismos valores restantes. Por eso la posición inicial del problema real es \(G(100,100)\), no \(F(100,100)\), ya que el jugador 1 empieza.
Las condiciones de borde son inmediatas: \(F(a,0)=1\) y \(G(a,0)=1\), porque el jugador 2 ya ha llegado a la meta; en cambio \(G(0,b)=0\), porque si el jugador 1 ya alcanzó 100 antes del siguiente turno del jugador 2, la carrera terminó.
El jugador 1 anota 1 punto con probabilidad \(1/2\) y 0 puntos con probabilidad \(1/2\). Por tanto, para \(a\ge 1\) y \(b\ge 1\),
$$G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}.$$
Esta identidad es la primera invariante importante: cada vez que el juego pasa por un turno del jugador 1, el valor de continuación es simplemente el promedio de dos estados vecinos de \(F\).
Si el jugador 2 elige un \(t\ge 1\), entonces
$$q_t=2^{-t},\qquad d_t=2^{t-1}$$
son la probabilidad de éxito y la puntuación ganada si ese éxito ocurre.
Definimos el valor de la rama de éxito así: \(S_t(a,b)=1\) si \(d_t\ge b\), porque el jugador 2 gana de inmediato, y en caso contrario \(S_t(a,b)=G(a,b-d_t)\), porque después de anotar \(d_t\) puntos el turno pasa al jugador 1.
Con \(t\) fijado, la ecuación de Bellman de un paso es
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\,G(a,b).$$
El detalle delicado está en la rama de fracaso: si el jugador 2 falla, las puntuaciones no cambian y el juego vuelve al comienzo del turno del jugador 1 en el mismo estado \((a,b)\). Por eso \(F(a,b)\) reaparece en ambos lados cuando expandimos \(G(a,b)\).
Sustituyendo \(G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}\) en la ecuación anterior se obtiene
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\frac{F(a,b)+F(a-1,b)}{2}.$$
Ahora se resuelve esta ecuación lineal para \(F(a,b)\):
$$F(a,b)=\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.$$
Como el jugador 2 escoge el mejor \(t\), la recurrencia definitiva es
$$\boxed{F(a,b)=\max_{t\ge 1}\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.}$$
Ésta es exactamente la fórmula cerrada que evalúan las implementaciones para cada estado \((a,b)\).
Para un estado fijo \((a,b)\), la fórmula solo usa dos tipos de valores ya conocidos: \(F(a-1,b)\), que está en la fila anterior, y \(S_t(a,b)\), que o bien vale 1 o bien involucra \(G(a,b-d_t)\) con \(b-d_t<b\).
Eso hace posible recorrer la tabla fila por fila y, dentro de cada fila, de izquierda a derecha. Cuando el código llega a \((a,b)\), todos sus dependientes ya fueron calculados.
Además, el conjunto de acciones relevantes es finito. En cuanto \(d_t\ge b\), cualquier éxito ya significa victoria inmediata, y un \(t\) mayor solo reduce la probabilidad de éxito \(q_t\). Así que solo importan \(O(\log b)\) candidatos; para la meta 100 basta un límite global pequeño.
Consideremos el estado \((a,b)=(1,2)\): al jugador 1 le falta 1 punto, al jugador 2 le faltan 2 puntos y es el turno del jugador 2.
Primero resolvemos el estado más simple \((1,1)\). Si el jugador 2 elige \(t=1\), entonces \(q_1=1/2\) y el éxito termina la partida de inmediato. La fórmula da
$$F(1,1)=\frac{2\cdot(1/2)\cdot 1+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{3},$$
y por tanto
$$G(1,1)=\frac{F(1,1)+F(0,1)}{2}=\frac{2/3+0}{2}=\frac{1}{3}.$$
Ahora comparemos dos opciones en \((1,2)\).
Si el jugador 2 elige \(t=1\), el éxito solo suma 1 punto, así que la rama favorable conduce a \(G(1,1)=1/3\). Como además \(F(0,2)=0\), se obtiene
$$F_{t=1}(1,2)=\frac{2\cdot(1/2)\cdot(1/3)+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{9}\approx 0.2222.$$
Si elige \(t=2\), entonces \(q_2=1/4\), pero la ganancia es de 2 puntos y eso basta para ganar en ese mismo turno:
$$F_{t=2}(1,2)=\frac{2\cdot(1/4)\cdot 1+(1-1/4)\cdot 0}{1+1/4}=\frac{2}{5}=0.4.$$
En este estado la jugada óptima es la más arriesgada, \(t=2\). La tabla completa de \(100\times 100\) estados resuelve exactamente ese mismo equilibrio entre probabilidad de éxito y tamaño del premio.
Las implementaciones en C++, Python y Java mantienen una tabla bidimensional para \(F(a,b)\). La columna \(b=0\) se inicializa con 1, reflejando que el jugador 2 ya ganó cuando no le falta ningún punto.
También precalculan las acciones candidatas: para cada \(t\) examinado se guardan \(q_t=2^{-t}\) y \(d_t=2^{t-1}\). Como las ganancias se duplican en cada paso, para el objetivo 100 solo hace falta revisar un número pequeño de acciones.
El bucle principal visita los estados en orden creciente de \(a\) y \(b\). En cada celda, la implementación toma el valor ya conocido \(F(a-1,b)\), calcula el valor de éxito \(S_t(a,b)\) para cada acción admisible, sustituye todo en la recurrencia cerrada y conserva el máximo.
La implementación en C++ además registra qué \(t\) fue el mejor en cada estado. Las versiones de Python y Java almacenan solo la tabla de probabilidades, porque el resultado final requiere únicamente el valor óptimo.
Una vez completada la tabla, la respuesta pedida se obtiene mediante una última transición del jugador 1:
$$G(100,100)=\frac{F(100,100)+F(99,100)}{2}.$$
El programa en C++ también incluye una verificación independiente mediante iteración de valores de Bellman en objetivos más pequeños y comprueba que su verificador paralelo coincide con la versión de un solo hilo. Eso no cambia el algoritmo principal, pero sí refuerza que la implementación de la recurrencia es correcta.
Para una meta general \(N\), hay \(N^2\) estados \((a,b)\). Cada estado prueba solo \(L\) acciones candidatas, con \(L=O(\log N)\) porque las ganancias posibles son potencias de dos. Por tanto, el tiempo de ejecución es \(O(N^2L)=O(N^2\log N)\).
El uso de memoria es \(O(N^2)\) para la tabla de probabilidades. Una de las implementaciones añade una tabla auxiliar de política y una rutina de verificación, pero el resolvedor principal sigue siendo una programación dinámica de espacio \(O(N^2)\). Para el caso real \(N=100\), este costo es muy pequeño.
两名玩家都从 0 分开始，先到 100 分者获胜。玩家 1 的规则固定不变：每一轮只抛一枚公平硬币，正面得 1 分，反面得 0 分。玩家 2 的每一轮则可以先选择一个正整数 \(T\)。一旦选定 \(T\)，这一轮以概率 \(2^{-T}\) 成功；成功时得到 \(2^{T-1}\) 分，失败时得 0 分。题目中由玩家 1 先手，要求计算在最优策略下玩家 2 的最大胜率。
解法并不去暴力模拟具体比赛，而是把问题改写成“双方距离终点还差多少分”的有限状态最优化问题。对实际目标 100 来说，起始位置的最优胜率计算结果是 \(0.83648556\)。
最自然也最有效的做法，是放弃“当前分数”这种表示，改为记录“还差多少分才能到 100”。这样整个游戏就变成了一个带 Bellman 递推的动态规划。
记 \(F(a,b)\) 为这样一个概率：当玩家 1 还差 \(a\) 分、玩家 2 还差 \(b\) 分，并且当前轮到玩家 2 行动时，玩家 2 最终获胜的最优概率。
再记 \(G(a,b)\) 为同样的量，但现在是“轮到玩家 1 行动”的回合起点。由于真实比赛是玩家 1 先手，所以真正需要的答案是 \(G(100,100)\)，而不是 \(F(100,100)\)。
边界条件非常直接：\(F(a,0)=1\) 且 \(G(a,0)=1\)，因为这表示玩家 2 已经到达目标；而 \(G(0,b)=0\)，因为如果玩家 1 已经先到终点，那么在玩家 2 下一次行动之前比赛就结束了。
玩家 1 每次只有两种结果：以概率 \(1/2\) 得 1 分，以概率 \(1/2\) 得 0 分。因此对所有 \(a\ge 1\)、\(b\ge 1\)，都有
$$G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}.$$
这条平均公式是实现中的第一个核心不变量：每当状态经过玩家 1 的回合，后续胜率只等于两个相邻 \(F\) 状态的平均值。
假设玩家 2 在当前回合选择 \(t\ge 1\)。那么
$$q_t=2^{-t},\qquad d_t=2^{t-1}$$
分别表示成功概率和成功时增加的分数。
把成功分支的后续价值记作 \(S_t(a,b)\)。如果 \(d_t\ge b\)，说明这一轮成功就已经到线，所以 \(S_t(a,b)=1\)。否则还没有结束，接下来轮到玩家 1，于是 \(S_t(a,b)=G(a,b-d_t)\)。
对于固定的 \(t\)，一轮决策对应的 Bellman 方程就是
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\,G(a,b).$$
这里最关键的地方在失败分支：如果玩家 2 这一轮没有成功，比分完全不变，游戏只是在同一个 \((a,b)\) 上转移到“玩家 1 的回合开始”。也正因为如此，把 \(G(a,b)\) 展开以后，\(F(a,b)\) 会出现在等式两边。
把 \(G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}\) 代回去，有
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\frac{F(a,b)+F(a-1,b)}{2}.$$
这是一个关于 \(F(a,b)\) 的线性方程，可以直接整理：
$$F(a,b)=\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.$$
由于玩家 2 会选择最优的 \(t\)，真正需要计算的是
$$\boxed{F(a,b)=\max_{t\ge 1}\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.}$$
这就是三份实现代码真正逐格计算的核心公式。
对固定状态 \((a,b)\) 来说，右侧只会用到两类已经可得的量：一类是上一行的 \(F(a-1,b)\)，另一类是 \(S_t(a,b)\)。而 \(S_t(a,b)\) 要么直接等于 1，要么会访问 \(G(a,b-d_t)\)，其中 \(b-d_t<b\)。
这意味着动态规划表可以按 \(a\) 递增、在每一行内按 \(b\) 递增的顺序填写。等程序走到 \((a,b)\) 时，所有依赖状态都已经完成了。
可选动作数量也是有限的。一旦某个 \(t\) 已满足 \(d_t\ge b\)，成功就已经意味着立刻获胜；再继续增大 \(t\) 只会让成功概率 \(q_t\) 更低，而不会带来更好的成功结果。因此真正需要考虑的动作个数只有 \(O(\log b)\) 个，对整张目标为 100 的表来说只需一个很小的全局上界。
来看状态 \((a,b)=(1,2)\)：玩家 1 还差 1 分，玩家 2 还差 2 分，并且现在轮到玩家 2。
先求更简单的 \((1,1)\)。如果玩家 2 选 \(t=1\)，那么 \(q_1=1/2\)，成功后立刻结束比赛，于是
$$F(1,1)=\frac{2\cdot(1/2)\cdot 1+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{3},$$
从而
$$G(1,1)=\frac{F(1,1)+F(0,1)}{2}=\frac{2/3+0}{2}=\frac{1}{3}.$$
现在比较 \((1,2)\) 下两个动作。
如果选 \(t=1\)，成功时只加 1 分，所以成功分支会走到 \(G(1,1)=1/3\)。又因为 \(F(0,2)=0\)，于是
$$F_{t=1}(1,2)=\frac{2\cdot(1/2)\cdot(1/3)+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{9}\approx 0.2222.$$
如果选 \(t=2\)，那么虽然成功概率下降到 \(q_2=1/4\)，但成功一次就正好得到 2 分并直接获胜：
$$F_{t=2}(1,2)=\frac{2\cdot(1/4)\cdot 1+(1-1/4)\cdot 0}{1+1/4}=\frac{2}{5}=0.4.$$
所以在这个状态下，更激进的 \(t=2\) 反而更好。整道题的本质，就是在所有 \((a,b)\) 上重复这种“成功概率变小，但成功奖励变大”的权衡。
C++、Python 和 Java 实现都维护一张二维表来存放 \(F(a,b)\)。其中 \(b=0\) 的整列先初始化为 1，因为这代表玩家 2 已经到达终点。
代码还会预先生成候选动作：对每个被检查的 \(t\)，保存 \(q_t=2^{-t}\) 和 \(d_t=2^{t-1}\)。由于得分增量每次都翻倍，所以在目标 100 的情况下，真正需要测试的动作非常少。
主循环按照 \(a\) 递增、\(b\) 递增的顺序访问每个状态。到达某个单元格时，实现先读取已经算好的 \(F(a-1,b)\)，再对每个允许的 \(t\) 计算成功分支 \(S_t(a,b)\)，代入闭式递推公式，并取最大值。
C++ 版本还会额外记录每个状态的最佳 \(t\)。Python 和 Java 版本则只保留概率表，因为最终输出只需要最优概率本身。
整张表完成之后，再做一次玩家 1 的状态转移，就得到题目要求的起始胜率：
$$G(100,100)=\frac{F(100,100)+F(99,100)}{2}.$$
C++ 程序还包含一个独立的 Bellman 值迭代校验器，用较小目标值重新验证结果，并检查其多线程与单线程版本是否一致。这些步骤不改变主算法，但能确认闭式递推的实现没有偏差。
对一般目标 \(N\) 而言，总共有 \(N^2\) 个状态 \((a,b)\)。每个状态只需测试 \(L\) 个动作，其中 \(L=O(\log N)\)，因为候选得分是 2 的幂。于是总时间复杂度是 \(O(N^2L)=O(N^2\log N)\)。
空间复杂度是存储概率表所需的 \(O(N^2)\)。其中一个实现还会附带策略表和验证逻辑，但主求解器本身仍然只是一个标准的 \(O(N^2)\) 空间动态规划。对本题的实际输入 \(N=100\) 来说，这个规模非常小。
Оба игрока стартуют с 0 очков и соревнуются, кто первым наберет 100. У игрока 1 ход фиксирован: в каждом раунде он подбрасывает одну честную монету и получает 1 очко с вероятностью \(1/2\) и 0 очков с вероятностью \(1/2\). Игрок 2 перед своим ходом выбирает положительное целое \(T\). После этого его ход успешен с вероятностью \(2^{-T}\); при успехе он получает \(2^{T-1}\) очков, а при неудаче не получает ничего. Игрок 1 ходит первым, и требуется найти максимальную вероятность победы игрока 2 при оптимальном выборе \(T\).
Решения не моделируют партии напрямую. Вместо этого игра переписывается как конечная задача оптимального управления по числу очков, которые еще остаются до финиша у каждого игрока. Для реальной цели 100 стартовая вероятность победы игрока 2 получается равной \(0.83648556\).
Самая важная идея состоит в том, чтобы работать не с уже набранными очками, а с оставшимся расстоянием до 100. После этого задача превращается в динамическое программирование с явной рекурсией Беллмана.
Обозначим через \(F(a,b)\) оптимальную вероятность того, что игрок 2 в итоге победит, если игроку 1 нужно еще \(a\) очков, игроку 2 нужно еще \(b\) очков, и сейчас ход игрока 2.
Также введем \(G(a,b)\) — ту же вероятность в начале хода игрока 1 при тех же остатках. Поэтому реальная стартовая позиция задачи — это \(G(100,100)\), а не \(F(100,100)\), поскольку первым ходит игрок 1.
Граничные условия немедленны: \(F(a,0)=1\) и \(G(a,0)=1\), потому что игрок 2 уже достиг цели. Напротив, \(G(0,b)=0\), потому что игрок 1 уже выиграл раньше, чем игрок 2 получил еще один ход.
Игрок 1 с вероятностью \(1/2\) получает одно очко и с вероятностью \(1/2\) не получает ничего. Следовательно, для \(a\ge 1\) и \(b\ge 1\)
$$G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}.$$
Это первая базовая инварианта решения: всякий раз, когда игра проходит через ход игрока 1, значение продолжения просто равно среднему двух соседних состояний \(F\).
Пусть игрок 2 выбирает \(t\ge 1\). Тогда
$$q_t=2^{-t},\qquad d_t=2^{t-1}$$
— это вероятность успеха и количество очков, которое он получает при успехе.
Введем значение успешной ветви \(S_t(a,b)\). Если \(d_t\ge b\), то \(S_t(a,b)=1\), потому что игрок 2 сразу выигрывает. Иначе \(S_t(a,b)=G(a,b-d_t)\), так как после набора \(d_t\) очков очередь переходит к игроку 1.
При фиксированном \(t\) одношаговое уравнение Беллмана имеет вид
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\,G(a,b).$$
Тонкость заключается в ветви неудачи: если игрок 2 не добился успеха, счет не меняется, и игра возвращается к началу хода игрока 1 в том же состоянии \((a,b)\). Поэтому после раскрытия \(G(a,b)\) величина \(F(a,b)\) появляется по обе стороны уравнения.
Подставим \(G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}\):
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\frac{F(a,b)+F(a-1,b)}{2}.$$
Это линейное уравнение можно решить относительно \(F(a,b)\):
$$F(a,b)=\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.$$
Так как игрок 2 выбирает лучший параметр, окончательная рекурсия равна
$$\boxed{F(a,b)=\max_{t\ge 1}\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.}$$
Именно эту закрытую формулу и вычисляют реализации для каждого состояния \((a,b)\).
Для фиксированного \((a,b)\) правая часть использует только два типа уже известных значений: \(F(a-1,b)\) из предыдущей строки и \(S_t(a,b)\), которое либо равно 1, либо обращается к \(G(a,b-d_t)\) с меньшим \(b\).
Поэтому достаточно проходить состояния по возрастанию \(a\) и, внутри каждой строки, по возрастанию \(b\). К моменту вычисления \((a,b)\) все необходимые зависимые состояния уже посчитаны.
Множество возможных действий тоже конечно. Как только выполнено \(d_t\ge b\), успех уже означает немедленную победу, а больший \(t\) только уменьшает вероятность успеха \(q_t\). Значит, реально значимы лишь \(O(\log b)\) кандидатов, и для цели 100 хватает очень небольшой глобальной границы.
Рассмотрим состояние \((a,b)=(1,2)\): игроку 1 нужен еще 1 балл, игроку 2 — еще 2 балла, и ходит игрок 2.
Сначала вычислим более простой случай \((1,1)\). Если игрок 2 выбирает \(t=1\), то \(q_1=1/2\), а успех немедленно завершает игру. Тогда
$$F(1,1)=\frac{2\cdot(1/2)\cdot 1+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{3},$$
и потому
$$G(1,1)=\frac{F(1,1)+F(0,1)}{2}=\frac{2/3+0}{2}=\frac{1}{3}.$$
Теперь сравним два действия в состоянии \((1,2)\).
Если выбрать \(t=1\), то при успехе набирается только 1 балл, и успешная ветвь ведет в \(G(1,1)=1/3\). Поскольку \(F(0,2)=0\), получаем
$$F_{t=1}(1,2)=\frac{2\cdot(1/2)\cdot(1/3)+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{9}\approx 0.2222.$$
Если же выбрать \(t=2\), вероятность успеха падает до \(q_2=1/4\), зато выигрыш при успехе равен 2 баллам и этого достаточно для немедленной победы:
$$F_{t=2}(1,2)=\frac{2\cdot(1/4)\cdot 1+(1-1/4)\cdot 0}{1+1/4}=\frac{2}{5}=0.4.$$
Здесь оптимальным оказывается более рискованный ход \(t=2\). Именно такой баланс между меньшей вероятностью успеха и большим вознаграждением и оптимизируется по всей таблице \(100\times 100\).
Реализации на C++, Python и Java поддерживают двумерную таблицу для \(F(a,b)\). Весь столбец \(b=0\) инициализируется единицами, потому что это состояния, в которых игрок 2 уже выиграл.
Также заранее подготавливаются кандидатные действия: для каждого проверяемого \(t\) код сохраняет \(q_t=2^{-t}\) и \(d_t=2^{t-1}\). Поскольку возможный выигрыш удваивается на каждом шаге, для цели 100 требуется проверить лишь небольшое число значений \(t\).
Главный цикл проходит состояния в порядке возрастания \(a\) и \(b\). В каждой ячейке программа берет уже известное значение \(F(a-1,b)\), вычисляет успешную ветвь \(S_t(a,b)\) для каждого допустимого \(t\), подставляет все в закрытую рекурсию и оставляет максимум.
Версия на C++ дополнительно хранит оптимальный выбор \(t\) для каждого состояния. Версии на Python и Java оставляют только таблицу вероятностей, потому что для окончательного ответа требуется лишь оптимальное значение.
После заполнения таблицы нужный ответ получается одним последним переходом игрока 1:
$$G(100,100)=\frac{F(100,100)+F(99,100)}{2}.$$
Программа на C++ также содержит независимую проверку через итерацию значений Беллмана на меньших целях и убеждается, что многопоточная и однопоточная версии этой проверки совпадают. Эти шаги не меняют основной алгоритм, но подтверждают корректность реализации рекурсии.
Для общей цели \(N\) имеется \(N^2\) состояний \((a,b)\). Для каждого состояния проверяется только \(L\) действий, где \(L=O(\log N)\), поскольку возможные выигрыши являются степенями двойки. Следовательно, время работы равно \(O(N^2L)=O(N^2\log N)\).
Память составляет \(O(N^2)\) для таблицы вероятностей. Одна из реализаций дополняет ее таблицей стратегии и кодом верификации, но основной решатель все равно остается обычной динамикой с памятью \(O(N^2)\). Для фактического входа Project Euler, где \(N=100\), это очень небольшой объем.
يبدأ اللاعبان من \(0\) نقطة، ومن يصل أولًا إلى \(100\) نقطة يفوز. حركة اللاعب الأول ثابتة تمامًا: في كل دور يرمي قطعة نقد عادلة واحدة، فيحصل على نقطة واحدة باحتمال \(1/2\) وعلى صفر باحتمال \(1/2\). أمّا اللاعب الثاني فيختار قبل كل دور عددًا صحيحًا موجبًا \(T\). بعد هذا الاختيار تكون فرصة النجاح \(2^{-T}\)، وإذا نجح يكسب \(2^{T-1}\) نقطة، وإذا فشل لا يكسب شيئًا. يبدأ اللاعب الأول، والمطلوب هو أكبر احتمال ممكن لفوز اللاعب الثاني إذا اختار \(T\) على النحو الأمثل في كل حالة.
الحلول لا تعتمد على محاكاة المباريات واحدةً واحدة، بل تعيد صياغة المسألة كمسألة تحكم مثلى منتهية على عدد النقاط المتبقية لكل لاعب حتى خط النهاية. وعند الهدف الحقيقي \(100\)، تكون قيمة الاحتمال الابتدائي المحسوبة هي \(0.83648556\) حتى ثماني منازل عشرية.
الفكرة الحاسمة هي عدم تتبع النقاط الحالية، بل تتبع عدد النقاط التي ما زال كل لاعب يحتاجها. عندها تتحول اللعبة إلى برمجة ديناميكية ذات علاقة Bellman صريحة.
لنرمز بـ \(F(a,b)\) إلى الاحتمال الأمثل لأن يفوز اللاعب الثاني في النهاية عندما يكون اللاعب الأول بحاجة إلى \(a\) نقطة إضافية، واللاعب الثاني بحاجة إلى \(b\) نقطة إضافية، ويكون الدور الحالي للاعب الثاني.
ونعرّف أيضًا \(G(a,b)\) بوصفه الاحتمال نفسه لكن في بداية دور اللاعب الأول مع القيم المتبقية نفسها. ولهذا فإن الحالة الابتدائية في المسألة الحقيقية هي \(G(100,100)\) لا \(F(100,100)\)، لأن اللاعب الأول هو من يبدأ.
شروط الحواف مباشرة: \(F(a,0)=1\) و\(G(a,0)=1\)، لأن اللاعب الثاني يكون قد وصل بالفعل إلى الهدف. وفي المقابل \(G(0,b)=0\)، لأن اللاعب الأول يكون قد حسم السباق قبل أن يحصل اللاعب الثاني على دور جديد.
اللاعب الأول يكسب نقطة واحدة باحتمال \(1/2\)، ولا يكسب شيئًا باحتمال \(1/2\). لذلك، لكل \(a\ge 1\) و\(b\ge 1\)،
$$G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}.$$
هذه الصيغة المتوسطة هي أول ثابت بنيوي في الحل: كلما مرّت اللعبة عبر دور اللاعب الأول، فإن قيمة الاستمرار لا تكون إلا متوسط حالتين متجاورتين من نوع \(F\).
إذا اختار اللاعب الثاني قيمة \(t\ge 1\)، فإن
$$q_t=2^{-t},\qquad d_t=2^{t-1}$$
يمثلان على الترتيب احتمال النجاح وعدد النقاط المكتسبة عند النجاح.
ولنعرّف قيمة فرع النجاح \(S_t(a,b)\) كما يلي: إذا كان \(d_t\ge b\) فإن \(S_t(a,b)=1\)، لأن اللاعب الثاني يفوز فورًا. أمّا إذا كان \(d_t<b\)، فإن \(S_t(a,b)=G(a,b-d_t)\)، لأن الدور ينتقل إلى اللاعب الأول بعد إضافة \(d_t\) نقطة.
وعند تثبيت \(t\)، تصبح معادلة Bellman ذات الخطوة الواحدة
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\,G(a,b).$$
النقطة الدقيقة موجودة في فرع الفشل: إذا أخفق اللاعب الثاني فلا تتغير النقاط، وتعود اللعبة إلى بداية دور اللاعب الأول في الحالة نفسها \((a,b)\). ولهذا يظهر \(F(a,b)\) على الطرفين عندما نفك \(G(a,b)\).
بالتعويض عن \(G(a,b)=\frac{F(a,b)+F(a-1,b)}{2}\) نحصل على
$$F(a,b)=q_t\,S_t(a,b)+(1-q_t)\frac{F(a,b)+F(a-1,b)}{2}.$$
وهذه معادلة خطية في \(F(a,b)\) يمكن حلّها مباشرة:
$$F(a,b)=\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.$$
وبما أن اللاعب الثاني يختار أفضل \(t\)، فإن العلاقة النهائية هي
$$\boxed{F(a,b)=\max_{t\ge 1}\frac{2q_t\,S_t(a,b)+(1-q_t)F(a-1,b)}{1+q_t}.}$$
هذه هي الصيغة المغلقة التي تنفذها جميع التطبيقات حرفيًا عند كل حالة \((a,b)\).
عند حالة ثابتة \((a,b)\)، لا تستعمل الصيغة إلا نوعين من القيم المحسوبة سابقًا: \(F(a-1,b)\) من الصف السابق، و\(S_t(a,b)\) التي تكون إما \(1\) مباشرة، أو قيمة من الشكل \(G(a,b-d_t)\) حيث \(b-d_t<b\).
ولهذا يكفي ملء الجدول سطرًا بعد سطر، وداخل كل سطر من القيم الأصغر لـ \(b\) إلى الأكبر. عندما يصل البرنامج إلى \((a,b)\)، تكون جميع الحالات التي يعتمد عليها قد حُسبت مسبقًا.
كما أن مجموعة الأفعال الممكنة منتهية فعليًا. فمتى صار \(d_t\ge b\)، فإن النجاح يعني فوزًا فوريًا على أي حال، وأي \(t\) أكبر من ذلك لا يفعل إلا تقليل احتمال النجاح \(q_t\). لذلك لا توجد إلا \(O(\log b)\) خيارات ذات معنى، ويكفي حد عالمي صغير بالنسبة إلى الهدف \(100\).
لننظر إلى الحالة \((a,b)=(1,2)\): يحتاج اللاعب الأول إلى نقطة واحدة إضافية، ويحتاج اللاعب الثاني إلى نقطتين إضافيتين، والدور الآن للاعب الثاني.
لنبدأ بالحالة الأبسط \((1,1)\). إذا اختار اللاعب الثاني \(t=1\)، فلدينا \(q_1=1/2\)، والنجاح ينهي المباراة فورًا. إذن
$$F(1,1)=\frac{2\cdot(1/2)\cdot 1+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{3},$$
ومن ثم
$$G(1,1)=\frac{F(1,1)+F(0,1)}{2}=\frac{2/3+0}{2}=\frac{1}{3}.$$
الآن نقارن بين قرارين في الحالة \((1,2)\).
إذا اختار \(t=1\)، فإن النجاح يمنحه نقطة واحدة فقط، وبالتالي يذهب فرع النجاح إلى \(G(1,1)=1/3\). ومع \(F(0,2)=0\) نحصل على
$$F_{t=1}(1,2)=\frac{2\cdot(1/2)\cdot(1/3)+(1-1/2)\cdot 0}{1+1/2}=\frac{2}{9}\approx 0.2222.$$
أمّا إذا اختار \(t=2\)، فإن احتمال النجاح ينخفض إلى \(q_2=1/4\)، لكن النجاح يعطي نقطتين كاملتين وينهي السباق مباشرة:
$$F_{t=2}(1,2)=\frac{2\cdot(1/4)\cdot 1+(1-1/4)\cdot 0}{1+1/4}=\frac{2}{5}=0.4.$$
إذن القرار الأفضل هنا هو الخيار الأكثر مخاطرة، أي \(t=2\). وهذا المثال الصغير يوضح بالضبط نوع المفاضلة بين صِغر احتمال النجاح وكِبر المكافأة الذي تحله البرمجة الديناميكية على كامل فضاء الحالات \(100\times 100\).
تحتفظ تطبيقات C++ وPython وJava بجدول ثنائي الأبعاد لقيم \(F(a,b)\). ويُهيَّأ العمود \(b=0\) بالقيمة 1، لأن هذه الحالات تمثل أن اللاعب الثاني قد فاز مسبقًا.
كما تُحضَّر الأفعال المرشحة مسبقًا: لكل \(t\) يتم اختباره، يُخزَّن كل من \(q_t=2^{-t}\) و\(d_t=2^{t-1}\). وبما أن مقدار النقاط المكتسبة يتضاعف كل مرة، فإن عدد الأفعال التي يجب فحصها عند الهدف 100 يبقى صغيرًا جدًا.
تمر الحلقة الرئيسية على الحالات بترتيب متزايد في \(a\) ثم \(b\). وعند كل خلية، تقرأ القيمة المحسوبة سابقًا \(F(a-1,b)\)، ثم تحسب قيمة النجاح \(S_t(a,b)\) لكل \(t\) مسموح، وتضع هذه الكميات في الصيغة المغلقة، ثم تحتفظ بأكبر قيمة.
يحفظ تنفيذ C++ كذلك الاختيار الأمثل لـ \(t\) في كل حالة. أمّا تنفيذا Python وJava فيحتفظان فقط بجدول الاحتمالات، لأن النتيجة النهائية لا تحتاج إلا إلى القيمة المثلى نفسها.
بعد اكتمال الجدول، تُستخرج الإجابة المطلوبة بتطبيق انتقال أخير خاص بدور اللاعب الأول:
$$G(100,100)=\frac{F(100,100)+F(99,100)}{2}.$$
ويحتوي برنامج C++ أيضًا على مدقّق مستقل يعتمد على تكرار القيم وفق Bellman لأهداف أصغر، ويتحقق من أن نسخته متعددة الخيوط تعطي النتيجة نفسها التي تعطيها النسخة أحادية الخيط. هذه الاختبارات ليست جزءًا من جوهر الخوارزمية، لكنها تؤكد أن تطبيق العلاقة المغلقة صحيح.
إذا كان الهدف العام هو \(N\)، فهناك \(N^2\) حالة من الشكل \((a,b)\). وفي كل حالة لا نختبر إلا \(L\) أفعال مرشحة، حيث \(L=O(\log N)\) لأن المكاسب الممكنة هي قوى للعدد 2. لذلك يكون الزمن الكلي \(O(N^2L)=O(N^2\log N)\).
أما الذاكرة فهي \(O(N^2)\) من أجل جدول الاحتمالات. ويضيف أحد التطبيقات جدول سياسة مساعدًا وروتين تحقق، لكن المحلّل الأساسي نفسه يبقى برمجة ديناميكية عادية بمساحة \(O(N^2)\). وبالنسبة إلى إدخال المسألة الفعلي \(N=100\)، فإن هذا الحجم صغير جدًا.