バックログ
成果物
アプリ（フロント）:https://blackjack-web-oec4.onrender.com/
バックエンドサーバー:https://blackjack-api-sfpa.onrender.com/
（無料サーバーのため読み込みには時間がかかります）
この記事時点でのgithub:https://github.com/morinonusi421/blackjack/tree/608a3bd2a62e3bd887a57aef826dc9cb86d7118f
今回ついに、ブラックジャックの最適行動の計算を実装します。
最も面白い部分です。
具体的には、
- 入力: ゲームの状態
- 出力: ヒット・スタンド・サレンダーそれぞれで返ってくるチップの期待値
という計算ができる関数の作成を目指します。
このプログラムをカジノに持ち込めば、常に最適な行動が取れるようになるはずです！（怒られるかもしれませんが）
この記事ではまず、高速化の工夫をせずに、愚直な最適解の計算プログラムの作り方を紹介します。
次に、「メモ化再帰」というテクニックを用いて、プログラムを高速化します。
最後に、Goのベンチマークテストの機能を用いて、高速化の効果を測定します。
大事な前提条件
この記事・私のアプリでは、ブラックジャックの山札は無限であり、常に全てのカードを等確率で引くという設定です。
実際のカジノでもカウンティングは禁止なので、悪くない簡略化だと考えています。
(もしもカウンティングを有効にするなら、別のアプローチを考える必要があります)1
最適行動の計算 理論編
有限ゲームとは
ブラックジャックの任意の局面は、「プレイヤーの手札の状況」と「ディラーの手札の状況」の組み合わせで表現できます。これをゲームの状態と呼びます。
そして各状態で、プレイヤーは以下の行動を選択できます。
- ヒット (Hit): もう1枚カードを引く
- スタンド (Stand): カードを引かずに勝負する
- サレンダー (Surrender): 賭け金の半分を諦めてゲームを降りる（最初の行動でのみ可能）
（本来はもっとありますが、私のアプリではこの3つに簡略化しています）
行動を選ぶと、ゲームは次の「状態」へと遷移します。例えば、ヒットを選べばプレイヤーの手札が変わり、新しい状態になります。この「状態」から「状態」への遷移を繰り返していくと、最終的にプレイヤーがバーストするか、スタンドして勝負がつくか、いずれかの終端にたどり着きます。
ここでポイントになるのは、ブラックジャックは何度か行動を繰り返すと、必ず終端に辿り着くという事実です。このような性質を持つゲームは有限ゲームと呼ばれ、終端までのステップが少ない場合は最適解を計算しやすいです。
再帰計算による最適行動の導出
有限ゲームの構造は、関数の呼び出しが連鎖していく再帰と非常に相性が良いです。
ある状態の最適行動を知るには、その状態で取りうる各アクション（ヒット、スタンド、サレンダー）を選んだ場合に、最終的にどれくらいの配当（ペイアウト）が期待できるか、その期待値を計算し、比較すれば良いわけです。
- スタンド: 終端に辿り着く。自分のスコアと、ディーラーが取りうる最終スコアの全パターンを比較して期待値を計算する
- サレンダー時の期待値: 常に賭け金の半分が戻るので、0.5の期待値
- ヒット時の期待値: 少し複雑。他の行動とは違い次が終端とは限らない。全ての「カードを引いた後の新しい状態」の最適行動の期待値を計算し、それらをすべて足し合わせる必要があります
ここで重要なのは、「ヒット後の状態」の最適期待値が分かっていないと、「現在の状態」のヒットの期待値が計算できないという点です。
これはまるで、ゴール（終端状態）からスタート（現在の状態）に向かって、一歩ずつ最適解を確定させていくパズルのようです。終端状態の期待値は簡単に確定できます（例：プレイヤーがバーストしたら期待値は0）。その結果を使って一つ前の状態の期待値を計算し、さらにその結果を使って、また一つ前へ…と、最適値が波のように伝播していくイメージです。
最適行動の計算 実装編
準備
最適解計算のロジックは複雑になりそうなので、専用のフォルダを用意しましょう。
バックエンド担当のapiフォルダの中に、新たにstrategyフォルダを作成しました。
.
├── game(folder)
├── go.mod
├── go.sum
├── handlers(folder)
├── main.go
├── package-lock.json
├── services(folder)
+└── strategy(folder)
最適解計算のために必要な諸々を、`strategy/common.go/に定義することにしました。
（本来はもっとファイル分割するべきですが、今回は小規模アプリのため横着しました）
まず、カードの出現確率をもつmapを用意しておきます。
var cardProbabilities = map[int]float64{
1: 1.0 / 13.0, 2: 1.0 / 13.0, 3: 1.0 / 13.0, 4: 1.0 / 13.0,
5: 1.0 / 13.0, 6: 1.0 / 13.0, 7: 1.0 / 13.0, 8: 1.0 / 13.0,
9: 1.0 / 13.0, 10: 4.0 / 13.0,
}
[10]だけ出現確率が高い理由を解説します。
ブラックジャックはルール上、[10,J,Q,K]が同等であり、すべて[10]とみなしても問題ありません。2
アプリ本体では演出上区別していましたが、ここでは高速化のために状態をまとめす。
続いて、ゲームの状態を表す構造体を新たに定義します。
// 戦略計算用の状態 game.goのGameStateより簡素
type StrategyState struct {
Player StrategyHand
Dealer StrategyHand
HasHit bool
}
// 戦略計算用の手札 game.goのHandより簡素
type StrategyHand struct {
Sum int
HasAce bool
}
// 新たな表現用のスコア計算関数
func calculateScore(sHand StrategyHand) int {
// バースト
if sHand.Sum > 21 {
return 0
}
if sHand.HasAce && sHand.Sum+10 <= 21 {
return sHand.Sum + 10
}
return sHand.Sum
}
今まで使っていたgame.goで定義していたゲーム状態では、1枚1枚の手札の情報を別個に持っていました。
ルール上最適行動に必要なのは「手札の数字の合計」「エースを持っているか」「ヒット済みか(=サレンダー可能か)」の3つだけなので、ここではよりシンプルな状態表現を用意します。
新旧を比較するとこのようなイメージです。
- 旧手札表現: ダイヤのQ + ハートのA + スペードの2
- 新手札表現: 合計スコア13 ; エースを持っている ; ヒット済みのためサレンダー不可
再帰計算の実装
前述した再帰計算を実際にコーディングしていきます。
中心となるのは、ある状態StrategyStateを受け取り、各行動の期待値を計算するCalculateAllExpectedPayouts関数です。
package strategy
// メモ化なしのブラックジャック戦略計算用構造体
// あらゆる可能性を全探索し、期待値を足し合わせることで、最適解を求める。
type UncachedCalculator struct{}
func NewUncachedCalculator() *UncachedCalculator {
return &UncachedCalculator{}
}
// ディーラーのアップカードから、ディーラーのスコア分布を計算する（メモ化なし）
func (c *UncachedCalculator) GetDealerScoreDistribution(dealerHand StrategyHand) map[int]float64 {
currentScore := calculateScore(dealerHand)
if currentScore >= 17 {
return map[int]float64{currentScore: 1.0}
}
if currentScore == 0 {
return map[int]float64{0: 1.0}
}
result := make(map[int]float64)
for card, prob := range cardProbabilities {
nextSum := dealerHand.Sum + card
nextHasAce := dealerHand.HasAce || (card == 1)
nextHand := StrategyHand{Sum: nextSum, HasAce: nextHasAce}
subDist := c.GetDealerScoreDistribution(nextHand)
for score, subProb := range subDist {
result[score] += prob * subProb
}
}
return result
}
// プレイヤーのスコアとディーラーの手札から、スタンド時の期待払い戻し（payout）を計算する（メモ化なし）
func (c *UncachedCalculator) CalculateStandExpectedPayout(playerScore int, dealerHand StrategyHand) float64 {
if playerScore == 0 {
return 0.0
}
dealerDist := c.GetDealerScoreDistribution(dealerHand)
expectedPayout := 0.0
for dealerScore, prob := range dealerDist {
if dealerScore < playerScore {
expectedPayout += 2.0 * prob
} else if dealerScore == playerScore {
expectedPayout += 1.0 * prob
}
}
return expectedPayout
}
// ゲームの状態から、各アクションの期待払い戻しを計算する（メモ化なし）
func (c *UncachedCalculator) CalculateAllExpectedPayouts(state StrategyState) StrategyExpectedPayouts {
var expectedPayouts StrategyExpectedPayouts
playerScore := calculateScore(state.Player)
if playerScore == 0 {
expectedPayouts.StandPayout = 0
expectedPayouts.HitPayout = 0
if !state.HasHit {
expectedPayouts.SurrenderPayout = 0.5
expectedPayouts.BestPayout = 0.5
} else {
expectedPayouts.SurrenderPayout = 0.0
expectedPayouts.BestPayout = 0.0
}
return expectedPayouts
}
standPayout := c.CalculateStandExpectedPayout(playerScore, state.Dealer)
expectedPayouts.StandPayout = standPayout
if !state.HasHit {
expectedPayouts.SurrenderPayout = 0.5
} else {
expectedPayouts.SurrenderPayout = 0.0
}
hit := 0.0
for card, prob := range cardProbabilities {
nextSum := state.Player.Sum + card
nextHasAce := state.Player.HasAce || (card == 1)
nextHand := StrategyHand{Sum: nextSum, HasAce: nextHasAce}
nextState := StrategyState{Player: nextHand, Dealer: state.Dealer, HasHit: true}
hit += c.CalculateAllExpectedPayouts(nextState).BestPayout * prob
}
expectedPayouts.HitPayout = hit
best := expectedPayouts.StandPayout
if expectedPayouts.HitPayout > best {
best = expectedPayouts.HitPayout
}
if expectedPayouts.SurrenderPayout > best {
best = expectedPayouts.SurrenderPayout
}
expectedPayouts.BestPayout = best
return expectedPayouts
}
特に注目すべきは、ヒットの期待値を計算している部分です。
c.CalculateAllExpectedPayouts(nextState).BestPayoutという部分で、自分自身を再帰的に呼び出しています。これにより、カードを引いた後の次の状態で得られるであろう最善の期待値を取得し、それにカードを引く確率 prob を掛けています。これをすべてのカードのパターンで合計することで、ヒットアクションの期待値が求まるわけです。
スタンド時の期待値CalculateStandExpectedPayoutも、内部ではディーラーの最終スコア分布を計算するためにGetDealerScoreDistributionという再帰関数を呼び出しています。ディーラーの行動は「スコアが17以上になるまでヒットする」という固定ルールなので、これも同様に再帰で全パターンを計算できるのです。
メモ化による高速化
理論
現在のプログラムはとても非効率的であり、爆発的な計算量を持っています。
なぜなら、同じ状態に対する計算を何度も繰り返すためです。
「プレイヤーの手札合計が18(エースなし)、ディラーは2を所持」という状況を考えます。
この状態に至るルートは無数にあります。（合計16から2を引いたときや、合計15から3を引いたとき等)
どこからこの状態に辿り着いたとしても、結局最適解は同じはずです。
そのため、計算結果をキャッシュに保存することで高速化が見込めます。
- 初めて出会う状況 -> 真面目に最適行動を計算。結果をmapに保存しておく
- 既知の状況 -> mapの最適行動を読み出すだけ。超高速
このような手法はメモ化再帰と呼ばれます。よく名前を聞く(かもしれない)動的計画法とも、本質的には同じものです。
実装
f
type Calculator struct {
dealerMemo map[StrategyHand]map[int]float64
standPayoutMemo map[standPayoutKey]float64
allExpectedPayoutsMemo map[StrategyState]StrategyExpectedPayouts
mu sync.RWMutex
}
// プレイヤーのスコアとディーラーの手札から、スタンド時の期待払い戻し（payout）を計算する
func (c *Calculator) CalculateStandExpectedPayout(playerScore int, dealerHand StrategyHand) float64 {
// キャッシュがあれば、計算せずにそれを再利用
key := standPayoutKey{playerScore: playerScore, dealerHand: dealerHand}
c.mu.RLock()
if v, ok := c.standPayoutMemo[key]; ok {
c.mu.RUnlock()
return v
}
c.mu.RUnlock()
// キャッシュがない場合は、普通に計算(同じなので省略）
// キャッシュに結果を保存
c.mu.Lock()
c.standPayoutMemo[key] = expectedPayout
c.mu.Unlock()
return expectedPayout
if v, ok := c.standPayoutMemo[key]; ok {のところで、mapに問い合わせをして既知の状態かを確かめています。
- ヒットした場合
- vには計算済みの期待値構造体が、okにはtrueが入る
- ヒットしない場合
- vにはnil,okにはfalseが入る
第二引数でokを受け取るのがGoっぽくていい感じですね。
もう一つのポイントは、sync.RWMutexによる排他制御です。
今回のプログラムはwebアプリのAPIとして利用する予定なです。最適行動のmapを同時に複数のリクエストが弄る可能性があり、これは予期せぬバグの原因となりかねません。
c.mu.Lock()とc.mu.Unlock()に囲まれている処理は他のスレッドから保護され、安全にmapを操作することができるようになります。
テスト
最適行動の計算のテストを書きたいのですが、計算結果が本当に合ってるかを知るすべはありません。
普通のテストのようにif got != tc.expectedみたいな書き方はできないわけです。
仕方がないので、printで出力の様子を見るだけのテストを作ります。
func TestCalculateAllExpectedPayouts_Calculator(t *testing.T) {
calc := NewCalculator()
// 例: プレイヤーA, ディーラー7, ヒットしていない
state := StrategyState{
Player: StrategyHand{Sum: 1, HasAce: true},
Dealer: StrategyHand{Sum: 7, HasAce: false},
HasHit: false,
}
expectedPayouts := calc.CalculateAllExpectedPayouts(state)
fmt.Printf("Hit: %f, Stand: %f, Surrender: %f, Best: %f\n", expectedPayouts.HitPayout, expectedPayouts.StandPayout, expectedPayouts.SurrenderPayout, expectedPayouts.BestPayout)
// プレイヤー16, ディーラー10, ヒットしていない
state2 := StrategyState{
Player: StrategyHand{Sum: 16, HasAce: false},
Dealer: StrategyHand{Sum: 10, HasAce: false},
HasHit: false,
}
expectedPayouts2 := calc.CalculateAllExpectedPayouts(state2)
fmt.Println("プレイヤーが11と5を持ち、ディーラーが10を持つ場合の、各アクションの期待払い戻し:")
fmt.Printf("Hit: %f, Stand: %f, Surrender: %f, Best: %f\n", expectedPayouts2.HitPayout, expectedPayouts2.StandPayout, expectedPayouts2.SurrenderPayout, expectedPayouts2.BestPayout)
}
この関数はTestから始まりますが、printしかしていないので絶対に失敗しないテストです。
このようなTestは通常の実行(go test)では無視されます。
go test -vとvオプションを指定すると、printの内容が標準出力に出てきます。
プレイヤーがAを持ち、ディーラーが7を持つ場合の、各アクションの期待払い戻し:
Hit: 1.457369, Stand: 0.524625, Surrender: 0.500000, Best: 1.457369
プレイヤーが11と5を持ち、ディーラーが10を持つ場合の、各アクションの期待払い戻し:
Hit: 0.430693, Stand: 0.424218, Surrender: 0.500000, Best: 0.500000
最初の状況では、Aを持っているので押せ押せでヒットした方が良いみたいです。期待値が1を超えているので、掛け金以上の払い戻しが期待できます。
二つ目の状況では、ヒットもスタンドも期待値が非常に低いです。この場合は降参するのがまだマシなようですね。
### ベンチマークテスト
メモ化の効果がどれだけ合ったか気になるので、ベンチマークテストを作ります。
ベンチマークテストとは関数の速度を測るためのテストのことで、Goでは簡単かつ強力なベンチマークテストのサポートがあります。
// ベンチマーク本体
func benchmarkCalculateAllExpectedPayouts(b *testing.B, calc interface {
CalculateAllExpectedPayouts(StrategyState) StrategyExpectedPayouts
}) {
states := []StrategyState{
// 適当な状態を3つ用意
{Player: StrategyHand{Sum: 2, HasAce: true}, Dealer: StrategyHand{Sum: 1, HasAce: true}, HasHit: false},
{Player: StrategyHand{Sum: 18, HasAce: false}, Dealer: StrategyHand{Sum: 10, HasAce: false}, HasHit: false},
{Player: StrategyHand{Sum: 15, HasAce: false}, Dealer: StrategyHand{Sum: 9, HasAce: false}, HasHit: true},
}
b.ResetTimer()
for i := 0; i < b.N; i++ {
for _, state := range states {
_ = calc.CalculateAllExpectedPayouts(state)
}
}
}
func BenchmarkCalculateAllExpectedPayouts_Calculator(b *testing.B) {
benchmarkCalculateAllExpectedPayouts(b, NewCalculator())
}
func BenchmarkCalculateAllExpectedPayouts_UncachedCalculator(b *testing.B) {
benchmarkCalculateAllExpectedPayouts(b, NewUncachedCalculator())
}
適当に用意した3つの状態にたいして、メモ化バージョンと愚直バージョンそれぞれで最適行動を求めています。
ベンチマークテストの動作は少々黒魔術的ですが、大事なのはこの部分です。
//bは *testing.B
for i := 0; i < b.N; i++ {
// 測りたい処理をここに書く
}
Testから始まる関数が自動的にテスト関数として認識されたように、
Benchmarkから始まる関数は自動的にベンチマーク関数として認識されます。
ベンチマークテストを実行するにはgo test -bench=.というオプションをつける必要があります。
Goはこのforループを何度も回し、十分な計測データが取れたと判断したらループを抜けます。（そのためb.Nの値は自動的に設定され、ユーザーは基本的に触りません）。かかった時間を計測してレポートにまとめてくれます。
今回作った関数では以下のような結果が出ました。
BenchmarkCalculateAllExpectedPayouts_Calculator-12 17933043 66.00 ns/op
// 以下、BenchmarkCalculateAllExpectedPayouts_UncachedCalculatorがタイムアウトしたという長いエラー
メモ化した関数は3つの状態に対して、66ナノ秒で結果を求めることができています。
(Goは17933043回の検証によりこの結果を出しています。これが自動設定されたb.Nです)
一方で、メモ化をしていない方の関数は、制限時間の3分をすぎても処理が終わらず、タイムアウトになってしまいました。
計算量爆発により、天文学的な速度の違いが出てしまいました！！
まとめ
この記事ではブラックジャックの最適解を計算し、メモ化による高速化の威力も見ることができました
今後は、
- 最適行動の計算を、webアプリに組み込む
- ゲームルールをいじれるようにする
- 最適行動も適応的に計算できるようにする
- ヒット、スタンド、サレンダー以外のアクションの実装
などを行なっていく予定です。