Reid Augustin

# NAME

Algorithm::Pair::Best - Perl module to select pairings (designed for Go tournaments, but can be used for anything, really).

# SYNOPSIS

``````    use Algorithm::Pair::Best;

my \$pair = Algorithm::Pair::Best->new( ? options ? );

\$pair->add( item, ? item, ... ? );

@pairList = \$pair->pick( ? \$window ? );``````

# DESCRIPTION

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 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 an info hash used to attach any random data to the item, and user supplied functions to provide a score for each item in relation to other items. 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 to get good 'local' results. 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 option below.

# METHODS

my \$pair = Algorithm::Pair::Best->new(?options?)

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).

## Options

window => number of pairs

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

negOnly => true or false

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 and a scoreSub can return a number greater than 0, the resultant pairing may not be optimal, even locally.

Default: 1 (enabled)

scoreSubs => reference to array of scoring subroutines

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;
},
my (\$my, \$candidate, \$explain) = @_;

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

Accessor methods can read and write the following items:

items reference to the list of added items (root only)
info reference to the user-defined info hash
cscores reference to the hash of scores cache
citems reference to list of candidates sorted by score
opp currently selected opponent, or undef if not paired
next next candidate in the list
window (class) default number of pairs in sliding window
negOnly (class) use 'negative scores only' optimization
scoreSubs (class) user-supplied list of scoring subroutines
bestScore (class) current best score for all pairings to date

Accessor methods set the appropriate variable if called with a parameter, and return the current (or new) value.

@pair_items = \$pair->add ( item [ item ...] )

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.

\$pair->score ( candidate )

Returns the score (as calculated by calling the list of user-supplied scoreSubs) of the current pairing item relative to the candidate pairing item.

\$pair->sortCandidates

Sort each candidate list for each item. This also 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, \$newscore) 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.

@pairs = \$pair->pick ( ?\$window? )

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.

\$pair->progress ( \$item0, \$item1 )

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
.  .  .``````
\$pairsRef = \$pair->wpick ( \$window )

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.

\$score = \$pair->scoreFunc ( \$candidate, \$score )

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
.  .  .``````

o gopair(1)

The gopair script from the Games::Go::GoPair package uses Algorithm::Pair::Best to run pairings for a go tournament

# AUTHOR

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.

3 POD Errors

The following errors were encountered while parsing the POD:

Around line 167:

You forgot a '=back' before '=head2'

Around line 317:

'=item' outside of any '=over'

Around line 718:

Can't have a 0 in =over 0