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.

Getty
Show Hide image

After Article 50 is triggered, what happens next?

Theresa May says Article 50 will be triggered on 29 March. The UK must prepare for years, if not decades, of negotiating. 

Back in June, when Europe woke to the news of Brexit, the response was muted. “When I first emerged from my haze to go to the European Parliament there was a big sign saying ‘We will miss you’, which was sweet,” Labour MEP Seb Dance remembered at a European Parliament event in London. “The German car industry said we don’t want any disruption of trade.”

But according to Dance – best known for holding up a “He’s Lying” sign behind Nigel Farage’s head – the mood has hardened with the passing months.

The UK is seen as demanding. The Prime Minister’s repeated refusal to guarantee EU citizens’ rights is viewed as toxic. The German car manufacturers now say the EU is more important than British trade. “I am afraid that bonhomie has evaporated,” Dance said. 

On Wednesday 29 March the UK will trigger Article 50. Doing so will end our period of national soul-searching and begin the formal process of divorce. So what next?

The European Parliament will have its say

In the EU, just as in the UK, the European Parliament will not be the lead negotiator. But it is nevertheless very powerful, because MEPs can vote on the final Brexit deal, and wield, in effect, a veto.

The Parliament’s chief negotiator is Guy Verhofstadt, a committed European who has previously given Remoaners hope with a plan to offer them EU passports. Expect them to tune in en masse to watch when this idea is revived in April (it’s unlikely to succeed, but MEPs want to discuss the principle). 

After Article 50 is triggered, Dance expects MEPs to draw up a resolution setting out its red lines in the Brexit negotiations, and present this to the European Commission.

The European Commission will spearhead negotiations

Although the Parliament may provide the most drama, it is the European Commission, which manages the day-to-day business of the EU, which will lead negotiations. The EU’s chief negotiator is Michel Barnier. 

Barnier is a member of the pan-EU European People’s Party, like Jean-Claude Juncker and German Chancellor Angela Merkel. He has said of the negotiations: “We are ready. Keep calm and negotiate.”

This will be a “deal” of two halves

The Brexit divorce is expected to take 16 to 18 months from March (although this is simply guesswork), which could mean Britain officially Brexits at the start of 2019.

But here’s the thing. The divorce is likely to focus on settling up bills and – hopefully – agreeing a transitional arrangement. This is because the real deal that will shape Britain’s future outside the EU is the trade deal. And there’s no deadline on that. 

As Dance put it: “The duration of that trade agreement will exceed the life of the current Parliament, and might exceed the life of the next as well.”

The trade agreement may look a bit like Ceta

The European Parliament has just approved the Comprehensive Economic and Trade Agreement (Ceta) with Canada, a mammoth trade deal which has taken eight years to negotiate. 

One of the main stumbling points in trade deals is agreeing on similar regulatory standards. The UK currently shares regulations with the rest of the UK, so this should speed up the process.

But another obstacle is that national or regional parliaments can vote against a trade deal. In October, the rebellious Belgian region of Wallonia nearly destroyed Ceta. An EU-UK deal would be far more politically sensitive. 

The only way is forward

Lawyers working for the campaign group The People’s Challenge have argued that it will legally be possible for the UK Parliament to revoke Article 50 if the choice is between a terrible deal and no deal at all. 

But other constitutional experts think this is highly unlikely to work – unless a penitent Britain can persuade the rest of the EU to agree to turn back the clock. 

Davor Jancic, who lectures on EU law at Queen Mary University of London, believes Article 50 is irrevocable. 

Jeff King, a professor of law at University College London, is also doubtful, but has this kernel of hope for all the Remainers out there:

“No EU law scholar has suggested that with the agreement of the other 27 member states you cannot allow a member state to withdraw its notice.”

Good luck chanting that at a march. 

Julia Rampen is the editor of The Staggers, The New Statesman's online rolling politics blog. She was previously deputy editor at Mirror Money Online and has worked as a financial journalist for several trade magazines.