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.

Campaign pictures/Office of Jorge Sharp
Show Hide image

Meet Jorge Sharp, the rising star of Chile’s left who beat right-wingers to running its second city

The 31-year-old human rights lawyer says he is inspired by Jeremy Corbyn’s alternative politics as he takes the fight to the Chilean establishment.

Bearded, with shaggy hair, chinos and a plaid shirt, 31-year-old Jorge Sharp does not look like your typical mayor elect. But that does nothing to stop him speaking with the conviction of one.

“Look, Chile is a country that solely operates centrally, as one unit,” he says. “It is not a federal country – the concentration of state functions is very compact. In reality, most of the power is in Santiago. There are many limitations when it comes to introducing significant changes [in local areas].”

In October, Sharp upset Chile’s political status quo by defeating establishment rivals in the mayoral election of Valparaíso, the second city of South America’s first OECD country. He is taking office today.

Often compared to Podemos in Spain, Sharp’s win was significant – not only as yet another example of voters turning against mainstream politics – because it denied Chilean right-wing candidates another seat during local elections that saw them sweep to power across the country.

As the results rolled in, Conservative politicians had managed to snatch dozens of seats from the country’s centre-left coalition, led by President Michelle Bachelet, a member of Chile’s Socialist Party.

Sitting in one of Valparaíso’s many bohemian cafes, Sharp accepts the comparison with Podemos gracefully but is keen to make sure that Chile’s new “autonomous left” movement is seen as distinct.

“What we are doing in Chile is a process that is difficult to compare with other emerging political movements in the world,” he says. “We are a distinct political group and we are a modern force for the left. We are a left that is distinct in our own country and that is different to the left in Spain, in Bolivia, and in Venezuela.”

Sharp’s Autonomous Left movement is not so much a party rather than a group of affiliated individuals who want to change Chilean politics for good. Considering its relatively small size, the so-called Aut Left experienced degrees of success in October.

Chilean voters may have punished Bachelet – also Chile’s first female leader – and her coalition after a number of corruption scandals, but they did not turn against left-wing politics completely. Where they had options, many Chileans voted for newer, younger and independent left-wing candidates. 

“We only had nine candidates and we won three of the races – in Punta Arenas, Antofagasta and Ñuñoa, a district of Santiago,” he says. “We hope that the experience here will help us to articulate a national message for all of Chile.”


Campaign pictures/Office of Jorge Sharp

For Sharp, the success of Jeremy Corbyn, Donald Trump and the pro-Brexit movement are due to people fed up – on a global scale – with their respective countries’ mainstream political parties or candidates. Given that assumption, how would he describe the cause of his own election success?

“The problem in Chile, and also for the people in Valparaíso, is that the resources go to very few people,” he says. “It was a vote to live better, to live differently. Our project for social policy is one that is more sufficient for all the people. It’s a return to democracy, to break the electoral status quo.”   

Sharp – like many – believes that the United States’ Democrat party missed out by passing up the opportunity to break with the status quo and choose Bernie Sanders over the chosen nominee Hillary Clinton. “They would have been better off with Sanders than Clinton,” he believes. 

“The [people] in the US are living through a deep economic crisis. These were the right conditions for Trump. The people weren’t looking for the candidate from the banks or Wall Street, not the ‘establishment’ candidate. The way forward was Sanders.”

Turning to other 2016 geo-political events, he claims Brexit was a case of Britons “looking for an answer to crises” about identity. Elsewhere in South America, the tactics of former Colombian president Álvaro Uribe – who led the “No” vote campaign against peace with the Farc – were “fundamentally undemocratic”.

In the future, Sharp hopes that he and the rest of the Autonomous Left will be better-prepared to take power in higher offices, in order to further reform social policy and politics in Chile.

“For these elections, we weren't unified enough,” he concedes. “For 2017 [when national elections take place], we will have one list of parliamentary candidates and one presidential candidate.”

And while Sharp clearly sympathises with other left-wing movements in countries throughout the world, this is not a call for a unified approach to take on the rise of the right.

“Every country has its own path,” he finishes. “There is no single correct path. What we need to do [in Chile] is articulate a force that’s outside the political mainstream.”

Oli Griffin is a freelance journalist based in Latin America.