Christer
Joined: Aug 02, 2003

Late last night, I enabled a new version of the scheduler. The change this time around was in how the scheduler picks which matches to schedule. To keep you all fully informed, this is how the scheduler works now:
Step one: Generate a graph of all potential matches
The first step is to create a list of all potential matchups. This is done in the most trivial way possible by simply matching every coach against every other. So if we have coaches A, B, C and D participating, the scheduler creates a list of the following pairs:
A vs B
A vs C
A vs D
B vs C
B vs D
C vs D
Step two: Find the best possible match for each potential coach pair
For each pair of coaches, the scheduler tries to find the "best" possible match. This is done by calculating the suitability score (more on this later) for each possible pair of teams between the two coaches. For example, we'll consider the pair A vs B above. We assume that coach A has 3 teams (A1, A2, and A3) while coach B has 2 teams (B1, B2). The suitability is calculated for all possible pairs. For example, we could get something like:
A1 vs B1 @950
A1 vs B2 @799
A2 vs B1 @893
A2 vs B2 @912
A3 vs B1 Not allowed due to strength difference
A3 vs B2 @635
With this lineup, the scheduler would pick A1 vs B1 as the match for the pair of coaches and skip the rest of the possible matches.
This is done for each pair of coaches. Note that this means that different teams may be picked against different coaches (so, for example, in the case A vs D above, we might end up with A3 vs D4 even if A1 was the best match against B's teams).
Step three: Pick the schedule
At this point, we have a list of potential matches, together with the suitability of each of them. The task that remains is to figure out the best way to schedule each coach to make the matches as fair as possible.
Since this task is nontrivial (look up the "Stable Roommates Problem" for further information on how complex this is), a "best effort" method is used:
There are two separate methods used which are run in a few different variations:
1. Looking "per match".
In this method, all the possible matches are put into a big list. The scheduler takes the match at the top of the list, and schedules it. Then it goes down to the next match, and checks if either of the coaches involved are already scheduled. If not, the match is scheduled. This is repeated through the list until all coaches are scheduled, or the list ends. There are three variations of this method, based on the sort order of the initial list:
a) Highest suitability first
b) Lowest suitability first
c) Random
2. Looking "per coach"
This method works in a similar manner as the above, but instead of making a big list of matches it makes a list of coaches. The scheduler then takes the top coach and picks the highest suitability score of the matces against the currently unscheduled opponents. Naturally, this is the highest one when it looks at the first coach. The process is then repeated down the list of coaches until all participants have been considered.
As with method 1 above, the variations of this method come from different ways to sort the initial list. The variations used now are:
a) Lowest "top" suitability (suitability of the best possible match)
b) Highest "top" suitability
c) Lowest total suitability (sum of all suitabilities)
d) Highest total suitability
e) Least number of possible opponents
f) Most number of possible opponents
g) Random
Step four: Choosing the schedule
At this point, the scheduler has a number of different possible schedules to consider. To pick which one to use, it simply adds up the total suitability of each schedule, and picks the one with the highest total suitability score.
The schedule is announced, and coaches can start playing.
Suitability score
The suitability score is calculated as follows:
1. Calculate the win probability (p) of the match as follows:
 Get the team strengths of the two teams.
 Adjust the strength of one of the teams with 5 TS per handicap.
 Calculate the win probability for the teams using the normal ranking formula. In this step, use equal rankings (ie, dR = 0).
 In the above ranking formula, if the normalised strength difference is above 5, use the following instead:
dT = (dT*3)  10*dT (properly adjusted for who is higher or lower)
 Apply racial factor as normal.
2. Subtract p by 0.5 (transposing the value to be centered around 0 rather than 0.5).
3. Define the distance as the absolute value of p
4. Apply a small random factor (adding 0  0.02)
5. Normalise the distance to 01
6. Get the base suitability as 1normalised distance
7. If the two teams are of the same race, multiply suitability by 0.97
8. If either team played the other in their last game, multiply suitability by 0.94
9. If there are any handicaps in the game, multiply suitability by (1numHandicaps * 0.03)
10. Scale suitability to 01000 (ie, multiply by 1000 and round to an integer). 
Last edited by Christer on Jul 29, 2009  11:00; edited 1 time in total 

Christer
Joined: Aug 02, 2003

To give you an example of how the scheduler works, I'll provide you with some data from one of the schedules that were generated last night.
There were 10 coaches who activated, and after step one and two in the process above, these potential matches were found:
Code:  runreallyfast
 runreallyfast vs Ropetus (Wood Elf 147/136 vs 129/137 Dwarf) @946
 runreallyfast vs benkobi (Ogre 182/163 vs 188/173 Dwarf) @929
 runreallyfast vs warpork (Ogre 182/163 vs 172/166 Chaos) @928
 runreallyfast vs wooti (Wood Elf 147/136 vs 185/152 Ogre) @913
 runreallyfast vs PurpleChest (Ogre 182/163 vs 131/139 Dark Elf) @890
 runreallyfast vs Fellwesterion (Ogre 182/163 vs 149/154 Khemri) @866

Fellwesterion
 Fellwesterion vs wooti (Khemri 149/154 vs 169/165 Chaos) @953
 Fellwesterion vs warpork (Khemri 149/154 vs 172/166 Chaos) @945
 Fellwesterion vs Ropetus (Khemri 149/154 vs 159/159 Chaos Dwarf) @942
 Fellwesterion vs PurpleChest (Khemri 149/154 vs 131/139 Dark Elf) @904
 runreallyfast vs Fellwesterion (Ogre 182/163 vs 149/154 Khemri) @866
 Fellwesterion vs benkobi (Khemri 149/154 vs 188/173 Dwarf) @810

Ropetus
 Ropetus vs warpork (Chaos Dwarf 159/159 vs 172/164 Wood Elf) @953
 runreallyfast vs Ropetus (Wood Elf 147/136 vs 129/137 Dwarf) @946
 Ropetus vs PurpleChest (Dwarf 129/137 vs 131/139 Dark Elf) @946
 Fellwesterion vs Ropetus (Khemri 149/154 vs 159/159 Chaos Dwarf) @942
 Ropetus vs wooti (Chaos Dwarf 159/159 vs 169/165 Chaos) @937
 Ropetus vs benkobi (Dark Elf 175/182 vs 188/173 Dwarf) @855

Kharnete
 Kharnete vs Haxtor (Chaos Dwarf 115/106 vs 102/93 Dark Elf) @830
 Kharnete vs Wop (Chaos Dwarf 115/106 vs 105/95 Chaos) @808

wooti
 wooti vs warpork (Chaos 169/165 vs 172/166 Chaos) @964
 Fellwesterion vs wooti (Khemri 149/154 vs 169/165 Chaos) @953
 Ropetus vs wooti (Chaos Dwarf 159/159 vs 169/165 Chaos) @937
 runreallyfast vs wooti (Wood Elf 147/136 vs 185/152 Ogre) @913
 wooti vs PurpleChest (Chaos 169/165 vs 175/170 Orc) @870
 wooti vs benkobi (Chaos 169/165 vs 188/173 Dwarf) @822

warpork
 warpork vs PurpleChest (Chaos Dwarf 166/173 vs 175/170 Orc) @995
 warpork vs benkobi (Dark Elf 186/170 vs 188/173 Dwarf) @980
 wooti vs warpork (Chaos 169/165 vs 172/166 Chaos) @964
 Ropetus vs warpork (Chaos Dwarf 159/159 vs 172/164 Wood Elf) @953
 Fellwesterion vs warpork (Khemri 149/154 vs 172/166 Chaos) @945
 runreallyfast vs warpork (Ogre 182/163 vs 172/166 Chaos) @928

PurpleChest
 warpork vs PurpleChest (Chaos Dwarf 166/173 vs 175/170 Orc) @995
 Ropetus vs PurpleChest (Dwarf 129/137 vs 131/139 Dark Elf) @946
 PurpleChest vs benkobi (Orc 175/170 vs 188/173 Dwarf) @940
 Fellwesterion vs PurpleChest (Khemri 149/154 vs 131/139 Dark Elf) @904
 runreallyfast vs PurpleChest (Ogre 182/163 vs 131/139 Dark Elf) @890
 wooti vs PurpleChest (Chaos 169/165 vs 175/170 Orc) @870

Wop
 Wop vs Haxtor (Chaos 105/95 vs 102/93 Dark Elf) @981
 Kharnete vs Wop (Chaos Dwarf 115/106 vs 105/95 Chaos) @808

Haxtor
 Wop vs Haxtor (Chaos 105/95 vs 102/93 Dark Elf) @981
 Kharnete vs Haxtor (Chaos Dwarf 115/106 vs 102/93 Dark Elf) @830

benkobi
 warpork vs benkobi (Dark Elf 186/170 vs 188/173 Dwarf) @980
 PurpleChest vs benkobi (Orc 175/170 vs 188/173 Dwarf) @940
 runreallyfast vs benkobi (Ogre 182/163 vs 188/173 Dwarf) @929
 Ropetus vs benkobi (Dark Elf 175/182 vs 188/173 Dwarf) @855
 wooti vs benkobi (Chaos 169/165 vs 188/173 Dwarf) @822
 Fellwesterion vs benkobi (Khemri 149/154 vs 188/173 Dwarf) @810 
In step three, this is what the scheduler considered:
Code:  Generating schedule #1
 Kharnete vs Haxtor (Chaos Dwarf 115/106 vs 102/93 Dark Elf) @830
 Ropetus vs PurpleChest (Dwarf 129/137 vs 131/139 Dark Elf) @946
 warpork vs benkobi (Dark Elf 186/170 vs 188/173 Dwarf) @980
 Fellwesterion vs wooti (Khemri 149/154 vs 169/165 Chaos) @953
New best score: 3709
Generating schedule #2
 wooti vs PurpleChest (Chaos 169/165 vs 175/170 Orc) @870
 Kharnete vs Wop (Chaos Dwarf 115/106 vs 105/95 Chaos) @808
 Fellwesterion vs benkobi (Khemri 149/154 vs 188/173 Dwarf) @810
 runreallyfast vs warpork (Ogre 182/163 vs 172/166 Chaos) @928
Generating schedule #3
 Ropetus vs wooti (Chaos Dwarf 159/159 vs 169/165 Chaos) @937
 Kharnete vs Wop (Chaos Dwarf 115/106 vs 105/95 Chaos) @808
 runreallyfast vs PurpleChest (Ogre 182/163 vs 131/139 Dark Elf) @890
 warpork vs benkobi (Dark Elf 186/170 vs 188/173 Dwarf) @980
Generating schedule #4
 Kharnete vs Haxtor (Chaos Dwarf 115/106 vs 102/93 Dark Elf) @830
 runreallyfast vs Ropetus (Wood Elf 147/136 vs 129/137 Dwarf) @946
 warpork vs benkobi (Dark Elf 186/170 vs 188/173 Dwarf) @980
 Fellwesterion vs wooti (Khemri 149/154 vs 169/165 Chaos) @953
Generating schedule #5
 runreallyfast vs benkobi (Ogre 182/163 vs 188/173 Dwarf) @929
 Wop vs Haxtor (Chaos 105/95 vs 102/93 Dark Elf) @981
 warpork vs PurpleChest (Chaos Dwarf 166/173 vs 175/170 Orc) @995
 Fellwesterion vs wooti (Khemri 149/154 vs 169/165 Chaos) @953
New best score: 3858
Generating schedule #6
 Kharnete vs Haxtor (Chaos Dwarf 115/106 vs 102/93 Dark Elf) @830
 runreallyfast vs Ropetus (Wood Elf 147/136 vs 129/137 Dwarf) @946
 warpork vs benkobi (Dark Elf 186/170 vs 188/173 Dwarf) @980
 Fellwesterion vs wooti (Khemri 149/154 vs 169/165 Chaos) @953
Generating schedule #7
 runreallyfast vs Ropetus (Wood Elf 147/136 vs 129/137 Dwarf) @946
 Wop vs Haxtor (Chaos 105/95 vs 102/93 Dark Elf) @981
 warpork vs PurpleChest (Chaos Dwarf 166/173 vs 175/170 Orc) @995
 Fellwesterion vs wooti (Khemri 149/154 vs 169/165 Chaos) @953
New best score: 3875
Generating schedule #8
 Kharnete vs Haxtor (Chaos Dwarf 115/106 vs 102/93 Dark Elf) @830
 runreallyfast vs Ropetus (Wood Elf 147/136 vs 129/137 Dwarf) @946
 warpork vs PurpleChest (Chaos Dwarf 166/173 vs 175/170 Orc) @995
 Fellwesterion vs wooti (Khemri 149/154 vs 169/165 Chaos) @953
Generating schedule #9
 Kharnete vs Haxtor (Chaos Dwarf 115/106 vs 102/93 Dark Elf) @830
 runreallyfast vs Ropetus (Wood Elf 147/136 vs 129/137 Dwarf) @946
 warpork vs PurpleChest (Chaos Dwarf 166/173 vs 175/170 Orc) @995
 Fellwesterion vs wooti (Khemri 149/154 vs 169/165 Chaos) @953
Generating schedule #10
 Kharnete vs Haxtor (Chaos Dwarf 115/106 vs 102/93 Dark Elf) @830
 runreallyfast vs Ropetus (Wood Elf 147/136 vs 129/137 Dwarf) @946
 warpork vs PurpleChest (Chaos Dwarf 166/173 vs 175/170 Orc) @995
 Fellwesterion vs wooti (Khemri 149/154 vs 169/165 Chaos) @953 
As you can see, the #1 schedule was obviously considered the best up until that point. After considering schedule #2 and #3, the first one was still the best. This is where the old scheduler would have stopped and it would have posted schedule #1 as the final one. Note that #1 was almost always the chosed schedule in the old system.
After these first three attempts, the scheduler started with the coachbased schedules instead and you see that schedule #5 is considered better and is marked as the best one so far. The scheduler then continues on and finds an even better one with #7, which ends up being the highest suitability score of them all.
As you can see, looking strictly at the suitability scores of the resulting schedule (#7), it looks more "fair" than the original #1 schedule that would have been picked before the change.
At this point, I'm fairly happy with how it picks the final schedule. However, I'm sure there are still improvements to be made in the suitability formula. 


DukeTyrion
Joined: Feb 18, 2004

Posted:
Jul 29, 2009  10:22 

Looks great.
That's alot of matchups being considered by the scheduler 


TheCetusProject
Joined: May 25, 2004

Posted:
Jul 29, 2009  10:27 

That looks like quite a significant improvement in that example. Of course, the match runreallyfast vs Ropetus (Wood Elf 147/136 vs 129/137 Dwarf) @946 could be further improved by not playing with handicaps for that game. 


Kraark
Joined: Dec 14, 2006

Posted:
Jul 29, 2009  10:28 


Christer
Joined: Aug 02, 2003

A consequence of how step four works is that the scheduler will pick a schedule where one person gets a lower score to improve the overall score. For example, a more recent example from this morning:
Code:  Generating schedule #1
 LowAV vs Blackwidow (Wood Elf 132/126 vs 116/112 Undead) @902
 Joonatin vs haenschel (Lizardmen 135/135 vs 145/142 Chaos) @935
 maznaz vs MenomaN (Chaos 180/184 vs 204/186 Orc) @944
 Emeyin vs freud (Chaos 245/216 vs 207/198 Wood Elf) @918
New best score: 3699
(...)
Generating schedule #5
 Joonatin vs freud (Lizardmen 135/135 vs 128/142 Necromantic) @963
 Emeyin vs MenomaN (Orc 240/210 vs 204/186 Orc) @822
 haenschel vs maznaz (Chaos 145/142 vs 136/139 Orc) @947
 LowAV vs Wreckage (Norse 100/94 vs 100/98 High Elf) @972
New best score: 3704 
You see that the chosen schedule has a lower minimum suitability than the first considered schedule. Effectively, the system picks the @822 match to improve the other matches. Is this the best way to handle it? What do you guys think? 


Rawlf
Joined: Jul 15, 2007

Posted:
Jul 29, 2009  10:40 

I was just thinking about how good the matchups were today. You are certainly doing a great job with scheduler Christer, thanks a lot!
Just one question: isn't the notpreferred team modifier redundant now with the new activation method? 


CircularLogic
Joined: Aug 22, 2003

Posted:
Jul 29, 2009  10:59 

What strike me, is that the scheduler will go lenghts to ensure the maximum number of games, even at the expense of all others. This is because even a very bad match ends up with a siutability of at least 600. That means that in a typical round of 8 coaches, the scheduler will do everything to cramp in that one outlier with the only possible match, even if it messes up the whole round and lowers the siutability of all other matchups by more then 150 points.
Maybe it would be better to use the mean siutability minus the standard deviation minus n*40, where n is the the difference between the maximum amount of possible matches (which is choaches/2 rounded down) and the number of scheduled matches. That way the scheduler would still try to match the maximum amount of matches but not at all cost. 


Christer
Joined: Aug 02, 2003

Rawlf wrote:  Just one question: isn't the notpreferred team modifier redundant now with the new activation method? 
It's actually not part of the formula anymore. Just forgot to remove it from the text here 


Christer
Joined: Aug 02, 2003

CircularLogic wrote:  What strike me, is that the scheduler will go lenghts to ensure the maximum number of games, even at the expense of all others. 
This is something that I've been aware of since the start. I have yet to see this actually happen though, but the possibility certainly exists regardless of how small the probability of it is.
The trick with the scheduler is that it needs to function well for any number of participants. The current max(suitability) method works better as the number of coaches increase. In your example, with 16 coaches, it'd be 75 lower per coach on average. With 32, it'd be 37 lower.
With an avg(S)stddev(S)k(N) function, I don't quite see how more coaches would affect the overall schedule. Also, the standard deviation tends to fluctuate a lot with a low number of inputs (ie, low number of matches), which might make it less useful here.
One way to avoid the volatility of the standard deviation with few data points is to simply do something like:
max(avg(S) + k*N), where S is suitability and N is the number of scheduled matches
The idea being that you simply try to maximise the average suitability, and add some value (k) to the total for each scheduled match. This would allow easy configuration of how much a match would be worth in terms of reduction in suitability for the other coaches. With k=20, the outlier would only be sscheduled if it didn't result in a reduction worse than 20 of the average suitability of the set.
Either way, it's not a terrible idea to have a system like this instead. 


Christer
Joined: Aug 02, 2003

.. and as a happy coincidence, this just happened:
Code:  Generating schedule #1
 Balle2000 vs peikko (Norse 120/120 vs 129/121 Chaos) @965
 haenschel vs Woodstock (Dwarf 163/161 vs 156/151 Dark Elf) @936
 Fathernurgle vs luigi (Ogre 172/146 vs 167/140 Nurgle's Rotters) @974
New best score: 2875
(...)
Generating schedule #3
 Woodstock vs Fathernurgle (Lizardmen 131/128 vs 172/146 Ogre) @887
 haenschel vs Balle2000 (Orc 165/149 vs 137/144 Amazon) @886
 peikko vs Lochlainn (Chaos 111/94 vs 130/99 Ogre) @963
 MenomaN vs luigi (Orc 204/193 vs 222/194 Khemri) @904
New best score: 3640
Generating schedule #4
 Balle2000 vs Woodstock (Norse 120/120 vs 131/128 Lizardmen) @963
 haenschel vs luigi (Khemri 155/139 vs 160/147 Lizardmen) @973
 peikko vs Lochlainn (Chaos 111/94 vs 130/99 Ogre) @963
 Fathernurgle vs MenomaN (Orc 203/194 vs 204/193 Orc) @959
New best score: 3858

The first attempt was with three matches scheduled with an average suitability of 958. A four match schedule was then found with an average suitability of 910. A reduction of suitability average by 48 points. Then another four match schedule was found with an average of 965, an improvement by 7 points. None of the three match schedules generated in any pass had a higher average than the first (in fact, most of them were the same schedule).
The worst case scenario is most likely very very uncommon though due to the minimum number of coaches and the fact that most people have multiple teams. Still, it may be worth considering the average method instead of using the total sum to avoid the extremes. 


Rawlf
Joined: Jul 15, 2007

Posted:
Jul 29, 2009  11:46 

Maybe you could use S² instead of S to strengthen the preference for high suitability scores. Granted, it wouldn't have made a difference in the given example. But it might do so when a S=600 match is in question? 


Unstoffe
Joined: Aug 22, 2004

Posted:
Jul 29, 2009  12:26 

Excellent work here  looking forward to getting some [B] games in at the weekend.
My thoughts on the points raised so far :
1) I like the way the scheduler tries to maximise the number of games, I would certainly rather get a slightly uneven match than for me or another coach to get no game at all.
2) I'm not sure about the 'picking one bad matchup if it means the others are good' thing though  seems to me a more even spread, even if the total score is slightly reduced, would be better. Suggestion : sum (1000S)² for each schedule found, and pick the one with the smallest result. 
_________________ British or thereabouts? Check out the White Isle League 

CircularLogic
Joined: Aug 22, 2003

Posted:
Jul 29, 2009  13:49 

Christer wrote: 
max(avg(S) + k*N), where S is suitability and N is the number of scheduled matches
...
With k=20, the outlier would only be sscheduled if it didn't result in a reduction worse than 20 of the average suitability of the set. 
That sounds like a very good idea. Personally I would add a modifier based on the deviation, too but that depends on the scheduling philosophy.
It comes down to finding the balance on two issues:
Major: Quality of matchups vs quantity of matchups (I`m in the quality camp here)
Minor: Average quality vs smalles deviation of quality (I`m in the smallest deviation camp)
So I`d like to suggest expanding the formula to:
max(avg(S) + k*N  RMSD/j)
k determines the quality vs quantity issue with a smaller k excluding more and more matches. 20 sounds like a reasonable starting point.
Higher j values go towards higher average siutability while lower j values to towards lower deviation. 


CircularLogic
Joined: Aug 22, 2003

Posted:
Jul 29, 2009  13:50 

btw: Can we move the box out of the testing phase? The system works pretty stable as far as I can see. 



 