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.

Photo: Getty
Show Hide image

President's purges: how the attempted Turkey coup changed Recep Tayyip Erdoğan

President Erdoğan was once feted by European leaders. Now he calls them Nazis. 

On the evening of Friday 15 July 2016, tanks began rolling into Istanbul. The state broadcaster announced a coup was underway.  Turkey’s irascible president, Recep Tayyip Erdoğan, was on a post-Ramadan holiday in the resort of Marmaris. Government ministers in the capital, Ankara, tried to prepare themselves for what they expected to be the last night of their lives. 

Then, at 12.37am, an anchor on CNN Turk News held up a smartphone. The camera zoomed in, to reveal Erdoğan on a Facetime video. His face was blurry, and behind him was a plain, white curtain, but his message was clear. “I urge the Turkish people to convene at public squares and airports,” he told watchers. “I never believed in a power higher than the power of the people.”

Erdoğan made a gamble that the army would not fire on the crowds. For the most part, it worked. Other politicians echoed his statement. Opposition parties condemned the coup, and demonstrators took to the street. Above Istanbul, a plane circled – the president, having escaped the army in Marmaris, was coming home to the city which made his career. 

The democratic moment swiftly faded.  Days later, Erdoğan banned all academics from leaving Turkey. More than 58,000 public sector workers were estimated to be kicked out of jobs, and 1,577 university deans were forced to resign. 

A year on from the coup, Erdoğan has succeeded in giving himself new constitutional powers. Freedom of the press is all but dead. He is increasingly characterised as an authoritarian abroad. Unsurprisingly, he sees himself differently.  “I don’t care if they call me dictator or whatever else,” he told university students in November. “It goes in one ear, out the other. What matters is what my people call me.”

Erdoğan was born in 1954, in Istanbul. Educated at a religious school, and from a working-class background, his early passion for football was eclipsed by politics.  As a religious conservative in a militantly secular state, he saw the limits of Turkey’s liberalism first hand.  In 1997, three years after he was elected mayor of Istanbul, his decision to read out an Ottoman poem comparing believers to soldiers earned him 10 months in prison for inciting religious hatred (in 2016, he sought a prosecution of his own against a German comedian who read out an offensive poem about him). 

Erdoğan, though, was pragmatic as well as radical. Building on his record as an effective mayor, he established the conservative Justice and Development Party (AKP) in 2001 and won the first of many elections the following year. He presided over an economic boom. Fatefully, he struck up an alliance with Fethullah Gülen, the leader of an Islamic social and education movement, who shared his antipathy to the secular elite and the military. With Gülen’s help, Erdoğan took on the “deep state” in a way previous democratic leaders had failed to do. Meanwhile, he was feted by world leaders as an example of a moderate, Islamic, democratic politician. His wife took tea with Laura Bush. Pundits started to talk of “Erdoğanism”. 

The years of Erdoğan the Magnificent could not last. Turkey’s economy wobbled, and in 2013, a year marked by mass protests, Erdoğan accused Gulen of trying to bring down the government. By 2016, the year of the coup, he was increasingly isolated from his traditional Western allies. In March, he told local politicians that phrases like democracy and freedom have “absolutely no value any longer”. 

Western newspapers increasingly caricatured Erdoğan as an Ottoman Vladimir Putin, but his country was also being rocked by forces outside presidential control. The Syrian revolution, welcomed by Erdoğan, had warped into a nightmarish conflict. An estimated 2.7 million Syrians had sought refuge in Turkey. The war, in turn, had exacerbated tensions with Turkey’s Kurds, and fed terrorism. After Erdoğan’s comments about democracy, he continued: “Those who stand on our side in the fight against terrorism are our friend. Those on the opposite side, are our enemy.”

After Erdoğan re-established control in the early hours of 16 July 2016, he quickly blamed the usual fifth column, the Gülenists  (Gülen, exiled in Pennsylvania, US, said his philosophy was “antithetical to armed rebellion”).  But he also attacked the West for failing to support his purges.  “This coup attempt has actors inside Turkey, but its script was written outside,” he told a group of multinationals operating in Turkey in early August

On 29 September, six weeks after the attempted coup, Erdoğan extended Turkey’s state of emergency by a further three months (the state of emergency is still in place, and is due to expire on 19 July 2017). By November,  he was preparing the ground for a further consolidation of power – a referendum on the constitution which would abolish the role of prime minister and give the president more executive powers. 

Meanwhile, civil society was feeling the effects of the coup. After the summer, children returned to schools to find their teachers fired and a new course about Erdoğan’s heroic defence of Turkey on the curriculum. The firing of public sector workers continued - dismissals were announced in the Turkish government’s law newsletter, the Official Gazette. In December, a cafeteria boss was detained after telling police officers he would not serve the president a cup of tea.

Erdoğan’s crackdown might have slipped from the world’s attention, if not for his determination that the world should take note. While in its early years, the AKP prioritised good diplomatic relations, by the spring of 2017 Erdoğan was accusing Germany of “fascist actions”, and the Dutch of being “Nazi remnants”. The backdrop to this dispute was the decision of European authorities to ban rallies designed to win over the three million Turkish voters based overseas

In April, after a campaign criticised by election monitors, Erdoğan won the referendum by a Brexit-style margin– 51 per cent to 49 per cent. Despite his victory, the result was seen as a backlash against the heavy-handed president. Erdoğan responded by blocking Wikipedia

Read more: A year after the failed coup, the purge goes on

One year after unarmed Turks stood in front of tanks in the name of democracy, around 150 journalists are in jail (Erdoğan told the BBC: “No one is jailed because of journalism here.”) But perhaps the best illustration of the Turkish president's new confidence was his trip to visit another outspoken populist in Washington DC, Donald Trump. A group of protestors gathered outside the Turkish embassy. Erdoğan’s bodyguards beat them up. 

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

0800 7318496