2016-06-21

Mac用とiOS用のフレームワークを作ってみた。

技術 Swift

ここで最後に触れた問題が、これ。

NSKeyedArchiver/NSKeyedUnarchiverでオブジェクトをエンコード/デコードすると、クラス名が(モジュール名).(クラス名)となるため、ある実行ファイルで保存したファイルを他の実行ファイルでロードすると、例外が発生する。

この問題があるので、例えば、

Mac用のアプリを作って学習を行う。
学習で得られたAIをエンコードしてファイルに保存する。
iOS用のアプリで保存されたファイルをデコードしてAIを復元する。

としようとすると、モジュール名が異なってデコードに失敗するという問題が出てくる。

もちろん、保存/復元するときに、NSKeyedArchiver/NSKeyedUnarchiverを使わず、Dictionaryとかにデータを置き直せば、このような問題は起きない。
強化学習用のニューラルネットワークをSwiftで書いてみた。（その6） - いものやま。でちょっと言及してたのは、このこと。
ただ、上記の記事でも言及してる通り、再帰的な構造を持つので、かなり面倒・・・

これを解決するもう一つの方法は、フレームワークを作ること。
フレームワークを作ってMac用のアプリとiOS用のアプリでそれぞれ使えば、フレームワークはアプリとモジュールが異なるので、独立したモジュール名になり、Mac用のアプリでもiOS用のアプリでもクラス名が同じ(フレームワークのモジュール名).(クラス名)になってくれる。

実際にやろうとすると起こる問題

ただ、これをいざやろうとすると、思った以上にいろいろな罠が・・・

まず、同じバイナリのフレームワークをMac用のアプリとiOS用のアプリの両方に使うことは出来ない。
これは考えてもみれば当然で、Macはx86_64アーキテクチャ、一方iOSはARMアーキテクチャなので、機械語のレベルで動作環境が異なってる。
なので、Mac用のフレームワークとiOS用のフレームワークは、それぞれ別のバイナリを用意してやらないといけない。

その上で、Mac用とiOS用のフレームワーク名は同じにしないといけない。
というのも、フレームワーク名がそのままモジュール名となるので、それが変わってしまったら、やろうとしていたNSKeyedArchiver/NSKeyedUnarchiverによるエンコード/デコードが出来なくなってしまうから。

このとき壁となるのが、1つのプロジェクトで同名のターゲットを作ることが出来ないという制約。
この制約がなければ、プロジェクトにMac用のフレームワークのターゲットとiOS用のフレームワークのターゲットを同名で用意すればいいだけなんだけど、この制約があるので、このようには出来ない。

解決方法

結果、試行錯誤して得られたのが、次の方法：

入れ物となるプロジェクトを作る。
入れ物となるプロジェクトにソースコードを用意する。
ビルド用のサブプロジェクトをMac用とiOS用に用意する。
ビルド用のサブプロジェクトにターゲットを追加する。
ビルド用のサブプロジェクトにソースコードを追加する。
それぞれのサブプロジェクトでビルドを行う。

正直、かなり手間・・・
まぁ、確かにちょっと特殊なユースケースなので、仕方ないのかもしれないけど。

以下で、手順の詳細を見ていく。

入れ物となるプロジェクトを作る

まずは、入れ物となるプロジェクトを作るところから。

その前に。後々アプリを作るプロジェクトも追加するので、最初にワークスペースを用意しておくといい。
ここでは、MultiTargetというフォルダを用意して、その中にMultiTarget.xcworkspaceというワークスペースを用意した。

f:id:yamaimo0625:20160619232551p:plain

まだ中身は空っぽ。
ここに、入れ物となるプロジェクトを作っていく。

まず、左下の"+"ボタンから、"New Project..."を選択。

f:id:yamaimo0625:20160619232921p:plain

ここで、空のプロジェクトを作るために、"Other"の中にある"Empty"という雛形を選ぶ。

f:id:yamaimo0625:20160619233031p:plain

"Empty"という雛形を選んだら、プロジェクト名を入力し（ここでは安直に"Test"とした。実際には"XYZFramework"といったようにした方がいい）、プロジェクトを作成する。
このとき、MultiTargetワークスペースに追加するようにしておく。
バージョン管理を行いたい場合、"Create Git repository on ..."にチェックも忘れずに。

f:id:yamaimo0625:20160619233416p:plain

これで入れ物となるプロジェクトが出来た。

入れ物となるプロジェクトにソースコードを用意する

入れ物となるプロジェクトが出来たら、ソースコードの用意。
Mac用のフレームワークもiOS用のフレームワークも、ソースコード自体は共通したものを使うので、ソースコードはこの入れ物となるプロジェクトに用意する。

"Common"というグループ（※名前は任意）を入れ物となるプロジェクトの下に作り、フォルダも作っておく。
そして、そのフォルダに共通で使われるソースコードを用意。

ここでは、以下のような簡単なコードを用意した。

f:id:yamaimo0625:20160619234038p:plain

ビルド用のサブプロジェクトをMac用とiOS用に用意する

さて、ここからが肝心。
ビルドを行うためのサブプロジェクトを、この入れ物のプロジェクトに追加していく。

まず、入れ物となるプロジェクトを選択した状態で、左下の"+"ボタンから、"New Project..."を選択。

f:id:yamaimo0625:20160619234447p:plain

そして、"Other"から"Empty"の雛形を選ぶ。
Mac用のフレームワークを作るときも、iOS用のフレームワークを作るときも、"Cocoa Framework"や"Cocoa Touch Framework"を選ばない、というのがポイント。

f:id:yamaimo0625:20160619234846p:plain

なんでこんなことをするのかというと、プロジェクト名とターゲット名を別にしたいから。

冒頭で述べた通り、今、ターゲット名はMac用でもiOS用でも同じにしたいという要求がある。
けど、一方で、同じプロジェクト名は使えない。
ここで、もし"Cocoa Framework"や"Cocoa Touch Framework"を選んでしまうと、プロジェクト名と同じターゲット名が自動的に作られてしまう。
そうなると、プロジェクト名を同じに出来ないということから、異なるターゲット名が自動で作られてしまうことになる。
これは都合が悪い。

もちろん、あとでターゲット名を変えたりすることも出来るのだけど、そのためにいろいろと修正が必要になるので、そういった手間が必要になるくらいなら、最初は空のプロジェクトを作って、あとからターゲットを追加した方が簡単。

なお、サブプロジェクトを作るとき、入れ物となるプロジェクト（今回の場合、"Test"）のグループに追加するというのを間違えないように。

f:id:yamaimo0625:20160619235558p:plain

さて、ここではMac用のサブプロジェクトを"Test_Mac"という名前、iOS用のサブプロジェクトを"Test_iOS"という名前で、それぞれ用意した。

f:id:yamaimo0625:20160619235656p:plain

見ての通り、まだ中身は空っぽ。
ここにターゲットを追加していく。

ビルド用のサブプロジェクトにターゲットを追加する

ターゲットを追加するプロジェクトを選択した状態で、"TARGETS"の下の方にある"+"ボタンを押して、ターゲットを追加する。

f:id:yamaimo0625:20160620222953p:plain

そして、Mac用のフレームワークを作るなら、"Cocoa Framework"、iOS用のフレームワークを作るなら、"Cocoa Touch Framework"を選択。

f:id:yamaimo0625:20160620223053p:plain

f:id:yamaimo0625:20160620223224p:plain

そのあと、"Product Name"にフレームワーク名にしたい名前をに入力する。

f:id:yamaimo0625:20160620223132p:plain

このとき、Mac用のフレームワークもiOS用のフレームワークも同じ名前にしておくのがポイント。

両方にターゲットを追加すると、以下のようになる。

f:id:yamaimo0625:20160620223959p:plain

まだビルドされていないので赤字になっているけど、同名のフレームワークがビルドされるようになっていることが分かると思う。

ビルド用のサブプロジェクトにソースコードを追加する

ターゲットも追加できたので、あとはサブプロジェクトにソースコードを追加するだけ。

ソースコードを追加するサブプロジェクトを選んだ状態で、コンテキストメニューから"Add Files to (サブプロジェクト)..."を選択。

f:id:yamaimo0625:20160620234255p:plain

そして、共通で使用するソースコードが入っているフォルダを選択する。

f:id:yamaimo0625:20160620234841p:plain

追加すると、こんな感じ。

f:id:yamaimo0625:20160620235301p:plain

ちなみに、同じ名前のソースコードが3つあるように見えるけど、実体は1つで、全部同じファイルになっている。
なので、1つのファイルを編集すれば、他のファイル（と言っても同じファイルなんだけど）の内容も同時に変わる。

最終的なフォルダ階層は、以下のような感じ。

f:id:yamaimo0625:20160620235527p:plain

それぞれのサブプロジェクトでビルドを行う

ここまできたら、あとはビルドするだけ。

スキームを切り替えて、"Product"メニューから"Build"を選べば、それぞれのフレームワークがビルドされる。

f:id:yamaimo0625:20160620235646p:plain

アプリの作成

せっかくなので、作ったフレームワークを使って簡単なアプリを作ってみる。

アプリを作る場合、同じワークスペースでプロジェクトを追加すると、作ったフレームワークをそのまま参照できるのでいい。
ということで、ワークスペースにプロジェクトを追加。
"Command Line Tool"の雛形を選ぶ。

f:id:yamaimo0625:20160621000246p:plain

追加するときには、入れ物となるプロジェクトに追加するのではなく、ワークスペースに追加するように注意。

f:id:yamaimo0625:20160621000427p:plain

プロジェクトを作ったら、ターゲットにリンクするフレームワークを追加する。
"TARGETS"の"Build Phases"、"Link Binary with Libraries"の"+"ボタンを押して、リンクするフレームワークを追加。

f:id:yamaimo0625:20160621000653p:plain

ダイアログの"Workspace"のところに作ったフレームワークが候補として出るので、適切なものを選択する。
Mac用とiOS用が同じ名前であるので、間違えないようにw（プロジェクト名でMac用かiOS用かは分かる）

f:id:yamaimo0625:20160621000917p:plain

あとはmain.swiftをちょろちょろっと。

f:id:yamaimo0625:20160621000941p:plain

作ったフレームワークは、import "(作ったフレームワーク名)"とすれば、使うことが出来る。

あとはビルドして実行すればOK。

・・・で終わらせたいんだけど、コマンドラインツールの場合、ちょっと問題があって、もう一手間（＾＾；

このまま実行すると、ビルドは成功するんだけど、"libswiftXXX.dylib"がないと怒られて、実行時エラーになるかもしれない。
その場合、フレームワークのターゲットのビルド設定で、"Build Settings" - "Build Options" - "Embedded Contnt Contains Swift Code"の設定を"YES"に変えてやる必要がある。
こうして実行すれば、実行時に警告がたくさん出る問題が別に起きてくるんだけど、実行自体は出来るようになる。

※これは現状のSwiftの仕様バグだと思う。
現状、Swiftで書かれたコードを動かすには、ランタイムで"libswiftXXX.dylib"という動的ライブラリが必要になっている。
Swiftで普通のアプリを作った場合には、このライブラリがバンドルのFrameworks内に存在するので、問題なくロード出来るのだけど、コマンドラインアプリの場合には、バンドルではないので、これらのライブラリが存在しない。
じゃあ、それらのライブラリが存在しない状態で、コマンドラインアプリがどうして動くのかといえば、コマンドラインアプリの場合、おそらくこのライブラリが静的にリンクされているから。
けど、フレームワークを使おうとした場合には、動的ライブラリはファイル名で検索がかけられてロードされるので、実際にはリンクすべきシンボル自体はコマンドラインアプリのバイナリの中に存在しているのだけど、フレームワークのSwiftのコードからはこのライブラリを見つけることが出来ず、ロードに失敗するのだと思う。
なお、"Embedded Contnt Contains Swift Code"のオプションは、フレームワークがObjective-Cなどで書かれたアプリから利用されたときのためのもの。
このオプションをつけると、フレームワークのバンドル内にFrameworksフォルダが用意され、そこにこれらのライブラリがコピーされるようになっている。
なんでそうするのかというと、Objective-Cなどで書かれたアプリの場合、アプリのバンドル内に"libswiftXXX.dylib"などの動的ライブラリが存在しないので、フレームワークは自前でこの動的ライブラリを用意してやらないといけないから。
そこで、このオプションをつけて動的ライブラリのコピーを自前で持っておけば、アプリ側がこれらのライブラリを持っていなくても、ちゃんと動くようになってくれる。
ということで、このような挙動になっているので、このオプションをつけると、コマンドラインアプリの場合もちゃんとロードが出来るようになる。
ただ、今度はロードされたモジュール内と、静的にリンクされたコマンドラインアプリ内に、同じシンボルが2つ存在してしまうことになる。
これが新たに出てくる警告の正体。
なので、本当は"libswiftXXX.dylib"などの動的ライブラリはシステムのロード可能なパスに置かれていて、コマンドラインアプリを作った場合も、ランタイムで動的にロードするとなっていないといけない。

今日はここまで！

2016-05-27

ペアーズのオリジナルルール「ヤック・チック・ノック・ダウン」を考えてみた。

ゲーム

テンデイズゲームズから日本語版が発売された、ペアーズ。

ペアーズ日本語版 | テンデイズゲームズ

1が1枚、2が2枚、・・・、10が10枚というカード構成で、ギャンブルゲームを中心とした様々なルールが用意されていて、とても面白い。

そして、今回、日本語版の発売を記念して、テンデイズゲームズで「ペアーズ・ルールデザインコンテスト」が開催されることとなった。

「ペアーズ」ルールデザインコンテスト開催のお知らせ – テンデイズゲームズブログ

なので、自分もさっそくオリジナルルールを考えて応募してみた。

ブログなどで公開してもいいということだったので、公開してみる。
タイトルは、「ヤック・チック・ノック・ダウン」（Yuck, Chick, Knock, Down）！

概要

ヤック・チック・ノック・ダウンは、ペアーズデッキ一組を使ったギャンブルゲーム。
各プレイヤーは、山札からカードを引いてくることで、自分の場と手札の合計を出来るだけ大きくし、ポットのチップを獲得することを目指す。
けど、自分の場にペアが出来てしまうと、脱落。
はてさて、蛮勇 (Yuck)、臆病 (Chick)、静観 (Knock)、撤退 (Down) のどれが正しいのか？

プレイ人数：4人〜6人
必要なもの：ペアーズデッキ一組、チップ一人あたり50枚程度
プレイ時間：30分程度

ゲームの準備、進行、目的

全員が同じ枚数のチップを持ってゲームをスタート。

ゲームは複数ラウンド行う。
各ラウンドでラウンドの勝者を決め、ラウンドの勝者はポットのチップをすべて獲得する。

誰かがチップを支払えなくなったら、そのラウンドでゲームは終了。
（もしくは、遊ぶラウンド数を最初に決めておいて、そのラウンド数が終わったら終了）

ゲームが終わったとき、チップをもっとも多く持っていたプレイヤーが、ゲームの勝者となる。

各ラウンドの進行

各ラウンドの最初に、各プレイヤーは参加費として、ポットに1チップずつ支払う。

すべてのカードを裏向きにしてよく混ぜ、各プレイヤーに裏向きで1枚ずつ配り、各プレイヤーの手札とする。
続いて、各プレイヤーの前に表向きで1枚ずつ配り、各プレイヤーの場札とする。
残ったカードは裏向きのまま山札とする。

プレイヤーは自分の手札を見ることが出来るけど、他のプレイヤーには見られないように。

最初のラウンドは、場札の数字がもっとも小さいプレイヤーがスタートプレイヤーになる。
もし複数いた場合、その中から適当な方法でスタートプレイヤーを決める。
2ラウンド目以降は、直前のラウンドの勝者がスタートプレイヤーになる。

スタートプレイヤーから順に、脱落していないプレイヤーは時計回りでアクションを行っていく。
出来るアクションは、次の4つのうち、いずれか1つ：

ヤック
チック
ノック
ダウン

各アクションの詳細は後述。

脱落していないプレイヤーが1人だけになったら、そのプレイヤーは即座にラウンドの勝者となる。
もしくは、脱落していないプレイヤー全員が連続でノックを行った場合、ショーダウンを行い、ラウンドの勝者を決定する。
ショーダウンの詳細は後述。

ラウンドの勝者が決まったら、ラウンドの勝者はポットのチップをすべて獲得する。
そして、次のラウンドを行う。

アクションの詳細

ヤック

山札からカードを1枚めくり、自分の場札に加える。

このとき、もし自分の場札にペアが出来てしまったら、脱落。
ペアになったカードの数字分のチップをポットに支払う。
例えば、7のペアが出来てしまったら、ポットに7チップ支払う。
そのあと、脱落したことを示すために、自分の場札と手札をすべて裏向きにする。

チック

まず、自分の手札の枚数と同じだけのチップをポットに支払う。
そして、山札からカードを1枚引き、自分の手札に加える。

このとき、もし自分の手札でペアが出来てしまったり、自分の場札と手札とでペアが出来てしまったとしても、脱落はしない。

ノック

机をノック。
そして、手番が次のプレイヤーに移る。

一度ノックしたあとでも、再び自分の手番が回ってくれば、アクションを行うことが出来る。

ダウン

表向きになっている場札（他のプレイヤーの場札も含む）のうち、好きな1枚を自分の手元に持ってくる。
そのあと、持ってきたカードの数字分のチップをポットに支払い、脱落する。
脱落したことを示すために、持ってきたカードと自分の場札と手札をすべて裏向きにする。

ショーダウンの詳細

脱落していないプレイヤー全員が連続でノックを行った場合、ショーダウンを行う。

最後にノックしたプレイヤーの次の手番のプレイヤーから順に、以下のようにショーダウンしていく：

自分の手札をすべて表向きにし、自分の場札に加える。
このとき、もし自分の場札にペア（3枚以上も含む）が出来てしまったら、脱落。
ペアになったカードの数字分のチップをポットに支払う。
ペアになったカードが複数組あった場合、そのそれぞれについて支払う。
例えば、場札が7, 7, 8, 8, 8, 10になった場合、合計で15チップをポットに支払う。

もし、ショーダウンしたプレイヤーが次々に脱落し、脱落していないプレイヤーがショーダウンしていない1人だけになった場合、そのプレイヤーはショーダウンすることなく、ラウンドの勝者となる。

全員がショーダウンを行ったら、脱落していないプレイヤーで場札の数字の合計を比較する。
場札の数字の合計がもっとも大きいプレイヤーが、ラウンドの勝者となる。
もし、場札の数字の合計がもっとも大きいプレイヤーが複数いた場合、その中でより後にショーダウンしたプレイヤーがラウンドの勝者となる。

漏れ抜けがないようにちょっとカッチリした書き方になっているので、難しそうに感じるかもしれないけど、実際にはすごく簡単なルール。
自分の手番では、場札にカードを追加するか、手札にカードを追加するか、ノックしてパスするか、安くチップを支払って降りるかを選択するだけ。
そして、場にペアが出来てしまったら脱落で、脱落しないようにしながら、出来るだけ場札と手札の合計を大きくなるようにする。

何回かテストプレイしてみたけど、自分自身、このルールはけっこう好きw
チックでペアが出来てしまったとしても、他のプレイヤーが全員脱落してしまえば勝ちだから、うまいこと立ち回ればなんとかなる気がするのが面白い。
まぁ、それで脱落した場合、ダメージが大きいので、ダウンして降りたら、相手も実はペアが出来ていたりとかねw

ちなみに、このゲームを遊ぶにはチップが必要だけど、この前ドンキにふらっと寄って買ったチップがなかなか良かった。

ポーカーチップ (中) ゲーム小物

出版社/メーカー: ぼりゅうむわんプロダクツ
メディア: おもちゃ＆ホビー
この商品を含むブログを見る

もちろん、ちゃんとしたポーカーチップとは比べものにならないけど、ほどよい大きさがあって、枚数もそれなりにあり、そのくせ軽いので、持ち運びに便利だと思う。
2組買って中身を組換え、40枚-40枚-20枚といった構成にしておくと、かなり使い勝手がよさそう。

今日はここまで！

2016-05-17

ポーカーのオッズとアウツの話。（その3）

ゲーム数学

昨日はポーカー（テキサスホールデム）でアウツからオッズを計算する方法を説明した。

ポーカーのオッズに関する説明でよく見るのは、ここまで。
といっても、比の形で表されたオッズを使った計算は、ほとんど見たことがないけど。

さて、ここまでの話は、間違ってはいない。
ただ、最初に書いた通り、自分には納得がいかない部分があった。
今日はその話を。

ベットは1回で終わるとは限らない

自分が納得いかなかった部分。
それは、ベットは1回で終わるとは限らないということ。

最初に考えたサイコロの例を思い出して欲しい。
そこでは、参加するかしないかを選択し、参加すると決めたら、あとは実際にサイコロを振るだけ。
勝ちの目が出れば賞金がもらえて、参加費も戻ってくる。
勝ちの目が出なければ、参加費が没収される。

一方、ポーカーを考えて欲しい。
フロップで参加するかしないかを選択し、参加すると決めたとする。
そうすると、ターンがめくられる。
ターンはヒットするかもしれないし、ヒットしないかもしれない。
けど、ヒットしようがしまいが、賞金はもらえず、なぜかまたベットが始まる。

おいおい、ちょっと待てよ、と。
自分は、参加費を払えばある確率に従って賞金がもらえると聞いて、この賭けに参加した。
けど、実際は、参加費を払って勝負に参加したら、別の勝負が始まって、その勝負への参加費がさらに必要だと言われた。
賞金はいつもらえるんだ？
これは詐欺じゃないか？

そう、ここが単純な賭けとポーカーの違い。

カードを1枚めくって、それがヒットするかしないかで勝負が決まるなら、ここまでの話は何の問題もない。
けど、実際にはそこで勝負は決まらず、さらに新しい賭けが始まるだけ。
勝つか負けるかは、そういった賭けをいくつか続けた結果として、最終的に決まる。

そうなると、最初に行った賭けの判断が正しかったのかどうかは、その最初の賭けを見るだけで簡単に判断できるような単純なものではなくなってしまっている。
けど、そのことについて指摘し、ちゃんと計算を行っている人を、自分は見たことがない。

はてさて、単純にポットオッズとオッズを比較する方法は、どれくらい正しいのか。
それとも、もっとハンド全体を通しての判断を行わないといけないのか。
それについて、以下では議論していく。

問題設定

ここでは、ポーカーを模した、次のようなゲームを考えてみる：

ゲーム1では、ポットに $(K+a)$ 入っていて、参加するにはポットに $a$ 支払う。
ゲーム1に参加しなかった場合、何も起こらない。
ポットに $a$ 支払ってゲーム1に参加すると、確率 $(1 - p)$ でゲーム2に、確率 $p$ でゲーム3に移行する。（ただし、 $0 \le p \lt \frac12$ とする）
なお、ゲーム2は負けやすいゲーム、ゲーム3は勝ちやすいゲームである。

ゲーム2では、ポットには $(K+2a+b)$ 入っていて、参加するにはポットに $b$ 支払う。
ゲーム2に参加しなかった場合、何も起こらない。（ゲーム1で支払った $a$ も返ってこない）
ポットに $b$ 支払ってゲーム2に参加すると、確率 $(1-q)$ で負け、確率 $q$ で勝つ。（ただし、 $0 \le q \lt \frac12$ とする）
負けた場合には何ももらえないが、勝った場合にはポットに入っている $(K+2a+2b)$ をもらえる。

ゲーム3もゲーム2と同様で、ポットには $(K+2a+c)$ 入っていて、参加するにはポットに $c$ 支払う。
ゲーム3に参加しなかった場合、何も起こらない。（ゲーム1で支払った $a$ も返ってこない）
ポットに $c$ 支払ってゲーム3に参加すると、確率 $(1-r)$ で負け、確率 $r$ で勝つ。（ただし、 $\frac12 \lt r \le 1$ とする）
負けた場合には何ももらえないが、勝った場合にはポットに入っている $(K+2a+2c)$ をもらえる。

イメージとしては、ヘッズアップで、

ゲーム1は、フロップでポットに $K$ 入っていて、相手が $a$ をベットしてきて、これにコールするかどうか。
ゲーム2は、ゲーム1でコールしたあと、ターンがめくられたけどヒットせず、相手が $b$ をベットしてきて、これにコールするかどうか。
ゲーム3は、ゲーム1でコールしたあと、ターンがめくられてヒットして、相手が $c$ をベットしてきて、これにコールするかどうか。
リバーではお互いチェックする。

という感じ。

それぞれの場合の利益を確認すると、以下のとおり：

ゲーム1に参加しなかった場合、利益は0。
ゲーム1に参加してゲーム2へ移行し、
- ゲーム2に参加しなかった場合、利益は $-a$ 。
- ゲーム2に参加して負けた場合、利益は $-a-b$ 。
- ゲーム2に参加して勝った場合、利益は $K+a+b$ 。
ゲーム1に参加してゲーム3へ移行し、
- ゲーム3に参加しなかった場合、利益は $-a$ 。
- ゲーム3に参加して負けた場合、利益は $-a-c$ 。
- ゲーム3に参加して勝った場合、利益は $K+a+c$ 。

図示すると、次のようになる：

f:id:yamaimo0625:20160516002632p:plain

このゲームにおいて、各ゲームでの正しい判断がどうなっているのかを調べていく。

ゲーム2について

まずはゲーム2について。

ゲーム2に参加した場合の期待値は、以下のとおり：

ただし、 $K' = K + 2a + b$ で、これはゲーム2のポットの最初の金額。

ゲーム2に参加すべきかどうかは、参加した場合の期待値が参加しない場合の期待値以上になっているかどうかだから、

すなわち、ゲーム2の $(\mbox{ポットオッズ}) \ge (\mbox{オッズ})$ と同値になっている。
これはポーカーでサンクコストを考慮してはいけない数学的な理由。 - いものやま。で言及した通り。
というか、元々このような問題を考えていて、サンクコストについてだけ切り出した記事が、上の記事。

なお、ゲーム2自体の期待値は、次のようになっている：

注意すべきは、参加すべきかどうかの判断からはサンクコストの $a$ が消えているけれど、期待値にはサンクコストの $a$ が残っているということ。
これがゲーム1の期待値を計算するときに意味を持つ。

ゲーム3について

ゲーム3はゲーム2と同じ構造なので、同様の議論で、次のようになることが分かる：

ゲーム3の期待値は、以下の通り：

ただし、 $K'' = K + 2a + c$ 。

そして、ゲーム3に参加すべきかどうかは、 $K'' : c \ge (1-r) : r$ かどうかで判断できる。

ゲーム1について

さて、問題はゲーム1。

単純にポットオッズとオッズを比較するのだと、次のような判断を行うことになる：

問題は、この判断が正しいのかどうか。

ゲーム2、ゲーム3の期待値から、ゲーム1に参加したときの期待値 $E$ は、次のようになる：

したがって、ゲーム1に参加すべきかどうかは、次のように判断することになる：

見ての通り、 $(K+a) : a \ge (1-p) : p$ かどうかなんていう単純な判断ではない。

さて、この複雑な判断をどう扱えばいいものなのか・・・？

ゲーム1の近似的な計算

厳密には先程の計算を行わないといけないのだけど、これだと複雑すぎてモノの本質が見えてこない。
そこで、次の2つの仮定を入れることで、近似的に計算が行えるようにしてみる。

入れる仮定は、次の2つ：

$r \approx 1$
$q \approx p$

これらの仮定の意味するところは、以下の通り：

ヒットしてゲーム3に移行した場合、ほぼ間違いなく勝てる
ヒットしなくてゲーム2に移行した場合も、ヒットする確率はゲーム1とほぼ変わらない

実際のゲームは必ずしもこうはならないので、かなり強い仮定ではあるのだけど、これくらい強い仮定を入れないと計算が進まないので、しかたない。
それに、そこまで無理のある仮定でもないし。

まず、 $r \approx 1$ の仮定があると、オッズ $(1-r) : r$ は限りなく0に近くなる。
なので、どんなにポットオッズが悪くてもコールした方が期待値は高くなるので、ゲーム3の期待値は次のように近似できる：

この結果と $q \approx p$ の仮定から、ゲーム1に参加したときの期待値 $E$ は次のように近似できる：

ここから先は、場合分けが必要。

まず、記述しやすくするために、 $\beta = p K' - (1 - p)b$ とする。
このとき、 $\beta \ge 0 \iff K' : b \ge (1 - p) : p$ であることに注意。

$\beta$ を $b$ について整理すると、

なので、 $\beta$ は $b$ に関する一次関数になっていて、 $0 \le p \lt \frac12$ なので、単調減少するようになっている。
これは、 $b=0$ のとき $\beta$ は最大で、 $b$ が大きくなるにつれ $\beta$ は小さくなっていき、 $\beta \lt 0$ になると、ゲーム2に参加しない方がいいということを意味する。

$K' : b \ge (1 - p) : p$ 、すなわち、 $\beta \ge 0$ のとき

ゲーム1に参加したときの期待値 $E$ は、次のようになる：

まず、もし $(K + a) : a \ge (1 - p) : p$ なら、 $E \ge 0$ を近似的に満たす。
なぜなら、そのとき、 $p(K+a) - (1 - p)a \ge 0$ なので、

となるから。
（ $\beta \ge 0$ であることに注意）

そこで、 $(K+a) : a \lt (1 - p) : p$ の場合を考える。

この場合、 $p(K+a) - (1 - p)a \lt 0$ なので、

であるから、

と、近似的に求まる。

すなわち、この場合は、近似的に

となる。

$K' : b \lt (1 - p) : p$ 、すなわち、 $\beta \lt 0$ のとき

この場合、ゲーム1に参加したときの期待値 $E$ は、次のようになる：

よって、この場合は、近似的に

となる。

〜〜〜

さて、以上の議論をまとめると、ゲーム1に参加すべきかどうかの判断は、近似的に次のように表わせることが分かる：

ただし、 $\beta = p K' - (1 - p)b$ で、 $\beta \lt a$ である。

ところで、この数式はどんな意味を持つのか？

インプライド・ポットオッズ

この数式で注目すべきは、 $(K + a + c) : (a - \mbox{max.} \{\beta, 0\}) \ge (K+a) : a$ ということ。
これは、ポットオッズよりもオッズが悪くても、参加した方が期待値が高くなる場合が存在するということを示している。

具体的には、ヒットした場合に相手から引き出せる金額が大きかったり（＝ $c$ が大きい場合）、ヒットしなかった場合の次の勝負でオッズよりも安く勝負に参加できる場合（＝ $\beta$ が大きい場合、すなわち、 $b$ が小さい場合）には、ポットオッズよりも悪いオッズでも、オッズにあう場合があるということ。

よく、インプライド・ポットオッズと呼ばれるオッズがあるけれど、 $(K + a + c) : (a - \mbox{max.} \{\beta, 0\})$ というオッズがまさにそれ。
もっとも、ちゃんと数式で示されることは滅多になく、感覚で語られるだけのことが多いけど。
でも、ちゃんとハンドを通しての期待値を計算すると、このように数式で導き出されてくる。

なお、 $c \rightarrow 0, b \rightarrow \infty$ とすると、 $(K + a + c) : (a - \mbox{max.} \{\beta, 0\}) \rightarrow (K + a) : a$ となる。
なので、単純にポットオッズとオッズを使った判断も、近似的には間違ってはいない。
ただし、それは少しゆるめの判断になっている。

それと、ここまで来て気づく、重要なことがある。
それは、単純な1回のベットのオッズと、ハンドを通してのオッズは、必ずしも一致しないということ。
この事実を知らないと、サンクコストはオッズに影響を与えないということがどれくらい凄いことなのかは、理解できない。

つまり、これまでの議論で分かる通り、ハンドを通してのオッズを計算すると、未来のベットは現在のベットのオッズに影響を与えることが分かる。
それなら、過去のベット（すなわちサンクコスト）も、ハンドを通してオッズを計算すれば、現在のベットのオッズに影響を与えそうなものだけど、実際には過去のベットは現在のベットのオッズに影響を与えない。
そこには非対称性が存在する。

これは重要なことだ。
なぜなら、もし、過去のベットが未来のベットと同様に現在のベットのオッズに影響を与えるのならば、オッズの計算はさらに複雑なものになっていただろう。
けど、この未来と過去に関する非対称性の存在のおかげで、サンクコストについては考えず、インプライド・ポットオッズだけを考えればいいということが分かってくる。

今日はここまで！

2016-05-16

ポーカーのオッズとアウツの話。（その2）

ゲーム数学 Ruby

昨日はサイコロの賭けを題材にオッズの基本的な話をした。

今日はポーカー（テキサスホールデム）でのアウツの話と、オッズとの関係について。

アウツ

昨日はサイコロの賭けを題材にしていたけど、実際に考えたいのはポーカーでのオッズについて。
そのとき必要となるのが、「アウツ」。

「アウツ」とは、ハンドを改善させるカードのこと。
なお、それがめくられれば勝てる可能性がかなり高くなるものに限定される場合もある。
（ハンドは改善されるけど、相手のハンドも改善されるなどで、勝てる可能性は上がらないものは、「ダウツ」（ディスカウント　アウツ）として「アウツ」とは区別して考えたりもする）

例えば、ハンドが $7\spadesuit$ $8\spadesuit$ 、ボードが $9\spadesuit$ $\mathrm{A}\spadesuit$ $10\heartsuit$ $2\diamondsuit$ の場合、現状では何の役も出来ていないけど、リバーで7か8がめくられればワンペア、6かJがめくられればストレート、もしくは何か $\spadesuit$ がめくられればフラッシュが完成する。
なので、アウツは

$7\heartsuit$ $7\diamondsuit$ $7\clubsuit$ → 7のワンペア
$8\heartsuit$ $8\diamondsuit$ $8\clubsuit$ → 8のワンペア
$6\heartsuit$ $6\diamondsuit$ $6\clubsuit$ → 6〜10のストレート
$\mathrm{J}\heartsuit$ $\mathrm{J}\diamondsuit$ $\mathrm{J}\clubsuit$ → 7〜Jのストレート
$2\spadesuit$ $3\spadesuit$ $4\spadesuit$ $5\spadesuit$ $6\spadesuit$ $10\spadesuit$ $\mathrm{J}\spadesuit$ $\mathrm{Q}\spadesuit$ $\mathrm{K}\spadesuit$ → フラッシュ

の、合計21枚となる。
（ただ、実際には、7や8は例えばAのワンペアに勝てないし、Jも相手のハンドがQKのときに10〜Aのストレートを作られる可能性があるので、ダウツになっている可能性がある）

アウツとオッズの関係

さて、この例で、仮にこれらのアウツのどれかがめくられれば確実に勝てるとした場合、オッズはどうなっているのか？

まず、これらのアウツ以外がめくられたときは負けなので、負ける事象数は $46 - 21 = 25$ となる。
一方、これらのアウツがめくられれば勝ちなので、勝つ事象数は $21$ 。
したがって、オッズは $25 : 21 \fallingdotseq 1.19 : 1 ( = 1 : 0.84)$ となる。

このように、アウツからオッズを計算することが出来る。

ちなみに、この場合、オッズは $1 : 0.84$ なので、ポットオッズが $1 : 0.84$ 以上ならーーすなわち、コールするのに必要な金額が現在のポットの84%以下ならーーコールしてリバーを見る価値があるということになる。

プリフロップ、フロップ、ターンでの、アウツに対するオッズを、以下のようにして計算してみた。
なお、ポットの金額と比較しやすいように、左項は100にしてある。

#!/usr/bin/env ruby

preflop_rest = 52 - 2
flop_rest = preflop_rest - 3
turn_rest = flop_rest - 1

odds_right = (0..25).map do |outs|
  [preflop_rest, flop_rest, turn_rest].map do |rest|
    # odds = (rest - outs) : outs
    #      = 100.0 : odds_right
    # so,
    # odds_right = (outs * 100.0) / (rest - outs)
    (outs * 100.0) / (rest - outs)
  end
end

puts "-----+--------------------------------------"
puts "outs | preflop      flop         turn"
puts "-----+--------------------------------------"
odds_right.each_with_index do |(preflop, flop, turn), outs|
  puts (sprintf "%4d | 100.0:%5.1f  100.0:%5.1f  100.0:%5.1f",
                outs, preflop, flop, turn)
end
puts "-----+--------------------------------------"

これを実行して出力すると、以下のようになる：

-----+--------------------------------------
outs | preflop      flop         turn
-----+--------------------------------------
   0 | 100.0:  0.0  100.0:  0.0  100.0:  0.0
   1 | 100.0:  2.0  100.0:  2.2  100.0:  2.2
   2 | 100.0:  4.2  100.0:  4.4  100.0:  4.5
   3 | 100.0:  6.4  100.0:  6.8  100.0:  7.0
   4 | 100.0:  8.7  100.0:  9.3  100.0:  9.5
   5 | 100.0: 11.1  100.0: 11.9  100.0: 12.2
   6 | 100.0: 13.6  100.0: 14.6  100.0: 15.0
   7 | 100.0: 16.3  100.0: 17.5  100.0: 17.9
   8 | 100.0: 19.0  100.0: 20.5  100.0: 21.1
   9 | 100.0: 22.0  100.0: 23.7  100.0: 24.3
  10 | 100.0: 25.0  100.0: 27.0  100.0: 27.8
  11 | 100.0: 28.2  100.0: 30.6  100.0: 31.4
  12 | 100.0: 31.6  100.0: 34.3  100.0: 35.3
  13 | 100.0: 35.1  100.0: 38.2  100.0: 39.4
  14 | 100.0: 38.9  100.0: 42.4  100.0: 43.8
  15 | 100.0: 42.9  100.0: 46.9  100.0: 48.4
  16 | 100.0: 47.1  100.0: 51.6  100.0: 53.3
  17 | 100.0: 51.5  100.0: 56.7  100.0: 58.6
  18 | 100.0: 56.2  100.0: 62.1  100.0: 64.3
  19 | 100.0: 61.3  100.0: 67.9  100.0: 70.4
  20 | 100.0: 66.7  100.0: 74.1  100.0: 76.9
  21 | 100.0: 72.4  100.0: 80.8  100.0: 84.0
  22 | 100.0: 78.6  100.0: 88.0  100.0: 91.7
  23 | 100.0: 85.2  100.0: 95.8  100.0:100.0
  24 | 100.0: 92.3  100.0:104.3  100.0:109.1
  25 | 100.0:100.0  100.0:113.6  100.0:119.0
-----+--------------------------------------

この表は、例えばプリフロップでアウツが10枚の場合、オッズは $100 : 25$ となっているので、コールに必要な金額がポットの金額の25%以下なら、コールする価値がある、といったふうに使うことが出来る。

この表を丸暗記するのはキツイので、オッズの左項を100としたときに、オッズの右項がアウツの何倍になっているのかを計算してみる。
すると、以下のようになる：

-----+--------------------
outs | preflop  flop  turn
-----+--------------------
   0 |     0.0   0.0   0.0
   1 |     2.0   2.2   2.2
   2 |     2.1   2.2   2.3
   3 |     2.1   2.3   2.3
   4 |     2.2   2.3   2.4
   5 |     2.2   2.4   2.4
   6 |     2.3   2.4   2.5
   7 |     2.3   2.5   2.6
   8 |     2.4   2.6   2.6
   9 |     2.4   2.6   2.7
  10 |     2.5   2.7   2.8
  11 |     2.6   2.8   2.9
  12 |     2.6   2.9   2.9
  13 |     2.7   2.9   3.0
  14 |     2.8   3.0   3.1
  15 |     2.9   3.1   3.2
  16 |     2.9   3.2   3.3
  17 |     3.0   3.3   3.4
  18 |     3.1   3.4   3.6
  19 |     3.2   3.6   3.7
  20 |     3.3   3.7   3.8
  21 |     3.4   3.8   4.0
  22 |     3.6   4.0   4.2
  23 |     3.7   4.2   4.3
  24 |     3.8   4.3   4.5
  25 |     4.0   4.5   4.8
-----+--------------------

なので、オッズの左項を100としたとき、オッズの右項はだいたい次のようになっている：

アウツの枚数	オッズの右項
0〜5	アウツの約2倍
6〜10	アウツの約2.5倍
11〜15	アウツの約3倍
16〜20	アウツの約3.5倍
21〜25	アウツの約4倍

一応、上記で求まる近似値と実際の値を比較すると、以下の通り：

-----+--------------------------------------------------
outs | approx.  preflop       flop          turn
-----+--------------------------------------------------
   0 |     0.0    0.0( +0.0)    0.0( +0.0)    0.0( +0.0)
   1 |     2.0    2.0( -0.0)    2.2( -0.2)    2.2( -0.2)
   2 |     4.0    4.2( -0.2)    4.4( -0.4)    4.5( -0.5)
   3 |     6.0    6.4( -0.4)    6.8( -0.8)    7.0( -1.0)
   4 |     8.0    8.7( -0.7)    9.3( -1.3)    9.5( -1.5)
   5 |    10.0   11.1( -1.1)   11.9( -1.9)   12.2( -2.2)
   6 |    15.0   13.6( +1.4)   14.6( +0.4)   15.0( +0.0)
   7 |    17.5   16.3( +1.2)   17.5( +0.0)   17.9( -0.4)
   8 |    20.0   19.0( +1.0)   20.5( -0.5)   21.1( -1.1)
   9 |    22.5   22.0( +0.5)   23.7( -1.2)   24.3( -1.8)
  10 |    25.0   25.0( +0.0)   27.0( -2.0)   27.8( -2.8)
  11 |    33.0   28.2( +4.8)   30.6( +2.4)   31.4( +1.6)
  12 |    36.0   31.6( +4.4)   34.3( +1.7)   35.3( +0.7)
  13 |    39.0   35.1( +3.9)   38.2( +0.8)   39.4( -0.4)
  14 |    42.0   38.9( +3.1)   42.4( -0.4)   43.8( -1.8)
  15 |    45.0   42.9( +2.1)   46.9( -1.9)   48.4( -3.4)
  16 |    56.0   47.1( +8.9)   51.6( +4.4)   53.3( +2.7)
  17 |    59.5   51.5( +8.0)   56.7( +2.8)   58.6( +0.9)
  18 |    63.0   56.2( +6.8)   62.1( +0.9)   64.3( -1.3)
  19 |    66.5   61.3( +5.2)   67.9( -1.4)   70.4( -3.9)
  20 |    70.0   66.7( +3.3)   74.1( -4.1)   76.9( -6.9)
  21 |    84.0   72.4(+11.6)   80.8( +3.2)   84.0( +0.0)
  22 |    88.0   78.6( +9.4)   88.0( +0.0)   91.7( -3.7)
  23 |    92.0   85.2( +6.8)   95.8( -3.8)  100.0( -8.0)
  24 |    96.0   92.3( +3.7)  104.3( -8.3)  109.1(-13.1)
  25 |   100.0  100.0( +0.0)  113.6(-13.6)  119.0(-19.0)
-----+--------------------------------------------------

大体数%の誤差で収まってるのが分かると思う。
（※プリフロップだとアウツが11枚以上だとだいぶ誤差があるけど、プリフロップだとそもそもそんなにアウツは存在しない。また、境界は誤差が大きいので、若干増減させて考えるようにするといい）

日本式のポットオッズの表現の話

なお、日本だとポットオッズは $n : 1$ の形ではなく $(n+1)$ 倍の形で表現されることが多い。
その場合、「ポットの金額 + コールするのに必要な金額」が「コールするのに必要な金額」の何倍かを計算し（これがポットオッズとして扱われる）、その逆数が勝つのに必要な勝率になる。
そして、アウツの約2倍が勝率になるので、それで比較して判断を行う。

ただ、これまでの話を見て分かる通り、比で計算する方が分かりやすかったりする。
あまり馴染みがなく、どう計算に使えばいいのかまで解説されていることはほとんどないので（少なくとも自分は見たことがない）、知られてないけど。

例えば、ターンでフラッシュを待っている状態（アウツは9枚）で、ポットの金額の $\frac15$ をベットされたときに、コールすべきかどうかの判断を考えてみる。

日本式だと、参加費を1としたとき、ポットの金額は5なので、ポットオッズは $1 + 5 = 6$ 倍ということになる。
すると、その逆数は $1 \div 6 \fallingdotseq 0.16$ なので、約16%がコールするのに必要な勝率となる。
そして、アウツは9枚で、勝率はその約2倍の18%なので、コールすべきという判断になる。

比を使う方法だと、ポットオッズは $5:1 = 100:20$ 。
そして、アウツが9枚のとき、オッズの左項を100としたときのオッズの右項は約2.5倍となるので、 $9 \times 2.5 = 22.5$ 。
なので、コールすべきという判断になる。

あるいは、ターンでストレートを待っている状態（アウツは8枚）で、ポットの金額に対して、どれくらいの金額までコールしていいのかを考えてみる。

日本式だと、アウツが8枚のときの勝率は $8 \times2 = 16$ なので、約16%。
この逆数は $1 \div 0.16 \fallingdotseq 6.25$ なので、約6倍のポットオッズならコールしていいことになる。
そうすると、コールに必要な金額を1とした場合、ポットの金額は約5となるので、 $1 \div 5 \fallingdotseq 0.2$ から、ポットの金額の約20%まではコールしていいとなる。

一方、比を使う方法なら、アウツが8枚のとき、オッズの左項を100としたときのオッズの右項は約2.5倍となるので、 $8 \times 2.5 = 20$ で、約20%まではコールしていいということが分かる。

ね、簡単でしょ？

ということで、オッズの計算をするなら、比を使った方法がオススメ。

今日はここまで！

2016-05-15

ポーカーのオッズとアウツの話。（その1）

ゲーム数学

ポーカー（テキサスホールデム）の理論的な話でよく出るのが、オッズとアウツの話。
それ自体は別に問題ないと思うのだけど、自分には納得いかない部分があったので、その話を。

ただ、そもそもオッズとアウツの話が分かっていないとよく分からないと思うので、まずはオッズの基本的な話から。

サイコロの賭け

オッズの話をするために、まずはサイコロを使った賭けを考えてみる。
考えるのは、次のような賭け：

参加費は50円。
サイコロを振って4以上が出れば、100円がもらえて参加費も返ってくる。
ただし、3以下が出た場合、参加費の50円は没収されてしまう。

さて、この賭けに乗るべきか否か？

数学的に考えると、これは当然、乗るべき。
というのも、

賭けに勝つ確率は50%で、その場合の儲けは100円
賭けに負ける確率は50%で、その場合の儲けは-50円

なので、賭けに乗った場合の儲けの期待値は、

$100 \times 0.5 + (-50) \times 0.5 = 25$ 円

となり、プラスの儲けが期待できるから。

このように、儲けの期待値を計算して、儲けの期待値がプラスになれば賭けに乗ればいいし、そうでなければ乗らない方がいいとなる。
基本的には。
（※イカサマとかなければ、ね）

「ポットオッズ」と「オッズ」

ただ、毎回このように期待値を計算すると大変なので、もう少し簡単に計算する方法がある。
そのときに使うのが、「ポットオッズ」と「オッズ」。

「ポットオッズ」とは、次の比のこと：

$(\mbox{賞金額}) : (\mbox{参加費})$

そして、「オッズ」とは、次の比のこと：

$(\mbox{負ける事象数}) : (\mbox{勝つ事象数})$

そして、 $\bf{ (\mbox{ポットオッズ}) \gt (\mbox{オッズ}) }$ であれば、賭けに乗るべきとなる。
（なお、比較しやすいように、普通は右の項が1になるように揃える）

なぜ $(\mbox{ポットオッズ}) \gt (\mbox{オッズ})$ なら賭けに乗るべきなのかは後で説明するとして、とりあえずはさっきの例で確認してみる：

まず、ポットオッズは

$(\mbox{賞金額}) : (\mbox{参加費}) = 100 : 50 = 2 : 1$

一方、オッズは

$(\mbox{負ける事象数}) : (\mbox{勝つ事象数}) = 3 : 3 = 1 : 1$

となり、確かに $(\mbox{ポットオッズ}) \gt (\mbox{オッズ})$ となってる。

別の例でも確認してみる：

今度は、参加費は20円で、サイコロを振って6が出たら100円がもらえて参加費も返ってきて、それ以外だと参加費が没収されるとする。

この場合、儲けの期待値は

$100 \times \frac16 + (-20) \times \frac56 = 0$ 円

なので、トントンといったところ。

これをポットオッズとオッズで計算してみると、

$(\mbox{ポットオッズ}) = 100 : 20 = 5 : 1$
$(\mbox{オッズ}) = 5 : 1$

となり、確かにトントンになっている。

またさらに別の例で、参加費は60円で、サイコロを振って5以上が出たら100円が貰えて参加費も返ってきて、4以下が出たら参加費が回収されるとする。

この場合、儲けの期待値は

$100 \times \frac13 + (-60) \times \frac23 = - \frac{20}{3}$

なので、賭けに乗るべきではない。

ポットオッズとオッズで計算してみても、

$(\mbox{ポットオッズ}) = 100 : 60 = 1.66 \ldots : 1$
$(\mbox{オッズ}) = 4 : 2 = 2 : 1$

であり、 $(\mbox{ポットオッズ}) \lt (\mbox{オッズ})$ なので、確かに賭けに乗るべきでないとなっている。

直感的な説明

さて、では、なぜ $(\mbox{ポットオッズ}) \gt (\mbox{オッズ})$ なら賭けに乗るべきなのかを、直感的に説明してみる。

比較のために、ポットオッズ、オッズの右項は1にすることにする：

$(\mbox{ポットオッズ}) = a : 1$
$(\mbox{オッズ}) = b : 1$

このとき、それぞれの左項の $a$ や $b$ が何を意味するのかを考えてみる。

まず、 $b$ というのは、1回勝つのに対して、何回負けるのかという回数を意味する。
そして、 $a$ というのは、1回負けたときに払う参加費を1とした場合に、勝ったときの儲けがいくらなのかを意味している。

すると、1回負けたときに払う参加費を1とすれば、1回勝つのに対して $b$ 回負けるわけだから、負けて払う参加費の総額は $b$ となる。
一方、1回勝ったときの儲けは $a$ 。
なので、 $a \gt b$ であれば、「勝ったときの儲け」が「負けて払う参加費の総額」より大きくなるので、賭けに乗るべきとなる。

数式を用いた説明

同じことを、数式でも説明してみる。

ポットオッズを $a : 1$ 、オッズを $b : 1$ としたとき、勝ったときの儲けは $a$ 、負けたときの儲けは-1、勝つ確率は $\frac{1}{1+b}$ 、負ける確率は $\frac{b}{1+b}$ となる。

この期待値を計算すると、

$a \times \frac{1}{1+b} + (-1) \times \frac{b}{1+b} = \frac{a-b}{1+b}$

これがプラスであれば賭けに乗るべきなわけだから、 $a \gt b$ 、すなわち、 $(\mbox{ポットオッズ}) \gt (\mbox{オッズ})$ ならば賭けに乗るべき、となる。

今日はここまで！

2016-04-30

ポーカーでサンクコストを考慮してはいけない数学的な理由。

ゲーム数学

久々にポーカー（テキサスホールデム）をやって面白かったので、昔考えたことを。

サンクコストを考慮してはならない

テキサスホールデムに関する理論を見ていると出てくるのが、「サンクコストを考慮してはならない」という話。

テキサスホールデムでは、ベットするタイミングが何回も回ってくることになる。
そうなると、「さっきこれだけベットしたんだから、もう後には引けない・・・」という状況がよくある。
これを諌めるのが、「サンクコストを考慮してはならない」という言葉。
つまり、これまでにいくらチップをつぎ込んできたのかは考えずに、今現在、どれだけ勝てる見込みがあるのかだけを考えろ、と。

これは「コンコルド効果」ーーもうどうやっても失敗すると分かっていても、これまでに注ぎ込んだ資産を諦めることが出来ずに、さらに損失を増やしてしまうことーーを防ぐための言葉とも言えるけど、自分にはどうにも納得がいかなかった。
というのも、その根拠がちゃんと数式で示されていないから。

例えば、『トーナメントポーカー入門テキサスホールデムの基礎理論』には、次のようにしか書かれていない：

既にポットに入れてしまったチップについては、既に投資したコストであり、勝負から撤退しても取り戻すことのできない、勝負に勝つ以外取り戻すことのできないコストとなっています。このようなコストのことを「サンクコスト（埋没費用）」といい、サンクコストについては、既に入ってしまった投資でありコストとして確定してしまっているため、現在の意思決定の合理性を判断する際に考慮してはならない要素とされます。

あるいは、ネットを見てみると、以下のような記述も。

サンクコストという言葉は実は半年前に知ったのですが、それはポーカーでは当たり前の話なんですよね。もちろん、感情的になって今までおカネ出してきたんだし、と判断がブレてしまうプレーヤーも少なくないですが。

これではただの精神論が語られているようにしか見えない。
そうであるならば、もちろん多くの場合には有益な言葉かもしれないけど、場合によってはそれが当てはまらないという可能性だって出てくる。

数式で簡単に示せるのなら示せばいいのに、その数式が出てこないとなると、ますます怪しく感じる。

期待値の計算

結論から言えば、「サンクコストを考慮してはいけない」というのは正しい。

もう少し厳密に言うと、「サンクコストを考慮してもいいけど、結果はサンクコストを考慮しないときと同じになる」。
そして、サンクコストを考慮に入れない方が計算が簡単なので、サンクコストを考慮に入れない方がいい、となる。
これは数学的にちゃんと示すことが出来る。

次のような簡単な例で考えてみる：

ターンまでに、自分は $a$ ドル投資しているとする。
つまり、サンクコストは $a$ ドル。
そして、リバーで相手が $b$ ドルベットしてきて、それにコールすべきかどうか。
勝てる確率は $p \: (0 \lt p \lt 1)$ 。
勝てば合計で $E$ ドル獲得できる。

このとき、

もし、コールするなら、利益の期待値は $pE - a - b$ ドル
コールしないなら、利益の期待値は $-a$ ドル

よって、コールすべきかどうかは、期待値を比較して、

$pE - a - b \ge -a$ なら、コールすべき
$pE - a - b \lt -a$ なら、降りるべき

となる。

ところで、この両辺には、どちらもサンクコストである $-a$ ドルという項が出てきている。
そこで、この判断は次のように簡単にすることが出来る：

$pE \ge b$ なら、コールすべき
$pE \lt b$ なら、降りるべき

つまり、サンクコストを考慮に入れることなく、現在のオッズのみから判断を下せることになる。

結局、サンクコストというのは、判断を行うときの両辺に現れてくるので、打ち消しあってしまい、現在の判断には影響を与えないことになる。
なので、現在の判断には考慮に入れず、現在のオッズからのみ判断を下すべきだ、となる。

これくらい簡単に数学的に示せるのだから、本とかでもチャチャっと示してくれればいいのにね。

今日はここまで！

2016-04-16

CodeIQ「ディビジョン・ナイン」問題を解いてみた。

Ruby

CodeIQで出題された「ディビジョン・ナイン」問題。

https://codeiq.jp/q/2561

Rubyで解いてみたので、コードを公開してみる。

問題

問題は以下のとおり：

1から4の数字を使って $n$ 桁の整数を作ります。
このとき、9の倍数となるものを考えましょう。

例えば $n = 3$ であれば、234、333、441、などが9の倍数です。
必ずしも1から4の全ての数字を使う必要はありません。

1から4の数字を使って作る $n$ 桁の整数のうち、9の倍数となるものの個数を $F(n)$ と定義します。

例えば、 $F(1) = F(2) = 0$ 、 $F(3) = 10$ 、 $F(4) = 40$ となることが確かめられます。

標準入力から、自然数 $n \: (1 \le n \le 20)$ が与えられます。
標準出力に $F(n)$ の値を出力するプログラムを書いてください。

自分の解答

9の倍数の判定は簡単で、各桁の数字を足して9で割り切れれば、9の倍数。
ということで、関数の再帰呼び出しを使った深さ優先探索のコードをまず書いた：

def f(n, nums)
  if n == 1
    rest = nums.inject(0, &:+) % 9
    (5 <= rest && rest <= 8) ? 1 : 0
  else
    (1..4).inject(0) do |result, t|
      result += f(n-1, [nums, t].flatten)
    end
  end
end

n = $stdin.gets.to_i
puts f(n, [])

関数 $f(n, nums)$ は、使う数字が決まっていない桁数 $n$ 、各桁で使うことにした数字の配列 $nums$ に対して、9で割り切れる数が何個あるかを返すもの。
例えば、 $f (2, [1, 1])$ であれば、11xx（xはそれぞれ1〜4の数字）という数のうち9で割り切れるものの個数、 $f (1, [1, 1, 1])$ であれば、111x（xは1〜4の数字）という数のうち9で割り切れるものの個数が返ってくる。

$n$ が1の場合は、使うことにした数字を全て足して9で割った余りが5〜8の間に入っていれば、9で割り切れる数を作ることができる。
例えば、割った余りが5になっていれば、最後の1つの数字として4を使えば、9で割り切れる数になる。
なので、そういう場合には1を、そうでない場合には0を返している。

そして、 $n$ が2以上の場合は、使う数字を1つ固定して再帰呼び出しすれば、1〜4を使った場合のそれぞれの9で割り切れる数の個数が分かるので、それを合計して返せばいい。

ということで、論理的にはこれでOKなんだけど、実際に実行すると、めちゃくちゃ時間がかかる（＾＾；
そこで、もうちょっと高速化を。

上のコードでは、各桁で使うことにした数字を配列のまま持っていて、最後 ( $n = 1$ のとき）に足し算を行っているけど、実際に必要なのは、各桁で使うことにした数字の合計を9で割った余りだけ。
そこで、次のように修正：

def f(n, rest)
  if n == 1
    (5 <= rest && rest <= 9) ? 1 : 0
  else
    (1..4).inject(0) do |result, t|
      result += f(n - 1, (rest + t) % 9)
    end
  end
end

n = $stdin.gets.to_i
puts f(n, 0)

$rest$ は各桁で使うことにした数字の合計を9で割った余り。
再帰呼び出しをするときには、使うことにした数字の配列を作って渡すんじゃなくて、使うことにした数字を $rest$ に足して9で割った余りを渡すようにしている。

これで配列を生成するコストは減ったけど、まだまだ遅い。

ただ、ここで $1 \le n \le 20$ 、 $0 \le rest \le 8$ であることを考えると、同じ引数での関数呼び出しが何度も行われている可能性が高い。
となれば、キャッシュを使ってやればかなり高速化するはず。

ということで、キャッシュを使うようにしたコードが以下：

@f_cache = [
  #  0,   1,   2,   3,   4,   5,   6,   7,   8, (rest)
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 0
  [  0,   0,   0,   0,   0,   1,   1,   1,   1], # 1
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 2
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 3
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 4
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 5
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 6
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 7
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 8
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 9
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 10
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 11
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 12
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 13
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 14
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 15
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 16
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 17
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 18
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 19
  [nil, nil, nil, nil, nil, nil, nil, nil, nil], # 20
]

def f(n, rest)
  cache = @f_cache[n][rest]
  if cache.nil?
    @f_cache[n][rest] =
      (1..4).inject(0) do |result, t|
        result += f(n - 1, (rest + t) % 9)
      end
  else
    cache
  end
end

n = $stdin.gets.to_i
puts f(n, 0)

関数 $f$ の各引数に対するキャッシュを用意して、まだ求まっていないところにはnilを入れてある。
そして、 $n = 1$ のときの $f$ の値は分かってるので、最初から入れてある。
こうすると、 $n$ が1かそうでないかの判定は不要になり、キャッシュに値があればその値を返し、そうでなければ値を求めてキャッシュに値を保存し、その値を返せばいいだけになる。

これで十分に速くなったので、用意されたテストケースもちゃんと時間内に解けるようになった。

ちなみに、これは動的計画法になってるみたい。
確かに、1つの桁の数字を決めてより小さい問題を解いていて（分割統治法）、また、より小さい問題のそれぞれの結果をキャッシュしてる（メモ化）。
動的計画法という名前自体は（ナップザック問題などで）知っていたけど、具体的なアルゴリズムのイメージは掴めてなかったので、自分の書いたコードが振り返ってみれば動的計画法になっていたというのは、ちょっと変な感じ。
強化学習の動的計画法とは、かなり違うしね。

少し補足しておくと、強化学習の動的計画法の方は、状態関数の値を他の状態関数の値を使って求めていて（ブートストラップ）、各状態関数の値を保存している（メモ化）という意味では、（定義次第では）動的計画法の条件を満たしていると言えなくもない。
ただ、関数の各値の関係を有向グラフにしたときにループが存在することがあるので、再帰で解くことが出来るとは限らない。
（つまり、厳密に言うと、より小さい部分問題に分割出来るとは限らない）
そこで、（ループしていない場合も）再帰を使って解くのではなく、ヤコビ法で反復を使って問題を解いている。
なので、ナップザック問題を解く動的計画法と、強化学習の動的計画法だと、かなりイメージが違う感じ。

今日はここまで！