概要
前回紹介したGreedy方式はとりあえずテーブルの人数のバランスを保つことができるという意味において、MTTのテーブルリバランシングとして手堅い方法であると考えられる。しかし、プレイヤー間の公平性や座席移動の好ましさという意味では必ずしも最適な方法であるとは言えないだろう。そのため、座席移動のコストを定義して、そのコストを最小になるように最適化問題を解いて、座席移動を行うアルゴリズムを考えてみよう。
テーブルリバランシングの目的関数
座席移動に伴うコスト（プレイヤー間の不公平性や移動に伴う時間のロス）には以下のような基準があると考えられる。
- ポジションの変化：移動前と移動後でプレイヤーのポジション変化の差（BTNからの席差）
- ブラインドの公平性：BB担当になるまでのプレイ回数
- プレイヤー毎の移動回数：移動回数がなるべく均等になるように調整（移動が多いほどプレイしていない時間が増える）
- テーブル間の人数差：テーブル間のプレイヤー数の差を最小化
- システム上の制約：可能な限りサーバを跨ぐ移動を減らすなど
これらの合成で、テーブル移動のコストを以下のように表現することができる。現在、座席\(\small i \)にいるプレイヤーを座席\(\small j \)に移動するコストを\(\small c_{ij}\)と表すと
\[\small c_{ij} = w_1 |p_i – p_j| + w_2 |b_i – b_j| + w_3 m_i + w_4 |t_i – t_j| + w_5 1_{\{s_i \neq s_j\}} \]
となる。ここで、\(\small p_i\)は座席\(\small i\)の次のゲームにおけるポジション、\(\small b_i\)は座席\(\small i\)の次のゲームにおけるBBまでのゲーム回数、\(\small m_i \)は座席\(\small i\)にいるプレイヤーの合計移動回数、\(\small t_i\)は座席\(\small i\)のテーブルのプレイヤー数、\(\small s_i\)は座席\(\small i\)のテーブルのサーバを表す。
もちろん、これは一例にすぎず、スタックの分布状況などを利用して特徴的なテーブルリバランシングが実現するようにコスト関数を定義することもできる。
最適割当問題とハンガリー法
MTTのテーブルリバランシングを数学的な問題として定式化すると、コストを最小化するように\(\small i \in I\)のプレイヤーを\(\small j \in J\)の座席に割り当てる問題として表現することができる。一般的にはプレイヤーの数と座席の数は異なるが、プレイヤー＋空席の数が座席の数に一致するという風に定式化すれば、一般性を失うことなくプレイヤーの数と座席の数が一致することを仮定することができる。このように、\(\small n\)個の資源を\(\small n\)個の対象にコストが最小に割り当てる数学的問題を最適割当問題（Optimal Assignment Problem）という。
最適割当問題は解法として効率的なアルゴリズムが知られており、ハンガリー法（Hangarian Algorithm）と言われる。以下で、ハンガリー法のアルゴリズムの概略を示そう。形式的には、ハンガリー法は二部グラフにおける最小コスト完全マッチング問題を解くためのアルゴリズム（？）であり、コスト行列に対して行操作と列操作を繰り返すことで、最適割当問題の解を算出する。
最初に、資源\(\small i\)を対象\(\small j\)に割り当てるコストが行列\(\small [c_{ij}]\)で与えられているとする（数が一致していない場合はダミーの行を入れることで調整する）。ハンガリー法の具体的なアルゴリズムは次の通りである。
- コスト行列の変換とゼロ点の作成: コスト行列の各行・各列から最小値を引く操作を繰り返すことで、ゼロ割当を探しやすくする。
- 行の削減・・・各行の最小値を求め、その行のすべての要素から最小値を引く。これにより、各行に少なくとも1つのゼロができる。
- 列の削減・・・行の削減後の行列に対し、今度は各列の最小値を求め、その列のすべての要素から最小値を引く。これにより、各列にも少なくとも1つのゼロができる。
- 最小被覆線の描画と最適性の判定: 現在のコスト行列のゼロをすべてカバーするために必要な最少の線（水平または垂直）の数\(\small K\)を求める。
- 最適性の判定: \(\small K=n\)の場合、最適解が見つかっているのでステップ3で解を特定する。
- \(\small K<n\)の場合、ステップ4でコスト行列を調整する。
- 最適割当の特定: ゼロをカバーする線の数が\(\small n\)個の場合、コスト行列がゼロになっている要素\(\small (i,j)\)から互いに重複しない組み合わせを選ぶ（解は一意とは限らない）。このようにして求めた解がコストを最小にする最適割当になる。
- コスト行列の再調整: 線でカバーされていない領域の中から最小値\(\small h\)を発見する。これを用いて、コスト行列の各要素を以下のように調整する。この操作ののちにステップ2に戻り、再度最適性の判定を行う。
- カバーされていないすべての要素から\(\small h\)を引く
- 2本の線で交差している要素（二重にカバーされている要素）に\(\small h\)を足す
- 1本の線でカバーされている要素は変更なし
- ステップ2～4を最適割当が見つかるまで繰り返す。
多くのプログラミング言語ではライブラリが存在するため、自分で実装する必要はなさそうであるが、上記のアルゴリズムで機械的に最適な割当を計算できるので、ゲーム終了ごとに各プレイヤーの最適な座席の割り当てを計算することでテーブルのリバランシングを実行することができる。
まとめ
Greedy方式と異なる方法として、様々なコスト関数を定義することで特徴を持ったテーブルリバランシングの方法を定義できる。例えば、座席の移動回数の公平性にやたらとこだわるアルゴリズムやブラインドの担当回数の公平性を重視するアルゴリズム、反対に、システム都合を優先するアルゴリズムなども考えられる。ハンガリー法を用いてそれらのコストを最小化するようにアルゴリズムを実装することができる。
現実には、Greedy方式で多くの場合それほど違和感がある座席移動にはならないように感じる。しかし、選択肢として何か偏ったテーブルリバランシングのアルゴリズムで遊ぶのが楽しいという場合もあるかもしれない。一般的なゲームでは公平性が重視されるが、公平性を無視した配分アルゴリズムなども面白いかもしれない。ランダムでBTNに多くアサインされるプレイヤーやSB,BBに多くアサインされるプレイヤーを選定するなどしてあえて不公平にするアルゴリズムなど運要素を入れてみるのも面白いだろう。そのうち、通常とは明らかに異なるテーブルリバランシングのアルゴリズム（スタックが少ないプレイヤーをブラインドにアサインして、さっさと負けさせて追い出そうとするアルゴリズムなど）も考えてみたい気がする。
