Title : Algorithm::Pair::Best
|
Location : Home > Languages > Perl > Package Title : Algorithm::Pair::Best |
|
Algorithm::Pair::Best - 対の抽出（碁のトーナメント用に設計されているが何にでも使える）
use Algorithm::Pair::Best; my $pair = Algorithm::Pair::Best->new( options ); $pair->add( item, item, ... ); @pairList = $pair->pick( $window );
Algorithm::Pair::Best->new オブジェクトを生成した後、対を組む項（プレイヤー）のリストを追加し、新しい項をリンクされたリストに接続する。リンクされたリストは偶数個の項から構成されていなければならない。さもないと対を抽出する際にエラーを発する。
対の生成は部分的には項が追加された順に決定されることもあるが、より重要なのは項にランダムに与えられた info ハッシュによって決定されたスコアに基づいて決定されることである。また他の項に関連した各項にスコアを与えるユーザ関数で決定することもできる。メインの名前空間から Algorithm::Pair::Best パッケージのメソッドにアクセスするのが便利であろう。（使用例は scoreSubs オプションを見よ。）
Algorithm::Pair::Best->pick は項の全ての組み合わせを探索し、最高のスコアの対を返す。これは項の数が増加すれば組み合わせの数は急速に増大するので処理時間のかかる方法である。
項 組み合わせ 2 1 (1) 4 3 (1 * 3) 6 15 (1 * 3 * 5) 8 105 (1 * 3 * 5 * 7) 10 945 (1 * 3 * 5 * 7 * 9 12 10395 (1 * 3 * 5 * 7 * 9 * 11) 14 135135 (1 * 3 * 5 * 7 * 9 * 11 * 13)
項数が多い場合に対を抽出することは明らかにまともなことではない。私のシステムでは12項（6対）に対しては2秒かかり、14項（7対）に対しては20秒かかった（'negative scores only' 最適化なしで）。30項に対してでもかなり長い時間がかかる。
幸運にも、大きな数に対しては、完璧ではないが極めてよい方法がある。一度に全てのリストから対を抽出するのではなくて、Algorithm::Pair::Best->pick でローカルな結果を得るためにより小さいグループを抽出する。新しい方法では window オプションを設定し、各 window で扱う対の数の上限を定めておく。window オプションは window 引数を明示的に用いて呼び出し、オーバライドされる。
$pair->pick($window);
詳しくは後述の window オプションを見よ。
my $pair = Algorithm::Pair::Best->new(options)
新しい Algorithm::Pair::Best オブジェクトは Algorithm::Pair::Best オブジェクトのリンクされたリストのルートとなる。このルートは対になるべき項を示さない。対になる項の集合の制御点となる。
項は add メソッドで Algorithm::Pair::Best リストに追加される。（以下を見よ。）
window => number of pairs
抽出作業中に対生成のためのウィンドウをずらしていく際の対のデフォルトの数を設定する。window 引数に値を渡すことでも設定することができる。
以下に、window の値が 5（対）の場合、どのように動くかを説明する。
最初の対1は10までの間に選ぶ。最初の対はそのままにして12までで項2を選ぶ。最初の対をそのままにして14までに項4を選ぶ。window をずらして最後の１０回に到達するまで行う。（１回の繰り返しの中で終える）
このように60人のプレイヤーからなるトーナメントは 1/4 分以下の時間（繰り返すが、私のシステムでの話）で生成することができる。動いている使用例は Games::Go::AGA の gopair を見よ。
デフォルトは 5 である。
negOnly => true or false
'negative scores only' 最適化を実行するか否かを指定する。sortCandidates の実行中に 0 より大きいスコアがあれば Algorithm::Pair::Best はこのフラグをオフにする。
重要：このフラグが返され、scoreSub が０より大きい値を返すことができれば、結果の対は局所的にも最適ではない。
デフォルトは 1 （実行）である。
scoreSubs => reference to array of scoring subroutines
以下のように、スコア付けサブルーティンが配列順に呼び出される。
foreach my $s (@{$my->scoreSubs}) {
$score += $my->$s($candidate);
}
スコアは加算され、対の抽出が行われる。最高の加算スコアを持つ対は「最良」として保持される。
注意：Algorithm::Pair::Best は０以下のスコアしか返さないスコア付けサブルーティンとはもっともよく動く。詳しくは sortCandidates メソッドを見よ。
スコア付けサブルーティンは以下のように対称的でなければならない。
$a->$scoreSub($b) == $b->$scoreSub($a)
例：
下記のスコアは負であることに注意しよう（Algorithm::Pair::Best は最大の連結スコアを探索する）。 'Negative scores only' は記憶しておくに値する最適化を可能にする。対の抽出時間を大幅に短縮することができる。（またはさらに大きい window を用いる）。詳しくは sortCandidates メソッドを見よ。
. . .
# スコア付けするサブルーチンの配列を生成する
our @scoreSubs = (
sub { # レイティングで異なる。
my ($my, $candidate, $explain) = @_;
# ここでは乗数は 1 で、これは標準的な因子の設定。
my $score = -(abs($my->rating - $candidate->rating));
return sprintf "rating:%5.1f", $score if ($explain);
return $score;
},
sub { # 既に対戦した？
my ($my, $candidate, $explain) = @_;
my $already = 0;
foreach (@{$my->{info}{played}}) {
$already++ if ($_ == $candidate); # 何度も彼と対戦するかも知れない
}
# 既に対戦したのなら大きなペナルティを科す
my $score = -16 * $already;
return sprintf "played:%3.0f", $score if ($explain);
return $score;
},
);
# 上記の「レイティングで異なる」スコア付けサブルーティンは
# Algorithm::Pair::Best 名前空間のレイティング accessor メソッドを必要とする。
{
package Algorithm::Pair::Best;
sub rating { # アクセスレイティングへメソッドを追加（上記の scoreSubs で使用）
my $my = shift;
$my->{info}{rating} = shift if (@_);
return $my->{info}{rating};
}
}
# メインの名前空間に戻る
. . .
上記の例では特別なオプションの $explain 引数があることに注意すること。 Algorithm::Pair::Best は引数を設定しないが、ユーザコードでは以下のように含むことができる。
my @reasons;
foreach my $sSub (@scoreSubs) {
push(@reasons, $p1->$sSub($p2, 1)); # スコアを説明する
}
printf "%8s vs %-8s %s\n", $id1, $id2, join(', ', @reasons);
$p2 と対になるようにいかに $p1 にスコア付けされるかを説明する。
デフォルトは空配列への参照である。
Accessor Methods
Accessor メソッドは以下の項を設定／取得できる。
Accessor メソッドはパラメータとともに呼び出されれば適切な変数を設定し、現在の（または新しい）値を返す。
@pair_items = $pair->add ( item [ item ...] )
対になるべき項（または複数の項）をを追加する。項はいかなるスカラでもよいが、この項と他の項との関係からスコア付けできるいくつかの種類の ID とその情報（レイティングと過去の対戦相手）を含むハッシュへの参照がもっとも有用である。
単項が追加されれば項のために生成されれば（呼び出しのコンテキストにかかわらず）返り値は Algorithm::Pair::Best オブジェクトへの参照である。
複数項が追加されれば、返り値は配列コンテキストの場合は生成された Algorithm::Pair::Best オブジェクトのリストであり、スカラコンテキストの場合はリストへの参照である。
注意：返り値の pair_items リストはまだ対になっていないので大して使いやすいわけではない。
$pair->score ( candidate )
現在の項と候補の項とのスコア（ユーザが定義した scorSubs のリストを呼び出すことで計算された）スコアを返す。
$pair->sortCandidates
各項に対する候補リストをソートする。各項の各候補のスコアをキャッシュしている。
通常は本ルーティンは、抽出を開始する前に sortCandidate を呼び出すように呼び出す必要はない。しかしながらソート自身に基づいて候補スコアを修正したければ（たとえばトーナメントの早期ラウンドで最良の試合が組まれてしまうのを防ぐためなど） sortCandidates を呼び出し、スコア修正を行い（候補のスコア付けされたリストへの参照を取得するために citems メソッドを用い、スコアを変更するために $item->score($candidate, $newscore) を用いる）。スコアのキャッシュを変更し、再度 sortCandidates を呼び出し、新しいスコアキャッシュに基づき再ソートを行う。
注意：sortCandidates の間中、スコアは非負であることが確認される。0 または負の値のみしか使われていないのであれば pick メソッドは現在の最良対以下のスコアをパスすることで最適化を行うことができる。０よりも大きいスコアがあれば 'negative scores only' (negOnly) 最適化は実行しない。
@pairs = $pair->pick ($window)
上記の説明セクションで記述されているように、 window ずらしテクニックで発見された最良の対を返す。window のサイズは $windows 対（2*$windows 項）である。もし window 引数がなければデフォルトの window が新しい呼び出しの際に用いられる。
pick は対の順序： item[0] は item[1] と対、item[2] は item[3] と対、などにおける Algorithm::Pair::Best オブジェクトのリスト（またはスカラコンテキストではリストへの参照）を返す。
pick は対のリストに対して健全さの確認を行う。すなわち重複している項や、選択されていない項がないことを確認する。
$pair->progress ( $item0, $item1 )
上記 pick ルーチン内で対が完成するたびにサブルーチンで進展が定義されているサブルーチンが呼び出されたかを確認する。もしそうであれば pick は $pair->progress($item0, $item1) を呼び出す。ただし $item0 及び $item1 は直近の追加対である。
進展は the Algorithm::Pair::Best パッケージ内では定義されない。これは呼び出し側で定義される。例えば各対が完成する際にメッセージを出力するには以下のようにする。
. . .
{
package Algorithm::Pair::Best;
sub progress {
my ($my, $item0, $item1) = @_;
# 文字列を返す 'id' メソッドが提供されていると仮定する。
print $item0->id, " paired with ", $item1->id, "\n";
}
}
# メインの名前空間に戻る
. . .
$pairsRef = $pair->wpick ( $window )
通常は wpick は pick メソッドからのみ呼び出される。
wpick はリスト（足した順で定義される）内の最初の対になっていない項から始まる$window 対（または 2*$window 項）の最良の対のリストへの参照を返す。返り値のリストは pick 内で記述された対の順となっている。
対になっている項が 2*$window 項より少なければエラーを出力し、残余の項の最良対を返す。奇数個の項が残っていればエラーを出力し、最後の項を除いた中で最良の対を返す。
対生成が追加リストの最初の項から始まっている間は返り値のリストは追加リストの最初の 2*$window 項の外部の項を含んでいるかもしれないことに注意すべきである。これは各項が参照対の順序化された対を持っているからである。しかしながら追加リストの最初の対になっていない項は返り値のリストの最初の項になるはずである。
同様に奇数個の項が残っている状況であっても、捨てる項は追加リストの最後の項である必要はない。
$score = $pair->scoreFunc ( $candidate, $score )
scoreFunc は Algorithm::Pair::Best パッケージでは定義されないが、pick メソッドは呼び出し側がサブルーティンを定義したかを名前で確認する。定義されていれば試行対生成時に currScore 総和に候補のスコアを足しこむたびに呼び出される。
通常は、Algorithm::Pair::Best は単純にスコアを足し、最高の総和を探索する。異なるスコア総和、例えば、スコアの２乗の総和にすれば（よい対のグループを１つの悪いグループが結果を悪くすることを防ぐため）異なる結果になる。scoreFunc はこの修正を提供する。
定義されていれば scoreFunc は以下のように呼び出される。
$score = $item->scoreFunc($candidate, $score);
ただし $item は現時点での Algorithm::Pair::Best の対であり、$candidate は検討中の候補であり、$score は $candidate の変更前のスコアである（wrt $item）。
重要：負のスコアを保持していることに注意すること（または最適化を起動しない。）
scoreFuncの使用例：
. . .
{
package Algorithm::Pair::Best;
sub scoreFunc {
my ($my, $candidate, $score) = @_;
# スコアの２乗を最小化したいので
return -($score * $score);
}
}
# メインの名前空間に戻る
. . .
Reid Augustin, <reid@HelloSix.com>
Copyright (C) 2004, 2005 by Reid Augustin
本ライブラリはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。Perl 5.8.5、利用者の選択によっては Perl 5以降の入手可能なバージョンで利用可能である。
|
|
Updated : 2008/08/17 |