|
![[image loading]](http://www.teamliquid.net/staff/HawaiianPig/sc2spl/SKPLbanner_bridge.jpg)
monk. wrote:
If anyone would like to help with a program that will let us calculate the hypothetical best team including trades, feel free to contact us!
Hopefully, this thread will serve as a hub, for those interested in solving this problem, to find resources, ask questions, and share information.
I'll be updating this thread as new information comes in.
Goal
Given rules and data for Fantasy Proleague '12-13, find the starting line-up and weekly trades that result in the highest point value at the end of the Proleague season (or any arbitrary week).
Resources
General Information and Rules:
Main Thread for Fantasy Proleague '12-13
Data:
Players: Race (P/T/Z), Team, Cost ($)
Teams: Cost ($)
Player Points
Team Points
https://docs.google.com/spreadsheet/ccc?key=0AquXzBNtz3J0dEVYN2dBR3lQUUtobFF1b0FFTHYyM1E
Thanks, to monk. and Spazer, for contributing.
Required Resources (still looking for these)
Have data or know the answer to any of these questions? Feel free to post in the thread or PM me.
I tried to cover everything needed to solve the problem between Resources and Required Resources. If I've overlooked anything, please let me know.
Rules:
How is trade value calculated at the start, and how are changes in trade value calculated week to week?
Given a team with 4 (P), 1 (T), 1 (Z), is it possible to use the 2 weekly main-team trades to make the following trade without breaking the rule for having at least one of each race on a team?
1 (T) -> 1 (Z)
1 (Z) -> 1 (T)
Data:
Player data: Starting Trade Value
Team data: Starting Trade Value
Game data: Player 1, Player 2, Week #, Set #, Winning Player
|
On December 31 2012 16:02 longdivision wrote:
Rules:
How is trade value calculated at the start, and how are changes in trade value calculated week to week?
I'm pretty sure the trade value at the start of the season was set arbitrarily due to this being the first SC2 proleague, so trade values were set based on opinions/other SC2 results. You'd probably have to ask for the original values.
On December 31 2012 16:02 longdivision wrote:
Given a team with 4 (P), 1 (T), 1 (Z), is it possible to use the 2 weekly main-team trades to make the following trade without breaking the rule for having at least one of each race on a team? (I didn't create a team for the current league, so I can't check.)
1 (T) -> 1 (Z)
1 (Z) -> 1 (T)
No, I don't think you can trade someone at all when they are the last player of that race on your team, so (in the given scenario) you'd have to bounce a toss first for a t/z to trade out the other.
|
United States8476 Posts
http://www.teamliquid.net/staff/monk/fantasy_proleague/fpl_lp_season1_data.xlsx
This is the file I've been using thus-far to calculate optimal teams without trades. It uses linear optimization, but this method isn't viable/efficient to calculate teams with trades and including trades goes beyond the scope of my algorithm/programming knowledge. However, this will be useful to you to extract players, initial costs, and races.
Edit: Updated file to include a page on teams. DL this new file please.
|
On December 31 2012 16:08 Cornix wrote:Show nested quote +On December 31 2012 16:02 longdivision wrote:
Rules:
How is trade value calculated at the start, and how are changes in trade value calculated week to week?
I'm pretty sure the trade value at the start of the season was set arbitrarily due to this being the first SC2 proleague, so trade values were set based on opinions/other SC2 results. You'd probably have to ask for the original values. Show nested quote +On December 31 2012 16:02 longdivision wrote:
Given a team with 4 (P), 1 (T), 1 (Z), is it possible to use the 2 weekly main-team trades to make the following trade without breaking the rule for having at least one of each race on a team? (I didn't create a team for the current league, so I can't check.)
1 (T) -> 1 (Z)
1 (Z) -> 1 (T)
No, I don't think you can trade someone at all when they are the last player of that race on your team, so (in the given scenario) you'd have to bounce a toss first for a t/z to trade out the other.
So Trade Value wasn't set in relation to Point Value? That's a bummer. Hopefully the file with initial values still exists on someone's harddrive.
Is it only possible to trade 1 player at a time in the trade UI? If both players were exchanged at the same time, it seems like the trade should be allowed.
|
On December 31 2012 16:40 longdivision wrote:
Is it only possible to trade 1 player at a time in the trade UI? If both players were exchanged at the same time, it seems like the trade should be allowed.
I think as long as you do both trades during the same "trading session" then it would work.
|
On December 31 2012 16:39 monk. wrote:http://www.teamliquid.net/staff/monk/fantasy_proleague/fpl_lp_season1.xlsxThis is the file I've been using thus-far to calculate optimal teams without trades. It uses linear optimization, but this method isn't viable/efficient to calculate teams without trades and including trades goes beyond the scope of my algorithm/programming knowledge. However, this will be useful to you to extract players, initial costs, and races.
Thanks, I'll repost the data in csv format when I get a chance.
I've briefly thought about how to approach this problem, and I think it's a bit more complicated than it seems at first glance. Given the number of players, trades, and weeks of competition, I'm not sure brute force is a viable option. If brute force is not viable, then I am probably in over my head as well. I welcome the challenge, though. My current job provides very rare chances to improve my programming skills.
|
On December 31 2012 16:45 Gfire wrote:Show nested quote +On December 31 2012 16:40 longdivision wrote:
Is it only possible to trade 1 player at a time in the trade UI? If both players were exchanged at the same time, it seems like the trade should be allowed. I think as long as you do both trades during the same "trading session" then it would work.
Can anyone confirm this definitively or experimentally?
|
On December 31 2012 16:59 longdivision wrote:Show nested quote +On December 31 2012 16:39 monk. wrote:http://www.teamliquid.net/staff/monk/fantasy_proleague/fpl_lp_season1.xlsxThis is the file I've been using thus-far to calculate optimal teams without trades. It uses linear optimization, but this method isn't viable/efficient to calculate teams without trades and including trades goes beyond the scope of my algorithm/programming knowledge. However, this will be useful to you to extract players, initial costs, and races. Thanks, I'll repost the data in csv format when I get a chance. I've briefly thought about how to approach this problem, and I think it's a bit more complicated that it seems at first glance. Given the number of players, trades, and weeks of competition, I'm not sure brute force is a viable option. If brute force is not viable, then I am probably in over my head as well. I welcome the challenge, though. My current job provides very rare chances to improve my programming skills.
Yeah, I was just taking a look at the numbers and I don't think brute force would really work.
You'd at least need a way to quickly identify a team which has no potential of being good so you can skip going through all the following trade possibilities.
Knowing the match results... Would it be reasonable to say that it's couldn't be a good idea to trade for someone who doesn't result in a better score after that week, or is there a situation where it's good to trade for someone even if it doesn't pay off until the following week?
|
On December 31 2012 17:07 Gfire wrote:Show nested quote +On December 31 2012 16:59 longdivision wrote:On December 31 2012 16:39 monk. wrote:http://www.teamliquid.net/staff/monk/fantasy_proleague/fpl_lp_season1.xlsxThis is the file I've been using thus-far to calculate optimal teams without trades. It uses linear optimization, but this method isn't viable/efficient to calculate teams without trades and including trades goes beyond the scope of my algorithm/programming knowledge. However, this will be useful to you to extract players, initial costs, and races. Thanks, I'll repost the data in csv format when I get a chance. I've briefly thought about how to approach this problem, and I think it's a bit more complicated that it seems at first glance. Given the number of players, trades, and weeks of competition, I'm not sure brute force is a viable option. If brute force is not viable, then I am probably in over my head as well. I welcome the challenge, though. My current job provides very rare chances to improve my programming skills. Yeah, I was just taking a look at the numbers and I don't think brute force would really work. You'd at least need a way to quickly identify a team which has no potential of being good so you can skip going through all the following trade possibilities. Knowing the match results... Would it be reasonable to say that it's couldn't be a good idea to trade for someone who doesn't result in a better score after that week, or is there a situation where it's good to trade for someone even if it doesn't pay off until the following week?
Yes, the tricky part seems to be that the starting point/path to an optimal team after week 2 may be different from the starting point/path to the optimal team after week 3 or 4.
Regarding narrowing down choices, I'm a bit too tired to contribute anything useful. I'll be back tomorrow.
|
The optimal anti-team you can probably compute pretty easily with A* and any sort of decent heuristic. My current idea for heuristic (untested and unproven) is to use dynamic programming to get decent lower limit each player and week.
The optimal main-team seems to be much harder problem. It might even be NP-hard since it's essentially longest path problem ( http://en.wikipedia.org/wiki/Longest_path_problem ). Unless someone is able to come up with something really smart we won't be able to prove that we have found the optimal team. It's likely you can get pretty decent results with some probabilistic optimization techniques (maybe something like MAX-MIN Ant System?) or linear programming with heavy restrictions but I'm not very experienced with these methods.
|
Unless it counts anti-team I didn't have a  until I traded for one... If it does count anti-team, I traded my anti-team terran at the same time.
|
Canada8033 Posts
On December 31 2012 17:07 Gfire wrote:Show nested quote +On December 31 2012 16:59 longdivision wrote:On December 31 2012 16:39 monk. wrote:http://www.teamliquid.net/staff/monk/fantasy_proleague/fpl_lp_season1.xlsxThis is the file I've been using thus-far to calculate optimal teams without trades. It uses linear optimization, but this method isn't viable/efficient to calculate teams without trades and including trades goes beyond the scope of my algorithm/programming knowledge. However, this will be useful to you to extract players, initial costs, and races. Thanks, I'll repost the data in csv format when I get a chance. I've briefly thought about how to approach this problem, and I think it's a bit more complicated that it seems at first glance. Given the number of players, trades, and weeks of competition, I'm not sure brute force is a viable option. If brute force is not viable, then I am probably in over my head as well. I welcome the challenge, though. My current job provides very rare chances to improve my programming skills. Yeah, I was just taking a look at the numbers and I don't think brute force would really work. You'd at least need a way to quickly identify a team which has no potential of being good so you can skip going through all the following trade possibilities.
I think brute force is still a viable solution. So far, all of the best teams without trading have used players that are within the top 20 for point gain. In all, I'd say it's pretty safe to ignore the bottom 40-50 players in terms of point gain. So if we take the top 30-40 players in terms of point gain for each week and intersect these sets, we can significantly reduce the number of possible teams.
Knowing the match results... Would it be reasonable to say that it's couldn't be a good idea to trade for someone who doesn't result in a better score after that week, or is there a situation where it's good to trade for someone even if it doesn't pay off until the following week?
If a trade results in net positive gain at any point in the future, that branch should be considered. However, all trades that result in a possible negative or 0 point gain can safely be ignored.
For instance, if we are considering trading player A for player B, and the point differential is -1 in the first new week and +4 in the second, we should consider that branch. We can also safely ignore all possible teams that result from trading player B during the first new week, because we would otherwise end up with a net loss in points.
I've already done a bunch of coding, btw. So far, my program can pull all the data from the FPL page (to get player, race, and cost data). I then parse Liquipedia to get win data. Using all this, I can calculate points gained per player per week. Once the trade value algorithm is figured out, the plan is to figure out and store the trade value for each player per week, and use that to implement some sort of trading function.
Here's an excel spreadsheet with weekly point gains for each player/team.
Outdated.
Edit:
On January 01 2013 02:30 y0su wrote:Unless it counts anti-team I didn't have a until I traded for one... If it does count anti-team, I traded my anti-team terran at the same time.
Anti-teams have no race restrictions.
|
On January 01 2013 02:10 Laquendi wrote:
The optimal anti-team you can probably compute pretty easily with A* and any sort of decent heuristic. My current idea for heuristic (untested and unproven) is to use dynamic programming to get decent lower limit each player and week.
Could you describe this approach for those (me included) who are not familiar with the more technical terms?
The optimal main-team seems to be much harder problem. It might even be NP-hard since it's essentially longest path problem ( http://en.wikipedia.org/wiki/Longest_path_problem ). Unless someone is able to come up with something really smart we won't be able to prove that we have found the optimal team. It's likely you can get pretty decent results with some probabilistic optimization techniques (maybe something like MAX-MIN Ant System?) or linear programming with heavy restrictions but I'm not very experienced with these methods.
Yikes. NP means the time to compute a solution grows exponentially with the size of the problem, right? Or at least it's not reducible to polynomial time.
Does anyone know when the league ends? Is it after 10 weeks? I wonder if it is realistic to solve this problem by going through all options.
On January 01 2013 02:30 y0su wrote:Unless it counts anti-team I didn't have a until I traded for one... If it does count anti-team, I traded my anti-team terran at the same time.
Fascinating... At this point, maybe it is easier to follow the rules as they were presented, instead of trying to model how the rules actually work.
|
On January 01 2013 08:32 Spazer wrote:
I think brute force is still a viable solution. So far, all of the best teams without trading have used players that are within the top 20 for point gain. In all, I'd say it's pretty safe to ignore the bottom 40-50 players in terms of point gain. So if we take the top 30-40 players in terms of point gain for each week and intersect these sets, we can significantly reduce the number of possible teams.
If a trade results in net positive gain at any point in the future, that branch should be considered. However, all trades that result in a possible negative or 0 point gain can safely be ignored.
These seem like good strategies.
For instance, if we are considering trading player A for player B, and the point differential is -1 in the first new week and +4 in the second, we should consider that branch. We can also safely ignore all possible teams that result from trading player B during the first new week, because we would otherwise end up with a net loss in points.
Could a situation arise where 4 players need to be traded over 2 weeks and trading player A for player B during the first week is the optimal solution?
I've already done a bunch of coding, btw. So far, my program can pull all the data from the FPL page (to get player, race, and cost data). I then parse Liquipedia to get win data. Using all this, I can calculate points gained per player per week. Once the trade value algorithm is figured out, the plan is to figure out and store the trade value for each player per week, and use that to implement some sort of trading function. Here's an excel spreadsheet with weekly point gains for each player/team. https://dl.dropbox.com/u/4718/Weekly Point Gain Data.xlsx
Would you be willing to share your code? I'm a fairly inexperienced programmer and want to learn more. I'm interested in how you get data from the FPL page, parse Liquipedia, and how you structure your code.
|
Canada8033 Posts
On January 01 2013 14:15 longdivision wrote:Show nested quote +For instance, if we are considering trading player A for player B, and the point differential is -1 in the first new week and +4 in the second, we should consider that branch. We can also safely ignore all possible teams that result from trading player B during the first new week, because we would otherwise end up with a net loss in points. Could a situation arise where 4 players need to be traded over 2 weeks and trading player A for player B during the first week is the optimal solution?
With my described method, all I check for in the current week is whether or not a trade returns a net positive gain at any point in the future. If so, then ALL future branches with that trade are considered. To clarify my previous example:
You have option to trade player A for player B.
Player A Player B Net gain from trade
Week 1: +4 +3 -1
Week 2: +2 +6 +4
So if I make the trade, I will have a net gain of +3 from the transaction in 2 weeks, so this branch will be considered. What I'm saying is that it's pointless to consider any branches wherein player B is traded away at the end of week 1, as this will leave us a net loss of -1, defeating the entire purpose of the trade.
The situation you mention (4 players being traded over 2 weeks) is already covered with this.
Show nested quote +I've already done a bunch of coding, btw. So far, my program can pull all the data from the FPL page (to get player, race, and cost data). I then parse Liquipedia to get win data. Using all this, I can calculate points gained per player per week. Once the trade value algorithm is figured out, the plan is to figure out and store the trade value for each player per week, and use that to implement some sort of trading function. Here's an excel spreadsheet with weekly point gains for each player/team. https://dl.dropbox.com/u/4718/Weekly Point Gain Data.xlsx Would you be willing to share your code? I'm a fairly inexperienced programmer and want to learn more. I'm interested in how you get data from the FPL page, parse Liquipedia, and how you structure your code.
https://github.com/spazer/FPL_Calculator
Written in C# with VS2010
|
United States33584 Posts
yay, people who do math are on the problem!
|
Canada8033 Posts
Things I've figured out:
- Trade value for each week is related to total points (all players with the same total points have the same trade value at the end of the round). Something like (Points / (Games Played / Games Per Week) is a factor. For the current round, final trade value can be found by dividing points by 4.5. The same can be done for other rounds, but the modifier is sometimes 4, sometimes 5.
- The initial cost of a team/player is factored into trade value. The amount it adds decreases every week, hitting zero at the end of the round.
- Adjusted trade value is just (trade value * # of matches the team has left to play)
|
I'll take another approach to this. Making a program that stores all good teams from each week, and then i'll try to implement a way to transform high earning teams from week 1 to equally teams next week, using all the rules to ensure i dont get lost along the way. It might be an ugly implementation, but i think the average computer should be able to solve such a problem given a fair time span. I'll keep you guys posted
|
Couldn't R1CH pull the actual trade value formulas from the FPL code? Understanding how the trade values increase and decrease and being able to recreate it is key to any intended program to solve the presented problem. Otherwise you will not be able to decide who you could eligibly trade for each week.
|
Canada8033 Posts
On January 04 2013 04:57 Proseat wrote:
Couldn't R1CH pull the actual trade value formulas from the FPL code? Understanding how the trade values increase and decrease and being able to recreate it is key to any intended program to solve the presented problem. Otherwise you will not be able to decide who you could eligibly trade for each week.
That's what we're waiting on at the moment. But that doesn't mean we can't try to figure it out ourselves in the meantime.
|
|
|
|
|
|
EPT
