統計モデルに基づく着順予測と、分枝限定法による馬券組合せ最適化についての検討

はじめに

本記事では、前回記事（競走馬と騎手の「強さ」をベイズ統計モデリングで推定する - walkingsdbgの日記）で紹介した統計モデルから予測した着順に基づき、最適な馬券の組合せを求める方法について説明します。

はじめに
統計モデルに基づく着順予測
馬券組合せ最適化
- 問題設定
- 分枝限定法による最適解の求め方
  - 分枝限定法とは
  - 上界の求め方
レースデータを使用した検証
まとめ

統計モデルに基づく着順予測

前回記事では、競馬の着順が決まるメカニズムを以下のように仮定し、統計モデルを構築しました。

競走馬と騎手にはそれぞれ固有の「強さ」が存在する。
競走馬と騎手がレースで発揮できる「強さ」（＝パフォーマンス）にはそれぞれバラつきが存在し、パフォーマンスは正規分布に従う。
競走馬と騎手のパフォーマンスの総和が大きい順にレースの着順が決まる。

このモデルに基づいて着順予測を行うには、モデルから生成した標本を利用します。例えば、ある馬が１着になる確率の予測方法は次の通りです。

競走馬と騎手のパフォーマンスを正規分布から生成し、そのパフォーマンスの大小でレース着順を決める、というシミュレーションを $N$ 回実施する。
$N$ 回のシミュレーションの内、ある馬 $i$ が１着になった回数を $n_i$ 回とすると、その馬が１着になる確率 $p_i$ は $p_i = n_i/N$ と求まる。

馬券組合せ最適化

競馬の着順が前回記事の統計モデルに従って決まる場合、どの馬が何％の確率で１着になるかを上記の方法で予測することが可能です。しかし、この予測結果だけでは、どのような馬券を購入すればよいかが分かりません（例えば、１着になる確率が最大の馬に１点張りすることもできますし、外れるリスクを避けて他の馬の馬券を合わせて購入することも可能です）。そこで以下では、着順予測結果から購入すべき馬券の組合せを求める方法について述べます。

問題設定

私は、以下の条件を満たす範囲で利益（＝払戻額－購入額）の期待値を最大化するような馬券の組合せを求めることを目指します。なお、ここでは単勝の馬券のみを買うことを前提とします*1。

予算は $Ｗ$ ×100円以内
損をする（利益が０円未満となる）確率が $\alpha$ 以下である

この利益の最大化問題を数式に直すと次のようになります。

評価関数

$\displaystyle \max_{z_{ij}} \sum_{i=1}^{N} \sum_{j=0}^{W} 100j \left(R_{i}p_{i}-1 \right)z_{ij} \tag{1} \label{1}$

制約条件

${ \displaystyle \begin{eqnarray} \sum_{i=1}^{N} \sum_{j=0}^{W} jz_{ij} \leq W \tag{2} \label{2} \\ \mathrm{Pr} \left(\sum_{i=1}^{N} \sum_{j=0}^{W} 100j(r_{i}-1)z_{ij} < 0 \right) \leq \alpha \tag{3} \label{3}\\ \sum_{j=0}^{W} z_{ij} = 1 \ \left(i = 1,2,\ldots,N \right) \tag{4} \label{4}\\ z_{ij} \in \{0,1\} \ \left(i = 1,2,\ldots,N, \ \ j = 0,1,\ldots, W \right) \tag{5} \label{5} \end{eqnarray} }$
ここで、式中に現れる記号の意味は以下の通りです。

$N$ ：馬券の総数
$R_i$ ：馬券 $i$ のオッズ
$p_i$ ：馬券 $i$ が当たる確率
$z_{ij}$ ：馬券 $i$ を $j \times 100$ 円で購入する／購入しないを指定する変数
$r_i$ ：馬券 $i$ の回収率（確率変数。当たれば $R_i$ 、外れれば $0$ ）

また、上式の意味は以下の通りです。

式\eqref{1}：利益の期待値[円]

（払戻額の期待値 $\sum_{i=1}^{N} \sum_{j=0}^{W} 100jz_{ij}R_{i}p_{i}$ [円]－購入額 $\sum_{i=1}^{N} \sum_{j=0}^{W} 100jz_{ij}$ [円]）

式\eqref{2}：購入額が予算を超えないようにする制約（条件1に対応）
式\eqref{3}：損をする確率がαを超えないようにする制約（条件2に対応）
式\eqref{4}：同じ馬券 $i$ を重複購入しないようにする制約
式\eqref{5}：購入する場合は1、購入しない場合は0。ただし $z_{i0} = 1$ の場合、馬券 $i$ を一切購入しないことを表す

分枝限定法による最適解の求め方

式\eqref{1}\eqref{2}\eqref{3}\eqref{4}\eqref{5}を満たす最適な馬券を求めるための一番シンプルな方法は、全ての馬券の組合せを探索することです。しかし、これは計算コストの観点で現実的ではありません。例えば、予算1万円で10頭立てのレースの馬券を購入する場合 $2^{100\times10} \approx 10^{301}$ 通りの組合せが存在するため*2、全ての馬券の組合せを探索することは困難です。そこで、私は分枝限定法という手法を用いて馬券の組合せを最適化しました。

分枝限定法とは

分枝限定法は、以下の分枝操作・限定操作という２種類の操作を繰り返すことで効率的に最適解を探索する方法です。

分枝操作：ある商品（ここでは馬券）を買う場合／買わない場合で場合分けすることにより、元の問題を分割する。
限定操作：分枝操作により分割された問題（部分問題）を評価して以下のことが判明した場合、部分問題の探索を打ち切る。
- 制約条件（ここでは式\eqref{2}\eqref{3}\eqref{4}\eqref{5}）を満たさない
- 部分問題の最適解の上界が暫定解（探索済の組合せの中での最適解）より小さい

例えば、予算1500円で、馬券Ａ・Ｂ・Ｃの中から最適な馬券の組合せを探索することを考えます。なお、簡単のためにそれぞれの馬券の値段は１０００円であるとします。また、分枝操作によりそれぞれの馬券を買う場合／買わない場合で場合分けし、下図のように①→②→③と探索を進めたとします。このとき、③では馬券Ａ・Ｂを購入して2000円を支払っているため、既に予算をオーバーしています。したがって、③以降のノードの探索を限定操作により打ち切ることが可能です。

f:id:walkingsdbg:20200416135923p:plain — 限定操作の一例（予算オーバーの場合）。番号のついたノードは探索順を表し、赤いノードは限定操作によって探索を打ち切られたノードを表す

もう一つ限定操作の例を挙げます。予算が3000円である点を除いて、問題設定は上記例と同様です。まず、下図のように①→②→③→④→⑤と探索を進め、暫定解としてノード⑤の3000円を得たとします。次に、ノード⑥において、部分問題の最適解の上界が後述の方法で2000円と判明したとします。このとき、上界（2000円）が暫定解（3000円）を下回っているため、⑥以降のノードを探索してもより良い解を得ることができないと分かります。したがって、限定操作により⑥以降のノードの探索を打ち切ることが可能です。

f:id:walkingsdbg:20200416143244p:plain — 限定操作の一例（上界が暫定解を下回る場合）。青のノードは暫定解を表す

このように、分枝限定法では限定操作を利用することで探索回数を減らすことが可能です。
なお、分枝限定法については以下の本・講義資料を参考にしました。より詳しい解説はこれらの資料をご覧ください。

組合せ最適化とアルゴリズム (インターネット時代の数学シリーズ 8)
- 作者:幹雄, 久保
- 発売日: 2000/12/10
- メディア: 単行本
http://www.dais.is.tohoku.ac.jp/~shioura/teaching/mp11/mp11-06.pdf

上界の求め方

分枝限定法では、元の問題の制約条件を緩めた緩和問題を解くことで最適解の上界を求めます。ここでは、非線形制約\eqref{3}\eqref{5}を線形制約に緩和し、線形計画法によって上界を計算します。まず、式\eqref{5}で定めた変数 $z_{ij}$ の定義域を{0,1}から実数に緩和します。次に、式\eqref{3}は「損をする（利益が０円未満となる）確率が $\alpha$ 以下である」という条件を表していますが、この条件を「全ての購入馬券が外れる確率が $\alpha$ 以下である」という条件に緩和します。緩和した条件は以下の式\eqref{6}のように $z_{i0}$ について線形であるため、式\eqref{1}\eqref{2}\eqref{4}\eqref{6}を線形計画法で解くことにより最適解の上界を求めることが可能になります。
${ \displaystyle \begin{eqnarray} (全ての購入馬券が外れる確率) &=& 1 - (少なくとも1つの購入馬券が当たる確率) \\ &=& 1 - \sum_{i=1}^N p_i\left(1-z_{i0}\right) \leq \alpha \tag{6} \label{6} \end{eqnarray} }$

レースデータを使用した検証

上述の着順予測と馬券組合せ最適化を用いて、過去のレースデータを用いたシミュレーションで回収率が100%を超えるか検証します。*3

使用データ

訓練データ：2017年1月～2018年11月のG1・G2・G3・オープンレース（計536レース）
テストデータ：2018年12月のG1レース（計5レース）

シミュレーション条件

$N = 2000$
$W = 100$
$\alpha = 0.2$
分枝限定法の探索回数上限*4： $10^5$ 回
馬券１口あたりの購入額*5： $500$ 円

結果・考察

テストデータ（計5レース）の購入額・払戻額・利益を以下に示します。なお、購入額が0円のレースは、上記の探索回数において暫定解が得られなかったレースを表します。

レース名	購入額[円]	払戻額[円]	利益[円]
チャンピオンズカップ(G1)	10,000	0	-10,000
阪神ジュベナイルフィリーズ(G1)	0	0	0
朝日杯フューチュリティステークス(G1)	10,000	11,500	1,500
有馬記念(G1)	0	0	0
ホープフルステークス	9,000	0	-9,000
合計	29,000	11,500	-17,500

上表より、総利益は-17,500円（回収率は約40%）という残念な結果になりました。。。この原因を調べるため、全ての購入馬券が外れたレース（チャンピオンズカップとホープフルステークス）について購入馬券と実際の着順を見ます。

チャンピオンズカップ

                 馬名 OoA   prob  odds weight
1    ルヴァンスレーヴ   1 0.1485   1.9     NA
2    ウェスタールンド   2 0.0630  32.1      5
3      サンライズソア   3 0.0980   8.2     15
4    アンジュデジール   4 0.0415  40.1      5
5    オメガパフューム   5 0.1350   9.2     15
6    サンライズノヴァ   6 0.1140  10.0     10
7        ノンコノユメ   7 0.0705  13.4     10
8              ミツバ   8 0.0500 139.5      5
9  ヒラボクラターシュ   9 0.0615  95.3      5
10     アスカノロマン  10 0.0010 296.0     NA
11   ケイティブレイブ  11 0.0710   5.0     20
12     センチュリオン  12 0.0590 251.8      5
13 インカンテーション  13 0.0665  75.5      5
14 アポロケンタッキー  14 0.0060 204.6     NA
15           パヴェル  15 0.0145  27.3     NA

ホープフルステークス

                 馬名 OoA   prob  odds weight
1  サートゥルナーリア   1 0.1965   1.8     NA
2  アドマイヤジャスタ   2 0.1075   6.2     15
3      ニシノデイジー   3 0.1990   6.6     15
4  コスモカレンドゥラ   4 0.0785  41.6      5
5  ブレイキングドーン   5 0.0975   9.9     10
6    ヴァンドギャルド   6 0.1215  10.4     10
7      ヒルノダカール   7 0.0285  68.7      5
8    キングリスティア   8 0.0175  24.4      5
9    ミッキーブラック   9 0.0625  35.8      5
10   マードレヴォイス  10 0.0165 436.3      5
11   ジャストアジゴロ  11 0.0255  70.3      5
12   ハクサンタイヨウ  12 0.0245 430.9      5
13       タニノドラマ  13 0.0245 171.0      5

ここで、各列の意味は以下の通りです。

OoA：着順
prob：統計モデルから推定した勝率
odds：単勝オッズ
weight：購入額（weight×100円）。NAは購入していないことを表す

購入馬券を見ると、1番人気の馬が含まれていないことが分かります。これは、1番人気の馬について、統計モデルから算出した勝率が低い割にオッズが高くないため、利益最大化の観点で良くない馬券と判断されたことが原因と考えられます。この戦略は、統計モデルから算出した勝率が妥当であれば良い戦略です。しかし、今回のシミュレーションでは馬券を購入した3レース中2レースで全滅という結果だったので、統計モデルによる勝率の推定精度が低いと考えています。参考情報ですが、以下ブログによるとG1レースで1番人気かつ単勝1倍台の馬の勝率は44.8%（本統計モデルでは15~19%程度）なので、現在使用している統計モデルは、1番人気の馬の勝率を過小評価していると考えています。
jra-van.jp

まとめ

統計モデルに基づく着順予測と分枝限定法を組み合せて、馬券組合せ最適化の方法を検討しました。過去のレースデータを用いた検証では回収率が約40％となったため、実戦投入には更なる改善が必要と分かりました。回収率が低い原因として統計モデルによる勝率の推定精度が低いことが考えられるため、今後は統計モデルの推定精度向上を行います。

*1:これは、制約条件\eqref{3}の計算がややこしくなる・問題の規模が大きくなることを避けるためです。利益最大化の観点では、単勝馬券に絞ることは選択肢を狭めるのであまり良くないです。

*2:1頭あたり、100円の単勝馬券を買う／買わない、200円の単勝馬券を買う／買わない、…10000円の単勝馬券を買う／買わない、という $2^{100}$ 通りの組合せがあるため、10頭立てのレースでは $2^{100\times10}$ 通りになります。