| 1 |
Well, what do you do when you want to solve an NP problem, your objective function is slow and your search space too large? You throw heuristics at it.
|
1 |
Well, what do you do when you want to solve an NP problem, your objective function is slow and your search space too large? You throw heuristics at it.
|
| 2 |
\n
|
2 |
\n
|
| 3 |
There's plenty of open source stuff available for these purposes.
|
|
|
| 4 |
\n
|
|
|
| 5 |
[url=https://en.wikipedia.org/wiki/Genetic_algorithm]Genetic algorithms[/url]:
|
3 |
[url=https://en.wikipedia.org/wiki/Genetic_algorithm]Genetic algorithms[/url]:
|
| 6 |
[spoiler]I could point you to [url=https://github.com/EmmittJ/PoESkillTree/tree/master/WPFSKillTree/TreeGenerator/Genetic]a GA implementation[/url] I contributed to a different open source project (it's technically under MIT license though), but in general genetic algorithms are pretty solid. You only need to provide a function that takes a bitstring and returns a score value.
|
4 |
[spoiler]I could point you to [url=https://github.com/EmmittJ/PoESkillTree/tree/master/WPFSKillTree/TreeGenerator/Genetic]a GA implementation[/url] I contributed to a different open source project (it's technically under MIT license though), but in general genetic algorithms are pretty solid. You only need to provide a function that takes a bitstring and returns a score value.
|
| 7 |
\n
|
5 |
\n
|
| 8 |
The open question is how to best map bitstrings to matchups (assuming we agree on one of the suggested scoring functions for team matchups, @Brackman provided these already though). This is somewhat complicated by the fact that team sizes aren't necessarily fixed.
|
6 |
The open question is how to best map bitstrings to matchups (assuming we agree on one of the suggested scoring functions for team matchups, @Brackman provided these already though). This is somewhat complicated by the fact that team sizes aren't necessarily fixed.
|
| 9 |
\n
|
7 |
\n
|
| 10 |
A naive solution would be to use bitstrings of length N*M for N players and M teams, where bit x being set means that player number x % N is placed in team floor(x / N). Obviously, this would generate lots and lots of invalid solutions (since a player can only be in one team at a time).
|
8 |
A naive solution would be to use bitstrings of length N*M for N players and M teams, where bit x being set means that player number x % N is placed in team floor(x / N). Obviously, this would generate lots and lots of invalid solutions (since a player can only be in one team at a time).
|
| 11 |
\n
|
9 |
\n
|
| 12 |
Given a way to enumerate all team combinations, it is alternatively also possible to interpret the entire bitstring as the number p of the team combination (e.g. 1100 = 12 -> 12th combination). Since team sizes are somewhat variable, the easiest mapping I can imagine here is the following:
|
10 |
Given a way to enumerate all team combinations, it is alternatively also possible to interpret the entire bitstring as the number p of the team combination (e.g. 1100 = 12 -> 12th combination). Since team sizes are somewhat variable, the easiest mapping I can imagine here is the following:
|
| 13 |
1. Convert the number p to base M (let's call it p_M).
|
11 |
1. Convert the number p to base M (let's call it p_M).
|
| 14 |
2. The [i]k[/i]th digit of p_M is the team number of player k.
|
12 |
2. The [i]k[/i]th digit of p_M is the team number of player k.
|
| 15 |
\n
|
13 |
\n
|
| 16 |
Consequently, you'd end up with M^N possible numbers and would therefore have to use bitstrings of length lg2(M) * N.
|
14 |
Consequently, you'd end up with M^N possible numbers and would therefore have to use bitstrings of length lg2(M) * N.
|
| 17 |
\n
|
15 |
\n
|
| 18 |
This would perform worst for high M (in relation to N), which is many-team FFA. It might be necessary to adopt a different mapping function (since leaving teams empty is not allowed*, which is harder to incorporate into the enumeration scheme above) for FFAs.
|
16 |
This would perform worst for high M (in relation to N), which is many-team FFA. It might be necessary to adopt a different mapping function (since leaving teams empty is not allowed*, which is harder to incorporate into the enumeration scheme above) for FFAs.
|
| 19 |
Further, this approach may be problematic because changing a single bit in the bitstring will end up producing completely different matchups when M is not a power of two, making the search space (from the perspective of the algorithm) a lot more pathological.
|
17 |
Further, this approach may be problematic because changing a single bit in the bitstring will end up producing completely different matchups when M is not a power of two, making the search space (from the perspective of the algorithm) a lot more pathological.
|
| 20 |
\n
|
18 |
\n
|
| 21 |
\n
|
19 |
\n
|
| 22 |
*I'm pretty sure that cases can be constructed where the best solution (from a mathematical standpoint) is one where teams are left empty. Is this actually to be forbidden?[/spoiler]
|
20 |
*I'm pretty sure that cases can be constructed where the best solution (from a mathematical standpoint) is one where teams are left empty. Is this actually to be forbidden?[/spoiler]
|
| 23 |
\n
|
21 |
\n
|
| 24 |
[url=https://en.wikipedia.org/wiki/Simulated_annealing]Simulated annealing[/url]:
|
22 |
[url=https://en.wikipedia.org/wiki/Simulated_annealing]Simulated annealing[/url]:
|
| 25 |
[spoiler]This is a different approach that might be more suited to the problem at hand, but it would require an implementation that is more intimately aware of the problem to be solved (whereas a GA just operates on bitstrings).
|
23 |
[spoiler]This is a different approach that might be more suited to the problem at hand, but it would require an implementation that is more intimately aware of the problem to be solved (whereas a GA just operates on bitstrings).
|
| 26 |
\n
|
24 |
\n
|
| 27 |
For simulated annealing, you randomly change (= move/swap players) the current state and then check if it got better. If it did, you keep going with it. If not, then you do a random roll that gets harder by how much worse it became and by how far into the optimization you are. Succeeding the roll means the (worse) solution is accepted, while failing it means you keep what you had before.
|
25 |
For simulated annealing, you randomly change (= move/swap players) the current state and then check if it got better. If it did, you keep going with it. If not, then you do a random roll that gets harder by how much worse it became and by how far into the optimization you are. Succeeding the roll means the (worse) solution is accepted, while failing it means you keep what you had before.
|
| 28 |
\n
|
26 |
\n
|
| 29 |
What makes this a promising approach is how moving players naturally corresponds to the "annealing" and thus prevents checking invalid/naturally horrible solutions.[/spoiler]
|
27 |
What makes this a promising approach is how moving players naturally corresponds to the "annealing" and thus prevents checking invalid/naturally horrible solutions.[/spoiler]
|
Balancer broken?