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

The toxic new right-wing media will outlast Trump even if he’s impeached

Fox News and a network of smaller outlets have created an alternative version of reality. That ecosystem might prove more durable than the US president. 

An early end to Donald Trump’s presidency looks more feasible than at any time in the 117 days since his inauguration.

The New York Times revealed on Tuesday that FBI director James Comey – who was fired by Trump a week ago – wrote a memo recording the President’s request he “let go” an investigation into links between Michael Flynn, Trump’s pick for national security advisor, and Russia.

Already there is talk of impeachment, not least because the crime Trump is accused of - obstructing justice - is the same one that ended Richard Nixon's presidency.

But with a Republican-controlled Congress the impeachment process would be long and fraught, and is only likely to succeed if public opinion, and particularly the opinion of the Republican voters, swings decisively against Trump.

In another era, the rolling coverage of the president's chaotic, incompetent and potentially corrupt administration might have pushed the needle far enough. But many of those Republican voters will make their decision about whether or not to stick with Trump based not on investigative reporting in the NYT or Washington Post, but based on reading a right-wing media ecosystem filled with distortions, distractions and fabrications.

That ecosystem – which spans new and (relatively) old media - will be going into overdrive to protect a president it helped elect, and who in turn has nourished it with praise and access.

On Monday, BuzzFeed’s Charlie Warzel took a forensic look at how a new breed of hyper-partisan right wing sites – what he calls the "Upside Down media" – tried to undermine and discredit claims that Trump disclosed sensitive security information to Russian officials.

The same tactics can already be seen just 24 hours later. Notorious conspiracist site Infowars talks of “saboteurs” and “turncoats” undermining the administration with leaks, mirroring an email from Trump’s campaign team sent late on Tuesday. Newsmax, another right-leaning sight with links to Trump, attacks the source of the story, asking in its web splash “Why did Comey wait so long?”. GatewayPundit, which published several false stories about Hillary Clinton during the election campaign, appears to have ignored the story altogether. 

As Warzel points out, these new sites work in concert with older media, in particular Rupert Murdoch’s ratings-topping cable news channel Fox News.

Fox initially underplayed the Comey memo’s significance, switching later to projecting the story as a media-led attack on Trump. At the time of publication, the Fox homepage led with a splash headlined: “THE SHOW MUST GO ON Lawmakers vow to focus on Trump agenda despite WH controversies.”

Fox acts as a source of validation for the newly established right-wing sites. Once Fox has covered a story, smaller sites can push further and faster, knowing that they aren't going too far from at least one outlet considered respectable and mainstream. If anything should make the UK value the impartiality rules, however imperfect, which govern its broadcast news, it’s Fox’s central role in enabling this toxic mix of misinformation.

These new media sites have another weapon, however. They understand and exploit the way internet platforms - in particular Facebook - are designed to maximise attention. They have found that playing on very human desires for stories that confirm our biases and trigger emotional responses is the best way to build audiences and win fans, and they have little compulsion abusing that knowledge.

This isn’t just a Trump or Fox-related phenomenon. It’s not even just a right-wing one. In both the US and the UK left-wing hyper-partisan sites with a tenuous relationship with the truth have sprung up. They have followed the same playbook, and in most cases the same advertising-based funding model, which has worked so well for the right. Emotive headlines, spun stories, outright fabrications and an insistence that “the corrupt mainstream media won’t report this” work just as well in generating clicks and shares for both ends of the political spectrum.

The main difference between the two political poles is that the right has benefited from an ideologically and temperamentally suited president, and a facilitator in Fox News. 

Of course the combined efforts of this new media and the Fox-led old may still fail. Trump’s recent transgressions appear so severe that they could break through to even his diehard supporters.

But if Trump does fall, the new right wing media ecosystem is unlikely to fall with him. 

0800 7318496