Algorithm::Pair::Best - deprecated - use Algorithm::Pair::Best2
version 1.036
use Algorithm::Pair::Best; my $pair = Algorithm::Pair::Best->new( ? options ? ); $pair->add( item, ? item, ... ? ); @pairList = $pair->pick( ? $window ? );
Given a set of user-supplied scoring functions that compare all possible pairs of items, Algorithm::Pair::Best attempts to find the 'best' collective pairings of the entire group of items.
After creating an Algorithm::Pair::Best->new object, add a list of items (players) to be paired. add connects the new items into a linked list. The total number of items added to the linked list must consist of an even number of items or you'll get an error when you try to pick the pairs.
Pairings are determined partially by the original order items were added, but more importantly, items are paired based on scores which are determined by user supplied functions that provide a score for each item in relation to other items (see scoreSubs below). An info hash is attached to each itme to assist the scoring functions. It may be convenient to add access methods to the Algorithm::Pair::Best package from the main namespace (see the scoreSubs option to new below for an example).
Algorithm::Pair::Best->pick explores all combinations of items and returns the pairing with the best (highest) score. This can be an expensive proposition - the number of combinations goes up very fast with respect to the number of items:
items combinations 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)
It is clearly unreasonable to try to pair a significant number of items. On my system it takes about 2 seconds to pair 12 items (6 pairs), and 20 seconds to pair 14 items (with no 'negative scores only' optimization). Trying to completely pair even 30 items would take too long.
Fortunately, there is a way to get pretty good results for large numbers, even if they're not perfect. Instead of trying to pair the whole list at once, Algorithm::Pair::Best->pick pairs a series of smaller groups within a 'window' to get good 'local' results. The list created by add should be moderately sorted so that most reasonable candidates will be within window range of each other.
The new method accepts a window option to limit the number of pairs in each window. The window option can also be overridden by calling pick with an explicit window argument:
$pair->pick($window);
See the description of the window and pick below.
Algorithm::Pair::Best is deprecated - use Algorithm::Pair::Best2
Algorithm::Pair::Best - Perl module to select pairings (designed for Go tournaments, but can be used for anything, really).
A new Algorithm::Pair::Best object becomes the root of a linked list of Algorithm::Pair::Best objects. This root does not represent an item to be paired. It's just a control point for the collection of items to be paired.
Items are added to the Algorithm::Pair::Best list with the <add> method (see below).
Sets the default number of pairs in the sliding pairing window during a pick. Can also be set by passing a window argument to pick.
Here's how a window value of 5 (pairs) works: first pair items 1 through 10. Keep the pairing for the top two items and then pair items 2 through 12. Keep the top pairing and move down to items 4 through 14. Keep sliding the window down until we reach the last 10 items (which are completed in one iteration). In this way, a tournament with 60 players takes less than 1/4 a minute (again, on my system) to pair with very good results. See the gopair script in Games::Go::AGA for a working example.
Default: 5
Enable/disable the 'negative scores only" optimization. If any score greater than 0 is found during sortCandidates, Algorithm::Pair::Best turns this flag off.
IMPORTANT: If this flag is turned on and a scoreSub can return a number greater than 0, the resultant pairing may not be optimal, even locally.
Default: 1 (enabled)
Scoring subroutines are called in array order as:
foreach my $s (@{$my->scoreSubs}) { $score += $my->$s($candidate); }
Scores are accumulated and pairings are attempted. The pairing with the highest cumulative score is kept as the 'best'. Note: Algorithm::Pair::Best works best with scoring subroutines that return only scores less than or equal to 0 - see the sortCandidates method for more details.
The scoring subroutines should be symmetric so that:
$a->$scoreSub($b) == $b->$scoreSub($a)
Example:
Note that the scores below are negative (Algorithm::Pair::Best searches for the highest combined score). 'Negative scores only' allows an optimization that is probably worth keeping in mind - it can reduce pairing time by several orders of magnitude (or allow a larger window). See the sortCandidates method for more information.
. . . # create an array of scoring subroutines: our @scoreSubs = ( sub { # difference in rating. my ($my, $candidate, $explain) = @_; # the multiplier here is 1, so that makes this the 'normal' factor my $score = -(abs($my->rating - $candidate->rating)); return sprintf "rating:%5.1f", $score if ($explain); return $score; }, sub { # already played? my ($my, $candidate, $explain) = @_; my $already = 0; foreach (@{$my->{info}{played}}) { $already++ if ($_ == $candidate); # we might have played him several times! } # large penalty for each time we've already played my $score = -16 * $already; return sprintf "played:%3.0f", $score if ($explain); return $score; }, ); # the 'difference in rating' scoring subroutine above needs a 'rating' # accessor method in the Algorithm::Pair::Best namespace: { package Algorithm::Pair::Best; sub rating { # add method to access ratings (used in scoreSubs above) my $my = shift; $my->{info}{rating} = shift if (@_); return $my->{info}{rating}; } } # back to the main namespace . . .
In the above example, note that there is an extra optional $explain argument. Algorithm::Pair::Best never sets that argument, but user code can include:
my @reasons; foreach my $sSub (@scoreSubs) { push(@reasons, $p1->$sSub($p2, 1)); # explain scoring } printf "%8s vs %-8s %s\n", $id1, $id2, join(', ', @reasons);
to explain how $p1 scores when paired with $p2.
Default: ref to empty array
Accessor methods can read and write the following items:
Accessor methods set the appropriate variable if called with a parameter, and return the current (or new) value.
Add an item (or several items) to be paired. The item(s) can be any scalar, but it's most useful if it is a reference to a hash that contains some kind of ID and information (like rating and previous opponents) that can be used to score this item relative to the other items.
If a single item is added, the return value is a reference to the Algorithm::Pair::Best object created for the item (regardless of calling context).
If multiple items are added, the return value is the list of created Algorithm::Pair::Best objects in array context, and a reference to the list in scalar context.
Note: the returned pair_items list is not very useful since they have not yet been paired.
Returns the score (as calculated by calling the list of user-supplied scoreSubs) of the current pairing item relative to the candidate pairing item.
The score is calculated only once, and the cached value is returned thereafter.
If new_score is defined, the cached candidate and item scores are set to new_score.
Sort each candidate list for each item. This method calls score (above) which caches the score for each candidate in each item.
Normally this routine does not need to be called as the pick method calls sortCandidate before it starts picking. However, if you would like to modify candidate scores based on the sorting itself (for example, in the early rounds of a tournament, you may wish to avoid pairing the best matches against each other), you can call sortCandidates, and then make scoring adjustments (use the citems method to get a reference to the sorted list of candidates, then use $item->score($candidate, $new_score) to change the score). After changing the score cache, calling the pick method calls sortCandidates once more which will re-sort based on the new scores cache.
Note: during sortCandidates, the scores are checked for non-negative values. If only 0 or negative values are used, the pick method can optimize by skipping branches that already score below the current best pairing. Any scores greater than 0 disable the 'negative scores only' (negOnly) optimization.
Returns the best pairing found using the sliding window technique (calling wpick) as discussed in DESCRIPTION above. The size of the window is $windows pairs (2*$windows items). If no window argument is passed, the default window selected in the new call is used.
pick returns the list (or a reference to the list in scalar context) of Algorithm::Pair::Best objects in pairing order: item[0] is paired to item[1], item[2] to item[3], etc.
pick performs a sanity check on the pairs list, checking that no item is paired twice, and that all items are paired.
Each time a pair is finalized in the pick routine above, it checks to see if a subroutine called progress has been defined. If so, pick calls $pair->progress($item0, $item1) where $item0 and $item1 are the most recently added pair of items.
progress is not defined in the Algorithm::Pair::Best package. It is meant to be provided by the caller. For example, to print a message as each pair is finalized:
. . . { package Algorithm::Pair::Best; sub progress { my ($my, $item0, $item1) = @_; # assuming you have provided an 'id' method that returns a string: print $item0->id, " paired with ", $item1->id, "\n"; } } # back to main:: namespace . . .
Normally wpick is only called by the pick method.
wpick returns a reference to a list of the best pairing of $window pairs (or 2*$window items) starting from the first unpaired item in the list (as determined by add order). The returned list is in pairing order as described in pick.
If there are fewer than 2*$window items remaining to be paired, prints an error and returns the best pairing for the remaining items. If an odd number of items remain, prints an error and returns the best pairing excluding the last item.
Note that while the pairing starts from the first item in the add list, the returned pairs list may contain items from outside the first 2*$window items in the add list. This is because each item has its own ordered list of preferred pairs. However, the first unpaired item in the add list will be the first item in the returned list.
Similarly, in the 'odd number of items remaining' situation, the discarded item is not neccessarily the last item in the add list.
scoreFunc is not defined in the Algorithm::Pair::Best package, but the pick method checks to see if the caller has defined a subroutine by that name. If defined, it is called each time a candidate score is added to the currScore total for a trial pairing.
Normally, Algorithm::Pair::Best simply adds the scores and tries for the highest total score. Some pairings may work better with a different total score, for example the sum of the squares of the scores (to reduce the ability of one bad pairing to compensate for a group of good pairings). scoreFunc provides a hook for this modification.
If defined, scoreFunc is called as:
$score = $item->scoreFunc($candidate, $score);
where $item is the current Algorithm::Pair::Best item being paired, $candidate is the current candidate item under consideration, and $score is $candidate's unaltered score (wrt $item).
IMPORTANT: Remember to retain negative scores (or disable the negOnly optimization.
Example use of scoreFunc: . . . { package Algorithm::Pair::Best; sub scoreFunc { my ($my, $candidate, $score) = @_;
# we want to minimize the squares of the scores: return -($score * $score); } } # back to main:: namespace . . .
The gopair script from the Games::Go::GoPair package uses Algorithm::Pair::Best to run pairings for a go tournament
Reid Augustin, <reid@HelloSix.com>
Copyright (C) 2004, 2005 by Reid Augustin
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.5 or, at your option, any later version of Perl 5 you may have available.
Reid Augustin <reid@hellosix.com>
This software is copyright (c) 2011 by Reid Augustin.
This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.
To install Algorithm::Pair::Best, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Algorithm::Pair::Best
CPAN shell
perl -MCPAN -e shell install Algorithm::Pair::Best
For more information on module installation, please visit the detailed CPAN module installation guide.