This discussion is archived
5 Replies Latest reply: Oct 4, 2010 9:53 AM by 801660 RSS

Algorithm question to maximize hockey pool

801660 Newbie
Currently Being Moderated
Hi! This is a little fun project that I have started to try and maximize my chances of winning our office hockey pool. I'm trying to find the best way to select 20 players that will give me the most points within a maximum salary cap.

For example, imagine that the raw data has
The Player Name
Position (Forward, Defensemen, Goalie)
Predicted amount of points for this season
Salary.

Now I want the 20 players that will give me the most point within X salary cap. Later on, as a phase 2, I would like to do the same thing however in this case, I only want 12 forwards, 6 defensemen and 2 goalie.

Now the obvious way is to simply go every possible combination, however while this will work it is not a valid option as with 500 players, this would have too many possible combination. I could add some smart filters to reduce the 500 players to the top 50 forwards, top 30 defensemen and top 15 goalies but still, this would be a very slow process.

I'm wondering if there are other algorithms out there to implement this. This is just for fun and not an important business request. But if you have some thoughts on how to proceed, please let me know.

Thanks for your help!
  • 1. Re: Algorithm question to maximize hockey pool
    800560 Newbie
    Currently Being Moderated
    How about something like a Genetic Algorithm?
  • 2. Re: Algorithm question to maximize hockey pool
    801660 Newbie
    Currently Being Moderated
    Interesting, I will take a look. Any particular suggestions? I'm also looking into combinaition algorithms.

    I can calculate the point per dollar value and once I have ranked the players using this new value, I can try to use this to identify the ones that will give me the most points for a certain salary cap, however I'm still unsure how to find the best combinaition of players.
  • 3. Re: Algorithm question to maximize hockey pool
    800560 Newbie
    Currently Being Moderated
    798657 wrote:
    Interesting, I will take a look. Any particular suggestions? I'm also looking into combinaition algorithms.

    I can calculate the point per dollar value and once I have ranked the players using this new value, I can try to use this to identify the ones that will give me the most points for a certain salary cap, however I'm still unsure how to find the best combinaition of players.
    I'm no Genetic Algorithm expert but from what I've read it does not guarantee finding the best solution. It will find pretty good solutions, possibly the best, in a relatively short period of time.

    For phase 1 maybe something like this:

    Each team of 20 players has a way to calculate its max points for a given salary cap.

    1. Create a bunch of random teams, for example 20 teams of 20 randomly selected players.

    2. Sort the list of teams.

    3. Take the top 4 teams and create child teams.
    3a. Take the first 8-12 players (randomly choose between 8 and 12) from team 1 and match with the last 8-12 players from team 2, then team 3, then team 4, choosing enough of the last 8-12 to make a 20 player team.
    3b. Repeat 3a for team 2 through team 4.
    3c. Take the first 8-12 players from team 1 and add 8-12 randomly selected players. Do the same for the second 8-12 players from team 1.
    3d. Repeat 3c for team 2 through team 4.


    4. Repeat 2-4 many times, like a few hundred or until the same team ends up the best for many consecutiive interations.

    For phase 2 you would have to make the reproduction algorithm more complex - make sure to take the right quantity of the type of player. You might also modify 3a and 3c. After you split the team it might work better to sort the players so the better players will appear first in the list. Or maybe just shuffle the list of 8-12 players. Otherwise, a lesser player might remain in the "gene pool" just because he happens to be first in the list of players.
  • 4. Re: Algorithm question to maximize hockey pool
    DrClap Expert
    Currently Being Moderated
    You have an instance of the Knapsack Problem there. The Wikipedia article could be a starting point for your research.
  • 5. Re: Algorithm question to maximize hockey pool
    801660 Newbie
    Currently Being Moderated
    thanks for all the replies. I haven't tried the genetic algorithm yet but this was my first try at the knapsack algorith with some help from other sources. It seems to work with just the Salary as a parameter. I'm struggling at figuring out how to add the 20 player team parameter. Its in .Net but should be easy to convert to Java.

    I was thinking of doing a seperate loop to figure out the best teams with 20 players reguardless of salary and then you compare the two list until you find one that is highest on the two list. Not sure.

    namespace HockeyPoolCalculator
    {
    public class ZeroOneKnapsack
    {

    protected List<Item> itemList = new List<Item>();
    protected int maxSalary = 0;
    protected int teamSize = 0;
    protected int teamSalary = 0;
    protected int points = 0;
    protected bool calculated = false;

    public ZeroOneKnapsack() { }

    public ZeroOneKnapsack(int _maxSalary)
    {
    setMaxSalary(_maxSalary);
    }

    public ZeroOneKnapsack(List<Item> _itemList)
    {
    setItemList(_itemList);
    }

    public ZeroOneKnapsack(List<Item> itemList, int maxSalary)
    {
    setItemList(_itemList);
    setMaxSalary(_maxSalary);
    }

    // calculte the solution of 0-1 knapsack problem with dynamic method:
    public virtual List<Item> calcSolution()
    {
    int n = itemList.Count;

    setInitialStateForCalculation();
    if (n > 0 && maxSalary > 0)
    {
    List<List<int>> playerList = new List<List<int>>();
    List<int> salaryList = new List<int>();

    //initialise list
    playerList.Add(salaryList);
    for (int j = 0; j <= maxSalary; j++)
    salaryList.Add(0);
    // Loop through players
    for (int i = 1; i <= n; i++)
    {
    List<int> prev = salaryList;
    playerList.Add(salaryList = new List<int>());
    for (int j = 0; j <= maxSalary; j++)
    {
    if (j > 0)
    {
    int wH = itemList.ElementAt(i - 1).getSalary();
    // Is the players salary more than the current calculated salary? If yes, then keep current max points, else get the highest amount between previous max points at that salary and new max points.
    salaryList.Add((wH > j)?prev.ElementAt(j): Math.Max(prev.ElementAt(j),itemList.ElementAt(i - 1).getPoints() + prev.ElementAt(j - wH)));
    }
    else
    {
    salaryList.Add(0);
    }
    } // for (j...)
    } // for (i...)
    points = salaryList.ElementAt(maxSalary);

    for (int i = n, j = maxSalary; i > 0 && j >= 0; i--)
    {
    int tempI = playerList.ElementAt(i).ElementAt(j);
    int tempI_1 = playerList.ElementAt(i - 1).ElementAt(j);
    if ((i == 0 && tempI > 0)||(i > 0 && tempI != tempI_1))
    {
    Item iH = itemList.ElementAt(i - 1);
    int wH = iH.getSalary();
    iH.setInKnapsack(1);
    j -= wH;
    teamSalary += wH;
    }
    } // for()



    calculated = true;
    } // if()
    return itemList;
    }

    // add an item to the item list
    public void add(String name, int Salary, int value)
    {
    if (name.Equals(""))
    name = "" + (itemList.Count() + 1);
    itemList.Add(new Item(name, Salary, value));
    setInitialStateForCalculation();
    }

    // add an item to the item list
    public void add(int Salary, int value)
    {
    add("", Salary, value); // the name will be "itemList.size() + 1"!
    }

    // remove an item from the item list
    public void remove(String name)
    {

    for (int pointer = 0; pointer <= itemList.Count-1; pointer++)

    {
    itemList[pointer].getName().Equals("");

    if (itemList.ElementAt(pointer).getName().Equals(itemList.ElementAt(pointer).getName()))
    {
    itemList.Remove(itemList.ElementAt(pointer));
    }
    }
    setInitialStateForCalculation();
    }

    // remove all items from the item list
    public void removeAllItems()
    {
    itemList.Clear();
    setInitialStateForCalculation();
    }

    public int getPoints()
    {
    if (!calculated)
    calcSolution();
    return points;
    }

    public int getSolutionSalary() { return teamSalary; }
    public bool isCalculated() { return calculated; }
    public int getMaxSalary() { return maxSalary; }

    public void setTeamSize(int _teamSize)
    {
    teamSize = _teamSize;
    }

    public int getTeamSize()
    {
    return teamSize;
    }

    public void setMaxSalary(int _maxSalary)
    {
    maxSalary = Math.Max(_maxSalary, 0);
    }

    public void setItemList(List<Item> _itemList) {
    if (_itemList != null) {
    itemList = _itemList;
    foreach (Item item in _itemList) {
    item.checkMembers();
    }
    }
    }

    // set the member with name "inKnapsack" by all items:
    private void setInKnapsackByAll(int inKnapsack) {
    foreach (Item item in itemList)
    if (inKnapsack > 0)
    item.setInKnapsack(1);
    else
    item.setInKnapsack(0);
    }

    // set the data members of class in the state of starting the calculation:
    protected void setInitialStateForCalculation()
    {
    setInKnapsackByAll(0);
    calculated = false;
    points = 0;
    teamSalary = 0;
    teamSize = 0;
    }

    }
    }

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points