How to get ants to solve a chess problem

Ants use a certain pattern, or algorithm, to forage for food, and this can be used to solve the famous “knight’s tour” chess problem.

Take a set of chess pieces and throw them all away except for one knight. Place the knight on any one of the 64 squares of a chess board.

Can you make 63 legal moves so that you visit every square on the chess board exactly once? As a reminder, a knight can move two squares in a straight line, followed by a ninety degree turn and a move of one further square. It might seem like a hard task, but this set of moves, called the knight’s tour, can be achieved in too many ways to count.

If you are able to make the 63 moves and end up on a square from which you can move back to the original square with the 64th legal move, then this is known as a closed tour. Other tours are called open tours.

Mathematicians have pondered how many closed tours exist, and they have come up with an astonishing number: more than 26 trillion. There are so many more open tours that we do not know the exact number.

Both Philip Hingston and I were so captivated by the knight’s tour problem that we wanted to find a different way to solve it. We found that motivation in nature – specifically in ants.

Ants use a certain pattern, or algorithm, to forage for food. This algorithm can be used to tackle many types of problems including the Travelling Salesman Problem and Vehicle Routing Problems. Philip and Graham wondered if they could use the ant colony optimisation algorithm to solve the knight’s tour problem.

Here’s how that algorithm works: a computer program is used to simulate a population of ants. These ants are assigned the task to find a solution to a problem. As each ant goes about their task they lay a pheromone trail – a smelly substance that ants use to communicate with each other. In the simulated algorithm, the most successful ants (the ones that solve the problem better), lay more pheromone than those that perform poorly.

We repeat this procedure many times (perhaps millions of times). Through repetitions, the pheromone trails on good solutions increase and they decrease on the poorer solutions due to evaporation, which is also programmed in the simulation algorithm.

In the simulation to solve the knight’s tour problem, the ants could only make legal knight moves and were restricted to stay within the confines of the chess board. If an ant successfully completes a tour then we reinforce that tour by depositing more pheromone on that tour, when compared to a tour that was not a full tour.

Ants which attempt to find later tours are more likely to follow higher levels of pheromone. This means that they are more likely to make the same moves as previously successful ants.

There is a balance to be struck. If the ants follow the successful ants too rigidly, then the algorithm will quickly converge to a single tour. If we encourage the ants too much, not to follow the pheromone of previous ants, then than they will just act randomly. So it is a case of tuning the algorithm’s parameters to try and find a good balance.

Using this algorithm, we were able to find almost half a million tours. This was a significant improvement over previous work, which was based on a genetic algorithm. These algorithms emulate Charles Darwin’s principle of natural evolution – survival of the fittest. Fitter members (those that perform well on the problem at hand) of a simulated population survive and weaker members die off.

It is not easy to say why the ant algorithm performed so well, when compared to the genetic algorithm. Perhaps it was down to tuning the algorithmic parameters, or perhaps ants really do like to play chess!

The knight’s tour problem was being worked on as far back as 840 AD. Little did those problem-solvers know that ants, albeit simulated ones, would be tackling the same puzzle more than 1,000 years in the future.

Graham Kendall does not work for, consult to, own shares in or receive funding from any company or organisation that would benefit from this article, and has no relevant affiliations.

The Conversation

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

A young man waits for a young woman to make her move at chess in 1865. Photo: London Stereoscopic Company/Getty Images

Graham Kendall is Professor of Operations Research and Vice-Provost at University of Nottingham.

Show Hide image

Marine Le Pen’s new disguise: a bid to rebrand her far-right party as the “National Rally”

Le Pen hopes to present her renamed party as the working-class alternative to Macron’s bourgeois elitism.

Marine Le Pen had just declared: “When foreigners are in France, they must respect the law and the people” when chants of “On est chez nous!” (“We are at home!”) broke out in the audience. French flags were waved in the air.

On 11 March, Le Pen, 49, was re-elected leader of her far-right party, Front National (FN), and announced it was to be renamed Rassemblement National (“National Rally”). “It must be a rallying cry, a call for those who have France and the French at their heart to join us,” she declared at the party’s conference in Lille, northern France.

It’s a pivotal moment for the party her father, Jean-Marie Le Pen, founded in 1972 and led until 2011. After going from a “jackass” far-right outfit known for its xenophobia, to the nationalist, anti-immigration party defeated in the final round of the 2017 French presidential election by the liberal candidate Emmanuel Macron, its goal is now to move “from opposition and into government”, Le Pen said.

For the FN leader, this is also a decisive moment. Le Pen’s credibility was damaged by her weak performance in the run-off debate and polls show her campaign eroded the political gains made during the party’s decade-long “de-demonisation”. “Her image is clearly tarnished,” Valérie Igounet, an expert on the French far right, told me. “But she is still supported by the party.” The FN claims its membership is around 80,000; Igounet says it is likely to have fallen to 50,000.

The proposed name will be put to a membership vote – as Le Pen’s re-election was, though she was the only candidate – but the move has already prompted concern.

Asked if they were happy with the rebrand, only 52 per cent of FN members answered yes. “It is a name that has negative connotations in French history,” Igounet said. Rassemblement National was a collaborationist party in the 1940s. It was also used in 1965 by defeated far-right presidential candidate Jean-Louis Tixier-Vignancour, whose campaign was run by Jean-Marie Le Pen. “For a party that wants to free itself from Le Pen’s father, it’s a surprising choice,” Igounet said. Another political organisation, Rassemblement pour la France, claims the FN has no right to the name.

Not all of the FN’s fundamentals have been abandoned. The logo, a red, white and blue flame inspired by an Italian neo-fascist party, remains. Membership surveys show 98 per cent still approve of the anti-immigration rhetoric, Igounet said.

Le Pen hopes the rebrand will enable new political alliances. Thierry Mariani, a former minister under Nicolas Sarkozy and member of the right-wing Républicains, has called for an alliance with the FN (which, he said, “has evolved”). But the Républicains’ leader, Laurent Wauquiez, is firmly opposed: “As long as I am leader, there will be no alliance with the FN,” he vowed. “The FN want to make alliances, but they have nowhere to go,” said Antoine de Cabanes, a researcher on the far right for the think tank Transform! Europe.

Can Le Pen’s party really be “de-demonised”? The former Donald Trump aide Steve Bannon, who is currently touring Europe, was invited to speak at the Lille conference. “Let them call you racists, let them call you xenophobes, let them call you nativists. Wear it as a badge of honour,” he told activists, to rapturous applause.

Bannon has also praised Marion Maréchal-Le Pen, Marine’s more conservative 28-year-old niece, as the party’s “rising star”. The younger Le Pen is on a “break” from French politics but addressed the US Republicans in Washington in February, where she declared her ambition to “make France great again”. Marion is tipped as a possible future leader. “She has the right name,” noted De Cabanes.

Marine Le Pen insisted she didn’t want to “make an ally” of Bannon, but rather to “listen to someone who defied expectation to win against all odds”. Yet even her father, a Holocaust denier whose politics are closer to Bannon’s than his daughter’s, described the choice of speaker as “not exactly de-demonising the party”.

It was not an isolated incident. On 10 March, Davy Rodríguez, a parliamentary assistant to Le Pen, was forced to resign after he was filmed using a racial slur in Lille.

The FN defended Bannon’s invitation on the grounds that “he embodies the rejection of the establishment, of the European Union and the system of politics and the media”. Le Pen called President Macron’s politics a “great downgrading of the middle and working class” and declared her party “the defender of the workers, the employees, the sorrowful farmers”.

The road to the 2022 presidential contest includes four elections – municipal, departmental, regional and European –  in which Le Pen hopes to present her renamed party as the working-class alternative to Macron’s bourgeois elitism. But in Lille, activists cheered wildly not when Le Pen spoke about the road ahead, but when she declared: “Legal and illegal immigration are not bearable any more!” Plus ça change… 

Pauline Bock writes about France, the Macron presidency, Brexit and EU citizens in the UK. She also happens to be French.

This article first appeared in the 13 March 2018 issue of the New Statesman, Putin’s spy game