Pairing Algorithm

Tetsuya Nakajima
(nakaji@othello.org)

Nov. 21, 2002

はじめに

この文章は、オセロ界では世界的に標準となっている組み合わせソフト PAPP のドキュメントを参考に書かれています。参考というよりも、大部分がその論文の翻訳で占められているんですが。PAPPでの考え方を説明しつつ、自作組み合わせソフト SLIM に取り入れた新しい考え方を説明します。

1. プレイヤ数は常に偶数

まず、プレイヤ数が奇数の場合には架空プレイヤを加えて偶数にします。架空プレイヤが対戦相手になったプレイヤは不戦勝とします。これによりプレイヤ数は常に 2N (N は正整数）であると仮定できます。すなわち、各ラウンド共に対局が N 局存在すると言えます。

2. 目的

対局 k において黒番を持つプレイヤを i k 、白番を持つプレイヤを j k で表します。このとき、その対戦がどの程度望ましくないかを pikjk で表します。全ての対局 (i 1 ,j 1 ), (i 2 ,j 2 )…, (i N ,j N ) に関して計算される pi1j1, pi2j2, …, piNjN の総和が最も小さくなる組み合わせを求めることが、この問題のゴールであると言えます。

これをそれらしい数式で書くと、次のようになります。

total_penalty = N
∑
K = 1
p i k j k

このtotal_penalty を最小化するのが目的です。

こいつは典型的なグラフ理論の最小化問題で、多項式時間で解ける ( O(n 3 ) ) らしいのですが、私はその辺知識がありません。SLIMの初期の実装では総当り方式で厳密解を求めようとしたため、N > 10 くらいになると全然計算が終わらなくて困りました。^^; 総当り方式では階乗のオーダーになってしまうんで当たり前と言えば当たり前なんですが。

3. ペナルティ

上で出てきた「どの程度望ましくない対戦か」を表すペナルティ p を、PAPP では下式で定義しています。

p ij = pen_color(i, BLACK) +pen_color(j, WHITE)
+ pen_undulation(i,j)
+ pen_repetition (i,j)
+ pen_chauvinism (i,j)
+ pen_elitism(i,j)

各項の意味を以降説明しますが、ちょいと日本の大会には向かない部分があると考え、SLIM では微妙に変更しています。

3.1. 手番に対するペナルティ

pen_color(i, color) 項は、このラウンドでプレイヤ i が color 番でプレイすることがどのくらい望ましくないか、を表します。ここでδi をプレイヤ i が前ラウンドまでに黒番でプレイした回数と白番でプレイした回数との差であると定義します。この時、プレイヤ i がこのラウンドで黒番を持つ場合のペナルティを pen_color(i, BLACK)、白番を持つ場合のペナルティを pen_color(i, WHITE) で表すと、それぞれ以下の式で計算されます。

pen_color(I, BLACK) = p_col [ |δi + 1| ] + pen_color_repetee
pen_color(I, WHITE) = p_col [ |δi – 1| ] + pen_color_repetee

pen_color_repetee 項は、直前のラウンドの手番と次のラウンドの手番が同じ場合に値 p_repcl を持ちます。直前のラウンドと次のラウンドで手番が違う場合には 0 になります。

SLIM の実装では日本では組み合わせで手番まで決めることは好まれないという判断に基づき、この項はペナルティ計算から除外しています。

3.2. 勝数の違うプレイヤの対戦に対するペナルティ

pen_undulation(i,j) 項は、勝数の違うプレイヤの対戦に対するペナルティです。

pen_undulation(i,j) = p_und [ F ] + pecorr_flood(i) + pecorr_flood(j)

ここで、F はプレイヤ i とプレイヤ j の「勝数×2+引分数」の差の絶対値を表します。p_und[0] は常にゼロになります。即ちプレイヤ i とプレイヤ j の勝数が等しい場合にはこの項は 0 となり、ペナルティに影響しません。一般に、n が大きくなればなるほど p_und[n] の値も大きくなるように設定します。

pecorr_flood(i) 項は、直前のラウンドで自分より勝数の少ないプレイヤと対戦した場合には次のラウンドでは自分より勝数の多いプレイヤと当たりやすく、直前のラウンドで自分より勝数の多いプレイヤと対戦した場合には次のラウンドでは自分より勝数の少ないプレイヤと当たりやすくするための調整項です。

直前のラウンドも次のラウンドも自分より勝数の多いプレイヤと対戦する場合、または直前のラウンドも次のラウンドも自分より勝数の少ないプレイヤと対戦する場合にはpecorr_flood(i) は値 p_flcum を持ちます。

直前のラウンドに自分より勝数の多いプレイヤと対戦していて次のラウンドは自分より勝数の少ないプレイヤと対戦する場合、または直前のラウンドに自分より勝数の少ないプレイヤと対戦していて次のラウンドは自分より勝数の多いプレイヤと対戦する場合にはpecorr_flood(i) は値 -min_fac を持ちます。

3.3. 再戦に対するペナルティ

pen_repetition(i,j) 項は、既に対戦済みの相手と再度対戦することに対するペナルティです。

プレイヤ i とプレイヤ j が既に同じ手番で対戦している場合には、pen_repetition(i,j)には値 p_mcoul が加えられます。プレイヤ i とプレイヤ j が違う手番で対戦している場合には pen_repetition(i,j) には値 p_clopp が加えられます。一般に、p_mcoul > p_clopp となるように設定します。

また、プレイヤ i とプレイヤ j が直前のラウンドで対戦している場合には、pen_repetition(i,j) には更に値 p_desuite が加えられます。

3.4. 同国選手同士の対戦に対するペナルティ

pen_chauvinism(i,j) は同国選手同士の対戦に対して加えられるペナルティです。プレイヤ i とプレイヤ j が同国選手の場合に、pen_chauvinism(i,j) は値 p_chauv[round] を取ります。ここで round は第何ラウンドかを表します。すなわち、このペナルティはそのラウンドが第何ラウンドであるかの関数になります。世界選手権では第12ラウンドと第13ラウンドでは対戦させないという決めがありますが、これはつまり、PAPP で p_chauv[12] と p_chauv[13] の値を猛烈に大きい値に設定して運用していると言えます。

SLIM は日本の大会で使用されることを前提に作られているので、この項は省略しています。

3.5. 上位で勝数の異なる対戦が組まれることに対するペナルティ

pen_elitism(i,j) 項は、勝ち数の異なるプレイヤ同士の対戦がなるべく上位で現れないようにするためのペナルティです。

勝数の異なるプレイヤ同士の対戦に対するペナルティ pen_undulation(i,j) は、その式が表すように勝数差の関数になっています。従って、5勝のプレイヤと4勝のプレイヤが対戦することに対するペナルティと、 1 勝のプレイヤと0勝のプレイヤが対戦することに対するペナルティに差がありません。それに差を付けるために pen_elitism(i,j) が設けられています。

pen_elitism(i,j) = p_elects[round] × (Si+Sj) × | (Si-Sj) |

ここで、Si, Sj はそれぞれのプレイヤの「勝数×2+引分数」を表します。

3.6. 順位の離れたプレイヤの対戦に対するペナルティ

上の 3.5 までが PAPP で使用しているペナルティですが、鋭い方は既にあることにお気づきでしょう。そう、この組み合わせアルゴリズムで評価しているのは各プレイヤの「勝数×2＋引分数」であり、石数なりブライトウェルポイントなりの二次的なポイントを組み合わせに用いていません。従って、日本で通常用いられている勝数及び石数で順番に並べ上から順々に当てる、という方式とかなりかけ離れることになります。これは想像するに、海外の大会では一般に十分な試合数をこなすため、このような組合わせ方法でも上位のプレイヤ同士がそれぞれに当たるので問題ないからなんでしょう。

ということで SLIM では、石数等の二次的ポイントも考慮に入れるため、以下の項を追加しています。

pen_undulation2(i,j) = ( Pi – Pj )2 (Si = Sj の場合)
pen_undulation2(i,j) = ( Ri + Pj )2 (Si > Sj の場合)
pen_undulation2(i,j) = ( Pi + Rj )2 (Si < Sj の場合)

ここで、P は同勝数内での順位 (1以上) を表し、R は同勝数内での下からの順位 (1以上) を表します。
この項により、同勝数内での対戦では順位の近いプレイヤ同士が当たりやすくなり、異なる勝数を持つプレイヤ間の対戦では上位グループ内の下位に近いプレイヤと下位グループの上位に近いプレイヤが当たりやすくなります。

4. ペナルティを最小化する組み合わせを求める

以上でペナルティの計算方法が定義されたので、後はこのペナルティの総和を最小化する組み合わせを求めるだけです。

PAPP の論文によれば先にも書いた通りこの最小化問題は O(n3) で解けるらしく、また PAPP の実装では O(n4) になっているそうです。しかし私はこの最小化問題の一般的な解き方を知らず、ネットで調べてもよくわかりませんでした。また、PAPP のソースコードを読む気力もありませんでした。そこで、欲張り法でとりあえず全組み合わせを作成し、その後ペナルティを小さくする方向に調整をするという自己流の実装を行っております。

まず、以下の方法でとりあえずの組み合わせを作成します。

  1. 対戦相手の決まっていないプレイヤの中で最も順位の高いプレイヤ x を選ぶ
  2. 対戦相手の決まっていないプレイヤの中で x と対戦するペナルティが最も低いプレイヤ y を選び x と y を組み合わせる
  3. 対戦相手の決まっていないプレイヤの中で最も順位の低いプレイヤ X を選ぶ
  4. 対戦相手の決まっていないプレイヤの中で X と対戦するペナルティが最も低いプレイヤ Y を選び X と Y を組み合わせる
  5. 1 に戻る

これでそれなりの組み合わせが作成されます。しかし全体順位の真ん中辺りは最後に組み合わせが実行されるため、ペナルティの高い組み合わせが多数出ることは想像に難くありません。そこで以下の調整のためのステップを踏みます。

  1. 任意のプレイヤ 2 人の対戦相手を入れ替えた場合に入れ替える前よりもペナルティの合計が低くなる場合、対戦相手を入れ替える。入れ替えが発生しなくなるまで全ての組み合わせについてチェック・入れ替えを実行する。
  2. 任意のプレイヤ 3 人の対戦相手を入れ替えた場合に入れ替える前よりもペナルティの合計が低くなる場合、対戦相手を入れ替える。入れ替えが発生しなくなるまで全ての組み合わせについてチェック・入れ替えを実行する。
  3. 任意のプレイヤ 4 人の対戦相手を入れ替えた場合に入れ替える前よりもペナルティの合計が低くなる場合、対戦相手を入れ替える。入れ替えが発生しなくなるまで全ての組み合わせについてチェック・入れ替えを実行する。

もちろんこの方法で厳密解が得られるとは限りませんが、それなりに良い結果が得られます。

なんかこう書いてしまうと SLIM の実装が相当手を抜いているように感じてしまうかもしれませんが、組み合わせソフトとして使えるか否かは、組み合わせ処理が高速であることと、組み合わせ結果に特段違和感を感じないこと、だと思います。微妙に言い訳がましいかもしれませんが、SLIM はこの 2 つの条件を満たしているはずです。

謝辞

テストユーザとしてさまざまな提案・バグ報告を行って下さった星竜一様、さまざまな提案・助言を下さった佐々木惣平様、連盟レイティング報告フォーマットを初めとしてさまざまな助言をして下さった佐藤伸二様、どうもありがとうございました。
また、これから SLIM を使って下さるであろうあなたにも、感謝致します。