Scheduling-Tournament-Pool-Optimization
Notes on Optimization 2011-10-13
The pool layout matrices used have duplicates only where they are unavoidable... These means that pools of 3 and 4 will have duplicated matches. There is no way around it. So at issue is whether we allow collisions or not, if we do, the more simple, fixed layout will force that.
These stats are all for the Fall 2011 season about halfway through. The season seems pretty small.
Full notes here on going through the various stats…
Summary is that I did add a Maximize non-collisions, but it ends up being the same as minimizing collisions because of the fact that a match is either a collision or a non-collision, so its just getting at the same info from a different direction…
I improved the pool layout choices for 5 & 6 team pools (all 29 non duplicated match possibilities are included). This helped the numbers bit.
the biggest issue is the 4 team pool layout options. There has to be at least one duplicated game. I added in a setting "Allow Dual Duplicated" that controls whether we allow 2 duplicated matches in a 4 team pool layout. Using this and "minimize collisions" is probably the best compromise between the current thoughts on duplication v collision. Compared to the fixed layout, we avoid 133 collisions and only add 12 duplications.
Some more work should still be done. I now have the means to generate the 120,119 different pool layout options for 7 & 8 team pools, but I dont want to enter all of them… So I need to generate a subset of those to include as options. That will give us some better options for larger pools.
Stats processing and such as follows
Original Stats for Fixed
all tourn summary, mode: Fixed : 830 collisions in 1864 games, all tourn summary, mode: Fixed : 357 duplications in 1864 games,
Original stats for minimize collisions:
all tourn summary, mode: Minimize Collisions : 584 collisions in 1864 games, all tourn summary, mode: Minimize Collisions : 488 duplications in 1864 games,
The original usyvlPoolLayout.php (at the start of this analysis) has:
- 3 choices for a 3 team pool, each allowing a single duplication
- 6 choices for a 4 team pool, 3 allow duplication of one match, 3 allow duplication for 2 matches
- 2 choices for a 5 team pool
- 6 choices for a 6 team pool
- 6 choices for a 7 team pool
Add more pool layout choices
I created combinatoricPairs.php to generate additional pool layouts.
- 5 and 6 team pools have 29 possible choices
- 7 and 8 team pools have 120119 possible choices.
Add in all possible options for 5&6
all tourn summary, mode: Minimize Collisions : 607 collisions in 1864 games, all tourn summary, mode: Minimize Collisions : 461 duplications in 1864 games,
Slight net improvement... duplications went down by 27, but collisions only increased by 23.
I find this result interesting in that this change affected only the 5&6 team pools, I actually expected duplications to be unchanged and collisions to go down... This result seems to indicate that some of the 5&6 team pools were seeing duplicated matches, but they should not have... Ahhhhh, found one of the 6 team pool layouts that had the last match being a duplicate of the first... So if that one avoided a collision (pretty likely since that first layout is typically well suited to the teams distribution) then we had some duplicates, but avoided collisions in those matches.
Add Maximize Non-Collisions
This seems to give the same results as minimizing collisions - which does make some sense. The pool layout we use do not have duplications, so a match is either a collision or non-collision.
all tourn summary, mode: Maximize Non-Collisions : 607 collisions in 1864 games, all tourn summary, mode: Maximize Non-Collisions : 461 duplications in 1864 games,
Re-Organize the 4 team pool layout
Was using the first pool with the lowest number. Looking at the pool layout, I did all the primary options first and then fall back to the more duplicated match layouts. I changed the order so that the more diverse (non-duplicated) matches are at the end and changed the algorithm to be if it is less than or equal then override which one to use... Didn't really change anything.
all tourn summary, mode: Maximize Non-Collisions : 607 collisions in 1864 games, all tourn summary, mode: Maximize Non-Collisions : 461 duplications in 1864 games,
Remove double duplicated match options for 4 team pool layouts
all tourn summary, mode: Maximize Non-Collisions : 697 collisions in 1864 games, all tourn summary, mode: Maximize Non-Collisions : 369 duplications in 1864 games,
So the net change here is 90 more collisions, and 92 less duplications from the option that allows 2 duplicated matches in one round Net change from Fixed layout though is 133 fewer collisions and only 12 more duplications.