The offside algorithm

By David Sumpter

In the summer of 1998 I went to the world cup in France. It was a time of great footballing excitement: everyone was talking about Michael Owen, Ronaldo and Zinedine Zidane. Unfortunately, I didn’t get to see any of them play. I was at the robot football world cup in Paris. I watched as little cubes on wheels whizzed around plastic pitches, and cute Sony robot dogs followed a bright orange ball. I wasn’t impressed. In the evening, while watching the real action on a gigantic TV screen in central Paris, I joked with friends about how bad the robots were by comparison. The day when they would beat humans at their own game seemed a very long way off.

The organisers of Robocup were more bullish. After the tournament in 1998 they threw down the gauntlet: “By the middle of the 21st century, a team of fully autonomous humanoid robot soccer players shall win a soccer game, complying with the official rules of FIFA, against the winner of the most recent World Cup.” They acknowledged that their goal was ambitious, but likened it to President John F. Kennedy’s pledge in 1961 that America would put a man on the Moon by the end of the decade. After all, it took only 50 years from the invention of the first computer until Deep Blue beat Gary Kasparov at chess.

Nearly two decades on, how far has robot football come? If you watch videos on YouTube, the situation does not seem promising. They show robots repeatedly walking into each other while the ball lies stationary half a metre away from them; a robot goalkeeper failing to dive as a softly struck shot rolls slowly past it; and players falling over as the force of their own kicking motion overbalances them.

But according to Tim Laue, a researcher at the University of Bremen and the joint team leader of the B-Human team, which won Robocup last year, the YouTube clips aren’t entirely representative of the best teams. There are different classes of robots, ranging from the small circular boxes on wheels, which now play high-speed six-a-side, to the human-size, which compete in penalty shoot-outs.

A good way of reliably measuring overall progress is to look at the Standard Platform League, in which all the players are the same model of robot, made by a manufacturer called Softbank. Fifty-eight centimetres tall, they walk on two legs and remain on their feet for about the same proportion of the match as human footballers do. They move slowly, but in the right direction, and can perform some fancy footwork. The B-Human robots are able to back-heel the ball and score goals with the outside of their feet.

Teamwork is improving too. Katie Genter, a PhD student at the University of Texas at Austin and member of the 2012 title winners UT Austin Villa, explained that her robots make both sideways passes and play through-balls. In 2012, Villa were the robot equivalent of the Barcelona team of the same era, their style all about passing and keeping possession. But in 2016 they lost in the final to the B-Human team. Laue was honest about his team’s approach to tactics: “walking to the ball and kicking it straight towards the opponents’ goal has been the most promising tactic for us for many years”.

Laue sees Robocup as a way to try out known algorithms in the wild, and a way to assess where we are with artificial intelligence research. Each time, the organisers introduce new challenges. In 2016, the orange ball was replaced with a black and white one. All previous algorithms had to do was locate the only orange object on the pitch. A black and white ball is much harder to find: it must be distinguished from the lines of the pitch and shadows cast by the other robots. This particular challenge led some teams to try out the same kind of neural network and deep-learning techniques used by Facebook and Apple’s face-recognition software. If the development of Robocup vision systems is successful, they could be used to track players and the ball in human football matches, which would be useful for assessing tactics.

The algorithms developed by Robocup programmers are problem-specific, designed to detect the lines of the pitch, the goalposts and the ball; and to optimise kicking and diving motions. This case-by-case approach has its limitations. Currently, the robots are performing a sequence of identification tasks, rather than learning how to play the game as a team. The biggest limitation, however, is physiological. As Laue put it: “I am slightly optimistic that the computing-related problems could be solved, but currently there is nothing we can manufacture that is comparable to human muscles.”

Clearly, there has been great progress in the last decade, and Genter and Laue remain hopeful about the possibility of a humans v robots football match in 2048. But after watching footage from the 2016 final, I’m far from convinced. One of Tim’s B-Human strikers, through on goal, failed to distinguish the ball from the shadow it cast on the goal line. The robot left the ball standing 5cm away from the goalmouth and ran back towards its own half, completely oblivious to where the ball had gone. Robot footballers may well have improved over the last 20 years, but human players don’t need to hang up their boots just yet.