0

I have a set of approximately 20,000 different football (soccer) trading cards (for those interested, this question is based on FIFA Ultimate Team). Each represents a football player and the card has an ability rating between 1 and 99. The higher the rating, the better the player's ability.

A player of this card game purchases 11 cards to form a team to use against the teams of other players. In this game, each team has a "chemistry" rating, between 1 and 100, which is dynamically calculated by the combinations of players in the team. Players are represented by their nationality, club and the league in which their clubs play, so players who play together that share leagues, nationalities or clubs have good chemistry levels, while those who do not, have bad chemistry levels. There are some other rules, but for the purpose of this question we can ignore them for now.

I want to figure out how to generate a team of 11 cards based on arbitrary rules. So for example, I want to be able to use some sort of algorithm or function to say "given the full set of players available, give me a squad with a minimum overall rating of 80 with a minimum 95 chemistry rating." Another example could be "given the full set of players available, give me the highest possible rated squad with a 100 chemistry rating, using only Italian players." The algorithm would then iterate through the entire set and return a squad of 11 based on the stated rules.

From the research I've done, I believe that this is a combinatorial optimisation problem, but I'm an average software engineer and not a mathematician so I'm unsure on how to proceed with this. Ideally, I'd like to take the answer to this and turn it into a library written in PHP or perhaps Python.

Jamie Hollern
  • 101
  • I have not mastered the details of your problem, but often such combinatorial problems are difficult (non-polynomial complexity) to solve exactly, and one then may be motivated to pursue approximate solutions. In your case the "stated rules" and "arbitrary rules" don't give Readers much indication of whether exact optimums or approximate optimums are most suitable. – hardmath Apr 19 '18 at 18:38
  • @hardmath Many thanks for your comment and apologies that my question doesn’t give enough detail. I’m unsure what’s suitable myself, as this is not my area of expertise, but any sort of nudge in the right direction is very much appreciated. Thanks again. – Jamie Hollern Apr 19 '18 at 18:46
  • 1
    You can't "iterate through the entire set" if by that you mean construct all possible teams. There are $5116579369477560619072992589136011820000$ possible $11$-man teams from $20000$ players. – saulspatz Apr 19 '18 at 18:55
  • @saulspatz Indeed! Sorry about my garbage terminology. I could manually figure this out, in code, by doing exactly what you've stated, but obviously that would be massively slow and inefficient. So I guess some sort of algorithm would be necessary to avoid that - I just don't know what I'm looking for. – Jamie Hollern Apr 19 '18 at 19:14
  • What is the procedure whereby teams are selected? I don't imagine that the same player can be on more than one team, or can he? – saulspatz Apr 20 '18 at 18:21
  • @saulspatz Teams are selected simply by the player deciding which cards they would like in their team (if they can afford the price of said card). Any given card can be in an unlimited number of teams and it isn't that unusual for two teams to face each other with identical lineups. – Jamie Hollern Apr 21 '18 at 11:54
  • 1
    It seems to me that the first thing to do is to eliminate most of the players from consideration. Why would you consider any but the highest-rated players? Then you might try grouping the remaining players into affinity groups with high "chemistry" using k-means or some other clustering algorithm. Perhaps there's more to the choosing than I understand -- I don't know the first thing about soccer. – saulspatz Apr 21 '18 at 15:01
  • That's a very good nudge in the right direction, thank you very much! There is more to choosing than what I've described; the biggest being that you have to purchase the cards using in-game currency. Some of the best cards cost millions in this currency, so much of the choice is based on what the player can afford. However, that was going to be a filter I added once I had a sort of proof of concept working for this. – Jamie Hollern Apr 21 '18 at 15:51

0 Answers0