On Wed, Nov 04, 2009 at 04:03:54PM -0500, Dave O'Neill wrote:
> A further refinement might be to let teams choose an ordering of field
> sites, rather than trying to guess based on straight-line distance
> calculations (car and transit commutes can be quite a lot longer for
> seemingly-short straight-line distances in Ottawa). Teams that really
> care could list all available fields in the order they would like to
> use them, and teams that don't care so much could just pick the top 1
> or 2. I'm not sure how this could tie into an opponent-selection
> metric, though.
Ok, some quick thinking over my final coffee of the day came up with
this flow:
Prerequisites:
a) Fields get refactored into Facilities (the location) and Fields
(the individual playing field).
b) Teams must now select an Opponent Preference (OP) from:
"Having the best opponent matters more than field location" (best
opponent)
"Field location matters more than a perfect opponent" (location)
"I don't care"
c) Teams can rank their preferred Facilities in order, choosing
up to 10 facilities in their list. (the limit of 10 is to keep
step 2 below to a workable runtime)
d) Site admins (or possibly individual coordinators) can choose to
allow Opponent Preference for a given league to be
team-selectable, forced to best-opponent (which should equate to
the current system for a purely ranking-based league), or forced
to location (which should produce a league where everyone gets
games in a desired location)
Algorithm:
1) Find all teams with an OP of best opponent, or don't care. Choose
nearest opponent on the ladder for each of these teams from that
set, respecting the ladder distance and games-between-repeat
thresholds. Possibly use multiple passes to optimize as at
present. At the end of this step, all best-opponent teams should
have an opponent, but no field assigned.
2) Find all remaining teams with an OP of location or don't care. Grab
each team's list of preferred facilities as well. Sort teams in
ascending order of field preference satisfaction (0 == never had
it, 1 == always had it). Pop off the top team on this list, mark
it as home, and find all other opponents on the list with the
same top facility preference and choose the nearest one on the
ladder, respecting games-between-repeat and maximum ladder
distance. If no matching opponent found, or no fields remaining
at that facility, choose home team's second-best facility
and repeat. At the end of this step, all location-preference
teams should have both an opponent, a home/away selection, and an
assigned field.
3) Iterate over all best-opponent matchups and choose a home team
using the current algorithm (converge on .500 for home games).
4) Sort best-opponent matchups in order of field preference
satisfaction. Pop off the top team and allocate a field from the
highest-preference facility with fields still available.
5) Done!
I'd appreciate if others on the list can think about it for a few
minutes and try to poke some holes in this. I think it meets the
criteria, but as we haven't fully defined what the acceptance criteria
are, maybe it doesn't :)
Cheers,
Dave
_______________________________________________
Leaguerunner mailing list
[email protected]
http://www.dmo.ca/cgi-bin/mailman/listinfo/leaguerunner
