Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithm to determine the best team and formation?

I am looking for suitable algorithms I could use in a sports team management simulator (e.g. hockey or soccer). Some features of the simulator:

  • The team can play with different formations (e.g. soccer's 4-4-2).
  • Each player in the team has a numeric rating for how good they are for each position in the formation.
  • There is a pool of squad players of varying abilities from which the team can be selected

What algorithms can be used to programmatically and efficiently determine the strongest teams and formations?

like image 777
Mark McLaren Avatar asked May 29 '12 19:05

Mark McLaren


1 Answers

If we model your problem by graph and noticing that the number of different formations is small, the problem is maximum weighted bipartite matching, which is solvable by Hungarian Algorithm, ....

To model the problem with bipartite graphs, put players in one part, and positions to the other part (e.g. in soccer), to form a pool of players and 11 positions for them, connect all players to all positions, and set the corresponding edge weights as a corresponding player rating in the position.

Now all you should do is to find a maximum (weighted) matching in this complete bipartite graph. (codes are available in wiki link).

I supposed we have a limited number of formations, for each formation we can find the corresponding matching graph, and its maximum weight matching, finally take maximum value over all possible formations (in all graphs).

like image 55
Saeed Amiri Avatar answered Oct 19 '22 12:10

Saeed Amiri