In this variant of Shut the Box, the cards are labeled \(1\) through \(12\). A roll of two fair six-sided dice produces an ordered outcome \(o=(x,y)\). After seeing that outcome, we may flip card \(x\), card \(y\), or card \(x+y\). Starting from the initial configuration and aiming for the state in which all twelve target bits are set, we want the strategy that minimizes the expected number of rolls.
The full game is small enough for exact dynamic programming but too large for hand analysis: there are \(2^{12}=4096\) states, \(36\) ordered dice outcomes, and a decision to make after every observed roll.
The problem is a finite Markov decision process with one absorbing goal state. The correct value function is the optimal expected number of remaining rolls from each state.
Represent the current configuration by a 12-bit mask \(s\in\{0,\dots,2^{12}-1\}\). Bit \(a-1\) records the status of card \(a\). The implementations use
$$s_0=0,\qquad s^\star=2^{12}-1$$
for the initial and target states. The exact interpretation of a bit as “open” or “closed” is irrelevant mathematically; what matters is that \(s_0\) is the start and \(s^\star\) is the absorbing goal.
For an observed dice result \(o=(x,y)\), the admissible toggle choices are
$$A(o)=\{x,\ y,\ x+y\}\subseteq \{1,\dots,12\}.$$
Choosing card \(a\in A(o)\) flips exactly one bit, so the successor state is
$$T(s,a)=s\oplus 2^{a-1}.$$
Every ordered outcome has probability
$$p(o)=\frac{1}{36}.$$
If \(x=y\), then the list \(x,y,x+y\) contains a repeated move. That causes no mathematical issue, because repeated candidates do not change the minimum over successor values.
Let \(V(s)\) be the optimal expected number of additional rolls needed to reach \(s^\star\). Then
$$V(s^\star)=0.$$
For every nonterminal state, the player first observes the dice outcome and only then chooses the best toggle. Therefore the minimization is inside the expectation:
$$V(s)=1+\sum_{o} p(o)\min_{a\in A(o)} V\bigl(T(s,a)\bigr),\qquad s\ne s^\star.$$
This is the key equation of the whole problem. A common mistake would be to choose one action before the roll; that would place the minimum outside the sum and would describe a different game.
A deterministic policy \(\pi\) assigns one allowed toggle to every pair \((s,o)\):
$$\pi(s,o)\in A(o).$$
Once \(\pi\) is fixed, its value function satisfies
$$V_{\pi}(s^\star)=0,$$
$$V_{\pi}(s)=1+\sum_{o} p(o)\,V_{\pi}\bigl(T(s,\pi(s,o))\bigr).$$
The implementations do not solve this linear system explicitly. Instead they repeatedly apply the fixed-policy update in place until the maximum change becomes tiny. Numerically, that is a relaxation scheme for the policy-specific Bellman equations.
After evaluating the current policy, each state-outcome pair is improved greedily by choosing the successor with the smallest estimated remaining cost:
$$\pi_{\text{new}}(s,o)\in \arg\min_{a\in A(o)} V\bigl(T(s,a)\bigr).$$
If no pair \((s,o)\) changes, the policy is already optimal for this finite state space, so the corresponding value function is the desired one. The programs then run one more high-precision evaluation pass to sharpen the final value \(V(s_0)\).
Before solving the 12-card game, the C++, Python, and Java implementations validate the method on a smaller model with 4 cards and coin outcomes \(x,y\in\{1,2\}\), each with probability \(1/4\). Starting from the empty state \(\varnothing\), the four ordered outcomes are \((1,1)\), \((1,2)\), \((2,1)\), and \((2,2)\).
From \(\varnothing\), the Bellman equation is
$$\begin{aligned} V(\varnothing)=1 &+\frac14 \min\bigl(V(\{1\}),V(\{2\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{2\}),V(\{4\})\bigr). \end{aligned}$$
This compactly shows the whole logic: every observed outcome contributes its own best successor, and only then are those contributions averaged. Solving all \(2^4=16\) states gives
$$V(\varnothing)=5.673651\ldots$$
which is exactly the numerical checkpoint used by the implementation before the full 12-card solve.
The C++, Python, and Java implementations all follow the same policy-iteration strategy. They enumerate all ordered outcomes, precompute the three candidate toggles for every state-outcome pair, and store a value array over all \(4096\) states.
Policy evaluation repeatedly sweeps through the nonterminal states and replaces the current value by
$$1+\sum_o p(o)\,V\bigl(T(s,\pi(s,o))\bigr).$$
Policy improvement then checks the three possible successors for each \((s,o)\) and keeps the one with the smallest current value estimate. The outer loop alternates these two phases until no decision changes. After that, a longer final evaluation with a tighter tolerance produces a stable six-decimal answer from the initial state.
The Java program mirrors the C++ numerical logic directly. The Python entry point returns the same result by invoking the same compiled solver, so the mathematical method remains identical across all three language versions.
Let \(S=2^{12}=4096\), let \(O=36\) be the number of ordered dice outcomes, and let \(A=3\) be the maximum number of candidate toggles. One policy-evaluation sweep costs \(O(SO)\), because the current action is already fixed for each state-outcome pair. One policy-improvement sweep costs \(O(SOA)\), because it compares up to three successors for each pair.
Memory usage is \(O(SO)\) for the policy table plus \(O(S)\) for the value array. With these constants, the method is comfortably small: the entire exact solve fits into a modest dynamic-programming loop instead of needing any large symbolic machinery.
In dieser Variante von Shut the Box gibt es Karten mit den Nummern \(1\) bis \(12\). Ein Wurf zweier fairer sechsseitiger Würfel erzeugt ein geordnetes Ergebnis \(o=(x,y)\). Nachdem dieses Ergebnis bekannt ist, darf man Karte \(x\), Karte \(y\) oder Karte \(x+y\) umklappen. Gesucht ist die Strategie, die vom Anfangszustand aus die erwartete Wurfzahl bis zum Zielzustand mit allen gesetzten Zielbits minimiert.
Die vollständige Zustandsmenge ist noch klein genug für exakte dynamische Programmierung, aber bereits zu groß für eine naive Fallunterscheidung: Es gibt \(2^{12}=4096\) Zustände, \(36\) geordnete Würfelergebnisse und nach jedem beobachteten Ergebnis eine eigene Entscheidung.
Das Problem ist ein endliches Markov-Entscheidungsproblem mit einem absorbierenden Zielzustand. Die richtige Größe ist also der optimale Erwartungswert der noch benötigten Würfe von jedem Zustand aus.
Die aktuelle Konfiguration wird als 12-Bit-Maske \(s\in\{0,\dots,2^{12}-1\}\) dargestellt. Bit \(a-1\) beschreibt den Status von Karte \(a\). Die Implementierungen verwenden
$$s_0=0,\qquad s^\star=2^{12}-1$$
als Start- bzw. Zielzustand. Ob man ein gesetztes Bit als „offen“ oder „geschlossen“ interpretiert, spielt mathematisch keine Rolle; wichtig ist nur, dass \(s_0\) der Anfang und \(s^\star\) das absorbierende Ziel ist.
Für ein beobachtetes Würfelergebnis \(o=(x,y)\) sind die erlaubten Umschaltungen
$$A(o)=\{x,\ y,\ x+y\}\subseteq \{1,\dots,12\}.$$
Wählt man Karte \(a\in A(o)\), dann kippt genau ein Bit, also lautet der Folgezustand
$$T(s,a)=s\oplus 2^{a-1}.$$
Jedes geordnete Ergebnis besitzt die Wahrscheinlichkeit
$$p(o)=\frac{1}{36}.$$
Falls \(x=y\) gilt, taucht derselbe Zug in der Liste mehrfach auf. Das ändert die Mathematik nicht, weil doppelte Kandidaten den Minimalwert über die Nachfolgezustände nicht beeinflussen.
Sei \(V(s)\) der optimale Erwartungswert der noch nötigen Würfe bis \(s^\star\). Dann gilt
$$V(s^\star)=0.$$
Für jeden nichtterminalen Zustand beobachtet man zuerst das Würfelergebnis und wählt erst danach den besten Zug. Darum steht das Minimum innerhalb des Erwartungswertes:
$$V(s)=1+\sum_{o} p(o)\min_{a\in A(o)} V\bigl(T(s,a)\bigr),\qquad s\ne s^\star.$$
Das ist die zentrale Gleichung des Problems. Würde man ein einziges \(a\) schon vor dem Wurf festlegen, läge das Minimum außerhalb der Summe und man hätte ein anderes Spiel modelliert.
Eine deterministische Politik \(\pi\) ordnet jedem Paar \((s,o)\) genau einen erlaubten Zug zu:
$$\pi(s,o)\in A(o).$$
Für festes \(\pi\) erfüllt die zugehörige Wertfunktion
$$V_{\pi}(s^\star)=0,$$
$$V_{\pi}(s)=1+\sum_{o} p(o)\,V_{\pi}\bigl(T(s,\pi(s,o))\bigr).$$
Die Implementierungen lösen dieses lineare Gleichungssystem nicht explizit. Stattdessen wird die feste Politik immer wieder in place relaxiert, bis die maximale Änderung verschwindend klein ist. Numerisch ist das genau eine iterative Auswertung der Bellman-Gleichungen für die aktuelle Politik.
Nach der Auswertung werden alle Zustand-Ergebnis-Paare greedy verbessert, indem man den Nachfolger mit dem kleinsten geschätzten Restwert wählt:
$$\pi_{\text{neu}}(s,o)\in \arg\min_{a\in A(o)} V\bigl(T(s,a)\bigr).$$
Wenn sich kein Paar \((s,o)\) mehr ändert, ist die Politik auf diesem endlichen Zustandsraum optimal. Danach folgt noch eine lange Endauswertung mit strengerer Toleranz, um den Startwert \(V(s_0)\) präzise zu stabilisieren.
Bevor das 12-Karten-Spiel gelöst wird, prüfen die C++-, Python- und Java-Implementierungen die Methode an einem kleineren Modell mit 4 Karten und Münzausgängen \(x,y\in\{1,2\}\), jeweils mit Wahrscheinlichkeit \(1/4\). Vom leeren Zustand \(\varnothing\) aus sind die vier geordneten Ergebnisse \((1,1)\), \((1,2)\), \((2,1)\) und \((2,2)\).
Für \(\varnothing\) lautet die Bellman-Gleichung
$$\begin{aligned} V(\varnothing)=1 &+\frac14 \min\bigl(V(\{1\}),V(\{2\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{2\}),V(\{4\})\bigr). \end{aligned}$$
Daran sieht man unmittelbar die gesamte Logik: Zu jedem beobachteten Ergebnis wird zunächst der beste Nachfolger gewählt, und erst danach werden die Beiträge gemittelt. Die Lösung aller \(2^4=16\) Zustände ergibt
$$V(\varnothing)=5.673651\ldots$$
genau den Kontrollwert, den die Implementierung vor dem vollen 12-Karten-Lauf überprüft.
Die C++-, Python- und Java-Implementierungen verwenden alle dieselbe Politikiterations-Idee. Sie enumerieren sämtliche geordneten Ergebnisse, berechnen für jedes Zustand-Ergebnis-Paar die drei möglichen Umschaltungen vor und halten ein Wertarray über alle \(4096\) Zustände.
Die Politikauswertung sweeped wiederholt über alle nichtterminalen Zustände und ersetzt den aktuellen Wert durch
$$1+\sum_o p(o)\,V\bigl(T(s,\pi(s,o))\bigr).$$
Die Politikverbesserung prüft anschließend für jedes \((s,o)\) die bis zu drei möglichen Nachfolger und behält den mit dem kleinsten aktuellen Schätzwert. Die äußere Schleife wechselt zwischen beiden Phasen, bis keine Entscheidung mehr geändert wird. Danach erzeugt eine längere Endauswertung mit strengerer Toleranz eine stabile Ausgabe auf sechs Nachkommastellen für den Startzustand.
Das Java-Programm spiegelt die numerische Logik der C++-Version direkt. Der Python-Einstieg liefert denselben Wert, indem er denselben kompilierten Löser verwendet; die mathematische Methode bleibt also in allen drei Sprachversionen identisch.
Sei \(S=2^{12}=4096\), \(O=36\) die Zahl geordneter Würfelergebnisse und \(A=3\) die maximale Zahl möglicher Umschaltungen. Ein Sweep zur Auswertung einer festen Politik kostet \(O(SO)\), weil die Aktion pro Zustand-Ergebnis-Paar bereits feststeht. Ein Sweep zur Politikverbesserung kostet \(O(SOA)\), weil für jedes Paar bis zu drei Nachfolger verglichen werden.
Der Speicherbedarf beträgt \(O(SO)\) für die Politikdaten plus \(O(S)\) für das Wertarray. Mit diesen Konstanten bleibt das Verfahren sehr kompakt: Das exakte Problem passt vollständig in eine kleine dynamische Programmierung und benötigt keine schwere symbolische Algebra.
Bu Shut the Box varyantında kartlar \(1\) ile \(12\) arasındadır. Adil iki altı yüzlü zar atıldığında sıralı bir sonuç \(o=(x,y)\) elde edilir. Bu sonucu gördükten sonra \(x\), \(y\) veya \(x+y\) numaralı kart çevrilebilir. Başlangıç durumundan tüm hedef bitlerinin \(1\) olduğu duruma ulaşmak için beklenen atış sayısını en aza indiren strateji aranır.
Tam durum uzayı kesin dinamik programlama için yeterince küçüktür, ama elle çözüm için fazla büyüktür: \(2^{12}=4096\) durum, \(36\) sıralı zar sonucu ve her gözlenen sonuçtan sonra verilmesi gereken bir karar vardır.
Problem, tek bir soğurucu hedef durumu olan sonlu bir Markov karar sürecidir. Dolayısıyla doğru büyüklük, her durumdan hedefe ulaşmak için kalan optimal beklenen atış sayısıdır.
Mevcut yapılandırmayı \(s\in\{0,\dots,2^{12}-1\}\) biçiminde 12 bitlik bir maske ile gösterelim. \(a-1\). bit, \(a\) numaralı kartın durumunu tutar. Uygulamalar
$$s_0=0,\qquad s^\star=2^{12}-1$$
değerlerini başlangıç ve hedef olarak kullanır. Bir bitin “açık” mı yoksa “kapalı” mı kabul edildiği matematik açısından önemli değildir; önemli olan \(s_0\)'ın başlangıç, \(s^\star\)'ın ise soğurucu hedef olmasıdır.
Gözlenen zar sonucu \(o=(x,y)\) için izinli çevirmeler
$$A(o)=\{x,\ y,\ x+y\}\subseteq \{1,\dots,12\}$$
kümesidir. \(a\in A(o)\) kartı seçilirse tam olarak bir bit çevrilir ve yeni durum
$$T(s,a)=s\oplus 2^{a-1}$$
olur. Her sıralı sonucun olasılığı
$$p(o)=\frac{1}{36}$$
şeklindedir. Eğer \(x=y\) ise listede aynı hamle iki kez görünür. Bu, minimumu değiştirmediği için matematiksel olarak sorun yaratmaz.
\(V(s)\), \(s^\star\)'a ulaşmak için gereken ek atış sayısının optimal beklentisi olsun. O zaman
$$V(s^\star)=0$$
vardır. Terminal olmayan her durumda oyuncu önce zar sonucunu görür, sonra en iyi çevirmeyi seçer. Bu yüzden minimizasyon beklentinin içindedir:
$$V(s)=1+\sum_{o} p(o)\min_{a\in A(o)} V\bigl(T(s,a)\bigr),\qquad s\ne s^\star.$$
Problemin temel denklemi budur. Eğer tek bir hamleyi sonucu görmeden seçiyor olsaydık minimum toplamın dışına çıkardı ve bambaşka bir oyun modellemiş olurduk.
Deterministik bir politika \(\pi\), her \((s,o)\) çifti için bir izinli çevirmeyi seçer:
$$\pi(s,o)\in A(o).$$
\(\pi\) sabitlenince karşılık gelen değer fonksiyonu
$$V_{\pi}(s^\star)=0,$$
$$V_{\pi}(s)=1+\sum_{o} p(o)\,V_{\pi}\bigl(T(s,\pi(s,o))\bigr)$$
eşitliklerini sağlar. Uygulamalar bu lineer sistemi doğrudan çözmez. Bunun yerine sabit politika güncellemesini yerinde tekrarlar ve en büyük değişim çok küçülene kadar gevşetme uygular. Sayısal açıdan bu, mevcut politika için Bellman denklemlerinin iteratif çözümüdür.
Politika değerlendirildikten sonra her durum-sonuç çifti, tahmini kalan maliyeti en küçük yapan ardıl durum seçilerek açgözlü biçimde iyileştirilir:
$$\pi_{\text{yeni}}(s,o)\in \arg\min_{a\in A(o)} V\bigl(T(s,a)\bigr).$$
Hiçbir \((s,o)\) çifti değişmiyorsa politika artık bu sonlu durum uzayı için optimaldir. Programlar daha sonra başlangıç değeri \(V(s_0)\)'ı keskinleştirmek için daha sıkı toleranslı son bir uzun değerlendirme yapar.
12 kartlık oyunu çözmeden önce C++, Python ve Java implementasyonları yöntemi 4 kartlı daha küçük bir modelde doğrular. Burada \(x,y\in\{1,2\}\) para benzeri çıktılardır ve her biri \(1/4\) olasılıklıdır. Boş durum \(\varnothing\) için dört sıralı sonuç \((1,1)\), \((1,2)\), \((2,1)\) ve \((2,2)\)'dir.
\(\varnothing\) durumundan Bellman denklemi
$$\begin{aligned} V(\varnothing)=1 &+\frac14 \min\bigl(V(\{1\}),V(\{2\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{2\}),V(\{4\})\bigr) \end{aligned}$$
olur. Burada tüm mantık açıkça görünür: Her gözlenen sonucun kendi en iyi ardılı seçilir, sonra bu katkılar ortalanır. Tüm \(2^4=16\) durum çözüldüğünde
$$V(\varnothing)=5.673651\ldots$$
elde edilir; bu da tam implementasyonun önce doğruladığı sayısal kontrol değeridir.
C++, Python ve Java implementasyonlarının tümü aynı politika iterasyonu fikrini kullanır. Bütün sıralı sonuçlar üretilir, her durum-sonuç çifti için üç aday çevrme önceden hazırlanır ve tüm \(4096\) durum üzerinde bir değer dizisi tutulur.
Politika değerlendirmesi, terminal olmayan durumlar üzerinde tekrar tekrar gezip mevcut değeri
$$1+\sum_o p(o)\,V\bigl(T(s,\pi(s,o))\bigr).$$
ifadesiyle günceller. Politika iyileştirmesi ise her \((s,o)\) için en fazla üç ardıl durumu kontrol eder ve mevcut tahmin altında en küçük değeri veren seçimi korur. Dış döngü bu iki aşamayı, artık hiçbir karar değişmeyene kadar ardışık olarak uygular. Sonunda daha uzun ve daha sıkı toleranslı bir değerlendirme, başlangıç durumundan altı ondalıklı kararlı sonucu üretir.
Java programı C++ sayısal mantığını doğrudan yansıtır. Python girişi ise aynı sonucu aynı derlenmiş çözücüyü çağırarak döndürür; böylece üç dil sürümünde de matematiksel yöntem aynıdır.
\(S=2^{12}=4096\), \(O=36\) sıralı zar sonucu ve \(A=3\) en fazla aday çevrme olsun. Sabit bir politikanın tek değerlendirme taraması \(O(SO)\) maliyetlidir; çünkü her durum-sonuç çifti için seçilmiş hamle zaten bellidir. Tek politika iyileştirme taraması ise her çiftte en fazla üç ardılı karşılaştırdığı için \(O(SOA)\) maliyetlidir.
Bellek kullanımı politika tablosu için \(O(SO)\), değer dizisi için \(O(S)\)'dir. Bu sabitlerle yöntem çok rahattır: Tam çözüm büyük sembolik araçlara ihtiyaç duymadan küçük bir dinamik programlama döngüsüne sığar.
En esta variante de Shut the Box, las cartas están numeradas del \(1\) al \(12\). Al lanzar dos dados justos de seis caras se obtiene un resultado ordenado \(o=(x,y)\). Después de observarlo, se puede voltear la carta \(x\), la carta \(y\) o la carta \(x+y\). Partiendo del estado inicial y buscando el estado objetivo en el que los doce bits objetivo están activados, se desea la estrategia que minimiza el número esperado de tiradas.
El espacio completo es suficientemente pequeño para un tratamiento exacto con programación dinámica, pero demasiado grande para resolverlo a mano: hay \(2^{12}=4096\) estados, \(36\) resultados ordenados y una decisión separada después de cada tirada observada.
El problema es un proceso de decisión de Markov finito con un único estado objetivo absorbente. Por tanto, la cantidad central es el valor esperado óptimo del número de tiradas restantes desde cada estado.
Representamos la configuración actual mediante una máscara de 12 bits \(s\in\{0,\dots,2^{12}-1\}\). El bit \(a-1\) describe el estado de la carta \(a\). Las implementaciones usan
$$s_0=0,\qquad s^\star=2^{12}-1$$
como estado inicial y objetivo. Desde el punto de vista matemático, no importa si un bit igual a \(1\) significa “abierta” o “cerrada”; lo importante es que \(s_0\) sea el inicio y \(s^\star\) el objetivo absorbente.
Para un resultado observado \(o=(x,y)\), las elecciones permitidas son
$$A(o)=\{x,\ y,\ x+y\}\subseteq \{1,\dots,12\}.$$
Si se elige la carta \(a\in A(o)\), se invierte exactamente un bit, así que el estado siguiente es
$$T(s,a)=s\oplus 2^{a-1}.$$
Cada resultado ordenado tiene probabilidad
$$p(o)=\frac{1}{36}.$$
Cuando \(x=y\), la lista \(x,y,x+y\) contiene un movimiento repetido. Eso no cambia nada en el análisis, porque repetir un candidato no altera el mínimo entre valores sucesores.
Sea \(V(s)\) el número esperado óptimo de tiradas adicionales necesarias para llegar a \(s^\star\). Entonces
$$V(s^\star)=0.$$
En todo estado no terminal, el jugador observa primero el resultado del dado y solo después elige la mejor inversión. Por eso el mínimo aparece dentro de la esperanza:
$$V(s)=1+\sum_{o} p(o)\min_{a\in A(o)} V\bigl(T(s,a)\bigr),\qquad s\ne s^\star.$$
Esta es la ecuación central del problema. Si el movimiento tuviera que fijarse antes de lanzar, el mínimo quedaría fuera de la suma y se modelaría un juego distinto.
Una política determinista \(\pi\) asigna una inversión permitida a cada par \((s,o)\):
$$\pi(s,o)\in A(o).$$
Una vez fijada \(\pi\), su función de valor cumple
$$V_{\pi}(s^\star)=0,$$
$$V_{\pi}(s)=1+\sum_{o} p(o)\,V_{\pi}\bigl(T(s,\pi(s,o))\bigr).$$
Las implementaciones no resuelven este sistema lineal de forma cerrada. En su lugar, aplican repetidamente la actualización de política fija en el mismo arreglo hasta que el cambio máximo sea minúsculo. Numéricamente, eso es una relajación iterativa de las ecuaciones de Bellman para la política actual.
Después de evaluar la política, cada par estado-resultado se mejora de manera voraz eligiendo el sucesor con menor coste restante estimado:
$$\pi_{\text{nueva}}(s,o)\in \arg\min_{a\in A(o)} V\bigl(T(s,a)\bigr).$$
Si ningún par \((s,o)\) cambia, la política ya es óptima en este espacio finito. A continuación, los programas ejecutan una evaluación final más larga y con tolerancia más estricta para afinar el valor inicial \(V(s_0)\).
Antes de resolver el juego de 12 cartas, las implementaciones en C++, Python y Java validan el método con un modelo más pequeño de 4 cartas y resultados tipo moneda \(x,y\in\{1,2\}\), cada uno con probabilidad \(1/4\). Desde el estado vacío \(\varnothing\), los cuatro resultados ordenados son \((1,1)\), \((1,2)\), \((2,1)\) y \((2,2)\).
La ecuación de Bellman para \(\varnothing\) es
$$\begin{aligned} V(\varnothing)=1 &+\frac14 \min\bigl(V(\{1\}),V(\{2\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{2\}),V(\{4\})\bigr). \end{aligned}$$
Este ejemplo deja clara toda la estructura: cada resultado observado aporta su mejor sucesor y solo después se promedian esas contribuciones. Al resolver los \(2^4=16\) estados se obtiene
$$V(\varnothing)=5.673651\ldots$$
que es exactamente el valor de verificación usado por la implementación antes de atacar el caso de 12 cartas.
Las implementaciones en C++, Python y Java siguen la misma estrategia de iteración de política. Enumeran todos los resultados ordenados, precalculan las tres inversiones candidatas para cada par estado-resultado y mantienen un arreglo de valores sobre los \(4096\) estados.
La evaluación de la política recorre repetidamente los estados no terminales y sustituye el valor actual por
$$1+\sum_o p(o)\,V\bigl(T(s,\pi(s,o))\bigr).$$
La mejora de la política examina después los hasta tres sucesores posibles de cada \((s,o)\) y conserva el que tiene la menor estimación actual. El lazo externo alterna ambas fases hasta que ninguna decisión cambia. Después, una evaluación final más larga y más estricta produce una salida estable con seis decimales desde el estado inicial.
El programa en Java refleja directamente la lógica numérica de C++. La entrada en Python devuelve el mismo resultado reutilizando el mismo solucionador compilado, de modo que el método matemático es idéntico en las tres versiones.
Sea \(S=2^{12}=4096\), sea \(O=36\) el número de resultados ordenados y sea \(A=3\) el número máximo de inversiones candidatas. Un barrido de evaluación de política cuesta \(O(SO)\), porque la acción ya está fijada en cada par estado-resultado. Un barrido de mejora cuesta \(O(SOA)\), porque compara hasta tres sucesores por par.
La memoria utilizada es \(O(SO)\) para la tabla de política y \(O(S)\) para el vector de valores. Con estas constantes, el método es muy manejable: la resolución exacta cabe en un ciclo pequeño de programación dinámica sin recurrir a maquinaria simbólica pesada.
在这个 Shut the Box 变体中，牌面编号为 \(1\) 到 \(12\)。掷两枚公平六面骰后，会得到一个有序结果 \(o=(x,y)\)。看到结果之后，可以翻转编号为 \(x\)、\(y\) 或 \(x+y\) 的那张牌。我们从初始状态出发，目标是到达十二个目标位全部为 \(1\) 的状态，并寻找使期望掷骰次数最小的策略。
整个问题适合用精确动态规划处理，但又已经大到不适合手工枚举：状态共有 \(2^{12}=4096\) 个，有序骰子结果共有 \(36\) 个，而且每一次观察到结果之后都要重新作出决策。
这个问题可以建模为一个有限的马尔可夫决策过程，其中目标状态是唯一的吸收状态。核心量是：从每个状态出发，到达目标还需要多少次掷骰，其最优期望是多少。
把当前局面表示成一个 12 位掩码 \(s\in\{0,\dots,2^{12}-1\}\)。第 \(a-1\) 位表示编号为 \(a\) 的牌当前处于哪一种状态。实现中使用
$$s_0=0,\qquad s^\star=2^{12}-1$$
分别表示初始状态和目标状态。从数学角度看，位值 \(1\) 究竟解释为“打开”还是“关闭”并不重要；重要的是 \(s_0\) 是起点，而 \(s^\star\) 是吸收终点。
对于观察到的结果 \(o=(x,y)\)，允许的翻转选择是
$$A(o)=\{x,\ y,\ x+y\}\subseteq \{1,\dots,12\}.$$
如果选择翻转 \(a\in A(o)\)，就只会改变一个二进制位，因此后继状态是
$$T(s,a)=s\oplus 2^{a-1}.$$
每一个有序结果的概率都是
$$p(o)=\frac{1}{36}.$$
当 \(x=y\) 时，列表 \(x,y,x+y\) 中会出现重复动作。不过这不会影响数学表达，因为在后继值中取最小值时，重复候选不会改变结果。
设 \(V(s)\) 为从状态 \(s\) 出发到达 \(s^\star\) 所需额外掷骰次数的最优期望，则
$$V(s^\star)=0.$$
对任何非终止状态，玩家都是先看到骰子结果，再决定翻哪一张牌，所以最小化必须放在期望内部：
$$V(s)=1+\sum_{o} p(o)\min_{a\in A(o)} V\bigl(T(s,a)\bigr),\qquad s\ne s^\star.$$
这就是整个题目的关键方程。一个常见误解是把动作当成掷骰之前就要固定的选择；如果那样做，最小值会跑到求和号外面，描述的就不是这里的游戏了。
设 \(\pi\) 是一条确定性策略，它为每个 \((s,o)\) 二元组指定一个允许动作：
$$\pi(s,o)\in A(o).$$
一旦 \(\pi\) 固定下来，对应的价值函数满足
$$V_{\pi}(s^\star)=0,$$
$$V_{\pi}(s)=1+\sum_{o} p(o)\,V_{\pi}\bigl(T(s,\pi(s,o))\bigr).$$
实现并没有显式求解这组线性方程，而是反复对固定策略的更新式做原地松弛，直到最大改变量足够小为止。从数值角度看，这就是对当前策略 Bellman 方程的迭代求解。
在得到当前策略的价值估计后，对每个状态-结果对都进行贪心改进，选择剩余代价估计最小的后继：
$$\pi_{\text{new}}(s,o)\in \arg\min_{a\in A(o)} V\bigl(T(s,a)\bigr).$$
如果没有任何 \((s,o)\) 发生变化，那么在这个有限状态空间上，该策略已经是最优策略。随后程序会再做一次更严格、更长的最终评估，以便把初始状态 \(V(s_0)\) 的数值稳定到所需精度。
在求解 12 张牌的完整问题之前，C++、Python 和 Java 实现都会先在一个更小的 4 张牌模型上验证方法。此时令 \(x,y\in\{1,2\}\)，每个有序结果的概率都是 \(1/4\)。从空状态 \(\varnothing\) 出发，四个结果分别是 \((1,1)\)、\((1,2)\)、\((2,1)\) 和 \((2,2)\)。
\(\varnothing\) 的 Bellman 方程写成
$$\begin{aligned} V(\varnothing)=1 &+\frac14 \min\bigl(V(\{1\}),V(\{2\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{2\}),V(\{4\})\bigr). \end{aligned}$$
这个例子完整展示了题目的结构：每一种已观察到的结果先各自选出最优后继，然后再把这些最优后继的价值做平均。把全部 \(2^4=16\) 个状态都解出来后，可得到
$$V(\varnothing)=5.673651\ldots$$
这正是实现中先验证的数值检查点，用来确认状态编码、转移规则和策略迭代都没有写错。
C++、Python 和 Java 实现都遵循同一套策略迭代思路。它们先枚举全部有序结果，再为每个状态-结果对预先列出三个候选翻转，并维护一个覆盖全部 \(4096\) 个状态的价值数组。
策略评估阶段会反复扫描所有非终止状态，把当前值更新为
$$1+\sum_o p(o)\,V\bigl(T(s,\pi(s,o))\bigr).$$
策略改进阶段随后检查每个 \((s,o)\) 的三个可能后继，保留当前估计值最小的那个。外层循环就在“评估当前策略”和“按后继值改进策略”之间交替，直到所有决策都稳定下来。最后再做一次容差更严格、迭代更长的评估，输出从初始状态出发的稳定六位小数答案。
Java 版本直接复现了 C++ 的数值逻辑。Python 入口则复用了同一个已编译求解器来返回相同结果，因此三种语言版本在数学方法上完全一致。
记 \(S=2^{12}=4096\)，记 \(O=36\) 为有序骰子结果个数，记 \(A=3\) 为每次结果对应的最大候选动作数。一次固定策略评估扫描的复杂度是 \(O(SO)\)，因为每个状态-结果对的动作已经固定。一次策略改进扫描的复杂度是 \(O(SOA)\)，因为它要比较每对最多三个后继。
空间复杂度为：策略表 \(O(SO)\)，价值数组 \(O(S)\)。在这里这些常数都很小，因此完整精确求解只需要一个规模适中的动态规划循环，而不需要大型符号运算工具。
В этой версии Shut the Box есть карты с номерами от \(1\) до \(12\). Бросок двух честных шестигранных кубиков дает упорядоченный результат \(o=(x,y)\). После того как результат известен, можно перевернуть карту \(x\), карту \(y\) или карту \(x+y\). Нужно найти стратегию, которая минимизирует математическое ожидание числа бросков от начальной конфигурации до состояния, где установлены все двенадцать целевых битов.
Полное пространство еще достаточно мало для точного динамического программирования, но уже слишком велико для ручного перебора: имеется \(2^{12}=4096\) состояний, \(36\) упорядоченных исходов и отдельное решение после каждого наблюдаемого броска.
Это конечный процесс принятия решений Маркова с одним поглощающим целевым состоянием. Поэтому главная величина здесь - оптимальное ожидаемое число оставшихся бросков из каждого состояния.
Текущую конфигурацию представим 12-битовой маской \(s\in\{0,\dots,2^{12}-1\}\). Бит \(a-1\) хранит состояние карты \(a\). Реализации используют
$$s_0=0,\qquad s^\star=2^{12}-1$$
как начальное и целевое состояния. С математической точки зрения неважно, трактуется ли бит \(1\) как «открыта» или «закрыта»; важно лишь, что \(s_0\) - старт, а \(s^\star\) - поглощающее завершение.
Для наблюдаемого результата \(o=(x,y)\) допустимые перевороты таковы:
$$A(o)=\{x,\ y,\ x+y\}\subseteq \{1,\dots,12\}.$$
Если выбрать карту \(a\in A(o)\), изменится ровно один бит, поэтому следующее состояние равно
$$T(s,a)=s\oplus 2^{a-1}.$$
Вероятность каждого упорядоченного исхода равна
$$p(o)=\frac{1}{36}.$$
Когда \(x=y\), в списке \(x,y,x+y\) появляется повторяющееся действие. Это ничего не меняет, потому что дублирование кандидата не влияет на минимум по значениям последующих состояний.
Пусть \(V(s)\) - оптимальное математическое ожидание числа дополнительных бросков до достижения \(s^\star\). Тогда
$$V(s^\star)=0.$$
В любом нетерминальном состоянии игрок сначала видит результат броска и только потом выбирает лучший переворот. Поэтому минимум стоит внутри математического ожидания:
$$V(s)=1+\sum_{o} p(o)\min_{a\in A(o)} V\bigl(T(s,a)\bigr),\qquad s\ne s^\star.$$
Это центральное уравнение задачи. Если бы действие нужно было фиксировать еще до броска, минимум стоял бы вне суммы, и речь шла бы уже о другой модели.
Детерминированная политика \(\pi\) сопоставляет каждой паре \((s,o)\) одно допустимое действие:
$$\pi(s,o)\in A(o).$$
После фиксации \(\pi\) ее функция ценности удовлетворяет уравнениям
$$V_{\pi}(s^\star)=0,$$
$$V_{\pi}(s)=1+\sum_{o} p(o)\,V_{\pi}\bigl(T(s,\pi(s,o))\bigr).$$
Реализации не решают эту линейную систему напрямую. Вместо этого они многократно выполняют in-place релаксацию для фиксированной политики, пока максимальное изменение не станет очень малым. Численно это и есть итеративная оценка уравнений Беллмана для текущей политики.
После оценки текущей политики каждая пара состояние-исход улучшается жадно: выбирается тот переход, у которого минимальна оценка оставшейся стоимости:
$$\pi_{\text{new}}(s,o)\in \arg\min_{a\in A(o)} V\bigl(T(s,a)\bigr).$$
Если ни одна пара \((s,o)\) больше не меняется, политика уже оптимальна для данного конечного пространства. После этого программы делают еще один длинный проход оценки с более жесткой точностью, чтобы стабилизировать итоговое значение \(V(s_0)\).
Прежде чем решать задачу на 12 картах, реализации на C++, Python и Java проверяют метод на меньшей модели с 4 картами и монетоподобными исходами \(x,y\in\{1,2\}\), каждый с вероятностью \(1/4\). Из пустого состояния \(\varnothing\) возможны четыре упорядоченных результата: \((1,1)\), \((1,2)\), \((2,1)\) и \((2,2)\).
Уравнение Беллмана для \(\varnothing\) имеет вид
$$\begin{aligned} V(\varnothing)=1 &+\frac14 \min\bigl(V(\{1\}),V(\{2\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{2\}),V(\{4\})\bigr). \end{aligned}$$
Здесь отчетливо видна вся структура задачи: для каждого наблюдаемого исхода сначала выбирается лучший следующий шаг, и только потом усредняются полученные вклады. Решение всех \(2^4=16\) состояний дает
$$V(\varnothing)=5.673651\ldots$$
ровно тот контрольный результат, который реализация проверяет перед полным запуском на 12 картах.
Реализации на C++, Python и Java используют одну и ту же схему итерации политики. Они перечисляют все упорядоченные исходы, заранее строят три кандидатных переворота для каждой пары состояние-исход и хранят массив значений на всех \(4096\) состояниях.
На этапе оценки политики программа многократно проходит по нетерминальным состояниям и обновляет текущее значение по формуле
$$1+\sum_o p(o)\,V\bigl(T(s,\pi(s,o))\bigr).$$
Затем этап улучшения политики проверяет до трех возможных successors для каждой пары \((s,o)\) и оставляет тот, у которого наименьшая текущая оценка. Внешний цикл чередует эти две фазы, пока ни одно решение не меняется. После этого выполняется более длинная финальная оценка с более строгим порогом, которая дает стабильный ответ с шестью знаками после запятой для начального состояния.
Версия на Java напрямую повторяет численную логику C++. Точка входа на Python возвращает тот же результат, переиспользуя тот же скомпилированный решатель, так что математический метод совпадает во всех трех языках.
Пусть \(S=2^{12}=4096\), \(O=36\) - число упорядоченных исходов, а \(A=3\) - максимальное число кандидатных действий. Один проход оценки фиксированной политики требует \(O(SO)\), потому что действие для каждой пары уже выбрано. Один проход улучшения требует \(O(SOA)\), так как нужно сравнить до трех successors для каждой пары.
Память составляет \(O(SO)\) для таблицы политики и \(O(S)\) для массива значений. При таких константах точное решение получается очень компактным: достаточно умеренного цикла динамического программирования без тяжелых символьных методов.
في هذه النسخة من Shut the Box توجد بطاقات مرقمة من \(1\) إلى \(12\). عند رمي زهرين عادلين سداسيي الأوجه نحصل على ناتج مرتب \(o=(x,y)\). بعد رؤية هذا الناتج يمكن قلب البطاقة \(x\) أو البطاقة \(y\) أو البطاقة \(x+y\). ننطلق من الحالة الابتدائية ونريد الوصول إلى الحالة التي تكون فيها جميع البتات الهدف الاثنتا عشرة مساوية لـ \(1\)، مع اختيار الإستراتيجية التي تصغر القيمة المتوقعة لعدد الرميات.
فضاء الحالات كله صغير بما يكفي لحل دقيق باستخدام البرمجة الديناميكية، لكنه أكبر من أن يعالج يدويا بسهولة: لدينا \(2^{12}=4096\) حالة، و\(36\) ناتجا مرتبا للزهر، وقرار منفصل بعد كل نتيجة مشاهدة.
يمكن نمذجة المسألة على أنها عملية قرار ماركوفية منتهية لها حالة هدف ماصة واحدة. لذلك فإن الكمية الأساسية هي القيمة المتوقعة المثلى لعدد الرميات المتبقية انطلاقا من كل حالة.
نمثل الوضع الحالي بقناع من 12 بتا \(s\in\{0,\dots,2^{12}-1\}\). البت رقم \(a-1\) يصف حالة البطاقة \(a\). تستخدم التنفيذات القيمتين
$$s_0=0,\qquad s^\star=2^{12}-1$$
للحالة الابتدائية والحالة الهدف. رياضيا لا يهم إن كان البت \(1\) يعني “مفتوحة” أو “مغلقة”; المهم فقط أن \(s_0\) هو البداية وأن \(s^\star\) هو الهدف الماص.
إذا كانت النتيجة المشاهدة هي \(o=(x,y)\)، فإن الاختيارات المسموح بها هي
$$A(o)=\{x,\ y,\ x+y\}\subseteq \{1,\dots,12\}.$$
وعند اختيار البطاقة \(a\in A(o)\) ينقلب بت واحد فقط، ولذلك تكون الحالة التالية
$$T(s,a)=s\oplus 2^{a-1}.$$
واحتمال كل ناتج مرتب هو
$$p(o)=\frac{1}{36}.$$
إذا كان \(x=y\) فستظهر حركة مكررة داخل القائمة \(x,y,x+y\). هذا لا يسبب أي مشكلة، لأن تكرار المرشح لا يغير قيمة الحد الأدنى بين الحالات اللاحقة.
لتكن \(V(s)\) هي القيمة المتوقعة المثلى لعدد الرميات الإضافية اللازمة للوصول إلى \(s^\star\). عندئذ
$$V(s^\star)=0.$$
وفي كل حالة غير نهائية يرى اللاعب نتيجة الزهر أولا ثم يختار أفضل قلب ممكن، ولهذا يوضع التصغير داخل التوقع:
$$V(s)=1+\sum_{o} p(o)\min_{a\in A(o)} V\bigl(T(s,a)\bigr),\qquad s\ne s^\star.$$
هذه هي المعادلة المركزية في المسألة. ولو كان لزاما تحديد الفعل قبل الرمية لانتقل الحد الأدنى إلى خارج المجموع، وعندها سنكون نصف لعبة مختلفة.
السياسة الحتمية \(\pi\) تسند فعلا مسموحا لكل زوج \((s,o)\):
$$\pi(s,o)\in A(o).$$
وبعد تثبيت \(\pi\) تصبح دالة القيمة الخاصة بها محققة للمعادلتين
$$V_{\pi}(s^\star)=0,$$
$$V_{\pi}(s)=1+\sum_{o} p(o)\,V_{\pi}\bigl(T(s,\pi(s,o))\bigr).$$
لا تقوم التنفيذات بحل هذا النظام الخطي مباشرة. بدلا من ذلك تطبق تحديث السياسة الثابتة تكراريا وبشكل in-place حتى يصبح أكبر تغير صغيرا جدا. عدديا، هذا يساوي استرخاء متكررا لمعادلات بيلمان الخاصة بالسياسة الحالية.
بعد تقييم السياسة الحالية، يحسن كل زوج حالة-نتيجة بطريقة جشعة عبر اختيار الخلف ذي أقل كلفة متبقية مقدرة:
$$\pi_{\text{new}}(s,o)\in \arg\min_{a\in A(o)} V\bigl(T(s,a)\bigr).$$
إذا لم يعد أي زوج \((s,o)\) يتغير، فهذه السياسة تكون قد أصبحت مثلى على هذا الفضاء المنتهي. بعد ذلك تجري البرامج تقييما نهائيا أطول وبعتبة أدق للحصول على قيمة مستقرة لـ \(V(s_0)\).
قبل حل لعبة البطاقات الاثنتي عشرة، تتحقق تنفيذات C++ وPython وJava من المنهج على نموذج أصغر من 4 بطاقات حيث \(x,y\in\{1,2\}\) ولكل ناتج مرتب احتمال \(1/4\). انطلاقا من الحالة الفارغة \(\varnothing\)، تكون النتائج الأربع المرتبة هي \((1,1)\) و\((1,2)\) و\((2,1)\) و\((2,2)\).
معادلة بيلمان للحالة \(\varnothing\) هي
$$\begin{aligned} V(\varnothing)=1 &+\frac14 \min\bigl(V(\{1\}),V(\{2\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{1\}),V(\{2\}),V(\{3\})\bigr) \\ &+\frac14 \min\bigl(V(\{2\}),V(\{4\})\bigr). \end{aligned}$$
يوضح هذا المثال المنطق كله بصورة مضغوطة: لكل نتيجة مشاهدة نختار أفضل حالة لاحقة أولا، ثم نأخذ متوسط هذه المساهمات. وعند حل جميع الحالات \(2^4=16\) نحصل على
$$V(\varnothing)=5.673651\ldots$$
وهي بالضبط القيمة العددية التي تستخدمها التنفيذات كنقطة تحقق قبل تشغيل الحالة الكاملة ذات 12 بطاقة.
تتبع تنفيذات C++ وPython وJava الفكرة نفسها القائمة على تكرار السياسة. فهي تعد جميع النتائج المرتبة، وتبني مسبقا ثلاث عمليات قلب مرشحة لكل زوج من الحالة والنتيجة، وتحافظ على مصفوفة قيم تغطي الحالات \(4096\) كلها.
في مرحلة تقييم السياسة، يجري المرور مرارا على الحالات غير النهائية ويستبدل التقدير الحالي بالقيمة
$$1+\sum_o p(o)\,V\bigl(T(s,\pi(s,o))\bigr).$$
ثم تفحص مرحلة تحسين السياسة الخلفيات الثلاثة الممكنة لكل \((s,o)\) وتحتفظ بالخلف الذي يملك أصغر تقدير حالي. وتستمر الحلقة الخارجية في التناوب بين هاتين المرحلتين حتى لا يتغير أي قرار. وبعد ذلك ينفذ تقييم أخير أطول وأكثر صرامة لإنتاج جواب ثابت بست منازل عشرية من الحالة الابتدائية.
يعكس برنامج Java المنطق العددي في C++ مباشرة. أما مدخل Python فيعيد النتيجة نفسها عبر إعادة استخدام المحلل المترجم نفسه، ولذلك تبقى الطريقة الرياضية متطابقة بين اللغات الثلاث.
لنكتب \(S=2^{12}=4096\)، ولنكتب \(O=36\) لعدد النتائج المرتبة، ولنكتب \(A=3\) لعدد الأفعال المرشحة على الأكثر. كلفة مرور واحد لتقييم سياسة ثابتة هي \(O(SO)\)، لأن الفعل المختار معروف مسبقا لكل زوج من الحالة والنتيجة. أما مرور تحسين السياسة فكلفته \(O(SOA)\)، لأنه يقارن حتى ثلاثة خلفيات لكل زوج.
استهلاك الذاكرة هو \(O(SO)\) لجدول السياسة و\(O(S)\) لمصفوفة القيم. ومع هذه الثوابت تبقى الطريقة صغيرة جدا عمليا: فالحل الدقيق كله يقع داخل حلقة برمجة ديناميكية متوسطة الحجم من دون الحاجة إلى أدوات رمزية ثقيلة.