Rules
A fantasy Proleague team consists of six players and one Proleague team. Each player and team you can acquire has an initial cost at the beginning of the round. You begin the season with 30 points to allocate to those six players and one team however you like, with one restriction: you must have one player of each race. Each week, for the four weeks in the round, players and teams accumulate points based on their performance and their costs adjust accordingly. At the end of each week, you are permitted to make two trades, which means taking a player from your team and swapping it for a different player from the pool. A trade is valid so long as the current cost of the player you are trading is at least the current cost of the player you are acquiring and the race requirement is still satisfied. One of the trades may be used on the team as well, with the same cost restriction. You lose one point for every trade you make. The goal is, naturally, to maximize the number of points scored by your team over the course of the round.
Model
Modeling the data is simple; each team has a cost and a point gain for each week (eight total values). The costs represent the cost of the team at the beginning of the week, and the point gains correspond to how many points the team gained in the week that followed. Players are represented in the same way except they additionally have a race.
I'll note that this problem is essentially boils down to search optimization; even without trading it is a knapsack problem, and trading only complicates things further. Luckily, there are only 89 players, eight teams, and four weeks, so a handful of optimizations can be applied to make the search space manageable. The remainder of this post breaks down into two sections: optimizing the initial players/team and optimizing the trades. For most of this discussion, I'm going to ignore the race requirement as it makes the problem much more difficult; fortunately, we still end up with a provably optimal solution (although not in the most elegant way).
Initial Team
Reducing the set of possible initial teams greatly limits the search space, so any pruning we can do before even considering trades is extremely helpful. The key here is identifying which players are strictly superior to which others. We'll define player A to be strictly superior to player B if the following conditions hold (defined similarly for teams):
- player A's initial cost is at most player B's initial cost;
- player A's cumulative points are at least player B's cumulative points at the end of each week;
- player A's cost is at least player B's cost at the end of each week; and
- there is some week for which player A's cumulative points or cost is strictly greater than player B's cumulative points or cost, respectively.
If all of those conditions hold, it's pretty easy to see that you should never choose player B over player A in your initial team. Whatever you do with player B in the future can be done with player A, and player A has some strict advantage over player B that you may be able to leverage (note that this is not true with the race requirement, because player B may have a race that is necessary for your team). So when choosing initial teams, we enforce that we never choose a player unless all players who are strictly superior to the player in question are on the team already, e.g. if there are six or more other players strictly superior to him, he will never be chosen on the initial team. This relatively simple optimization limits the initial space of a few billion teams to on the order of 100,000.
Trading
To reduce the space of trading, we need a very similar concept to strict superiority. Player A is superior from week w to player B if, from week w onward, the following conditions hold:
- player A's cumulative points from week w are at least player B's cumulative points from week w at the end of each week; and
- player A's cost is at least player B's cost at the end of each week.
Then, when deciding whether to trade player A for player B at the beginning of week w, we only consider it if player A's cost that week is at least player B's (required), player B is not already on the team (required), and player A is not superior from week w to player B after subtracting one from B's points (to account for the trade cost). So for each week we can build the list of potential trades for each player after applying this filter.
We can further reduce the search space by the following observation. Suppose we are considering trading player A at the beginning of week w. If players B and C both satisfy the above criteria but player B is superior from week w to player C, there is no reason to explore the space resulting from trading player A for player C since trading for player B is always a better choice. For example, this means that when making the final trade, you only need to consider the player that scores the highest in that last week among all possible players you can trade for, which is a pretty intuitive result.
Result
After applying the optimizations described, I was able to exhaustively search for all potential optimal teams in less than an hour. The best team (for those who actually played) can be found in this forum post. Note that the team there does indeed satisfy the race requirement, which is the last point to discuss. I implemented all of the optimizations ignoring the race requirement because it's much more difficult to determine when a player should always be chosen over another when the race factors in. It turns out, however, that the best team ignoring the race requirement altogether scores the same number of points as the best team I found which satisfies the race requirement. That proves that the team is indeed optimal, although not in the most satisfying way. I've continued to think about a good way of modeling the race requirement without eliminating most of the benefit from the optimizations but have come up empty so far. Regardless, I found interesting theoretical value in the process as well as a practical result; we'll see how it deals with the next round of data once it's in.
No comments:
Post a Comment