スポーツの最適化 優勝決定可能性問題 スポーツスケジュール問題.

Presentation on theme: "スポーツの最適化 優勝決定可能性問題 スポーツスケジュール問題."— Presentation transcript:

1 スポーツの最適化 優勝決定可能性問題 スポーツスケジュール問題

2 優勝決定可能性問題 ・毎年、プロスポーツのシーズン終了間際になると、「○○チームは5位確定」とか、「××チームは自力優勝の可能性が消えた」とか言われます ・マジックとか、○位確定とか、自力優勝とか、降格ラインとか、いろいろな言葉があります。

3 順位に関する用語 自力優勝：自分が残り試合全部勝てば、他のチームがどれだけがんばっても優勝できる ⇔ 自力優勝できる
自力優勝：自分が残り試合全部勝てば、他のチームがどれだけがんばっても優勝できる　⇔　自力優勝できる マジック：自分以外の任意のチームに対して、そのチームが残り試合全部勝っても、自分が t 試合勝てば優勝できる 　⇔　マジックが t 確定：今後、残りの全ての試合の勝敗がどのようになっても自分の順位が1通りに決まること

4 なんでいろいろ調べるの？ ・今のチームの有利不利を正確に知りたい。いろいろな角度から知りたい （完全に分かるとつまらないんだけど）
・今のチームの有利不利を正確に知りたい。いろいろな角度から知りたい　 　　（完全に分かるとつまらないんだけど） ・主観的な直感による評価では水掛け論になるので、数理的な指標が欲しい

5 優勝（びり）の可能性 ・「○○位確定」「自力優勝が消えた」は良く言われるけど、ほんとに優勝（あるいはびり）の可能性がなくなったかどうかを知りたい ・組合せの問題なので、数理的に解が存在する ・組合せ最適化問題として定式化してみる

6 問題 ・リーグ戦の途中の段階（いくつかの試合は結果がでた）で、あるチーム x が優勝（あるいはビリ）する可能性は残されているか （残りの試合結果の組合せを加えて、チーム x がトップになるものはあるか） ・ x が残りの試合を全部勝つ（全部で最高の結果を出した場合）のみを考えれば良い ・ 順位の評価はいろいろあるが、まずは勝った数としよう

7 問題を整理 ・整理すると 入力： － チーム x が関わらない、未消化の試合の組合せ － チーム x の最大の勝ち数 z 出力：

8 最小費用流問題で解く ・各試合（カード）は、どちらかのチームが勝つ ⇒ 各試合を、各チームに分配すると見なせる
　　⇒ 各試合を、各チームに分配すると見なせる ・各カードをチームに運ぶ、輸送問題として定式化する 制約を考えると： ・各カードから荷物が１つ出る。行き先はそのカードの対戦チームどちらか ・各チームが受け取る荷物は z を超えてはいけない

9 輸送問題の実行可能解があるかどうか判定する問題 （輸送問題なので、解は整数）  線形計画で解ける
ネットワーク 1 1 1 1 1 1 1 1 残り カード Aチーム Bチーム Cチーム Dチーム z － (現在の 勝ち数)以下 z － (現在の 勝ち数)以下 ・・・・・ 輸送問題の実行可能解があるかどうか判定する問題 （輸送問題なので、解は整数）　　　線形計画で解ける

10 ・あるチームが、ビリになる可能性は残っているか？ ・ 優勝可能性問題を逆さまにして解けばよい （全ての負けと勝ちを反転させる）
ビリ可能性判定問題 ・あるチームが、ビリになる可能性は残っているか？ ・ 優勝可能性問題を逆さまにして解けばよい 　　　（全ての負けと勝ちを反転させる）

11 ビリから2番目の可能性判定問題 ・あるチーム x が、ビリ、あるいはビリから2番目になる可能性は残っているか？
　　　　（リーグの降格可能性を調べる） － まず、 x がビリになれるか調べる － （なれないとして）、次に他の各チーム y について、 y がビリで、x がビリから2番目になる可能性があるかどうか調べる ・ y はx に残り全て勝つとしてよい （x はビリにはなれないから） ・ x, y 以外のチームはx, y に全て勝つとしてよい 　　⇒ x, y 以外のチームの勝ち数が全て x より大きくできるか 　　⇒ 同じ方法で解ける

12 順位が他の基準の場合 ・同様にして解ける場合 －勝ち点制度で、勝ちが2、引き分けが1、負けが0のとき
　－勝ち点制度で、勝ちが2、引き分けが1、負けが0のとき 　－勝ち負け以外の場合の勝ち点が、普通の勝ちより点数が悪くなるものしかないとき 　　（Vゴール勝ちなど：その場合だけ考えればよい、 　　あるいは、両チームの勝ち点の合計が常に一定かつ全ての場合がありうる）

13 順位が他の基準の場合 ・同様にして解けない場合 － 勝率で評価し、引き分けがある場合（輸送問題にならない）
　－ 勝率で評価し、引き分けがある場合（輸送問題にならない） 　－ 一試合での両チームの勝ち点の合計が一定でない場合 　－ 一試合での両チームの勝ち点の配分に存在しないパターンがある場合 　　(5-0、0-5、4-1、1-4 はあるが 2-3、3-2がない、など)

14 うまく解けない場合 ・ 勝率で評価する場合 ⇒ 輸送問題にならなくなる ・ チーム y の勝率 ＝ y の勝数 ／ （y の勝数＋負数）
・ 勝率で評価する場合　⇒　輸送問題にならなくなる ・ チーム y の勝率　＝　y の勝数　／　（y の勝数＋負数） ・ チーム y の勝率が z　以下　 　　　⇒　（y の勝数＋負数） z　≧　y の勝数　 ・ 引き分けがあるので、（y の勝数＋負数）が定数でない 制約は線形だが、小数解が出るかも 　　⇒　整数計画で解くしかない

15 うまく解けない場合 (2) ・ １試合の両チームの勝ち点のパターンがいくつかある場合 （k通りあるとする） なんとか整数計画にしてみよう
・ 試合 i の勝ち点パターンが j のときの 　　　チーム y の勝ち点をsijy とする ・ 試合 i の勝ち点パターンが j のとき１、そうでないとき0となる01変数を pij とする

16 うまく解けない場合２ ・ チーム y の勝ち点が z 以下 ⇒ Σ sijypij ≦ z
　　　　　⇒　Σ pij ＝ 1 for each i まとめると、以下の条件を満たす実行可能解があるかどうかを判定する問題になる Σ sijypij ≦ z Σ pij ＝ 1 pij ∈ {0,1}

17 実際使えるの？ メリット： ・ 降格なし、の情報を早く算定できる ・ 優勝に関してあらたな尺度ができる デメリット：
・ 優勝の望みのないチームは、雰囲気が盛り下がる？ ・ 計算がめんどくさい （データをそろえて、プログラムに入力しなければならない） 　←　マジックや自力優勝は、手計算でできる

18 優勝判定問題 ・ 優勝、ビリなど、上位・下位の順位になる可能性があるかどうかを判定する問題を、線形計画（輸送問題）で解ける
・ 線形計画なので、試合数が多くても計算できる ・ 引分ありの勝率、均一でない勝ち点制度などでは線形計画では計算できない ・ 実際の計算は、他の指標に比べて面倒

19 試合のスケジュール問題 ・ スポーツの試合スケジュールを決めるのは意外と大変 ← いろいろな条件があるから ・ 決める事柄（変数）
・ スポーツの試合スケジュールを決めるのは意外と大変　　 　　　　　← いろいろな条件があるから ・ 決める事柄（変数） 　－ 各日の試合の組合せ（カード） 　－ どちらのホームで試合をするか ・ 制約 　－ 全ての試合を行う 　－ チームは同時に異なる試合はできない（割当問題） 　－ ホームとアウェーは同数であること 　－ アウェーの試合は連続しないこと 　－ 試合日に球場が使えること

20 数理計画としてとらえる ・ 制約を満たす（なるべく良い）解（変数の組合せ）を見つける ⇒ 最適化問題
　　　　⇒ 最適化問題 ・ しかし、普通に定式化すると変数の数が多すぎて、ソルバーでは解けない。 ・ さてどうしましょう ・ オリジナルな解法を作った

21 ホームアウェーのパターン ・ 決めるのは、ホーム・アウェーと組合せ － 組合せは候補数が多い － ホーム･アウェーのほうが制約が厳しい
　－　組合せは候補数が多い 　－　ホーム･アウェーのほうが制約が厳しい ・ まず、可能なホーム／アウェーのパターンを列挙して、 各々に対して解が存在するかどうか調べる

22 ホームアウェーのパターン数 ・ 各チームが各試合日でホーム・アウェーどちらを行うか決める ・ 制約、及びよく考えられる条件は
　－　ホーム・アウェーの３連続は禁止 　－　シーズン開始直後／終了直前のホーム･アウェーの２連続も 　－　同時刻に試合を行うチーム数は偶数、かつ半分がホーム 　－　前半戦と後半戦は同じスケジュールで、ホームとアウェーだけ入れ替える

23 ホームアウェーのパターン数 (2) － ホーム・アウェーの３連続は禁止 － シーズン開始直後／終了直前のホーム･アウェーの２連続も
　－　ホーム・アウェーの３連続は禁止 　－　シーズン開始直後／終了直前のホーム･アウェーの２連続も 　－　同時刻に試合を行うチーム数は偶数、かつ半分がホーム 　－　前半戦と後半戦は同じスケジュールで、ホームとアウェーだけ入れ替える ・ 例えば、２連続するホーム・アウェーの数を最小にする 　　（どうしてもどこかには２連続が発生） ここまで絞り込むと、通常、解はとても少ない （16チームなら1通り？）　　⇒　列挙する

24 ・ 例えば6チームの場合 １ ２ ３ ４ ５ ａ ｈ ｈ ａ ｈ ａ ｈ ａ ａ ｈ ｈ ａ ａ ｈ ａ ｈ ａ ｈ ｈ ａ
ホームアウェーのパターン例 ・ 例えば6チームの場合 １ ２ ３ ４ ５ ａ ｈ ｈ ａ ｈ ａ ｈ ａ ａ ｈ ｈ ａ ａ ｈ ａ ｈ ａ ｈ ｈ ａ こういうものを列挙して、これに割り当てられる カードを調べる

25 組合せを割り当てる ・ 各カードをある日に割り当てる ・ 条件は、 １． 同一チームが2つのカードに割り当てないこと
　１． 同一チームが2つのカードに割り当てないこと 　２． 各カードにホームのチームとアウェーのチームをちょうど１つずつ割り当てること ２．の条件から、カードを割り当てられる日が自動的に決まる あとは１．の条件を制約にして割り当て問題を解く 　　（整数条件が必要）

26 実際には ・ 好カードはなるべく後にする、という条件が必要 ・ 視聴率があがるような組合せ（人間系？） ・ もっと政治的な思惑が多いかも
・ 夏の高校野球で阪神が甲子園球場を使えなくなるような、そのチーム以外の要因も入る

27 ・ スポーツスケジューリングの紹介 ・ ホーム・アウェーのパターン列挙 ・ カードの割り当て
まとめ ・ スポーツスケジューリングの紹介 ・ ホーム・アウェーのパターン列挙 ・ カードの割り当て