Monthly Archives: August 2014

Explainer: how are football fixtures set?

Graham Kendall, University of Nottingham

When the English football fixtures were announced in June, many fans would have studied them from their own perspective. Are the fixtures fair to their team? Why do they have to travel the full length of the country on a Wednesday evening in the middle of February when, no doubt, it will be cold and raining?

Some people might consider fixtures to be biased. But the truth is that scheduling any sporting event is an incredibly complex job. Let’s stick with the example of English football to understand why.

The basics

English football is divided into four main divisions, with the English Premier League (EPL) being the jewel in the crown, receiving world-wide attention. Each division has to play a double round-robin tournament – that is, each team has to play every other team in the division twice, once at home and once away.

For the EPL, this means 380 games have to be played. The other divisions play 552 games each, making it a total of 2,036 games to be played and scheduled over the football season.

Pairings

Teams from one division do not play teams in other divisions, so you might think that we can simply schedule each division independently. This is not the case. The football league operates a pairing system. Paired teams cannot play at home on the same day, or even the same weekend. This is done for reasons such as:

Crowd control: The police do not want paired teams such as Manchester United and Manchester City playing at home on the same day. This is because it will mean four sets of supporters will be in the centre of Manchester, making policing difficult.

Revenue maximisation: Some clubs would prefer other clubs not to be playing at home over the same weekend as they believe that it has an effect on their revenue.

Shared resources: Some clubs may share resources such as stewards and if they are playing at the same time, there may not be enough stewards for both fixtures.

Transport: The transport police would like to minimise the places where travelling fans are likely to meet and restrict the number of opposing fans that are passing through main transport hubs at any given time.

It is not always possible to respect every pairing, but the high priority pairings, such as Manchester City and Manchester United, will be given special attention.

Taking the fans into account

Over the busy Christmas and New Year period, the overall travel distances are kept to a minimum to save the fans having to travel long distances.

The fixtures are arranged so that a team does not have too many home (or away) fixtures in a row. This is to spread the costs for the home fans and to give pitches time to recover. In an ideal world teams would have alternate home/away fixtures, but it is impossible to do this for every team, for the entire season.

Even if we only had to consider the factors above it would still be a complex task to produce a schedule that is considered fair by everybody. But these factors just scratch the surface, and many others need to be taken into account.

Clubs will have special requests for a variety of reasons. These could include that their stadium is being used for a music concert on a certain date, it is a public holiday weekend and the town would prefer not to have football supporters visiting the town at that time, or there is another major event taking place in the town which should not be held at the same time as a large sporting event.

The police will have additional conditions, such as not wanting too many teams playing in the area under their control. For example, the number of fixtures that can take place in the London and Manchester areas are restricted. The police will also look at what other events they have to police, such as demonstrations, that are taking place at the same time.

Other football competitions – for example, the FA cup, international fixtures, other European fixtures – also need to be borne in mind.

Some sensitive fixtures may have to be given special consideration due to the previous history of particular clubs, which might not just mean them playing one another but also where particular groups of supporters might meet before and after a match. You don’t, for example, want lots of supporters all travelling through London at the same time, even though the fixtures might be taking place outside of London.

It may be preferential to play some derby fixtures at certain times. Some clubs might prefer to play a high-profile local derby on a midweek evening. They are likely to get a capacity crowd, whereas if the fixture was against a team where the fans had to travel a long way, they might not be inclined to travel on a midweek evening, so the clubs might prefer these fixtures to take place at the weekend.

How are fixtures scheduled?

Before the start of the season the Football League – the overarching management body – sends out a questionnaire to all the clubs asking for any special requests, although they are not guaranteed to be respected.

Once all the data has been collected, the initial schedules are produced. There follows a period of discussion with the key stakeholders – the clubs, the Football League, the Premier League and the police.

The schedule is gradually refined until everybody agrees that they have workable solution. But even with that, some games may have to be rescheduled during the season, because of cancellation, for whatever reason.

How could it be done?

Scheduling sporting events is a popular topic among researchers.

The scheduling of games is not so different from the problem supermarkets face when they need to deliver groceries (or even Santa delivering presents). For any scheduling problem the usual procedure is to develop a mathematical model and then attempt to optimise that model using one of the many tools that are available.

If the problem you are trying to solve is small enough, you may be able to use an exact method. But, as the problems get larger, exact methods tend to take too long, perhaps even millions of years of computation.

If we cannot use exact methods, then we have to resort to other methodologies such as meta-heuristics and hyper-heuristics. These algorithms tend to be reasonably fast and, although they cannot guarantee to return the optimal solution, they tend to give good solutions to the problem at hand.

Amongst the most popular methods for sports scheduling is simulated annealing, which draws its inspiration from the way metals are cooled to ensure that they have a uniform crystal structure. Like many approaches the method is based on a natural phenomena – with perhaps the most well known being genetic algorithms, which are based on Darwin’s theory of the survival of the fittest.

When simulated annealing is used for sports scheduling it starts with an initial schedule – which is probably terrible, but it gives us something to work with. It tries to improve the schedule by making small changes. This might be swapping a home and away team, changing the date of a fixture, switching two home (or away) teams etc. The important thing is that small changes are made in the hope we gradually improve the overall schedule. There are some algorithmic details that we need to control but simulated annealing is easy to understand, easy to implement and tends to run quite fast. This makes it the algorithm of choice for many researchers, and not just for sports scheduling problems, but for a wide variety of optimisation problems – such as delivering groceries.

It works – so why the fuss?

Without doubt, the Football League does a fantastic job in creating the schedules. But there is room for improvement.

We might be able to take more stakeholders into account. At the moment, supporters have little direct input. Perhaps it may be possible to take the weather into account. Or the fixtures could be arranged so that the chances of every team having something to play for are maximised. Or it may allow players to finally take that winter break they have been talking about for a while.

These are all questions not just for English football. Better algorithms are bound to improve scheduling.

Graham Kendall, Professor of Operations Research and Vice-Provost, University of Nottingham

This article was originally published on The Conversation. Read the original article.

4-4-2 becomes 0101: inside the competitive world of robot football

Alan Winfield, University of the West of England

The whistle has just been blown on one of the most thrilling events on the international sporting calendar. It took place in Brazil and pitted teams from all over the world against each other, each hoping to make it into the history books. But no managers were fired, no grass had to be watered and certainly no one got bitten.

The event was the Robocup, a tournament that sees professional footballers replaced by robots. It’s one of a number of regular tournaments for teams of programmers and robotics experts to show off their latest work.

The Robocup standard platform league matches play out on a much smaller scale than your average World Cup match. An arena of around 6 metres by 9 metres is marked out as a miniature pitch and 10, rather than 22 players file on to battle it out. The players are NAO robots, state of the art bipedal humanoid robots which stand about 60cm tall.

This is not what you might describe as a high-speed contest. The robots walk to take a kick or a tackle and, really, waddle might be a more apt word for their approach. The ball never gets lofted into the air and that’s probably for the best – a header might cause a serious malfunction.

A 2014 final.

But the game is far from boring. Sitting around the arena, boys and girls, with family standing behind, are rapt, cheering with every contact. And make no mistake, the robots are properly playing. They pass, position and defend just like human players.

On either side of the pitch a row of desks can be found. This is where the brains behind the teams sit. Behind a row of laptops, they anxiously watch their players perform. But they are not controlling the robots. These coder/managers send the command to start the players when the referee signals kick-off but during the match the robots are completely autonomous.

This is what makes robot football so extraordinary. The robots are not just being moved around the pitch by remote control; they are making their own decisions. They control where they run (or waddle), pass the ball and shoot for the goal without any live direction from a human. Their choices are based on what they see and the position of the ball, their teammates and the opposing team.

It’s what’s inside that counts

While a team of human players often comes complete with a dazzling array of ridiculous haircuts and tattoos, it is much harder to tell a team of robots apart. All the players are physically identical – the only visible differences on a robot football pitch are coloured markings to differentiate the two teams.

Booting up.
Robocup2013, CC BY-NC-SA

But appearances can be deceptive. Under their plastic skins the teams are far from the same. Each runs completely different software that has been painstakingly crafted by the team coders. The software to make these robots play football cannot be downloaded from an app store. It has to be crafted from scratch. Football is a complex sport and there are potentially limitless strategies that a team could use to win. This is hard-core coding.

The contest is, in effect, a battle of software. All things being equal – and at the moment they pretty much are – the team with the smartest programming, coding the cleverest plays will emerge victorious.

A NAO player receives vital attention.
RoboCup2013, CC BY-NC-SA

At the end of the first-half the robots are brought to a halt. At this point, the team coders can be seen furiously attacking their laptops. This is their chance to quickly modify their robots’ software after seeing how they performed in the first half. They might have as little as ten minutes to do it, which seems like a risky strategy.

There’s a chance that the coders could make a mistake that renders the robots incapable of doing anything at all, let alone play a better game, but it’s a chance worth taking. If, in the first-half, the other team breaks out some nifty new moves, running rings (perhaps literally) around their opponents, this is the best opportunity the coders will get to raise their team’s game. It’s the robot equivalent of the tough talking in the half-time dressing room.

It’s easy to see why Robocup and the FIRA world cup, the two major international competitions, are so successful. Both contests have been running since around 1996. Some teams enter every year, building tremendous experience and a sophisticated code base. And several world-leading research groups use these contests as a test-bed for new approaches to multi-robot collaboration, publishing their findings in leading robotics journals afterwards.

As a robotics competition robot football ticks all the boxes: a game with universal appeal yet also hugely demanding for robots; it’s a fun way for young roboticists to learn robot programming, and it’s a great spectator sport too.

Alan Winfield, Professor of Electronic Engineering, University of the West of England

This article was originally published on The Conversation. Read the original article.