50 coaches online • Server time: 17:17
Index Search Usergroups Profile
Log in
Recent Forum Topics goto Post Free Blood Bowl Toke...goto Post White Isle League - ...goto Post Another I need a log...
SearchSearch 
Post new topic   Reply to topic
View previous topic Log in to check your private messages View next topic
Christer



Joined: Aug 02, 2003

Post   Posted: Jul 29, 2009 - 09:54
FUMBBL Staff
Reply with quote Back to top

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 match-ups. 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 non-trivial (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 0-1

6. Get the base suitability as 1-normalised 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 (1-numHandicaps * 0.03)

10. Scale suitability to 0-1000 (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

Post   Posted: Jul 29, 2009 - 09:55
FUMBBL Staff
Reply with quote Back to top

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 coach-based 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

Post   Posted: Jul 29, 2009 - 10:22 Reply with quote Back to top

Looks great.

That's alot of match-ups being considered by the scheduler
TheCetusProject



Joined: May 25, 2004

Post   Posted: Jul 29, 2009 - 10:27 Reply with quote Back to top

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

Post   Posted: Jul 29, 2009 - 10:28 Reply with quote Back to top

Well, I will just say thanks for the hard work Christer. I think I got most of it and it looks good.

_________________
[url=http://forumbilder.se/images/b9220091130111202.jpg]Image[/URL]
Christer



Joined: Aug 02, 2003

Post   Posted: Jul 29, 2009 - 10:35
FUMBBL Staff
Reply with quote Back to top

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 Men-o-maN  (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 Men-o-maN  (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

Post   Posted: Jul 29, 2009 - 10:40 Reply with quote Back to top

I was just thinking about how good the matchups were today. Smile You are certainly doing a great job with scheduler Christer, thanks a lot!

Just one question: isn't the not-preferred team modifier redundant now with the new activation method?
CircularLogic



Joined: Aug 22, 2003

Post   Posted: Jul 29, 2009 - 10:59 Reply with quote Back to top

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

Post   Posted: Jul 29, 2009 - 11:01
FUMBBL Staff
Reply with quote Back to top

Rawlf wrote:
Just one question: isn't the not-preferred 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 Smile
Christer



Joined: Aug 02, 2003

Post   Posted: Jul 29, 2009 - 11:25
FUMBBL Staff
Reply with quote Back to top

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

Post   Posted: Jul 29, 2009 - 11:38
FUMBBL Staff
Reply with quote Back to top

.. 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
- Men-o-maN 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 Men-o-maN  (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

Post   Posted: Jul 29, 2009 - 11:46 Reply with quote Back to top

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

Post   Posted: Jul 29, 2009 - 12:26 Reply with quote Back to top

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 (1000-S) 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

Post   Posted: Jul 29, 2009 - 13:49 Reply with quote Back to top

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

Post   Posted: Jul 29, 2009 - 13:50 Reply with quote Back to top

btw: Can we move the box out of the testing phase? The system works pretty stable as far as I can see.
Display posts from previous:     
 Jump to:   
All times are GMT + 1 Hour
Post new topic   Reply to topic
View previous topic Log in to check your private messages View next topic
Powered by PNphpBB2 1.2 © 2003 PNphpBB Group
Credits