Three fair six-sided dice are rolled. A player who sees all three faces chooses one die to hide. The second player then sees the two remaining faces and chooses the option with the larger expected payoff: either take the hidden die, whose value is uncertain, or take the better of the two visible dice, whose value is known exactly. The task is to determine the optimal expected payoff when the hider plays as well as possible.
The local implementations do not guess a simple rule such as “always hide the largest die”. They solve the game exactly. The key observation is that once a visible pair has been fixed, the second player only needs two quantities: the conditional mean of the hidden die and the larger visible face. That turns the full game into a compact linear program.
Write an ordered state as \(s=(d_1,d_2,d_3)\in\{1,\ldots,6\}^3\), and let \(a\in\{1,2,3\}\) denote which die is hidden. All \(216\) ordered states are equally likely, so \(p_s=1/216\).
The state space is ordered, but the observation is not: after one die is hidden, the second player only sees the unordered pair of visible faces. Therefore the observation space is
$$\mathcal{O}=\{\{u,v\}:1\le u\le v\le 6\},\qquad |\mathcal{O}|=\binom{7}{2}=21.$$
For each state-action pair \((s,a)\), let \(o(s,a)\in\mathcal{O}\) be that visible multiset, let \(h(s,a)\) be the hidden face, and define
$$m(o)=\max(o)$$
as the best visible die the second player could take immediately. The smaller visible die is irrelevant to optimal play, because choosing it is always dominated by choosing the larger visible die.
The hider may randomize. Let \(x_{s,a}\ge 0\) be the probability of hiding die \(a\) in state \(s\). For every state, these probabilities must sum to \(1\):
$$\sum_{a=1}^3 x_{s,a}=1\qquad(s\in\{1,\ldots,6\}^3).$$
For a fixed observation \(o\), the total probability of producing that observation is
$$q_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
Conditioned on seeing \(o\), the expected value of the hidden die is
$$\mu_o=\frac{1}{q_o}\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a}\qquad(q_o>0).$$
So after observation \(o\), the second player compares the sure visible value \(m(o)\) with the conditional hidden expectation \(\mu_o\). The contribution of \(o\) to the overall expected payoff is therefore
$$q_o\max(\mu_o,m(o)).$$
The expression above is piecewise linear, but it can be written exactly with one auxiliary variable \(T_o\) for each observation class. First note that
$$q_o\mu_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a},$$
and also
$$q_om(o)=m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
Hence it is enough to impose
$$T_o\ge \sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a},$$
$$T_o\ge m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
If the objective is to minimize \(\sum_{o\in\mathcal{O}}T_o\), every \(T_o\) is forced down to the larger of those two quantities. Therefore
$$\sum_{o\in\mathcal{O}}T_o=\sum_{o\in\mathcal{O}} q_o\max(\mu_o,m(o)),$$
which is exactly the second player’s expected payoff. The whole problem is thus the linear program
$$\min \sum_{o\in\mathcal{O}}T_o$$
subject to the state-normalization equations and the two inequalities above for every observation.
Take the observation \(o=\{2,5\}\). Then \(m(o)=5\). This observation can come from many ordered state-action pairs, for example by hiding the first die in \((4,2,5)\) or by hiding the second die in \((2,6,5)\). The strategy decides how much probability mass each such pair contributes.
If the resulting conditional mean of the hidden die is \(\mu_o=29/6\), then the sure visible \(5\) is better, so this observation contributes \(5q_o\). If instead \(\mu_o=16/3\), then taking the hidden die is better, and the contribution becomes \((16/3)q_o\). The two inequalities for \(T_o\) cover both situations without any case split inside the solver.
The C++, Python, and Java implementations enumerate all \(216\) ordered three-die states and all \(3\) hide choices, giving \(648\) state-action columns. For each column they precompute the observation class, the hidden face, and the larger visible face. They also keep the smaller two-dice version of the same model, which has \(36\) states, \(2\) hide choices, and \(6\) observation classes.
The linear program uses one normalization row per state and two rows per observation class. For the target instance that is \(216+2\cdot 21=258\) rows. It also uses \(21\) auxiliary observation variables, \(42\) slack variables for the inequalities, and \(216\) artificial variables for Phase I.
The state-normalization equations do not come with an obvious feasible basis, so the implementation starts with a standard two-phase simplex. Phase I minimizes the sum of artificial variables; feasibility is certified when that optimum reaches \(0\). The artificial columns are then removed, any row that has become redundant is dropped, and Phase II minimizes \(\sum T_o\) by maximizing its negative in tableau form.
Before solving the three-dice target, the same machinery is run on the two-dice instance and checked against the known value \(145/36\). The C++ implementation also parallelizes the coefficient fill for the observation rows, while the Python and Java implementations perform the same arithmetic serially.
Tableau construction is linear in the number of state-action pairs, because each column contributes to exactly one hidden-value row and one visible-value row. For the target case this means \(648\) such contributions, plus fixed row and column setup.
The main cost is the simplex pivoting. In the three-dice instance, Phase I starts from a \(258\times 927\) tableau, and Phase II continues with \(711\) columns after the artificial variables are removed. As with any simplex implementation, the theoretical worst case is exponential in the number of pivots, but at this matrix size the exact solve is practical. Memory usage is \(O(mn)\) for the tableau.
Es werden drei faire sechsseitige Würfel geworfen. Ein Spieler sieht alle drei Augen und wählt genau einen Würfel zum Verbergen. Der zweite Spieler sieht danach die beiden übrigen Augen und nimmt die Option mit dem größeren Erwartungswert: entweder den verborgenen Würfel, dessen Wert unsicher ist, oder den besseren der beiden sichtbaren Würfel, dessen Wert sicher bekannt ist. Gesucht ist der optimale Erwartungswert, wenn der Verberger bestmöglich spielt.
Die Implementierungen raten nicht auf eine einfache Regel wie „verberge immer den größten Würfel“. Sie lösen das Spiel exakt. Der entscheidende Punkt ist: Sobald ein sichtbares Paar feststeht, braucht der zweite Spieler nur zwei Zahlen, nämlich den bedingten Erwartungswert des verborgenen Würfels und den größeren sichtbaren Wert. Genau dadurch wird das Spiel zu einem kleinen linearen Programm.
Schreibe einen geordneten Zustand als \(s=(d_1,d_2,d_3)\in\{1,\ldots,6\}^3\), und lasse \(a\in\{1,2,3\}\) den verborgenen Würfel bezeichnen. Alle \(216\) geordneten Zustände sind gleich wahrscheinlich, also gilt \(p_s=1/216\).
Der Zustandsraum ist geordnet, die Beobachtung aber nicht: Nachdem ein Würfel verborgen wurde, sieht der zweite Spieler nur das ungeordnete Paar der sichtbaren Augen. Daher ist der Beobachtungsraum
$$\mathcal{O}=\{\{u,v\}:1\le u\le v\le 6\},\qquad |\mathcal{O}|=\binom{7}{2}=21.$$
Für jedes Zustand-Aktions-Paar \((s,a)\) sei \(o(s,a)\in\mathcal{O}\) diese sichtbare Multimenge, \(h(s,a)\) der verborgene Wert und
$$m(o)=\max(o)$$
der beste sichtbare Würfel, den der zweite Spieler sofort wählen könnte. Der kleinere sichtbare Würfel ist für optimales Spiel irrelevant, weil er stets vom größeren sichtbaren Würfel dominiert wird.
Der Verberger darf randomisieren. Sei \(x_{s,a}\ge 0\) die Wahrscheinlichkeit, im Zustand \(s\) den Würfel \(a\) zu verbergen. Für jeden Zustand müssen diese Wahrscheinlichkeiten \(1\) ergeben:
$$\sum_{a=1}^3 x_{s,a}=1\qquad(s\in\{1,\ldots,6\}^3).$$
Für eine feste Beobachtung \(o\) ist die Gesamtwahrscheinlichkeit dieser Beobachtung
$$q_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
Bedingt auf die Beobachtung \(o\) ist der Erwartungswert des verborgenen Würfels
$$\mu_o=\frac{1}{q_o}\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a}\qquad(q_o>0).$$
Nach Beobachtung \(o\) vergleicht der zweite Spieler also den sicheren sichtbaren Wert \(m(o)\) mit dem bedingten verborgenen Erwartungswert \(\mu_o\). Der Beitrag von \(o\) zum gesamten Erwartungswert ist deshalb
$$q_o\max(\mu_o,m(o)).$$
Dieser Ausdruck ist stückweise linear, lässt sich aber exakt mit einer Hilfsvariable \(T_o\) pro Beobachtungsklasse formulieren. Zunächst gilt
$$q_o\mu_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a},$$
und außerdem
$$q_om(o)=m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
Es genügt daher, die Nebenbedingungen
$$T_o\ge \sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a},$$
$$T_o\ge m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}$$
zu fordern. Wird \(\sum_{o\in\mathcal{O}}T_o\) minimiert, dann wird jedes \(T_o\) genau auf das Maximum dieser beiden Größen gedrückt. Also ist
$$\sum_{o\in\mathcal{O}}T_o=\sum_{o\in\mathcal{O}} q_o\max(\mu_o,m(o)),$$
also exakt der Erwartungswert des zweiten Spielers. Das gesamte Problem ist damit das lineare Programm
$$\min \sum_{o\in\mathcal{O}}T_o$$
unter den Zustandsnormalisierungen und den beiden Ungleichungen für jede Beobachtung.
Nimm \(o=\{2,5\}\). Dann ist \(m(o)=5\). Diese Beobachtung kann aus vielen geordneten Zustand-Aktions-Paaren entstehen, etwa durch das Verbergen des ersten Würfels in \((4,2,5)\) oder des zweiten Würfels in \((2,6,5)\). Die Strategie legt fest, wie viel Wahrscheinlichkeitsmasse jedes dieser Paare beiträgt.
Falls der bedingte Erwartungswert des verborgenen Würfels \(\mu_o=29/6\) ist, ist der sichere sichtbare \(5\) besser, und der Beitrag dieser Beobachtung ist \(5q_o\). Falls stattdessen \(\mu_o=16/3\) gilt, ist der verborgene Würfel besser, und der Beitrag wird zu \((16/3)q_o\). Die beiden Ungleichungen für \(T_o\) decken beide Fälle ab, ohne dass der Solver verzweigen muss.
Die C++-, Python- und Java-Implementierungen enumerieren alle \(216\) geordneten Dreiwürfel-Zustände und alle \(3\) Verbergungsaktionen, also \(648\) Zustand-Aktions-Spalten. Für jede Spalte werden die Beobachtungsklasse, der verborgene Wert und der größere sichtbare Wert vorab berechnet. Zusätzlich bleibt die kleinere Zweiwürfel-Version desselben Modells erhalten; sie hat \(36\) Zustände, \(2\) Verbergungsaktionen und \(6\) Beobachtungsklassen.
Das lineare Programm besitzt eine Normierungszeile pro Zustand und zwei Zeilen pro Beobachtungsklasse. Für den Ziel-Fall sind das \(216+2\cdot 21=258\) Zeilen. Hinzu kommen \(21\) Beobachtungs-Hilfsvariablen, \(42\) Schlupfvariablen für die Ungleichungen und \(216\) künstliche Variablen für Phase I.
Die Zustandsgleichungen liefern keine offensichtliche zulässige Anfangsbasis, deshalb beginnt die Implementierung mit einem klassischen Zweiphasen-Simplex. Phase I minimiert die Summe der künstlichen Variablen; Zulässigkeit ist nachgewiesen, sobald dieses Optimum \(0\) erreicht. Danach werden die künstlichen Spalten entfernt, nun redundante Zeilen verworfen und in Phase II wird \(\sum T_o\) minimiert, indem im Tableau die negative Zielfunktion maximiert wird.
Bevor der Dreiwürfel-Fall gelöst wird, wird dieselbe Mechanik auf die Zweiwürfel-Variante angewandt und gegen den bekannten Wert \(145/36\) geprüft. Die C++-Implementierung parallelisiert außerdem das Eintragen der Koeffizienten in die Beobachtungszeilen, während Python und Java dieselbe Rechnung seriell ausführen.
Der Aufbau des Tableaus ist linear in der Anzahl der Zustand-Aktions-Paare, weil jede Spalte genau zu einer Verborgenen-Zeile und einer Sichtbaren-Zeile beiträgt. Im Ziel-Fall sind das \(648\) solche Beiträge plus der feste Aufbau der übrigen Zeilen und Spalten.
Die Hauptkosten entstehen durch die Simplex-Pivots. Für drei Würfel startet Phase I mit einem Tableau der Größe \(258\times 927\), und nach dem Entfernen der künstlichen Variablen arbeitet Phase II mit \(711\) Spalten weiter. Wie immer beim Simplex ist der theoretische Worst Case in der Pivotzahl exponentiell, praktisch ist diese Matrix aber klein genug für eine exakte Lösung. Der Speicherbedarf beträgt \(O(mn)\) für das Tableau.
Üç adil altı yüzlü zar atılıyor. Bütün yüzleri gören ilk oyuncu bir zarı gizliyor. İkinci oyuncu daha sonra kalan iki yüzü görüyor ve beklenen getirisi daha büyük olan seçeneği alıyor: ya değeri belirsiz olan gizli zarı ya da değeri kesin olarak bilinen iki görünür zardan büyüğünü. Soru, gizleyen oyuncu en iyi şekilde oynadığında oluşan en iyi beklenen değeri istemektedir.
Yerel çözümler “her zaman en büyük zarı gizle” gibi sezgisel kuralları denemiyor. Oyunu tam olarak çözüyorlar. Kritik fikir şu: görünür çift sabitlendiği anda ikinci oyuncunun kararını belirleyen tek şey, gizli zarın koşullu ortalaması ile görünür büyük yüzdür. Bu da oyunu küçük ama tam bir doğrusal programa dönüştürüyor.
Sıralı durumu \(s=(d_1,d_2,d_3)\in\{1,\ldots,6\}^3\) ile gösterelim; \(a\in\{1,2,3\}\) hangi zarın gizlendiğini göstersin. Tüm \(216\) sıralı durum eş olasılıklıdır, dolayısıyla \(p_s=1/216\).
Durum uzayı sıralıdır, fakat gözlem sıralı değildir: bir zar gizlendikten sonra ikinci oyuncu yalnızca görünür iki yüzün sırasız çiftini görür. Bu yüzden gözlem uzayı
$$\mathcal{O}=\{\{u,v\}:1\le u\le v\le 6\},\qquad |\mathcal{O}|=\binom{7}{2}=21$$
olur. Her durum-eylem çifti \((s,a)\) için \(o(s,a)\in\mathcal{O}\) görünür çokluğu, \(h(s,a)\) gizli yüzü ve
$$m(o)=\max(o)$$
görünür seçenekler arasından hemen alınabilecek en iyi yüzü göstersin. Küçük görünür yüz optimal oyunda önemsizdir; çünkü onu seçmek, büyük görünür yüzü seçmek tarafından her zaman baskılanır.
Gizleyen oyuncu rassallaştırma yapabilir. \(x_{s,a}\ge 0\), durum \(s\) gerçekleştiğinde \(a\) numaralı zarı gizleme olasılığı olsun. Her durumda bu olasılıkların toplamı \(1\) olmalıdır:
$$\sum_{a=1}^3 x_{s,a}=1\qquad(s\in\{1,\ldots,6\}^3).$$
Sabit bir \(o\) gözlemi için, bu gözlemin toplam olasılığı
$$q_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}$$
şeklindedir. \(o\) görüldüğünde gizli zarın koşullu beklenen değeri ise
$$\mu_o=\frac{1}{q_o}\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a}\qquad(q_o>0)$$
olur. Dolayısıyla ikinci oyuncu, \(o\) gözlemi altında kesin görünür değer \(m(o)\) ile gizli zarın koşullu ortalaması \(\mu_o\) arasında seçim yapar. Bu gözlemin toplam beklenen katkısı
$$q_o\max(\mu_o,m(o))$$
olur.
Bu ifade parçalı doğrusaldır; fakat her gözlem sınıfı için bir \(T_o\) yardımcı değişkeni ile tam olarak yazılabilir. Önce
$$q_o\mu_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a}$$
olduğunu, ayrıca
$$q_om(o)=m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}$$
olduğunu not edelim. O halde şu iki kısıt yeterlidir:
$$T_o\ge \sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a},$$
$$T_o\ge m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
Amaç \(\sum_{o\in\mathcal{O}}T_o\) değerini küçültmek olunca, her \(T_o\) bu iki miktarın büyüğüne kadar iner. Böylece
$$\sum_{o\in\mathcal{O}}T_o=\sum_{o\in\mathcal{O}} q_o\max(\mu_o,m(o)),$$
yani tam olarak ikinci oyuncunun beklenen kazancı elde edilir. Sonuçta problem, her gözlem için yukarıdaki iki eşitsizlik ve her durum için normalizasyon denklemi altında
$$\min \sum_{o\in\mathcal{O}}T_o$$
biçimindeki doğrusal programa indirgenir.
\(o=\{2,5\}\) gözlemini ele alalım. Bu durumda \(m(o)=5\) olur. Bu gözlem, örneğin \((4,2,5)\) durumunda birinci zarı gizleyerek ya da \((2,6,5)\) durumunda ikinci zarı gizleyerek ortaya çıkabilir. Strateji, bu tür durum-eylem çiftlerinin her birine ne kadar olasılık kütlesi verildiğini belirler.
Eğer gizli zarın koşullu ortalaması \(\mu_o=29/6\) ise, kesin görünür \(5\) daha iyidir ve bu gözlemin katkısı \(5q_o\) olur. Eğer bunun yerine \(\mu_o=16/3\) ise, gizli zarı seçmek daha iyidir ve katkı \((16/3)q_o\) olur. \(T_o\) için yazılan iki eşitsizlik, çözücü içinde ayrı bir durum ayrımı yapmadan bu iki senaryoyu da kapsar.
C++, Python ve Java uygulamaları tüm \(216\) sıralı üç-zar durumunu ve tüm \(3\) gizleme seçimini açarak \(648\) durum-eylem sütunu üretir. Her sütun için gözlem sınıfı, gizli yüz ve büyük görünür yüz önceden hesaplanır. Aynı mekanizmanın daha küçük iki-zarlı sürümü de tutulur; orada \(36\) durum, \(2\) gizleme seçimi ve \(6\) gözlem sınıfı vardır.
Doğrusal program her durum için bir normalizasyon satırı ve her gözlem sınıfı için iki satır kullanır. Hedef örnekte bu sayı \(216+2\cdot 21=258\) satırdır. Buna ek olarak \(21\) gözlem yardımcı değişkeni, eşitsizlikler için \(42\) slack değişkeni ve Faz I için \(216\) yapay değişken bulunur.
Durum normalizasyon denklemleri açık bir başlangıç bazisi vermediği için uygulama klasik iki fazlı simplex ile başlar. Faz I, yapay değişkenlerin toplamını küçültür; optimum \(0\) olduğunda fizibilite kanıtlanmış olur. Sonra yapay sütunlar atılır, artık gereksiz hale gelen satırlar düşürülür ve Faz II, tablo işareti gereği negatifini maksimize ederek \(\sum T_o\) değerini minimize eder.
Üç-zarlı hedef çözülmeden önce aynı yöntem iki-zarlı örnekte çalıştırılır ve bilinen \(145/36\) değeriyle kontrol edilir. C++ uygulaması ayrıca gözlem satırlarının katsayılarını doldurma işini paralelleştirir; Python ve Java sürümleri aynı hesabı seri yapar.
Tablo kurma maliyeti durum-eylem çifti sayısında doğrusaldır; çünkü her sütun tam olarak bir gizli-değer satırına ve bir görünür-değer satırına katkı verir. Hedef durumda bu, sabit satır ve sütun kurulumuna ek olarak \(648\) katkı demektir.
Ana maliyet simplex pivotlarıdır. Üç-zarlı örnekte Faz I, \(258\times 927\) boyutlu bir tabloda başlar; yapay değişkenler silindikten sonra Faz II \(711\) sütunla devam eder. Simplex için teorik en kötü durum pivot sayısı üstel olabilir, fakat bu matris boyutunda tam çözüm pratik olarak rahattır. Bellek kullanımı tablo için \(O(mn)\) düzeyindedir.
Se lanzan tres dados justos de seis caras. Un jugador ve las tres caras y elige un dado para ocultarlo. El segundo jugador ve entonces las dos caras restantes y toma la opción con mayor valor esperado: o bien quedarse con el dado oculto, cuyo valor es incierto, o bien tomar el mejor de los dos dados visibles, cuyo valor se conoce exactamente. La tarea consiste en hallar el valor esperado óptimo cuando quien oculta juega de la mejor manera posible.
Las implementaciones no prueban reglas heurísticas del tipo “ocultar siempre el dado más grande”. Resuelven el juego de forma exacta. La observación clave es que, una vez fijado el par visible, el segundo jugador sólo necesita dos cantidades: la media condicional del dado oculto y la mayor cara visible. Eso convierte el problema completo en un programa lineal pequeño pero exacto.
Escribamos un estado ordenado como \(s=(d_1,d_2,d_3)\in\{1,\ldots,6\}^3\), y sea \(a\in\{1,2,3\}\) el índice del dado que se oculta. Los \(216\) estados ordenados son equiprobables, así que \(p_s=1/216\).
El espacio de estados es ordenado, pero la observación no lo es: después de ocultar un dado, el segundo jugador sólo ve el par no ordenado de caras visibles. Por tanto, el espacio de observaciones es
$$\mathcal{O}=\{\{u,v\}:1\le u\le v\le 6\},\qquad |\mathcal{O}|=\binom{7}{2}=21.$$
Para cada par estado-acción \((s,a)\), definimos \(o(s,a)\in\mathcal{O}\) como ese multiconjunto visible, \(h(s,a)\) como la cara oculta y
$$m(o)=\max(o)$$
como el mejor dado visible que el segundo jugador podría tomar inmediatamente. La cara visible menor no influye en la respuesta óptima, porque siempre está dominada por la visible mayor.
El jugador que oculta puede mezclar estrategias. Sea \(x_{s,a}\ge 0\) la probabilidad de ocultar el dado \(a\) en el estado \(s\). Para cada estado, esas probabilidades deben sumar \(1\):
$$\sum_{a=1}^3 x_{s,a}=1\qquad(s\in\{1,\ldots,6\}^3).$$
Para una observación fija \(o\), la probabilidad total de producirla es
$$q_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
Condicionado a ver \(o\), el valor esperado del dado oculto es
$$\mu_o=\frac{1}{q_o}\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a}\qquad(q_o>0).$$
Así, tras observar \(o\), el segundo jugador compara el valor visible seguro \(m(o)\) con la esperanza condicional \(\mu_o\) del dado oculto. La contribución de \(o\) al valor esperado total es
$$q_o\max(\mu_o,m(o)).$$
La expresión anterior es lineal a trozos, pero se vuelve completamente lineal si introducimos una variable auxiliar \(T_o\) para cada clase de observación. Primero,
$$q_o\mu_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a},$$
y además
$$q_om(o)=m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
Por lo tanto basta imponer
$$T_o\ge \sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a},$$
$$T_o\ge m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
Si el objetivo es minimizar \(\sum_{o\in\mathcal{O}}T_o\), cada \(T_o\) queda forzada al mayor de esas dos cantidades. En consecuencia,
$$\sum_{o\in\mathcal{O}}T_o=\sum_{o\in\mathcal{O}} q_o\max(\mu_o,m(o)),$$
que es exactamente el valor esperado del segundo jugador. Todo el problema queda entonces en el programa lineal
$$\min \sum_{o\in\mathcal{O}}T_o$$
sujeto a las ecuaciones de normalización por estado y a las dos desigualdades anteriores para cada observación.
Tomemos \(o=\{2,5\}\). Entonces \(m(o)=5\). Esa observación puede venir de muchos pares estado-acción ordenados, por ejemplo ocultando el primer dado en \((4,2,5)\) o el segundo en \((2,6,5)\). La estrategia determina cuánta masa de probabilidad aporta cada uno de esos pares.
Si la media condicional del dado oculto resulta ser \(\mu_o=29/6\), conviene tomar el \(5\) visible, y la contribución de esa observación es \(5q_o\). Si en cambio \(\mu_o=16/3\), conviene elegir el dado oculto, y la contribución pasa a ser \((16/3)q_o\). Las dos desigualdades de \(T_o\) cubren ambos casos sin necesidad de ramificar dentro del solucionador.
Las implementaciones en C++, Python y Java enumeran los \(216\) estados ordenados de tres dados y las \(3\) decisiones posibles de ocultación, lo que produce \(648\) columnas de estado-acción. Para cada columna se precalculan la clase de observación, la cara oculta y la cara visible mayor. También se conserva la versión más pequeña del mismo modelo con dos dados, que tiene \(36\) estados, \(2\) acciones de ocultación y \(6\) clases de observación.
El programa lineal usa una fila de normalización por estado y dos filas por clase de observación. En el caso objetivo eso da \(216+2\cdot 21=258\) filas. Además hay \(21\) variables auxiliares de observación, \(42\) variables de holgura para las desigualdades y \(216\) variables artificiales para la Fase I.
Las ecuaciones de normalización por estado no proporcionan una base factible obvia, así que la implementación arranca con un simplex clásico en dos fases. La Fase I minimiza la suma de las variables artificiales; la factibilidad queda certificada cuando ese óptimo llega a \(0\). Después se eliminan las columnas artificiales, se descarta cualquier fila que haya quedado redundante y la Fase II minimiza \(\sum T_o\) maximizando su negativo en la convención del tableau.
Antes de resolver el caso objetivo de tres dados, el mismo procedimiento se ejecuta sobre la variante de dos dados y se contrasta con el valor conocido \(145/36\). La implementación en C++ también paraleliza el llenado de coeficientes de las filas de observación, mientras que Python y Java realizan el mismo cálculo en serie.
La construcción del tableau es lineal en el número de pares estado-acción, porque cada columna contribuye exactamente a una fila de valor oculto y a una fila de valor visible. En el caso objetivo eso significa \(648\) contribuciones, además de la preparación fija de filas y columnas.
El coste principal está en los pivotes del simplex. Con tres dados, la Fase I empieza con un tableau de \(258\times 927\), y la Fase II continúa con \(711\) columnas una vez eliminadas las variables artificiales. Como ocurre siempre con simplex, el peor caso teórico para el número de pivotes es exponencial, pero con este tamaño de matriz la resolución exacta es perfectamente práctica. La memoria es \(O(mn)\) para el tableau.
题目中的游戏使用三枚公平的六面骰子。第一位玩家先看到三个点数，再决定藏起其中一枚。第二位玩家随后只能看到另外两枚骰子的点数，并且会选择期望收益更大的方案：要么拿那枚被藏起来的骰子，要么直接拿两枚可见骰子中较大的那一枚。题目要求的是，在藏骰子的一方采取最优策略时，第二位玩家最终能保证得到的最优期望值。
这些实现并不是去猜某条经验规则，例如“总是藏最大值”或“总是藏中间值”。它们把整个博弈精确地写成一个线性规划。关键事实是：一旦可见的那一对点数固定下来，第二位玩家真正需要比较的只有两件事，隐藏骰子的条件期望，以及当前可见点数中的最大值。正因为如此，原问题可以被压缩成一个规模不大但完全精确的优化模型。
把一个有序状态写成 \(s=(d_1,d_2,d_3)\in\{1,\ldots,6\}^3\)，用 \(a\in\{1,2,3\}\) 表示藏的是第几枚骰子。三枚骰子的有序结果共有 \(216\) 个，而且等概率出现，所以 \(p_s=1/216\)。
状态空间是有序的，但观测不是。因为藏起一枚之后，第二位玩家只会看到另外两枚骰子的无序点数组合，而不会关心它们原来位于哪个位置。因此观测空间是
$$\mathcal{O}=\{\{u,v\}:1\le u\le v\le 6\},\qquad |\mathcal{O}|=\binom{7}{2}=21.$$
对每个状态-动作对 \((s,a)\)，记 \(o(s,a)\in\mathcal{O}\) 为可见的点数多重集，\(h(s,a)\) 为被藏起来的点数，并定义
$$m(o)=\max(o)$$
表示当前观测下可以立刻拿走的最佳可见骰子。较小的那枚可见骰子在最优策略中完全不会被选，因为它总是被较大的可见骰子支配。
藏骰子的一方可以使用混合策略。设 \(x_{s,a}\ge 0\) 表示在状态 \(s\) 下选择隐藏第 \(a\) 枚骰子的概率。对每个状态，这三个概率必须满足
$$\sum_{a=1}^3 x_{s,a}=1\qquad(s\in\{1,\ldots,6\}^3).$$
对于某个固定观测 \(o\)，产生该观测的总概率是
$$q_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
在已经看到 \(o\) 的条件下，被隐藏骰子的条件期望为
$$\mu_o=\frac{1}{q_o}\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a}\qquad(q_o>0).$$
于是第二位玩家面对观测 \(o\) 时，真正比较的是确定的可见收益 \(m(o)\) 和隐藏骰子的条件期望 \(\mu_o\)。因此观测 \(o\) 对总期望的贡献就是
$$q_o\max(\mu_o,m(o)).$$
上面的表达式是分段线性的，但只要为每个观测类别引入一个辅助变量 \(T_o\)，就可以把它完整地改写成线性形式。先注意
$$q_o\mu_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a},$$
同时还有
$$q_om(o)=m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
所以只需要加入两条约束：
$$T_o\ge \sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a},$$
$$T_o\ge m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
当目标函数是最小化 \(\sum_{o\in\mathcal{O}}T_o\) 时，每个 \(T_o\) 都会被压到上述两项中的较大者。因此
$$\sum_{o\in\mathcal{O}}T_o=\sum_{o\in\mathcal{O}} q_o\max(\mu_o,m(o)),$$
这恰好就是第二位玩家的总期望收益。于是原问题被准确地改写成下面的线性规划：
$$\min \sum_{o\in\mathcal{O}}T_o$$
并满足每个状态的归一化等式，以及每个观测对应的两条不等式。
考虑观测 \(o=\{2,5\}\)。这时 \(m(o)=5\)。这种观测可以来自许多不同的有序状态-动作对，例如在 \((4,2,5)\) 中隐藏第一枚骰子，或者在 \((2,6,5)\) 中隐藏第二枚骰子。不同策略会给这些状态-动作对分配不同的概率质量。
如果在该观测下，隐藏骰子的条件期望是 \(\mu_o=29/6\)，那么直接拿可见的 \(5\) 更好，这个观测对总期望的贡献就是 \(5q_o\)。如果条件期望变成 \(\mu_o=16/3\)，那么选隐藏骰子更划算，贡献就变成 \((16/3)q_o\)。辅助变量 \(T_o\) 的两条线性约束正是同时覆盖这两种情形，而不需要在求解器内部显式分支。
C++、Python 和 Java 实现都会枚举全部 \(216\) 个三骰子有序状态，以及每个状态下 \(3\) 种可能的隐藏选择，因此一共有 \(648\) 个状态-动作列。对每一列，程序都会预先算出它对应的观测类别、被隐藏的点数，以及那一列下最大的可见点数。实现里还保留了同一模型的两骰子小版本，用来做校验；那一版共有 \(36\) 个状态、\(2\) 个隐藏动作和 \(6\) 个观测类别。
线性规划本身对每个状态放一条归一化约束，对每个观测类别放两条约束。对三骰子的目标实例来说，这一共是 \(216+2\cdot 21=258\) 行。除此之外，还有 \(21\) 个观测辅助变量、\(42\) 个把不等式改写成等式所需的松弛变量，以及 \(216\) 个 Phase I 人工变量。
状态归一化方程本身并不给出一个显然可行的初始基，因此实现采用标准的两阶段单纯形法。第一阶段最小化人工变量之和；当这个最优值达到 \(0\) 时，就说明线性规划可行。随后删去人工变量对应的列，丢弃已经变成冗余的行，再进入第二阶段，在 tableau 的符号约定下通过最大化 \(-\sum T_o\) 来完成对 \(\sum T_o\) 的最小化。
在真正求解三骰子目标之前，实现会先运行两骰子版本，并验证结果是否等于已知值 \(145/36\)。此外，C++ 版本会把观测约束行的系数填充并行化；Python 和 Java 版本执行的是同样的算术，只是不做并行。
构造 tableau 的成本与状态-动作对的数量成线性关系，因为每一列只会向一条“隐藏值”约束和一条“可见值”约束各贡献一次。在目标实例里，这部分只有 \(648\) 次核心贡献，再加上固定规模的行列初始化。
真正的主要成本来自单纯形迭代。三骰子时，第一阶段从一个 \(258\times 927\) 的 tableau 开始；去掉人工变量之后，第二阶段还剩 \(711\) 列。和所有 simplex 实现一样，理论上的最坏 pivot 数可以是指数级，但在这个矩阵规模下，精确求解完全可行。内存开销主要是 tableau，本质上是 \(O(mn)\)。
Бросаются три честные шестигранные кости. Первый игрок видит все три значения и выбирает одну кость, которую нужно скрыть. Второй игрок после этого видит две оставшиеся кости и выбирает вариант с наибольшим ожидаемым выигрышем: либо взять скрытую кость, значение которой неизвестно, либо взять лучшую из двух видимых костей, значение которой известно точно. Требуется найти оптимальный ожидаемый выигрыш при наилучшей игре скрывающего.
Локальные реализации не пытаются угадать простое правило вроде «всегда скрывать максимум». Они решают задачу точно. Главный факт состоит в том, что после фиксации видимой пары второму игроку нужны только две величины: условное среднее скрытой кости и максимальное видимое значение. Благодаря этому вся игра сводится к компактной задаче линейного программирования.
Обозначим упорядоченное состояние через \(s=(d_1,d_2,d_3)\in\{1,\ldots,6\}^3\), а через \(a\in\{1,2,3\}\) укажем, какая кость скрывается. Все \(216\) упорядоченных состояний равновероятны, поэтому \(p_s=1/216\).
Пространство состояний упорядочено, а наблюдение нет: после скрытия одной кости второй игрок видит только неупорядоченную пару оставшихся значений. Поэтому пространство наблюдений равно
$$\mathcal{O}=\{\{u,v\}:1\le u\le v\le 6\},\qquad |\mathcal{O}|=\binom{7}{2}=21.$$
Для каждой пары \((s,a)\) обозначим через \(o(s,a)\in\mathcal{O}\) этот видимый мультимножество, через \(h(s,a)\) скрытое значение и введём
$$m(o)=\max(o)$$
как лучшую видимую кость, которую второй игрок может взять сразу. Меньшая видимая кость для оптимальной игры несущественна, потому что она всегда доминируется большей видимой костью.
Скрывающий игрок может использовать смешанную стратегию. Пусть \(x_{s,a}\ge 0\) обозначает вероятность скрыть кость \(a\) в состоянии \(s\). Для каждого состояния эти вероятности должны суммироваться в \(1\):
$$\sum_{a=1}^3 x_{s,a}=1\qquad(s\in\{1,\ldots,6\}^3).$$
Для фиксированного наблюдения \(o\) полная вероятность получить именно его равна
$$q_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
Условное математическое ожидание скрытой кости при наблюдении \(o\) равно
$$\mu_o=\frac{1}{q_o}\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a}\qquad(q_o>0).$$
Значит, увидев \(o\), второй игрок сравнивает гарантированное видимое значение \(m(o)\) с условным ожиданием скрытой кости \(\mu_o\). Вклад наблюдения \(o\) в общий ожидаемый выигрыш равен
$$q_o\max(\mu_o,m(o)).$$
Это выражение кусочно-линейно, но его можно записать точно, введя по одной вспомогательной переменной \(T_o\) для каждого класса наблюдений. Сначала заметим, что
$$q_o\mu_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a},$$
а также
$$q_om(o)=m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
Следовательно, достаточно наложить ограничения
$$T_o\ge \sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a},$$
$$T_o\ge m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
Если минимизировать \(\sum_{o\in\mathcal{O}}T_o\), то каждая переменная \(T_o\) опускается ровно до максимума этих двух величин. Поэтому
$$\sum_{o\in\mathcal{O}}T_o=\sum_{o\in\mathcal{O}} q_o\max(\mu_o,m(o)),$$
то есть получается точный ожидаемый выигрыш второго игрока. Вся задача тем самым превращается в линейную программу
$$\min \sum_{o\in\mathcal{O}}T_o$$
при уравнениях нормировки по состояниям и двух неравенствах для каждого наблюдения.
Рассмотрим \(o=\{2,5\}\). Тогда \(m(o)=5\). Такое наблюдение может возникать из множества упорядоченных пар состояние-действие, например при скрытии первой кости в \((4,2,5)\) или второй кости в \((2,6,5)\). Стратегия определяет, какую вероятность получает каждая такая пара.
Если условное среднее скрытой кости равно \(\mu_o=29/6\), выгоднее взять видимую \(5\), и вклад этого наблюдения равен \(5q_o\). Если же \(\mu_o=16/3\), выгоднее выбирать скрытую кость, и вклад становится \((16/3)q_o\). Два линейных ограничения для \(T_o\) охватывают оба случая без явного ветвления в решателе.
Реализации на C++, Python и Java перечисляют все \(216\) упорядоченных состояний трёх костей и все \(3\) варианта скрытия, что даёт \(648\) столбцов вида «состояние-действие». Для каждого столбца заранее вычисляются класс наблюдения, скрытое значение и максимальное видимое значение. Там же сохраняется и меньшая модель для двух костей: \(36\) состояний, \(2\) действия скрытия и \(6\) классов наблюдений.
Линейная программа содержит по одной строке нормировки на каждое состояние и по две строки на каждый класс наблюдений. Для целевого случая это \(216+2\cdot 21=258\) строк. Дополнительно используются \(21\) вспомогательная переменная наблюдений, \(42\) slack-переменные для неравенств и \(216\) искусственных переменных для Фазы I.
Уравнения нормировки по состояниям не дают очевидного допустимого начального базиса, поэтому реализация начинает со стандартного двухфазного симплекса. Фаза I минимизирует сумму искусственных переменных; достижение значения \(0\) доказывает допустимость. Затем искусственные столбцы удаляются, ставшие избыточными строки отбрасываются, и на Фазе II минимизируется \(\sum T_o\) через максимизацию её отрицания в табличной записи.
Прежде чем решать целевой случай с тремя костями, тот же механизм запускается на варианте с двумя костями и сверяется с известным значением \(145/36\). Реализация на C++ дополнительно распараллеливает заполнение коэффициентов строк наблюдений, а Python и Java выполняют ту же арифметику последовательно.
Построение tableau линейно по числу пар «состояние-действие», потому что каждый столбец вносит вклад ровно в одну строку для скрытого значения и в одну строку для видимого значения. В целевом случае это всего \(648\) таких вкладов плюс фиксированная подготовка строк и столбцов.
Основная стоимость связана с pivot-шагами симплекс-метода. Для трёх костей Фаза I начинается с tableau размера \(258\times 927\), а после удаления искусственных переменных Фаза II продолжается уже с \(711\) столбцами. Как и всегда у simplex, теоретический худший случай по числу pivot-шагов экспоненциален, но на этой матрице точное решение вполне практично. Память составляет \(O(mn)\) для самого tableau.
في هذه المسألة تُرمى ثلاث نردات عادلة ذات ستة أوجه. اللاعب الأول يرى القيم الثلاث كلها ثم يختار نردة واحدة ليخفيها. بعد ذلك يرى اللاعب الثاني القيمتين الظاهرتين فقط، ثم يختار الخيار ذي العائد المتوقع الأكبر: إما أن يأخذ النردة المخفية ذات القيمة غير المعلومة، أو أن يأخذ أفضل النردتين الظاهرتين ذات القيمة المعروفة مباشرة. المطلوب هو إيجاد القيمة المتوقعة المثلى عندما يلعب المُخفي بأفضل صورة ممكنة.
التنفيذات المحلية لا تعتمد على قاعدة حدسية مثل "أخفِ أكبر قيمة دائماً". بل تحل اللعبة بدقة كاملة. الفكرة الحاسمة هي أنه ما إن تثبت الزوجية الظاهرة، فإن اللاعب الثاني لا يحتاج إلا إلى كميتين فقط: المتوسط الشرطي للنردة المخفية، وأكبر قيمة ظاهرة. ومن هنا تتحول اللعبة كلها إلى نموذج برمجة خطية صغير لكنه دقيق تماماً.
لنكتب الحالة المرتبة على صورة \(s=(d_1,d_2,d_3)\in\{1,\ldots,6\}^3\)، ولتكن \(a\in\{1,2,3\}\) هي فهرس النردة التي تُخفى. جميع الحالات المرتبة وعددها \(216\) متساوية الاحتمال، لذلك \(p_s=1/216\).
فضاء الحالات مرتب، أما المشاهدة فليست مرتبة: بعد إخفاء نردة واحدة لا يرى اللاعب الثاني إلا الزوج غير المرتب من القيم الظاهرة. لذلك يكون فضاء المشاهدات
$$\mathcal{O}=\{\{u,v\}:1\le u\le v\le 6\},\qquad |\mathcal{O}|=\binom{7}{2}=21.$$
لكل زوج \((s,a)\)، نرمز إلى المشاهدة الظاهرة بـ \(o(s,a)\in\mathcal{O}\)، وإلى القيمة المخفية بـ \(h(s,a)\)، ونعرف
$$m(o)=\max(o)$$
بوصفها أفضل نردة ظاهرة يمكن أخذها فوراً. أما النردة الظاهرة الأصغر فلا تؤثر في اللعب الأمثل، لأن اختيارها يكون دائماً أسوأ من اختيار الظاهرة الأكبر.
يمكن للاعب المُخفي أن يستخدم استراتيجية مختلطة. لِنرمز بـ \(x_{s,a}\ge 0\) إلى احتمال إخفاء النردة \(a\) عندما تكون الحالة هي \(s\). ويجب أن تحقق هذه الاحتمالات في كل حالة
$$\sum_{a=1}^3 x_{s,a}=1\qquad(s\in\{1,\ldots,6\}^3).$$
ولكل مشاهدة ثابتة \(o\)، فإن الاحتمال الكلي لظهورها يساوي
$$q_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
أما القيمة المتوقعة الشرطية للنردة المخفية بعد رؤية \(o\) فهي
$$\mu_o=\frac{1}{q_o}\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a}\qquad(q_o>0).$$
إذن، بعد مشاهدة \(o\)، يقارن اللاعب الثاني بين القيمة الظاهرة المضمونة \(m(o)\) وبين المتوسط الشرطي \(\mu_o\) للنردة المخفية. ومن ثم يكون إسهام هذه المشاهدة في القيمة المتوقعة الكلية هو
$$q_o\max(\mu_o,m(o)).$$
هذا التعبير خطي على أجزاء، لكنه يصبح خطياً تماماً إذا أدخلنا متغيراً مساعداً \(T_o\) لكل فئة مشاهدة. نلاحظ أولاً أن
$$q_o\mu_o=\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a},$$
وكذلك
$$q_om(o)=m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
لذلك يكفي فرض القيدين
$$T_o\ge \sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,h(s,a)\,x_{s,a},$$
$$T_o\ge m(o)\sum_{\substack{(s,a)\\o(s,a)=o}} p_s\,x_{s,a}.$$
وعندما يكون الهدف هو تصغير \(\sum_{o\in\mathcal{O}}T_o\)، فإن كل \(T_o\) يهبط إلى الأكبر من هاتين الكميتين. وبالتالي
$$\sum_{o\in\mathcal{O}}T_o=\sum_{o\in\mathcal{O}} q_o\max(\mu_o,m(o)),$$
وهو بالضبط العائد المتوقع للاعب الثاني. وبذلك تصبح المسألة كلها هي برنامج خطي من الشكل
$$\min \sum_{o\in\mathcal{O}}T_o$$
مع معادلات التطبيع على الحالات، والقيدين السابقين لكل مشاهدة.
لنأخذ المشاهدة \(o=\{2,5\}\). عندئذ يكون \(m(o)=5\). يمكن أن تنتج هذه المشاهدة من أزواج كثيرة من الحالة والفعل، مثلاً عند إخفاء النردة الأولى في \((4,2,5)\)، أو إخفاء النردة الثانية في \((2,6,5)\). والاستراتيجية هي التي تحدد كم من الكتلة الاحتمالية يذهب إلى كل زوج من هذه الأزواج.
إذا كان المتوسط الشرطي للنردة المخفية هو \(\mu_o=29/6\)، فإن أخذ \(5\) الظاهرة أفضل، فيكون إسهام هذه المشاهدة \(5q_o\). وإذا أصبح \(\mu_o=16/3\)، فإن اختيار النردة المخفية هو الأفضل، ويصبح الإسهام \((16/3)q_o\). القيدان الخطيان الخاصان بـ \(T_o\) يغطيان الحالتين معاً من دون أي تفريع داخل المحلّل.
تنفّذ حلول C++ وPython وJava تعداد جميع الحالات المرتبة الثلاثية وعددها \(216\)، وجميع خيارات الإخفاء الثلاثة، فتنتج \(648\) عموداً من نوع حالة-فعل. ولكل عمود تُحسب مسبقاً فئة المشاهدة، والقيمة المخفية، وأكبر قيمة ظاهرة. كما تُحتفظ أيضاً بالنسخة الأصغر ذات النردتين من النموذج نفسه، وفيها \(36\) حالة و\(2\) خيارا إخفاء و\(6\) فئات مشاهدة.
البرنامج الخطي يستخدم سطراً واحداً للتطبيع لكل حالة، وسطرين لكل فئة مشاهدة. في الحالة الهدفية يكون المجموع \(216+2\cdot 21=258\) سطراً. ويضاف إلى ذلك \(21\) متغيراً مساعداً للمشاهدات، و\(42\) متغير slack لتمثيل المتباينات، و\(216\) متغيراً اصطناعياً في المرحلة الأولى.
معادلات التطبيع على الحالات لا تعطي أساساً ابتدائياً مقبولاً بشكل مباشر، لذلك تبدأ الشيفرة بطريقة السمبلكس ثنائية الطور. في الطور الأول يُصغَّر مجموع المتغيرات الاصطناعية؛ وعندما تصل القيمة المثلى إلى \(0\) تكون إمكانية الحل قد ثبتت. بعد ذلك تُحذف الأعمدة الاصطناعية، وتُسقط أي صفوف أصبحت زائدة، ثم يعمل الطور الثاني على تصغير \(\sum T_o\) عبر تعظيم سالبها في تمثيل الجدول.
قبل حل مسألة النردات الثلاث فعلياً، تُشغَّل الآلية نفسها على نسخة النردتين، ويُفحَص الناتج مقابل القيمة المعروفة \(145/36\). كما أن تنفيذ C++ يوازي عملية تعبئة معاملات صفوف المشاهدات، بينما تنفذ Python وJava الحساب نفسه بشكل تسلسلي.
كلفة بناء الجدول خطية في عدد أزواج الحالة والفعل، لأن كل عمود يساهم مرة واحدة فقط في صف قيمة مخفية ومرة واحدة فقط في صف قيمة ظاهرة. وفي الحالة الهدفية يعني هذا \(648\) مساهمة من هذا النوع، إضافة إلى الإعداد الثابت لبقية الصفوف والأعمدة.
الكلفة الرئيسية تأتي من محاورات السمبلكس. في مسألة النردات الثلاث يبدأ الطور الأول بجدول حجمه \(258\times 927\)، وبعد حذف المتغيرات الاصطناعية يكمل الطور الثاني مع \(711\) عموداً. وكما هو معتاد في simplex، فإن أسوأ عدد نظري للمحاورات أسي، لكن هذا الحجم من المصفوفات صغير بما يكفي ليكون الحل الدقيق عملياً. استهلاك الذاكرة هو \(O(mn)\) للجدول نفسه.