スポーツの最適化 • 優勝決定可能性問題 • スポーツスケジュール問題優勝決定可能性問題・毎年、プロスポーツのシーズン終了間際になると、「○○ チームは5位確定」とか、「××チームは自力優勝の可能性が消えた」とか言われます・マジックとか、○位確定とか、自力優勝とか、降格ラインとか、いろいろな言葉があります。順位に関する用語自力優勝：自分が残り試合全部勝てば、他のチームがどれだけがんばっても優勝できる ⇔ 自力優勝できるマジック：自分以外の任意のチームに対して、そのチームが残り試合全部勝っても、自分が t 試合勝てば優勝できる ⇔ マジックが t 確定：今後、残りの全ての試合の勝敗がどのようになっても自分の順位が1通りに決まることなんでいろいろ調べるの？・今のチームの有利不利を正確に知りたい。いろいろな角度から知りたい（完全に分かるとつまらないんだけど）・主観的な直感による評価では水掛け論になるので、数理的な指標が欲しい優勝（びり）の可能性・「○○位確定」「自力優勝が消えた」は良く言われるけど、ほんとに優勝（あるいはびり）の可能性がなくなったかどうかを知りたい・組合せの問題なので、数理的に解が存在する・組合せ最適化問題として定式化してみる問題・リーグ戦の途中の段階（いくつかの試合は結果がでた）で、あるチーム x が優勝（あるいはビリ）する可能性は残されているか（残りの試合結果の組合せを加えて、チーム x がトップになるものはあるか）・ x が残りの試合を全部勝つ（全部で最高の結果を出した場合）のみを考えれば良い・順位の評価はいろいろあるが、まずは勝った数としよう問題を整理・整理すると入力：－チーム x が関わらない、未消化の試合の組合せ－チーム x の最大の勝ち数 z 出力：－ x 以外のチームの勝ち数がすべて z 以下になるような、未消化試合の星取りはあるか最小費用流問題で解く・各試合（カード）は、どちらかのチームが勝つ ⇒ 各試合を、各チームに分配すると見なせる・各カードをチームに運ぶ、輸送問題として定式化する制約を考えると：・各カードから荷物が１つ出る。行き先はそのカードの対戦チームどちらか・各チームが受け取る荷物は z を超えてはいけないネットワーク 1 1 1 1 1 1 1 1 残りカード Aチーム z － (現在の勝ち数)以下 Bチーム z － (現在の勝ち数)以下 Cチーム Dチーム・・・・・輸送問題の実行可能解があるかどうか判定する問題（輸送問題なので、解は整数）  線形計画で解けるビリ可能性判定問題・あるチームが、ビリになる可能性は残っているか？・優勝可能性問題を逆さまにして解けばよい（全ての負けと勝ちを反転させる）ビリから2番目の可能性判定問題・あるチーム x が、ビリ、あるいはビリから2番目になる可能性は残っているか？（リーグの降格可能性を調べる）－まず、 x がビリになれるか調べる－（なれないとして）、次に他の各チーム y について、 y がビリで、 x がビリから2番目になる可能性があるかどうか調べる・ y はx に残り全て勝つとしてよい（x はビリにはなれないから）・ x, y 以外のチームはx, y に全て勝つとしてよい ⇒ x, y 以外のチームの勝ち数が全て x より大きくできるか ⇒ 同じ方法で解ける順位が他の基準の場合・同様にして解ける場合－勝ち点制度で、勝ちが2、引き分けが1、負けが0のとき－勝ち負け以外の場合の勝ち点が、普通の勝ちより点数が悪くなるものしかないとき（Vゴール勝ちなど：その場合だけ考えればよい、あるいは、両チームの勝ち点の合計が常に一定かつ全ての場合がありうる）順位が他の基準の場合・同様にして解けない場合－勝率で評価し、引き分けがある場合（輸送問題にならない）－一試合での両チームの勝ち点の合計が一定でない場合－一試合での両チームの勝ち点の配分に存在しないパターンがある場合 (5-0、0-5、4-1、1-4 はあるが 2-3、3-2がない、など) うまく解けない場合・勝率で評価する場合 ⇒ 輸送問題にならなくなる・チーム y の勝率＝ y の勝数／（y の勝数＋負数）・チーム y の勝率が z 以下 ⇒ （y の勝数＋負数） z ≧ y の勝数・引き分けがあるので、（y の勝数＋負数）が定数でない制約は線形だが、小数解が出るかも ⇒ 整数計画で解くしかないうまく解けない場合 (2) ・１試合の両チームの勝ち点のパターンがいくつかある場合（k通りあるとする）なんとか整数計画にしてみよう・試合 i の勝ち点パターンが j のときのチーム y の勝ち点をsijy とする・試合 i の勝ち点パターンが j のとき１、そうでないとき0となる01変数を pij とするうまく解けない場合２・チーム y の勝ち点が z 以下 ⇒ Σ sijypij ≦ z ・試合 i の勝ち点パターンはどれかひとつだけ1になる ⇒ Σ pij ＝ 1 for each i まとめると、以下の条件を満たす実行可能解があるかどうかを判定する問題になる Σ sijypij ≦ z Σ pij ＝ 1 pij ∈ {0,1} 実際使えるの？メリット：・降格なし、の情報を早く算定できる・優勝に関してあらたな尺度ができるデメリット：・優勝の望みのないチームは、雰囲気が盛り下がる？・計算がめんどくさい（データをそろえて、プログラムに入力しなければならない） ← マジックや自力優勝は、手計算でできる優勝判定問題・優勝、ビリなど、上位・下位の順位になる可能性があるかどうかを判定する問題を、線形計画（輸送問題）で解ける・線形計画なので、試合数が多くても計算できる・引分ありの勝率、均一でない勝ち点制度などでは線形計画では計算できない・実際の計算は、他の指標に比べて面倒試合のスケジュール問題・スポーツの試合スケジュールを決めるのは意外と大変 ← いろいろな条件があるから・決める事柄（変数）－各日の試合の組合せ（カード）－どちらのホームで試合をするか・制約－全ての試合を行う－チームは同時に異なる試合はできない（割当問題）－ホームとアウェーは同数であること－アウェーの試合は連続しないこと－試合日に球場が使えること数理計画としてとらえる・制約を満たす（なるべく良い）解（変数の組合せ）を見つける ⇒ 最適化問題・しかし、普通に定式化すると変数の数が多すぎて、ソルバーでは解けない。・さてどうしましょう・オリジナルな解法を作ったホームアウェーのパターン・決めるのは、ホーム・アウェーと組合せ－組合せは候補数が多い－ホーム･アウェーのほうが制約が厳しい・まず、可能なホーム／アウェーのパターンを列挙して、各々に対して解が存在するかどうか調べるホームアウェーのパターン数・各チームが各試合日でホーム・アウェーどちらを行うか決める・制約、及びよく考えられる条件は－ホーム・アウェーの３連続は禁止－シーズン開始直後／終了直前のホーム･アウェーの２連続も－同時刻に試合を行うチーム数は偶数、かつ半分がホーム－前半戦と後半戦は同じスケジュールで、ホームとアウェーだけ入れ替えるホームアウェーのパターン数 (2) －ホーム・アウェーの３連続は禁止－シーズン開始直後／終了直前のホーム･アウェーの２連続も－同時刻に試合を行うチーム数は偶数、かつ半分がホーム－前半戦と後半戦は同じスケジュールで、ホームとアウェーだけ入れ替える・例えば、２連続するホーム・アウェーの数を最小にする（どうしてもどこかには２連続が発生）ここまで絞り込むと、通常、解はとても少ない（16チームなら1通り？） ⇒ 列挙するホームアウェーのパターン例・例えば6チームの場合１ａａａｈｈｈ２ｈｈｈａａａ３ｈａａａｈｈ４ａａａｈｈｈ５ｈｈｈａａａこういうものを列挙して、これに割り当てられるカードを調べる組合せを割り当てる・各カードをある日に割り当てる・条件は、１．同一チームが2つのカードに割り当てないこと２．各カードにホームのチームとアウェーのチームをちょうど１つずつ割り当てること２．の条件から、カードを割り当てられる日が自動的に決まるあとは１．の条件を制約にして割り当て問題を解く（整数条件が必要）実際には・好カードはなるべく後にする、という条件が必要・視聴率があがるような組合せ（人間系？）・もっと政治的な思惑が多いかも・夏の高校野球で阪神が甲子園球場を使えなくなるような、そのチーム以外の要因も入るまとめ・スポーツスケジューリングの紹介・ホーム・アウェーのパターン列挙・カードの割り当て