Next Best Move
- ayush singh
- May 28, 2023
- 6 min read
Updated: Dec 2, 2025
Optimise the Game of Soccer: A Linear Programming approach through Python
This project is based on a game-play of a football game on a 15x15 grid with 3+3 players wherein given particular parameters underlying the game, we figure out the best move for every player in the 2 teams using linear programming. The optimum move is decided at every iteration wherein each iteration corresponds to every player making one move out of the following - dribble, pass or shoot. So essentially we try to optimize the moves given the current player positions and ball position. We consider two major parameters for our model - first is safety of any point on the grid which takes into account enemy team and self team distances; and second is distance from the opponent goal post. For most part of the analysis, we looked at 3v3 scenarios and at later stages, we tried increasing the number players to understand it's effect on the game-play. We used Pulp - a python library for solving the linear programming part and other visualization libraries of python were also used for displaying the game-play.
Challenges faced
The major challenges on the onset of the project were related to the basic formulation of the problem and various forms of constraints to be included in the problem. Formulating the distance and safety functions for optimum game-play was also challenging as our score function is a proxy for higher number of goals secured for any team and various problems could occur during the game-play with a wrong score function like - lower incentive for reducing goalpost distance can make the game-play stretching on for longer duration and even getting stuck in the middle of the field; higher penalty in safety function for grid points near opponents can make players moving away from the goalpost even with few opponents defending the goal, leading to sub-optimal actions.
At later stages of the project, another challenge we faced was how to include uncertainty in the game given that the whole problem had been modelled and solved in a deterministic sense till that point. Opponent intercept code was modified to include uncertainty, by taking the probability of a successful intercept during a shoot/pass or dribble to be 0.3 for every opponent player lying near the trajectory of the ball.
Another problem that we faced was that players used to shoot to the goalpost from really large distances when the trajectory scores for other moves were very low. So as to solve this problem, we modified the trajectory scores of such passes and shoots to −∞ so as to avoid such a move. Another problem that occurred was that many times passes kept on happening between same 2 players while other opponent team players kept on advancing and finally surrounded them. This happened because rather than moving forward by dribbling (to a position close to opponent players), the team players had higher scores for passing to team mates. In order to mitigate this issue, we limited consecutive passes made between same players to 2 by maintaining another variable which was updated at every iteration.
Implementation in brief
We defined six functions details of which are mentioned below:
Distance
Distance is a simple function which will be utilised to calculate distance between two players.
Safety
This function is used to mark how safe a point is on the grid which is a measure of current team players’ influence versus the opponent team players’ influence. The ’reach’ of a player is what we define as influence in this context and is taken to be a decaying function radially.
This function was chosen because we wanted scores of grid points away from opponents higher and away from team players to be lower. 1 was added in the denominator to avoid the denominator becoming zero and k was kept in the formula to control how fast function decreases away from opponents/team players. The first term had later been replaced with a constant factor to decrease clustering (as awarding grid points positively for positions near team players promoted clustering of team players and led to easier interception by opponent players).
Trajectory Score
Now that we have all the essential parameters defined, we can calculate the trajectory of any given path with any pair of starting and ending point. Initially this was taken to be the minimum of scores of every point along a path, then it was later taken to be an average along the path.
Dribble
The score of any surrounding point to which a player can dribble to would be an average of the scores of passing to the others and shooting to the goalpost from the new position. Thus every possible dribble position has a score associated with it, which is returned along with information regarding how many possible positions are there for any player .
Intercepting and Uncertainty
In order to include uncertainty in this deterministic decision making, we included another parameter, the probability of a successful intercept by the opponent team. In our implementation, we consider the opponents closer than 0.5 (each grid point being a distance of 1 apart along x and y axis) to the line of pass/shoot as the opponent players who can intercept the ball. Then each player is assigned the same probability of intercepting the ball and iterating through these opponent players, whomsoever successfully intercepts the ball first gets the ball for the next iteration. For intercepts during a dribble, we consider only those opponents who can reach the previous or new position of the player with the ball, and same uncertainty of intercept has been implemented for these opponents.
Another way to introduce uncertainty which we plan on including in the future is intercept at goal. As of now we don’t have a dedicated goalkeeper. We can keep a goalkeeper restricted to the goalpost grid point and we can assign some probability of intercepting the ball within a radius r around the goalpost and once the ball is intercepted, goalkeeper will shoot to the team player with highest score function.
Opponent moves
We are optimizing for the best move for the team currently having the ball. For opponent move, we first calculate the safety for the opponent team, which is calculated similarly except that the opponent team (op) and team (te) get reversed in the function calculating safety (higher safety for grid points near the players of the team having the ball). The score is simply safety now, instead of multiplication of safety and distance functions because when the team does not possess the ball as their priority should be to get the ball, and not scoring a goal post shoot. Since the actions for the opponent team is limited to dribble only, we simply extract the maximum dribble score from the possible dribble positions for every opponent team layer using max function in python as we already have the arrays for the dribble scores for every opponent team player.
Conclusion
From our analysis and methodology we can see that it is indeed possible to simulate a football game using less than ten constraints and make it interactive as well. Various issues such as clustering, players getting to same positions, and various such issues required innovative solutions and even a simple looking project such as this required thorough understanding of the foundations of optimization and mathematical formulations. Introduction of uncertainty in intercepts help in making the game-play different even for the same initial positions of all the team players.
In our model we are able to quantify the score of any given trajectory and this is updated every time players move around on the grid. Initially dribbles were coded to not occur during passing but this was modified by getting rid of condition variables and changing the constraints a little. By introducing the idea of hashing function we will be able to get rid of corner cases which had popped up. The model that we made using linear programming and knowledge of football differs from conventional methods of solving such problems like reinforcement learning which make use of historical data. In future, we may even compare such models to our model in order to improvise our own methodology of solving, and to simply observe how simple modeling methods using LP compare against sophisticated techniques such as RL.
Such kinds of hands on project are very helpful in getting to know how to implement various modeling techniques taught in class theoretically and such practical applications make the course even more exciting.
Future scope of the Project
As we can see in the video, there is a problem of clustering, where the intercept occurs repeatedly as the distance less than 1/2 units condition is satisfied frequently when all the team players are located close to one another and the game stagnates at continuous interception by opponent team. To take care of this we propose to introduce the concept of throwing the ball in a random area in space at a range of 6 units so that game proceeds rather than getting stuck.
We also plan on including the concept of defenders wherein we can add constraint that a constant fraction of the number of team players need to stay behind half line to defend the goalposts from shoots directly into goalpost
As described in previous sections, we also plan on including the concept of goalkeeper and hashing function for solving the problem of 2 players at the same grid point.
Comments